人工智能搜索技術(shù)二

目錄第一章緒論第二章知識(shí)表示

第三章搜索技術(shù)第四章推理技術(shù)第五章機(jī)器學(xué)習(xí)

第六章專(zhuān)家系統(tǒng)第七章自動(dòng)規(guī)劃系統(tǒng)第八章自然語(yǔ)言理解第九章智能控制第十章人工智能程序設(shè)計(jì)3.1盲目搜索盲目搜索：即無(wú)信息搜索寬度優(yōu)先與深度優(yōu)先3.1.1圖搜索策略

圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿(mǎn)足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。研究圖搜索的一般策略，能夠給出圖搜索過(guò)程的一般步驟。

3.1盲目搜索3.1.1圖搜索策略例3.1從王某家族的四代中找王A的后代且其壽命為X的人

A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,513.1盲目搜索3.1.1圖搜索策略1.圖搜索(GRAPHSEARCH)的一般過(guò)程(1)建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中。(2)建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。(3)LOOP：若OPEN表是空表，則失敗退出。(4)選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中。稱(chēng)此節(jié)點(diǎn)為節(jié)點(diǎn)n。(5)若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。3.1盲目搜索3.1.1圖搜索策略1.圖搜索(GRAPHSEARCH)的一般過(guò)程(6)擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。(7)對(duì)那些未曾在G中出現(xiàn)過(guò)的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過(guò)的)M成員設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需要更改通到n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颉?8)按某一任意方式或按某個(gè)探試值，重排OPEN表。(9)GOLOOP。

3.1盲目搜索節(jié)點(diǎn)父輩節(jié)點(diǎn)3.1.1圖搜索策略2.圖搜索算法的幾個(gè)重要名詞（1）OPEN表與CLOSE表OPEN表CLOSED表編號(hào)節(jié)點(diǎn)父輩節(jié)點(diǎn)3.1盲目搜索3.1.1圖搜索策略3.搜索圖與搜索樹(shù)搜索過(guò)程框圖開(kāi)

始初始化：S放入OPEN表，CLOES表置空,n=1OPEN表中的第一個(gè)結(jié)點(diǎn)n移至CLOSE表若n的后繼未曾在搜索圖G中出現(xiàn)，則將其放入OPEN表的末端，并提供返回結(jié)點(diǎn)n的指針,置n=n+1根據(jù)后繼結(jié)點(diǎn)在搜索圖G中的出現(xiàn)情況修改指針?lè)较蛞滥撤N準(zhǔn)則重新排序OPEN表失敗成功NYNOPEN為空表NULL？n=目標(biāo)結(jié)點(diǎn)D嗎?Y3.1盲目搜索3.1.1圖搜索策略4.圖搜索方法分析：圖搜索過(guò)程的第8步對(duì)OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個(gè)“最好”的節(jié)點(diǎn)作為第4步擴(kuò)展用。這種排序可以是任意的即盲目的(屬于盲目搜索)，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù)(屬于啟發(fā)式搜索)。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，這一過(guò)程就宣告成功結(jié)束。這時(shí)，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向S返回追溯。當(dāng)搜索樹(shù)不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時(shí)，過(guò)程就以失敗告終(某些節(jié)點(diǎn)最終可能沒(méi)有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。

3.1盲目搜索3.1.2寬度優(yōu)先搜索

定義3.1如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索（breadth-firstsearch)3.1盲盲目搜搜索寬寬度度優(yōu)先先搜索索寬度優(yōu)優(yōu)先搜搜索算算法(1)把把起始始節(jié)點(diǎn)點(diǎn)放到到OPEN表中中(如如果該該起始始節(jié)點(diǎn)點(diǎn)為一一目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)，則則求得得一個(gè)個(gè)解答答)。。(2)如如果OPEN是是個(gè)空空表，，則沒(méi)沒(méi)有解解，失失敗退退出；；否則則繼續(xù)續(xù)。(3)把把第一一個(gè)節(jié)節(jié)點(diǎn)(節(jié)點(diǎn)點(diǎn)n)從OPEN表表移出出，并并把它它放入入CLOSED的擴(kuò)擴(kuò)展節(jié)節(jié)點(diǎn)表表中。。(4)擴(kuò)擴(kuò)展節(jié)節(jié)點(diǎn)n。如如果沒(méi)沒(méi)有后后繼節(jié)節(jié)點(diǎn)，，則轉(zhuǎn)轉(zhuǎn)向上上述第第(2)步步。(5)把把n的的所有有后繼繼節(jié)點(diǎn)點(diǎn)放到到OPEN表的的末端端，并并提供供從這這些后后繼節(jié)節(jié)點(diǎn)回回到n的指指針。。(6)如如果n的任任一個(gè)個(gè)后繼繼節(jié)點(diǎn)點(diǎn)是個(gè)個(gè)目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)，則則找到到一個(gè)個(gè)解答答，成成功退退出；；否則則轉(zhuǎn)向向第(2)步。。3.1盲盲目搜搜索寬寬度度優(yōu)先先搜索索例3.2八數(shù)碼碼問(wèn)題題操作規(guī)規(guī)定:允允許空空格四四周上上、下下、左左、右右的數(shù)數(shù)碼塊塊移入入空格格中，，不許許斜方方向移移動(dòng)，，不許許返回回先輩輩結(jié)點(diǎn)點(diǎn)。初始布布局S和目目標(biāo)狀狀態(tài)D如下圖圖所示示：3.1盲盲目搜搜索寬寬度度優(yōu)先先搜索索例3.2八數(shù)碼問(wèn)問(wèn)題3.1盲盲目搜搜索深深度優(yōu)優(yōu)先搜索索深度優(yōu)先先算法步步驟：(1)初初始結(jié)結(jié)點(diǎn)S放放到未擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)OPEN中；；(2)若若OPEN為為空，則則搜索失失敗，問(wèn)問(wèn)題無(wú)解解；(3)彈彈出OPEN表中最最頂端結(jié)結(jié)點(diǎn)放到到CLOSE表表中，并并給出順順序編號(hào)號(hào)n；(4)若若n為為目標(biāo)結(jié)結(jié)點(diǎn)D，，則搜索索成功，，問(wèn)題有有解；(5)若若n無(wú)無(wú)子結(jié)點(diǎn)點(diǎn)，轉(zhuǎn)(2)；；(6)擴(kuò)擴(kuò)展n結(jié)點(diǎn)，，將其所所有子結(jié)結(jié)點(diǎn)配上上返回n的指針針，并按按次序壓壓入OPEN堆堆棧，轉(zhuǎn)轉(zhuǎn)(2)。3.1盲盲目搜搜索深深度優(yōu)優(yōu)先搜索索3.1盲盲目搜搜索深深度優(yōu)優(yōu)先搜索索有界深度度優(yōu)先搜搜索：引入搜索索深度限限制值d，使深度優(yōu)優(yōu)先搜索索過(guò)程具具有完備備性。。設(shè)定搜索索深度限限制d=5，，問(wèn)題同深深度優(yōu)先先算法中中的八數(shù)數(shù)碼問(wèn)題題(2)。3.1盲盲目搜搜索深深度優(yōu)優(yōu)先搜索索3.1盲盲目搜搜索深深度優(yōu)優(yōu)先搜索索有界深度度優(yōu)先算算法步驟驟：(1)初初始結(jié)點(diǎn)點(diǎn)S放入入堆棧OPEN中；(2)若若OPEN為空，則則搜索失失敗，問(wèn)問(wèn)題無(wú)解解；(3)彈彈出OPEN中棧頂結(jié)結(jié)點(diǎn)n，，放入CLOSE表中，并并給出順順序編號(hào)號(hào)n；(4)若若n為目目標(biāo)結(jié)點(diǎn)點(diǎn)D，則則搜索成成功，問(wèn)問(wèn)題有解解；(5)若若n的深深度d(n)=d，則則轉(zhuǎn)(2)；；(6)若若n無(wú)子子結(jié)點(diǎn)，，即不可可擴(kuò)展，，轉(zhuǎn)(2)；；(7)擴(kuò)擴(kuò)展結(jié)點(diǎn)點(diǎn)n，將將其所有有子結(jié)點(diǎn)點(diǎn)配上返返回n的的指針，，并壓入入OPEN堆棧，轉(zhuǎn)轉(zhuǎn)(2)。3.1盲盲目搜搜索等等代價(jià)價(jià)搜索寬度優(yōu)先先搜索可可被推廣廣用來(lái)解解決尋找找從起始始狀態(tài)至至目標(biāo)狀狀態(tài)的具具有最小小代價(jià)的的路徑問(wèn)問(wèn)題，這這種推廣廣了的寬寬度優(yōu)先先搜索算算法叫做做等代價(jià)價(jià)搜索算算法。等代價(jià)搜搜索中的的幾個(gè)記記號(hào)起始節(jié)點(diǎn)點(diǎn)記為S；從節(jié)點(diǎn)i到它的的后繼節(jié)節(jié)點(diǎn)j的的連接弧弧線(xiàn)代價(jià)價(jià)記為c(i，，j)；；起始節(jié)點(diǎn)點(diǎn)S到任任一節(jié)點(diǎn)點(diǎn)i的路路徑代價(jià)價(jià)記為g(i)。如果所有有的連接接弧線(xiàn)具具有相等等的代價(jià)價(jià)，那么么等代價(jià)價(jià)算法就就簡(jiǎn)化為為寬度優(yōu)優(yōu)先搜索索算法。3.2啟啟發(fā)式式搜索盲目搜索索的不足足：效率率低，耗耗費(fèi)空間間與時(shí)間間。啟發(fā)式搜搜索：利利用問(wèn)題題域特性性的信息息（啟發(fā)發(fā)信息））進(jìn)行搜搜索。啟啟發(fā)式搜搜索策略略啟發(fā)式信信息按用用途分為為三種：：（1）用用于確定定要擴(kuò)展展的下一一個(gè)節(jié)點(diǎn)點(diǎn)，避免免盲目擴(kuò)擴(kuò)展。（2）在在擴(kuò)展一一個(gè)節(jié)點(diǎn)點(diǎn)的過(guò)程程中，用用于確定定要生成成哪一個(gè)個(gè)或哪幾幾個(gè)后繼繼節(jié)點(diǎn)，，避免盲盲目生成成所有可可能節(jié)點(diǎn)點(diǎn)。（3）用用于確定定某些應(yīng)應(yīng)該從搜搜索樹(shù)中中拋棄或或修剪得得節(jié)點(diǎn)。。3.2啟啟發(fā)式式搜索有序搜索索（orderedsearch）：利利用第一一種啟發(fā)發(fā)信息，，總是選選擇“最最有希望望”的節(jié)節(jié)點(diǎn)作為為下一個(gè)個(gè)被擴(kuò)展展的節(jié)點(diǎn)點(diǎn)。估價(jià)函數(shù)數(shù)（evaluationfunction)：估估算節(jié)點(diǎn)點(diǎn)“希望望”的量量度，這這種量度度叫做估估價(jià)函數(shù)數(shù)。建立估價(jià)價(jià)函數(shù)的的一般方方法：試試圖確定定一個(gè)處處在最佳佳路徑上上的節(jié)點(diǎn)點(diǎn)的概率率；提出出任意節(jié)節(jié)點(diǎn)與目目標(biāo)集之之間的距距離量度度或差別別量度；；或者在在棋盤(pán)式式的博弈弈和難題題中根據(jù)據(jù)棋局的的某些特特點(diǎn)來(lái)決決定棋局局的得分分?jǐn)?shù)。這這些特點(diǎn)點(diǎn)被認(rèn)為為與向目目標(biāo)節(jié)點(diǎn)點(diǎn)前進(jìn)一一步的希希望程度度有關(guān)。。f(n)——表表示節(jié)點(diǎn)點(diǎn)n的估估價(jià)函數(shù)數(shù)值3.2啟啟發(fā)式式搜索有有序搜索索用估價(jià)函函數(shù)f來(lái)來(lái)排列GRAPHSEARCH第8步中OPEN表上的的節(jié)點(diǎn)。。應(yīng)用某某個(gè)算法法(例如如等代價(jià)價(jià)算法)選擇OPEN表上具具有最小小f值的的節(jié)點(diǎn)作作為下一一個(gè)要擴(kuò)擴(kuò)展的節(jié)節(jié)點(diǎn)。這這種搜索索方法叫叫做有序搜索索或最佳優(yōu)先先搜索(best-firstsearch)，而其算算法就叫叫做有序搜索索算法或最佳優(yōu)先先算法。3.2啟啟發(fā)式式搜索有有序搜索索有序狀態(tài)態(tài)空間搜搜索算法法：(1)把把起始始節(jié)點(diǎn)S放到OPEN表中，，計(jì)算f(S)并把其其值與節(jié)節(jié)點(diǎn)S聯(lián)聯(lián)系起來(lái)來(lái)。(2)如如果OPEN是個(gè)空空表，則則失敗退退出，無(wú)無(wú)解。(3)從從OPEN表表中選擇擇一個(gè)f值最小小的節(jié)點(diǎn)點(diǎn)i。結(jié)結(jié)果有幾幾個(gè)節(jié)點(diǎn)點(diǎn)合格，，當(dāng)其中中有一個(gè)個(gè)為目標(biāo)標(biāo)節(jié)點(diǎn)時(shí)時(shí)，則選選擇此目目標(biāo)節(jié)點(diǎn)點(diǎn)，否則則就選擇擇其中任任一個(gè)節(jié)節(jié)點(diǎn)作為為節(jié)點(diǎn)i。(4)把把節(jié)點(diǎn)點(diǎn)i從OPEN表中移移出，并并把它放放入CLOSED的擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)表中。。3.2啟啟發(fā)式式搜索有有序搜索索(5)如如果i是個(gè)目目標(biāo)節(jié)點(diǎn)點(diǎn)，則成成功退出出，求得得一個(gè)解解。(6)擴(kuò)擴(kuò)展節(jié)節(jié)點(diǎn)i，，生成其其全部后后繼節(jié)點(diǎn)點(diǎn)。對(duì)于于i的每每一個(gè)后后繼節(jié)點(diǎn)點(diǎn)j：(a)計(jì)計(jì)算f(j)。(b)如如果j既不在在OPEN表中中，又不不在CLOSED表中中，則用用估價(jià)函函數(shù)f把把它添入入OPEN表。。從j加加一指向向其父輩輩節(jié)點(diǎn)i的指針針，以便便一旦找找到目標(biāo)標(biāo)節(jié)點(diǎn)時(shí)時(shí)記住一一個(gè)解答答路徑。。(c)如如果j已在OPEN表上或或CLOSED表上，，則比較較剛剛對(duì)對(duì)j計(jì)算算過(guò)的f值和前前面計(jì)算算過(guò)的該該節(jié)點(diǎn)在在表中的的f值。。如果新新的f值值較小，，則3.2啟啟發(fā)式式搜索有有序搜索索(i)以以此新新值取代代舊值。。(ii)從從j指向i，，而不是指向向它的父輩節(jié)節(jié)點(diǎn)。(iii)如如果節(jié)點(diǎn)j在CLOSED表中，，則把它移回回OPEN表表。(7)轉(zhuǎn)向向(2)，即即GOTO(2)。3.2啟發(fā)發(fā)式搜索有有序搜索開(kāi)始把S放入OPEN表OPEN為空空表？失敗選取OPEN表中f值最最小的節(jié)點(diǎn)i，放放入CLOSED表i=Sg？成功是是擴(kuò)展i得后繼繼節(jié)點(diǎn)j，計(jì)計(jì)算f(j)，提供返回i的指指針，利用f(j)對(duì)OPEN表重新排序調(diào)調(diào)整父子關(guān)系系及指針3.2啟發(fā)發(fā)式搜索有有序搜索寬度優(yōu)先搜索索、等代價(jià)搜搜索和深度優(yōu)優(yōu)先搜索統(tǒng)統(tǒng)統(tǒng)是有序搜索索技術(shù)的特例例。對(duì)于寬度度優(yōu)先搜索，，選擇f(i)作為節(jié)點(diǎn)點(diǎn)i的深度。。對(duì)于等代價(jià)價(jià)搜索，f(i)是從起起始節(jié)點(diǎn)至節(jié)節(jié)點(diǎn)i這段路路徑的代價(jià)。。有序搜索的有有效性直接取取決于f的選選擇，如果選選擇的f不合合適，有序搜搜索就可能失失去一個(gè)最好好的解甚至全全部的解。如如果沒(méi)有適用用的準(zhǔn)確的希希望量度，那那么f的選擇擇將涉及兩個(gè)個(gè)方面的內(nèi)容容：一方面是是一個(gè)時(shí)間和和空間之間的的折衷方案；；另一方面是是保證有一個(gè)個(gè)最優(yōu)的解或或任意解。3.2啟發(fā)發(fā)式搜索有有序搜索例3.4：八八數(shù)碼難題,采用了簡(jiǎn)簡(jiǎn)單的估價(jià)函函數(shù)f(n)=d(n)+W(n)其中：d(n)是搜索樹(shù)樹(shù)中節(jié)點(diǎn)n的的深度；W(n)用來(lái)計(jì)計(jì)算對(duì)應(yīng)于節(jié)節(jié)點(diǎn)n的數(shù)據(jù)據(jù)庫(kù)中錯(cuò)放的的棋子個(gè)數(shù)。。因此，起始始節(jié)點(diǎn)棋局的f值等于0+4=4。。283164753.2啟發(fā)發(fā)式搜索有有序搜索283164752831647528314765283164752831476523184765283147658321476528371465231847652331847651238476512384765123784653.2啟發(fā)發(fā)式搜索3.2.3A*算法A*算法是一一種有序搜索索算法，其特特點(diǎn)在于對(duì)估估價(jià)函數(shù)的定定義上。1.A*算法法的估估價(jià)函函數(shù)k(ni，nj)：表表示任任意兩兩個(gè)節(jié)節(jié)點(diǎn)ni和nj之間最最小代代價(jià)路路徑的的實(shí)際際代價(jià)價(jià)(對(duì)對(duì)于兩兩節(jié)點(diǎn)點(diǎn)間沒(méi)沒(méi)有通通路的的節(jié)點(diǎn)點(diǎn)，函函數(shù)k沒(méi)有有定義義)。。k(n,ti)：從從節(jié)點(diǎn)點(diǎn)n到到某個(gè)個(gè)具體體的目目標(biāo)節(jié)節(jié)點(diǎn)ti，某一一條最最小代代價(jià)路路徑的的代價(jià)價(jià)。h*(n)：表表示整整個(gè)目目標(biāo)節(jié)節(jié)點(diǎn)集集合｛｛ti｝上所所有k(n,ti)中最最小的的一個(gè)個(gè)，因因此，，h*(n)就就是從從n到到目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)最小小代價(jià)價(jià)路徑徑的代代價(jià)，，而且且從n到目目標(biāo)節(jié)節(jié)點(diǎn)能能夠獲獲得h*(n)的任任一路路徑就就是一一條從從n到到某個(gè)個(gè)目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)的最最佳路路徑(對(duì)于于任何何不能能到達(dá)達(dá)目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)的節(jié)節(jié)點(diǎn)n，函函數(shù)h*沒(méi)沒(méi)有定定義)。3.2啟啟發(fā)式式搜索索3.2.3A*算算法定義g*為g*(n)=k(S,n)從已知知起始始節(jié)點(diǎn)點(diǎn)S到到任意意節(jié)點(diǎn)點(diǎn)n的的一條條最佳佳路徑徑代價(jià)價(jià)。定義函函數(shù)f*，，f*(n)=g*(n)+h*(n)使得在在任一一節(jié)點(diǎn)點(diǎn)n上上其函函數(shù)值值f*(n)就就是從從節(jié)點(diǎn)點(diǎn)S到到節(jié)點(diǎn)點(diǎn)n的的一條條最佳佳路徑徑的實(shí)實(shí)際代代價(jià)加加上從從節(jié)點(diǎn)點(diǎn)n到到某目目標(biāo)節(jié)節(jié)點(diǎn)的的一條條最佳佳路徑徑的代代價(jià)之之和。。3.2啟啟發(fā)式式搜索索3.2.3A*算算法希望估估價(jià)函函數(shù)f是f*的的一個(gè)個(gè)估計(jì)計(jì)，此此估計(jì)計(jì)可由由下式式給出出：f(n)=g(n)+h(n)其中：：g是是g*的估估計(jì)；；h是是h*的估估計(jì)。。對(duì)于g(n)：：一個(gè)個(gè)明顯顯的選選擇就就是搜搜索樹(shù)樹(shù)中從從S到到n這這段路路徑的的代價(jià)價(jià)，這這一代代價(jià)可可以由由從n到S尋找找指針針時(shí)，，把所所遇到到的各各段弧弧線(xiàn)的的代價(jià)價(jià)加起起來(lái)給給出(這條條路徑徑就是是到目目前為為止用用搜索索算法法找到到的從從S到到n的的最小小代價(jià)價(jià)路徑徑)。。這個(gè)個(gè)定義義包含含了g(n)≥≥g*(n)。。h(n)：：對(duì)h*(n)的的估計(jì)計(jì)，依依賴(lài)于于有關(guān)關(guān)問(wèn)題題的領(lǐng)領(lǐng)域的的啟發(fā)發(fā)信息息。這這種信信息可可能與與八數(shù)數(shù)碼難難題中中的函函數(shù)W(n)所所用的的那種種信息息相似似。把把h叫叫做啟啟發(fā)函函數(shù)。。3.2啟啟發(fā)式式搜索索3.2.3A*算算法2.A算算法和和A*算法法的定定義定義3.3在GRAPHSEARCH過(guò)過(guò)程中中，如如果第第8步步的重重排OPEN表表是依依據(jù)f(x)=g(x)+h(x)進(jìn)行行的，，則稱(chēng)稱(chēng)該過(guò)過(guò)程為為A算算法。。定義3.4在A算法法中，如如果對(duì)所所有的x存在h(x)≤h*(x),則稱(chēng)稱(chēng)h(x)為h*(x)的下下界，它它表示某某種偏于于保守的的估計(jì)。。定義3.5采用h*(x)的下界界h(x)為啟啟發(fā)函數(shù)數(shù)的A算算法，稱(chēng)稱(chēng)為A*算法。。當(dāng)h=0時(shí)，，A*算算法就變變?yōu)橛行蛐蛩阉魉闼惴?。A算法和和A*搜搜索算法法的目標(biāo)標(biāo)有所不不同：A搜索索算法雖雖然希望望能找到到問(wèn)題的的最優(yōu)解解，但主主要追求求的是求求解效率率；而A*搜索索算法直直接目標(biāo)標(biāo)就在于于要找到到問(wèn)題的的最優(yōu)解解及其解解的路徑徑，即便便搜索效效率有所所降低也也在所不不惜。3.2.3A*算算法開(kāi)始把S放入OPEN表表,記f=hOPEN為為空表？失敗選取OPEN表中未未設(shè)置過(guò)的的具有最小小f值的節(jié)點(diǎn)BESTNODE，放放入CLOSED表表BESTNODE=Sg？成功是是擴(kuò)展BESTNODE，產(chǎn)生生后繼節(jié)點(diǎn)點(diǎn)SUVVESSOR建立從SUCCESSOR返返回BESTNODE的指針針計(jì)算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR)SUCCESSOR∈OPEN？否是3.2.3A*算算法把SECCESSOR放入OPEN表表，加入BESTNODE的后裔裔表g(SUCCESSOR)<g(OLD)？否重新確定OLD的父父輩節(jié)點(diǎn)為為BESTNODE，并修正父輩輩節(jié)點(diǎn)的g值和f值值，記下g(OLD)SUCCESSOR∈CLOSED？？否是SECCESSOR=OLD，把它添添到BESTNODE的的后繼節(jié)點(diǎn)點(diǎn)表中是否計(jì)算f值3.3博博弈樹(shù)搜索索3.3.1博弈弈概述何謂博弈？？博弈就是下下棋、打牌牌、競(jìng)技、、戰(zhàn)爭(zhēng)等一一類(lèi)競(jìng)爭(zhēng)性性智能活動(dòng)動(dòng)?！岸肆愫秃头桥既恍孕匀畔ⅰ薄辈┺模?）二人人零和：對(duì)壘的MAX、MIN雙方輪輪流采取行行動(dòng)，博弈弈的結(jié)果只只有三種情情況：MAX方勝，，MIN方方勝，和局局。（2）全信信息：在對(duì)壘過(guò)程程中，任何何一方都了了解當(dāng)前格格局及過(guò)去去的歷史。。（3）非偶偶然性：任何一方在在采取行動(dòng)動(dòng)前都要根根據(jù)當(dāng)前的的實(shí)際情況況，進(jìn)行得得失分析，，選取對(duì)自自己最為有有利而對(duì)對(duì)對(duì)方最為不不利的對(duì)策策，不存在在“碰運(yùn)氣氣”，“僥僥幸”及““偶然失誤誤”等隨機(jī)機(jī)因素。3.3博博弈樹(shù)搜索索3.3.1博弈弈概述參加博弈的的各方都希希望己方取取得勝利。。因此，當(dāng)當(dāng)一方面臨臨多個(gè)行動(dòng)動(dòng)方案選擇擇時(shí)，博弈的各方方總是要挑挑選對(duì)自己己最為有利利而對(duì)對(duì)方方最不利的的那個(gè)行動(dòng)動(dòng)方案。假如MAX方的的目標(biāo)：盡可能使自自己達(dá)到最最大（或最最高）的分分?jǐn)?shù)分枝節(jié)節(jié)點(diǎn)，可用“或”關(guān)系來(lái)描述述，稱(chēng)之為為MAX方節(jié)點(diǎn)；而當(dāng)輪到MIN方行行動(dòng)時(shí)，MIN方的的目標(biāo)：盡可能使MIN方獲獲得最小（（或最低））的分?jǐn)?shù)分分枝節(jié)點(diǎn)，，這對(duì)MIN方來(lái)說(shuō)，，這些行動(dòng)動(dòng)方案或分分?jǐn)?shù)分枝節(jié)節(jié)點(diǎn)之間，，可以用“與”關(guān)系來(lái)描述述，是由MIN方自主進(jìn)行控控制的，故故又稱(chēng)之為為MIN節(jié)點(diǎn)。3.3博博弈樹(shù)搜索索3.3.1博弈弈概述把上述雙方方逐層交替替的博弈過(guò)過(guò)程用與/或樹(shù)（圖圖）描述表表達(dá)出來(lái)，，就得到了了一棵具有有“與/或或”節(jié)點(diǎn)交交替出現(xiàn)的的博弈樹(shù)。。博弈樹(shù)有如如下特點(diǎn)：：（1）博弈弈的初始格格局是初始始節(jié)點(diǎn)。（2）在博博弈樹(shù)中，，由于雙方輪流地地?cái)U(kuò)展節(jié)點(diǎn)點(diǎn)，“或””節(jié)點(diǎn)和““與”節(jié)點(diǎn)點(diǎn)逐層交替替出現(xiàn)。如果自己一一方擴(kuò)展的的節(jié)點(diǎn)之間間是“或””關(guān)系，則則對(duì)方擴(kuò)展展的節(jié)點(diǎn)之之間是“與與”關(guān)系。。（3）把本本方獲勝的的終局定義義為本原問(wèn)問(wèn)題，相應(yīng)應(yīng)最優(yōu)搜索索路徑上的的節(jié)點(diǎn)是可可解節(jié)點(diǎn)，，而所有使使對(duì)方獲勝勝的終局和和屬于對(duì)方方最優(yōu)搜索索路徑上的的節(jié)點(diǎn)則是是不可解節(jié)節(jié)點(diǎn)。此外外，所有其其它的節(jié)點(diǎn)點(diǎn)則是具有有風(fēng)險(xiǎn)的中中間節(jié)點(diǎn)。。3.3博博弈樹(shù)搜索索3.3.2極小極極大分析法法在二人博弈弈過(guò)程中，，最直觀而而可靠的常常用分析方方法就是極極小極大化化搜索法。。其主要描描述思想和和算法：（1）設(shè)博博弈的一方方為MAX方，其目目標(biāo)是盡可可能使自己己得到最高高分；另一一方為MIN方,其其目標(biāo)是是盡可能給給MAX方方送出最低低分。所謂謂極小極大大化分析法法是一種要要輪流為每每一方尋找找一個(gè)最優(yōu)優(yōu)行動(dòng)方案案的方法。。在圖中，，方框形狀狀“□”表表示是MAX方控制制的或節(jié)點(diǎn)點(diǎn)；圓形框框形狀“○○”表示MIN方控控制與節(jié)點(diǎn)點(diǎn)。（2）考慮慮每一方案案實(shí)施后對(duì)對(duì)方可能采采取的所有有行動(dòng)，并并為其計(jì)算算可能的得得分；（3）為計(jì)計(jì)算得分，，需要根據(jù)據(jù)問(wèn)題的特特性信息定定義一個(gè)估估價(jià)函數(shù)，，用來(lái)估算算當(dāng)前博弈弈樹(shù)所有端端節(jié)點(diǎn)的得得分。此時(shí)時(shí)估算出來(lái)來(lái)的得分稱(chēng)稱(chēng)為的靜態(tài)態(tài)估值。3.3博博弈樹(shù)搜索索3.3.2極小極大大分析法（4）當(dāng)端端節(jié)點(diǎn)的估估值計(jì)算出出來(lái)后，再再推算父輩輩節(jié)點(diǎn)的等等分，推算算方法是：：對(duì)“或””節(jié)點(diǎn)，選選擇其子節(jié)節(jié)點(diǎn)中最大大的得分作作為父輩節(jié)節(jié)點(diǎn)的得分分（選擇對(duì)對(duì)自己最有有利的方案案）；對(duì)““與”節(jié)點(diǎn)點(diǎn)，選其子子節(jié)點(diǎn)中一一個(gè)最小的的得分作為為作為父輩輩節(jié)點(diǎn)的得得分（立足足于最壞的的情況）。。這樣計(jì)算算出的父輩輩節(jié)點(diǎn)的等等分稱(chēng)為倒倒推值。（5）如果果一個(gè)行動(dòng)動(dòng)方案能獲獲得較大的的倒推值，，則它就是是當(dāng)前最好好的行動(dòng)方方案。存儲(chǔ)受限問(wèn)問(wèn)題：先生生成一定深深度的博弈弈樹(shù)，進(jìn)行行極小極大大分析，找找出當(dāng)前的的最好的行行動(dòng)方案。。然后再已已選定的分分支上再擴(kuò)擴(kuò)展一定的的深度，如如此反復(fù)。。3.3.2極小極大大分析法4-1-1812-50-4-9-151143-1–158101425-59606-410–9-1125MAX-MIN博弈弈樹(shù)的倒推推值計(jì)算h(S0)=？4820-14-13.3博博弈樹(shù)搜索索3.3博博弈樹(shù)搜索索3.3.3α-ββ剪枝技術(shù)術(shù)基本思想：：邊生成博博弈樹(shù)邊估估算各節(jié)點(diǎn)點(diǎn)的倒推值值，并且根根據(jù)評(píng)估出出的倒推值值范圍，及及時(shí)停止擴(kuò)擴(kuò)展那些已已無(wú)必要再再擴(kuò)展的子子節(jié)點(diǎn)。具體剪枝方方法：（1）對(duì)對(duì)于一個(gè)““與”節(jié)點(diǎn)點(diǎn)MIN，，若能估計(jì)計(jì)出其倒推推值上界ββ，并且這這個(gè)β值不不大于MIN的父輩輩節(jié)點(diǎn)（一一定是“或或”節(jié)點(diǎn)））的估計(jì)倒倒推值的下下界α，即即α≥ββ，則就不不必要再擴(kuò)擴(kuò)展該MIN節(jié)點(diǎn)的的其余子節(jié)節(jié)點(diǎn)了。這這一過(guò)程稱(chēng)稱(chēng)為α剪枝枝。（2）對(duì)于于一個(gè)“或或”節(jié)點(diǎn)MAX，若若能估計(jì)出出其倒推值值下界α，，并且這這個(gè)α值值不小于MAX的父父輩節(jié)點(diǎn)（（一定是““與”節(jié)點(diǎn)點(diǎn)）的估計(jì)計(jì)倒推值的的上界β，，即α≥≥β，則則就不必要要再擴(kuò)展該該MAX節(jié)節(jié)點(diǎn)的其余余子節(jié)點(diǎn)了了。這一過(guò)過(guò)程稱(chēng)為ββ剪枝。。3.3博博弈樹(shù)搜索索3.3.3α-ββ剪枝技術(shù)術(shù)從算法中看看到：（1）MAX節(jié)點(diǎn)（（包括起始始節(jié)點(diǎn)）的的α值永不不減少。（2）MIN節(jié)點(diǎn)（（包括起始始節(jié)點(diǎn)）的的β值永不不增加。在搜索期期間，αα和ββ值的的計(jì)算如如下：（1）一一個(gè)MAX節(jié)點(diǎn)點(diǎn)的α值值等于其其后繼節(jié)節(jié)點(diǎn)當(dāng)前前最大的的最終倒倒推值。。（2）一一個(gè)MIN節(jié)點(diǎn)點(diǎn)的β值值等于于其后繼繼節(jié)點(diǎn)當(dāng)當(dāng)前最小小的最終終倒推值值。3.3博博弈樹(shù)樹(shù)搜索αα-β剪剪枝技術(shù)術(shù)例3.5一字字棋搜索索樹(shù)α和和β值計(jì)計(jì)算估價(jià)函數(shù)數(shù)g(p)定義義如下：：（1）若若當(dāng)前棋棋局對(duì)任任何一方方都不是是獲勝的的，則g(p)=(所所有空格格都放上上MAX的棋子子之后3個(gè)棋子子所組成成的行列列及對(duì)角角線(xiàn)的總總數(shù)）—（所有空空格都放放上MIN的棋棋子之后后3個(gè)棋棋子所組組成的行行列及對(duì)對(duì)角線(xiàn)的的總數(shù)））（2）若若p是MAX獲獲勝，則則g(p)=+∞∞（3）若若p是MIN獲獲勝，則則g(p)=-∞∞上圖中，，g(p)=6-4=2，其其中×表表示MAX方，，○表表示MIN方○×αα-β剪剪枝技術(shù)術(shù)3.3博博弈樹(shù)樹(shù)搜索×××○×○×○×○×○○×初始節(jié)點(diǎn)點(diǎn)α=-1ABC-1β=-16-5=15-5=06-5=15-5=04-5=-15-6=-1αα-β剪剪枝技術(shù)術(shù)3.3博博弈樹(shù)樹(shù)搜索4-1-1812-50-4-9-151143-1–158101425-59606-410–9-1125MAX-MIN博弈樹(shù)樹(shù)的倒推推值計(jì)算算h(S0)=？4820-14-1αα-β剪剪枝技術(shù)術(shù)3.3博博弈樹(shù)樹(shù)搜索h(S0)=？441133–1–18810822-5-52244x?554×α×α

×β

×α

×α

×α

×α

博弈樹(shù)的的α-ββ剪枝實(shí)實(shí)現(xiàn)過(guò)程程3.3博博弈樹(shù)樹(shù)搜索αα-β剪剪枝技術(shù)術(shù)要進(jìn)行αα-β剪剪枝，必必須至少少使某一一部分的的搜索樹(shù)樹(shù)生長(zhǎng)到到最大深深度，因因?yàn)棣梁秃挺轮当乇仨氁远硕斯?jié)點(diǎn)的的靜態(tài)估估值為依依據(jù)。因因此采用用α-ββ剪枝技技術(shù)通常常都要使使用某種種深度優(yōu)優(yōu)先的搜搜索方法法。3.4遺遺傳算算法生物群體體的生存存過(guò)程普普遍遵循循達(dá)爾文文的物競(jìng)競(jìng)天擇、、適者生生存的進(jìn)進(jìn)化準(zhǔn)則則；生物物通過(guò)個(gè)個(gè)體間的的選擇、、交叉、、變異來(lái)來(lái)適應(yīng)大大自然環(huán)環(huán)境。生生物染色色體用數(shù)數(shù)學(xué)方式式或計(jì)算算機(jī)方式式來(lái)體現(xiàn)現(xiàn)就是一一串?dāng)?shù)碼碼，仍叫叫染色體體，有時(shí)時(shí)也叫個(gè)個(gè)體；適適應(yīng)能力力用對(duì)應(yīng)應(yīng)一個(gè)染染色體的的數(shù)值來(lái)來(lái)衡量；；染色體體的選擇擇或淘汰汰問(wèn)題是是按求最最大還是是最小問(wèn)問(wèn)題來(lái)進(jìn)進(jìn)行。遺傳算法法是模仿仿生物遺遺傳學(xué)和和自然選選擇機(jī)理理，通過(guò)過(guò)人工方方式構(gòu)造造的一類(lèi)類(lèi)優(yōu)化搜搜索算法法，是對(duì)對(duì)生物進(jìn)進(jìn)化過(guò)程程進(jìn)行的的一種數(shù)數(shù)學(xué)仿真真，是進(jìn)進(jìn)化計(jì)算算的一種種最重要要形式。。3.4遺遺傳算算法遺傳算法法提出：：于20世世紀(jì)60年代由由密歇根根(Michigan)大學(xué)學(xué)Hollstien,Bagleyh和Rosenberg等人人在其博博士論文文中首先先加以研研究；1975年，美美國(guó)J.H.Holland教授在在其著作作“AdaptationinNaturalandArtificialSystems”中系統(tǒng)地地闡述了了遺傳算算法，給給出了遺遺傳算法法的基本本定理和和大量的的數(shù)學(xué)理理論證明明。遺傳算法法發(fā)展：：DavidE.Goldberg教授授1989年出出版了“GeneticAlgorichms”一書(shū)，這這一著作作通常被被認(rèn)為是是遺傳算算法的方方法、理理論及應(yīng)應(yīng)用的全全面系統(tǒng)統(tǒng)的總結(jié)結(jié)。從1985年起，，國(guó)際上上開(kāi)始陸陸續(xù)舉行行遺傳算算法的國(guó)國(guó)際會(huì)議議，后來(lái)來(lái)又更名名為進(jìn)化化計(jì)算。。參加進(jìn)進(jìn)化計(jì)算算國(guó)際會(huì)會(huì)議的人人數(shù)及收收錄文章章的數(shù)量量、廣度度和深度度逐年擴(kuò)擴(kuò)大。從從此，進(jìn)進(jìn)化計(jì)算算逐漸成成為人們們用來(lái)解解決高度度復(fù)雜問(wèn)問(wèn)題的新新思路和和新方法法。3.4遺遺傳算算法遺傳算法法特點(diǎn)：：遺傳算法法是一種種基于空空間搜索索的算法法，它通通過(guò)自然然選擇、、遺傳、、變異等等操作以以及達(dá)爾爾文適者者生存的的理論，，模擬自自然進(jìn)化化過(guò)程來(lái)來(lái)尋找所所求問(wèn)題題的解答答。遺傳傳算法具具有以下下特點(diǎn)：：(1)遺遺傳算算法是對(duì)對(duì)參數(shù)集集合的編編碼而非非針對(duì)參參數(shù)本身身進(jìn)行進(jìn)進(jìn)化；(2)遺遺傳算算法是從從問(wèn)題解解的編碼碼組開(kāi)始始而非從從單個(gè)解解開(kāi)始搜搜索；(3)遺遺傳算算法利用用目標(biāo)函函數(shù)的適適應(yīng)度這這一信息息而非利利用導(dǎo)數(shù)數(shù)或其它它輔助信信息來(lái)指指導(dǎo)搜索索；(4)遺遺傳算算法利利用選選擇、、交叉叉、變變異等等算子子而不不是利利用確確定性性規(guī)則則進(jìn)行行隨機(jī)機(jī)操作作。3.4遺遺傳算算法遺傳算算法應(yīng)應(yīng)用：：J.H.Holland博士士于1975年年提出出遺傳傳算法法,當(dāng)當(dāng)時(shí)并并沒(méi)有有引起起學(xué)術(shù)術(shù)界足足夠的的重視視。直直到二二十世世紀(jì)80年年代中中期,隨著著計(jì)算算機(jī)技技術(shù)日日新月月異高高速發(fā)發(fā)展與與進(jìn)步步,遺遺傳算算法首首先成成功地地應(yīng)用用于AI機(jī)機(jī)器學(xué)學(xué)習(xí)和和神經(jīng)經(jīng)網(wǎng)絡(luò)絡(luò)方面面;后后來(lái)又又在諸諸如函函數(shù)優(yōu)優(yōu)化、、自動(dòng)動(dòng)控制制、圖圖象識(shí)識(shí)別、、分子子生物物學(xué)、、優(yōu)化化調(diào)度度以及及機(jī)械械、土土木、、電力力工程程等工工業(yè)系系統(tǒng)和和許多多領(lǐng)域域中得得到應(yīng)應(yīng)用,顯示示出誘誘人的的前景景。從從此，，遺傳傳算法法始才才得到到學(xué)術(shù)術(shù)界普普遍關(guān)關(guān)注與與認(rèn)可可。3.4遺遺傳算算法遺遺傳算算法的的基本本原理理霍蘭德德提出出的遺遺傳算算法通通常稱(chēng)稱(chēng)為簡(jiǎn)簡(jiǎn)單遺遺傳算算法（（SGA））?，F(xiàn)現(xiàn)以此此作為為討論論主要要對(duì)象象，加加上適適應(yīng)的的改進(jìn)進(jìn)，來(lái)來(lái)分析析遺傳傳算法法的結(jié)結(jié)構(gòu)和和機(jī)理理。在在討論論中會(huì)會(huì)結(jié)合合銷(xiāo)售售員旅旅行問(wèn)問(wèn)題（（TSP））來(lái)說(shuō)說(shuō)明。。1.編編碼碼與解解碼許多應(yīng)應(yīng)用問(wèn)問(wèn)題的的結(jié)構(gòu)構(gòu)很復(fù)復(fù)雜，，但可可以化化為簡(jiǎn)簡(jiǎn)單的的位串串形式式編碼碼表示示。將將問(wèn)題題結(jié)構(gòu)構(gòu)變換換為位位串形形式編編碼表表示的的過(guò)程程叫編編碼；；而相相反將將位串串形式式編碼碼表示示變換換為原原問(wèn)題題結(jié)構(gòu)構(gòu)的過(guò)過(guò)程叫叫解碼碼或譯譯碼。。把位位串形形式編編碼表表示叫叫染色色體，，有時(shí)時(shí)也叫叫個(gè)體體。3.4遺遺傳算算法遺遺傳算算法的的基本本原理理例：對(duì)對(duì)于銷(xiāo)銷(xiāo)售員員旅行行問(wèn)題題（TravellingsalesmanProblem,TSP）），設(shè)設(shè)有n個(gè)城城市，，城市市i和和城市市j之之間的的距離離為d(i,j)，，要求求找到到一條條遍訪(fǎng)訪(fǎng)每個(gè)個(gè)城市市一次次而且且恰好好一次次的旅旅行線(xiàn)線(xiàn)路，，使其其路徑徑總長(zhǎng)長(zhǎng)度為為最短短。按按一條條回路路中城城市的的次序序進(jìn)行行編碼碼。從從城市市w1開(kāi)始，，依次次經(jīng)過(guò)過(guò)城市市w2，………，wn，最后后回到到城市市w1，我們們就有有如下下編碼碼表示示：w1w2……wn由于是是回路路，記記wn+1=w1。它其其實(shí)是是1，，………，n的一個(gè)個(gè)循環(huán)環(huán)排列列。要要注意意w1，w2，……，wn是互不相同同的。3.4遺遺傳算法3.4.1遺傳算算法的基本本原理2.適應(yīng)應(yīng)度函數(shù)為了體現(xiàn)染染色體的適適應(yīng)能力，，引入了對(duì)對(duì)問(wèn)題中的的每一個(gè)染染色體都能能進(jìn)行度量量的函數(shù)，，叫適應(yīng)度度函數(shù)（fitnessfunction））。TSP的目標(biāo)是是路徑總長(zhǎng)長(zhǎng)度為最短短，自然地地，路徑總總長(zhǎng)度的倒倒數(shù)就可作作為T(mén)SP問(wèn)題的適適應(yīng)度函數(shù)數(shù):其中wn+1=w1適應(yīng)度函數(shù)數(shù)要有效反反映每一個(gè)個(gè)染色體與與問(wèn)題的最最優(yōu)解染色色體之間的的差距。適適應(yīng)度函數(shù)數(shù)的取值大大小與求解解問(wèn)題對(duì)象象的意義有有很大的關(guān)關(guān)系。3.4遺遺傳算法3.4.1遺傳算算法的基本本原理3.遺傳傳操作簡(jiǎn)單遺傳算算法的遺傳傳操作主要要有有三種種:選擇(selection)、交交叉(crossover)、變異(mutation)。改進(jìn)進(jìn)的遺傳算算法大量擴(kuò)擴(kuò)充了遺傳傳操作，以以達(dá)到更高高的效率。。選擇操作也也叫復(fù)制（（reproduction）操作，，根據(jù)個(gè)體體的適應(yīng)度度函數(shù)值所所度量的優(yōu)優(yōu)劣程度決決定它在下下一代是被被淘汰還是是被遺傳。。簡(jiǎn)單遺傳算算法采用賭賭輪選擇機(jī)機(jī)制，令∑∑fi表示群體的的適應(yīng)度值值之總和，，fi表示種群中中第i個(gè)染染色體的適適應(yīng)度值，，它產(chǎn)生后后代的能力力正好為其其適應(yīng)度值值所占份額額fi/∑fi。3.4遺遺傳算法3.4.1遺傳算算法的基本本原理3.遺傳傳操作交叉操作的的簡(jiǎn)單方式式是將被選選擇出的兩兩個(gè)個(gè)體P1和P2作為父母母?jìng)€(gè)體，將將兩者的部部分碼值進(jìn)進(jìn)行交換。。產(chǎn)生一個(gè)1~7之間間的隨機(jī)數(shù)數(shù)c，假設(shè)設(shè)為3，則則將P1和和P2的低低3位交換換10001110P1：11011001P2：3.4遺遺傳算法3.4.1遺傳算算法的基本本原理3.遺傳傳操作10001110P1：11011001P2：1000100111011110Q1：Q2：3.4遺遺傳算法3.4.1遺傳算算法的基本本原理3.遺傳傳操作變異操作的的簡(jiǎn)單方式式是改變數(shù)數(shù)碼串的某某個(gè)位置上上的數(shù)碼。。二進(jìn)制編編碼表示的的簡(jiǎn)單變異異操作是將將0與1互互換：0變變異為1，，1變異為為0。隨機(jī)產(chǎn)生一一個(gè)1~8之間的數(shù)數(shù)k，假設(shè)設(shè)k=5，，對(duì)從右往往左第5位位變異操作作。1010011013.4遺遺傳算法3.4.1遺傳算算法的基本本原理4.控制制參數(shù)交叉發(fā)生的的概率：0.6~0.95變異的概率率：0.001~0.01種群的個(gè)數(shù)數(shù)：30~100個(gè)體的長(zhǎng)度度：定長(zhǎng)和和變長(zhǎng)3.4遺遺傳算法3.4.2遺傳算算法的結(jié)構(gòu)構(gòu)選擇：由個(gè)個(gè)體適應(yīng)度度值決定的某個(gè)規(guī)則則。交叉：按概概率Pc進(jìn)行變異：按概概率Pm進(jìn)行終止條件：：①完成了了預(yù)先給定定的進(jìn)化代代數(shù)②種群中中的最優(yōu)個(gè)個(gè)體在連續(xù)續(xù)若干代沒(méi)有改進(jìn)或或平均適應(yīng)應(yīng)度在連續(xù)續(xù)若干代基本沒(méi)沒(méi)有改進(jìn)開(kāi)始初始化種群群選擇操作終止條件否適應(yīng)度最有有優(yōu)個(gè)體計(jì)算適應(yīng)度度值交叉操作變異操作結(jié)束3.4遺遺傳算法3.4.3遺傳算算法的性能能遺傳算法求求得的解是是一滿(mǎn)意解解。影響解解質(zhì)量的因因素：種群的數(shù)量量：太小缺缺少多樣性性，太多影影響效率適應(yīng)度函數(shù)數(shù)：提升優(yōu)優(yōu)良個(gè)體的的適應(yīng)度交叉和變異異：不同的的問(wèn)題需構(gòu)構(gòu)造性能更更優(yōu)的交叉叉和變異操操作交叉概率和和變異概率率：分析：對(duì)該該問(wèn)題雖然然也可以采采用枚舉的的方法來(lái)解解決,但枚枚舉法卻是是一種效率率很低的方方法.可運(yùn)運(yùn)用遺傳算算法來(lái)求解解該問(wèn)題.解：首先對(duì)對(duì)問(wèn)題進(jìn)行行初始化，，以獲得初初始種群;（1）確確定適當(dāng)?shù)牡木幋a方案案：將x編編碼表示為為染色體的的數(shù)字符號(hào)號(hào)串。針對(duì)對(duì)本題自變變量x定義義域,取值值范圍為[0，31],考慮慮采用二進(jìn)進(jìn)制數(shù)來(lái)對(duì)對(duì)其編碼,由25=32,故使用5位無(wú)符號(hào)號(hào)二進(jìn)制數(shù)數(shù)組成染色色體數(shù)字字字符串,用用以表達(dá)變變量x及問(wèn)題的解解答過(guò)程。。例:設(shè)有函數(shù)f(x)=x2,請(qǐng)用遺遺傳算法求求其自變量量x在區(qū)間[0，31]取整數(shù)數(shù)值時(shí)的最最大值，并并說(shuō)明此函函數(shù)的優(yōu)化化問(wèn)題。3.4遺遺傳算法（2）選擇擇初始種群群:通過(guò)隨隨機(jī)的方法法來(lái)產(chǎn)生染染色體的數(shù)數(shù)字串，并并組成初始始種群。例例如，為得得到數(shù)字串串的某位——又稱(chēng)之為基基因(genes)，使用計(jì)計(jì)算機(jī)在0～1之間間產(chǎn)生隨機(jī)機(jī)數(shù)K，并并按照數(shù)K的變化區(qū)區(qū)域來(lái)規(guī)定定基因代碼碼如下：0，（0≤K＜0.5）1，（0.5≤K≤1）3.4遺遺傳算法G=于是隨機(jī)生成4個(gè)染色體的數(shù)數(shù)字符串為為：01101110000100010011從而構(gòu)造了了初始種群群，完成了了遺傳算法法的準(zhǔn)備。。3.4遺遺傳算法表初始種種群染色體體及對(duì)應(yīng)的的適應(yīng)值3.4遺遺傳算法染色體標(biāo)號(hào)

串

x

適應(yīng)值f(x)=x2占整體的百分?jǐn)?shù)

1

01101

169

14.4%

2

11000

576

49.2%

301000

64

5.5%

4

10011

361

30.9%

總計(jì)∑（初始種群值）

1170

100.0%（3）復(fù)制制(選擇):選擇適應(yīng)值值大的串作作為母本，，使在下一一代中有更更多的機(jī)會(huì)會(huì)繁殖其子子孫。要在四個(gè)種種子個(gè)體中中做選擇，，要求仍然然得到四個(gè)個(gè)染色體，，可依據(jù)適適應(yīng)度概率率比例制定定如下規(guī)則則：低于0.125以下下的染色體體被淘汰；；在0.125～0.375之之間的染色色體被復(fù)制制一個(gè)；在0.375～0.625之之間的染色色體被復(fù)制制兩個(gè)；在0.625～0.875之之間的染色色體被復(fù)制制三個(gè)；在0.875以上的的染色體可可復(fù)制四個(gè)個(gè)。3.4遺遺傳算法對(duì)應(yīng)于上例例，按照適適應(yīng)度的計(jì)計(jì)算，經(jīng)復(fù)復(fù)制操作后后，得到新新的染色體體種群為011011100011000100113.4遺遺傳算法某個(gè)染色體體是否被復(fù)復(fù)制,可以以通過(guò)概率率決策法、、適應(yīng)度比比例法或“輪盤(pán)賭”的隨機(jī)方法法來(lái)斷定。。對(duì)應(yīng)輪盤(pán)盤(pán)賭轉(zhuǎn)盤(pán)的的隨機(jī)方法法,根據(jù)表表6.1數(shù)數(shù)據(jù)，繪制制出的輪盤(pán)盤(pán)賭轉(zhuǎn)盤(pán),如圖所示示:進(jìn)化計(jì)算———基本遺傳算法原原理49.2﹪30.9%14.4%5.5%011011100011000100113.4遺遺傳算法初始種群x值適應(yīng)度選擇概率期望值實(shí)際復(fù)制數(shù)編號(hào)（隨機(jī)產(chǎn)生）（無(wú)符號(hào)整數(shù)）f(x)=x2Pc

f(xi)/fA（或轉(zhuǎn)輪法）

101101131690.1440.581

211000245760.4921.972

3010008640.0550.220

410011193610.3091.231

∑11701.004.004.0

平均(A)

2930.251.001.0

MAX5760.491.972.0初始種群染染色體準(zhǔn)備備復(fù)制操作作的各項(xiàng)計(jì)計(jì)算數(shù)據(jù)（4）交叉:交叉具體分分兩步：①①將新復(fù)制制產(chǎn)生的染色體隨機(jī)兩兩匹匹配,稱(chēng)其為雙親親染色體；②再把雙親染色體體進(jìn)行交叉繁繁殖。交叉的實(shí)現(xiàn)現(xiàn):設(shè)染染色體數(shù)字字串長(zhǎng)度為為L(zhǎng)，把L個(gè)數(shù)字位間間空隙分別別標(biāo)記為：：1，，2，…，L－1隨機(jī)從[1，L－1]中選選取某一整整數(shù)位置k，0<k<L交換雙親染染色體交換換點(diǎn)位置k右邊的部部分，就形形成了兩個(gè)個(gè)新的數(shù)字字符串（也也可以只交交換其中的的第k基因因），得到到了兩個(gè)新新的染色體體，又稱(chēng)之之為下一代代染色體。。3.4遺遺傳算法例如，將上上例初始種種群的兩個(gè)個(gè)體A1=01┇10┇1A2=11┇00┇0假定從1到到4間選取取兩個(gè)隨機(jī)機(jī)數(shù)，得到到к1=2，к2=4，那么么經(jīng)過(guò)交叉叉操作之后后將得到如如下兩組新新的數(shù)字符符串A1#=01000A2#=111013.4遺遺傳算法A3#=01100A4#=11001前一組數(shù)字字串是使用用к1=2,即將將第2位后后的3～5位交換得得到；后一組數(shù)字字串是使用用к2=4，即僅僅將第5位位因子進(jìn)行交換而而得。3.4遺遺傳算法編號(hào)復(fù)制操作后的區(qū)配池匹配號(hào)(隨機(jī)選取)交叉空隙位(隨機(jī)選取)交叉后新種群新種群x值適應(yīng)度f(wàn)(x)=x21011012201000864211000121110129841311000441100125625410011341000016256總計(jì)（∑）1786平均(A)446.5最大值(MAX)

841復(fù)制、交叉叉操作的各各項(xiàng)數(shù)據(jù)（5）變異異:設(shè)變異概率率取為0.001,則對(duì)于種種群總共有有20個(gè)基基因位.期望的變異異串位數(shù)計(jì)計(jì)算:20×0.001=0.02(位),故一般來(lái)說(shuō)說(shuō),該例中中無(wú)基因位位數(shù)值的改改變.從表表11-2和11-3可以看看出,每經(jīng)經(jīng)過(guò)一次復(fù)復(fù)制、交叉叉和變異操操作后,目目標(biāo)函數(shù)的的最優(yōu)值和和平均值就就會(huì)有所提提高。在上例中，，種群的平平均適應(yīng)值值從293增至446.5;最大的適適應(yīng)度數(shù)值值從576增至841。特點(diǎn)：每經(jīng)經(jīng)一次進(jìn)化化計(jì)算步驟驟,問(wèn)題解解答便向著著最優(yōu)方向向前進(jìn)了一一步;若該該過(guò)程一直直進(jìn)行下去去,就將最最終走向全全局的最優(yōu)優(yōu)解.可見(jiàn)見(jiàn)進(jìn)化計(jì)算算的每一步步操作簡(jiǎn)單單,并且系系統(tǒng)的求解解過(guò)程是依依照計(jì)算方方法與規(guī)律律來(lái)決定,與本源問(wèn)問(wèn)題自身的的特性很少少相關(guān)。3.4遺遺傳算法固體退火原原理：固體體內(nèi)部粒子子隨著溫度度升高而變變?yōu)闊o(wú)