第3章-搜索原理

第3章搜索原理知識(shí)點(diǎn)重難點(diǎn)學(xué)習(xí)要求知識(shí)點(diǎn)盲目搜索啟發(fā)式搜索博弈樹(shù)搜索遺傳算法模擬退火算法

重難點(diǎn)寬度優(yōu)先深度優(yōu)先等代價(jià)搜索有序搜索A*算法博弈樹(shù)搜索學(xué)習(xí)要求重點(diǎn)掌握寬度優(yōu)先和深度優(yōu)先搜索算法掌握等代價(jià)搜索算法掌握啟發(fā)式搜索相關(guān)知識(shí)理解博弈樹(shù)搜索相關(guān)技術(shù)掌握遺傳算法基本原理理解模擬退火算法基本原理第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹(shù)搜索3.4遺傳算法3.5模擬退火算法3.1盲目搜索知識(shí)是解決問(wèn)題的基礎(chǔ)，解決問(wèn)題的方法一種就是算法，但對(duì)很多問(wèn)題沒(méi)有有效的算法（或無(wú)現(xiàn)成算法），這時(shí)就可利用最一般方法即搜索來(lái)解決。1、搜索的概念根據(jù)問(wèn)題的實(shí)際情況，按照一定的策略或規(guī)則，從知識(shí)庫(kù)中尋找可利用的知識(shí)，從而構(gòu)造出一條使問(wèn)題獲得解決的推理路線(xiàn)的過(guò)程，就稱(chēng)為搜索。盲目搜索（續(xù)）搜索包含兩層含義：一是要找到從初始事實(shí)到問(wèn)題最終答案的一條推理路線(xiàn)，另一是找到的這條路線(xiàn)是時(shí)間和空間復(fù)雜度最小的求解路線(xiàn)。2、搜索的種類(lèi)分為盲目搜索和啟發(fā)式搜索。

盲目搜索又稱(chēng)無(wú)信息搜索，即在搜索過(guò)程中，只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索，而沒(méi)有任何中間信息來(lái)改變這些控制策略。即問(wèn)題本身的特性對(duì)搜索控制策略沒(méi)有任何影響，這就使搜索帶有盲目性，效率不高。只用于解決比較簡(jiǎn)單的問(wèn)題。盲目搜索（續(xù)）

啟發(fā)式搜索又稱(chēng)有信息搜索，指搜索求解過(guò)程中，根據(jù)問(wèn)題本身的特性或搜索過(guò)程中產(chǎn)生的一些信息來(lái)不斷改變或調(diào)整搜索的方向，使搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解，并找到最優(yōu)解。求解的效率更高，更易于求解復(fù)雜的問(wèn)題。盲目搜索（續(xù)）（1）寬度優(yōu)先搜索（2）深度優(yōu)先搜索（3）等代價(jià)搜索3.1.1圖搜索策略搜索法求解問(wèn)題的基本思想:首先將問(wèn)題的初始狀態(tài)(即狀態(tài)空間圖中的初始節(jié)點(diǎn))當(dāng)做當(dāng)前狀態(tài)，選擇一適當(dāng)?shù)乃惴饔糜诋?dāng)前狀態(tài)，生成一組后繼狀態(tài)（或稱(chēng)后繼節(jié)點(diǎn)），然后檢查這組后繼狀態(tài)中有沒(méi)有目標(biāo)狀態(tài)。如果有，則說(shuō)明搜索成功，從初始狀態(tài)到目標(biāo)狀態(tài)的一系列算符即是問(wèn)題的解；若沒(méi)有，則按某種控制策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)，重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)或不再有可供操作的狀態(tài)及算符為止。圖搜索策略舉例從某王姓家族的四代中找王A的后代且其壽命為X的人。

王A：壽命47，有兒子王B1、王B3、王B2

王B1：壽命77，有兒子王C1、王C2

王B3：壽命52，有兒子王D1

王B2：壽命65，有兒子王E1、王E2

王F1：壽命32

王G1：壽命96

王C2：壽命87，有兒子王F1

王D1：壽命77，沒(méi)有兒子

王E1：壽命57，有兒子王G1

王E2：壽命92，有兒子王H1

王C1：壽命27，沒(méi)有兒子

王H1：壽命51

若X=57，下面討論一種可通用的圖搜索策略求解此問(wèn)題。

用圖表示方法的家族表圖搜索策略（續(xù)）1、概念已擴(kuò)展節(jié)點(diǎn)：對(duì)于狀態(tài)圖中的某個(gè)節(jié)點(diǎn)，若求出了它的后繼節(jié)點(diǎn)，稱(chēng)已擴(kuò)展節(jié)點(diǎn)。未擴(kuò)展節(jié)點(diǎn)：對(duì)于狀態(tài)圖中的某個(gè)節(jié)點(diǎn)，尚未求出它的后繼節(jié)點(diǎn)，稱(chēng)未擴(kuò)展節(jié)點(diǎn)。擴(kuò)展：就是用合適的算符對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行操作，生成一組后繼節(jié)點(diǎn)，擴(kuò)展過(guò)程實(shí)際上就是求后繼節(jié)點(diǎn)的過(guò)程。圖搜索策略（續(xù)）2、狀態(tài)空間圖的一般搜索算法用兩個(gè)表分別存放已擴(kuò)展節(jié)點(diǎn)和未擴(kuò)展節(jié)點(diǎn)，OPEN表存放未擴(kuò)展節(jié)點(diǎn)，CLOSED表存放已擴(kuò)展節(jié)點(diǎn)。兩個(gè)表的結(jié)構(gòu)如下：

OPEN表：

CLOSED表：節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)狀態(tài)空間圖的一般搜索算法（1）建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到OPEN表中。（2）建立CLOSED表，且置為空表。（3）若OPEN表是空表，則問(wèn)題無(wú)解，失敗退出。狀態(tài)空間圖的一般搜索算法（4）選擇OPEN表中的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出，并放入CLOSED表中，將此節(jié)點(diǎn)記為節(jié)點(diǎn)n，它是CLOSED表中節(jié)點(diǎn)的編號(hào)。（5）若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出。問(wèn)題的解即可從圖G中沿著指針從n到S這條路徑而得到。

IFGOAL(N)THENEXIT(SUCCESS)狀態(tài)空間圖的一般搜索算法（6）擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M中的這些成員作為n的后繼節(jié)點(diǎn)加入圖G中。狀態(tài)空間圖的一般搜索算法（7）針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理對(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è)较颉顟B(tài)空間圖的一般搜索算法（8）按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序。（9）轉(zhuǎn)第（3）步。

GOLOOP一般搜索過(guò)程框圖例子例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}圖搜索策略（續(xù)）3、搜索圖與搜索樹(shù)

圖搜索過(guò)程生成一個(gè)明確的圖G（稱(chēng)為搜索圖）和一個(gè)G的子集T（稱(chēng)為搜索樹(shù)），樹(shù)T上的每個(gè)節(jié)點(diǎn)也在圖G中。例：二階Hanoi塔問(wèn)題。狀態(tài)空間圖如下。（1，1）（2，1）（3，1）（2，3）（3，2）（3，3）（1，3）（1，2）（2，2）A(2,1)A(1,2)初始狀態(tài)目標(biāo)狀態(tài)SS1S2S3S4S5S6S7S8圖搜索策略（續(xù)）搜索圖G為：搜索樹(shù)T為：SS1S2S3S4S5S6S7S8S8SS1S2S3S4S5S6S7圖搜索策略（續(xù)）4、圖搜索方法的幾點(diǎn)分析（1）對(duì)OPEN表進(jìn)行排序（盲目或啟發(fā)式搜索）。（2）被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，成功，回溯，可找到路徑。否則，失敗終止情況下沒(méi)有解路徑。

在利用狀態(tài)空間搜索方法求解問(wèn)題時(shí)，并不是將整個(gè)問(wèn)題的狀態(tài)空間圖全部輸入計(jì)算機(jī)，而是只存入問(wèn)題有關(guān)的部分狀態(tài)空間圖，這部分是在搜索過(guò)程中生成的，并且每前進(jìn)一步，都要檢查是否到達(dá)目標(biāo)節(jié)點(diǎn)，這樣就可盡量減少生成與問(wèn)題求解無(wú)關(guān)的狀態(tài)，從而提高了解題效率，節(jié)省了存儲(chǔ)空間。3.1.2寬度優(yōu)先搜索定義如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。寬度優(yōu)先搜索又稱(chēng)廣度優(yōu)先搜索，是一種盲目搜索策略。其基本思想是：從初始節(jié)點(diǎn)開(kāi)始，逐層對(duì)節(jié)點(diǎn)進(jìn)行依次擴(kuò)展，并考慮它是否為目標(biāo)節(jié)點(diǎn)，在對(duì)下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）前，必須完成對(duì)當(dāng)前層的所有節(jié)點(diǎn)的擴(kuò)展（或搜索）。寬度優(yōu)先搜索特點(diǎn)：OPEN表中的節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面寬度優(yōu)先搜索示意圖寬度優(yōu)先搜索算法(1)把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。

(2)如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。

(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。

寬度優(yōu)先搜索算法(4)擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。

(5)把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。

(6)如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。寬度優(yōu)先搜索算法框圖寬度優(yōu)先搜索方法分析（1）將OPEN表作為“先進(jìn)先出”的隊(duì)列進(jìn)行操作；（2）寬度優(yōu)先搜索方法能夠保證在搜索樹(shù)中找到一條通向目標(biāo)節(jié)點(diǎn)的最短路徑（即寬度優(yōu)先搜索策略是完備的）；（3）搜索樹(shù)提供了所有存在的路徑；（4）盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)較遠(yuǎn)時(shí)，將產(chǎn)生大量無(wú)用節(jié)點(diǎn)。重排九宮問(wèn)題初始狀態(tài)目標(biāo)狀態(tài)算符：左移、上移、右移、下移優(yōu)點(diǎn)：只要有解，用廣度優(yōu)先搜素總可以得到，而且路徑最短缺點(diǎn)：搜索效率低，特別是目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題3.1.3深度優(yōu)先搜索定義深度優(yōu)先搜索也是一種盲目搜索策略，其基本思想是：首先擴(kuò)展最新產(chǎn)生的（即最深）節(jié)點(diǎn)，即從初始節(jié)點(diǎn)S開(kāi)始，在其后繼節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)，對(duì)其進(jìn)行考察，若它不是目標(biāo)節(jié)點(diǎn)，則對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展，并再?gòu)乃暮罄^節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察。依次類(lèi)推，一直搜索下去，當(dāng)?shù)竭_(dá)某個(gè)既非目標(biāo)節(jié)點(diǎn)又無(wú)法繼續(xù)擴(kuò)展的節(jié)點(diǎn)時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。深度優(yōu)先搜索示意圖定義節(jié)點(diǎn)的深度(1)起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。

(2)任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1。

深度優(yōu)先搜索（續(xù)）有界深度優(yōu)先搜索為了避免考慮太長(zhǎng)的路徑(防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去)，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度，即深度界限(dm)。任何節(jié)點(diǎn)如果達(dá)到了深度界限，都將被作為沒(méi)有后繼節(jié)點(diǎn)處理。有界深度優(yōu)先搜索算法(1)把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解。

(2)如果OPEN為一空表，則失敗退出。

(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移到CLOSED表。

(4)如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向(2)。

(5)擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒(méi)有后裔，則轉(zhuǎn)向(2)。

(6)如果后繼節(jié)點(diǎn)中有任一個(gè)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解，成功退出；否則，轉(zhuǎn)向(2)。

有界深度優(yōu)先搜索算法框圖深度優(yōu)先搜索策略分析（1）將OPEN表作為“先進(jìn)后出”的棧進(jìn)行操作；（2）深度優(yōu)先搜索所求得的解答路徑不一定是最短路徑；（3）深度界限得選擇很重要，過(guò)大，可能會(huì)影響搜索效率，過(guò)小，有可能求不到解。有界深度優(yōu)先搜索策略是不完備的。深度界限dm的選擇先任意給定一個(gè)較小的數(shù)作為dm，進(jìn)行有界深度的優(yōu)先搜索，當(dāng)深度達(dá)到dm時(shí)仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，且CLOSE表中人有待擴(kuò)展節(jié)點(diǎn)時(shí)，將這些節(jié)點(diǎn)送回OPEN表，同時(shí)增大深度界限dm，繼續(xù)向下搜索。只要有解，一定可以找到。按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹(shù)，深度界限為53.1.4等代價(jià)搜索定義有些問(wèn)題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。寬度優(yōu)先搜索可被推廣用來(lái)解決這種尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問(wèn)題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算法。等代價(jià)搜索（續(xù)）代價(jià)樹(shù)：邊上有代價(jià)（或費(fèi)用）S：起始節(jié)點(diǎn)。c(i,j):

節(jié)點(diǎn)i到它的后繼節(jié)點(diǎn)j的連接弧線(xiàn)代價(jià)。g(i):

起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)，在搜索樹(shù)上它也是從起始節(jié)點(diǎn)S到節(jié)點(diǎn)i的最少代價(jià)路徑上的代價(jià)。代價(jià)的計(jì)算公式：g(j)=g(i)+c(i,j)等代價(jià)搜索的基本思想每次從OPEN表中選擇節(jié)點(diǎn)向CLOSE中傳送時(shí)，總是選擇其代價(jià)為最小的節(jié)點(diǎn)等代價(jià)搜索（續(xù)）等代價(jià)搜索算法

與寬度優(yōu)先搜索算法區(qū)別，以g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)，即根據(jù)節(jié)點(diǎn)的代價(jià)大小對(duì)OPEN表中的所有節(jié)點(diǎn)進(jìn)行從小到大的排序。（1）把起始節(jié)點(diǎn)S放到OPEN表中。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則令g(S)=0；（2）如果OPEN表是個(gè)空表，則沒(méi)有解而失敗退出；等代價(jià)搜索（續(xù)）（3）從OPEN表中選擇一個(gè)節(jié)點(diǎn)i，使其g(i)為最小。如果有幾個(gè)節(jié)點(diǎn)都合格，那么就要選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn)i（如果有目標(biāo)節(jié)點(diǎn)）；否則，就從中選一個(gè)作為節(jié)點(diǎn)i。把節(jié)點(diǎn)i從OPEN表移至CLOSED表中；（4）如果節(jié)點(diǎn)i為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；（5）擴(kuò)展節(jié)點(diǎn)i。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向步驟（2）（6）對(duì)于節(jié)點(diǎn)i的每個(gè)后繼節(jié)點(diǎn)j，計(jì)算g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點(diǎn)j放進(jìn)OPEN表。提供回到節(jié)點(diǎn)i的指針。（7）轉(zhuǎn)向步驟（2）。等代價(jià)搜索（續(xù)）舉例分析例：推銷(xiāo)員旅行問(wèn)題。

假設(shè)A，B，C，D，E是5個(gè)城市，推銷(xiāo)員從城市A出發(fā)，到達(dá)城市E，走怎樣的路線(xiàn)費(fèi)用最省？5個(gè)城市間的交通圖及每?jī)蓚€(gè)城市間的旅行費(fèi)用如圖所示。ABCDE675348畫(huà)代價(jià)樹(shù)的原則作業(yè)1、分別用寬度優(yōu)先搜索、有界深度優(yōu)先搜索（深度界限5）求解下圖所示八數(shù)碼難題。初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，并畫(huà)出對(duì)應(yīng)搜索樹(shù)。2318476512384765S0Sg作業(yè)（續(xù)）2、推銷(xiāo)員旅行問(wèn)題。設(shè)有5個(gè)相互直達(dá)的城市A、B、C、D、E，如下圖所示，各城市間的交通費(fèi)用已在圖中標(biāo)出。推銷(xiāo)員從城市A出發(fā)，去每個(gè)城市各旅行一次，最后到達(dá)城市E，請(qǐng)找出一條費(fèi)用最省的旅行路線(xiàn)。80ABCDE90858065170110140160100第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹(shù)搜索3.4遺傳算法3.5模擬退火算法3.1啟發(fā)式搜索

啟發(fā)式搜索要用到問(wèn)題自身的某些特性信息，以指導(dǎo)搜索朝著有希望的方向前進(jìn)。搜索效率高概念：?jiǎn)l(fā)性信息啟發(fā)信息是進(jìn)行搜索技術(shù)所需要的一些有關(guān)具體問(wèn)題領(lǐng)域的特性的信息。按用途可分為3種。（1）用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展。概念：?jiǎn)l(fā)性信息（2）在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于決定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目地同時(shí)生成所有可能的節(jié)點(diǎn)。（3）用于決定某些應(yīng)該從搜索樹(shù)中拋棄或修剪的節(jié)點(diǎn)。概念：估價(jià)函數(shù)用于評(píng)估節(jié)點(diǎn)重要性的函數(shù)，叫做估價(jià)函數(shù)概念：估價(jià)函數(shù)一個(gè)節(jié)點(diǎn)的“希望”有幾種不同的定義方法。在狀態(tài)空間問(wèn)題中，一種定義是估算目標(biāo)節(jié)點(diǎn)到此節(jié)點(diǎn)的距離；另一種定義是整條路徑（包括被估價(jià)過(guò)的節(jié)點(diǎn)）的長(zhǎng)度或難度。用符號(hào)f來(lái)標(biāo)記估價(jià)函數(shù)，用f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值。估價(jià)函數(shù)的一般形式f(x)=g(x)+h(x)f(x)：估價(jià)函數(shù)定義為從初始節(jié)點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)估計(jì)值。作用是估價(jià)OPEN表中各節(jié)點(diǎn)的重要性，決定OPEN表的次序；g(x)為初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)付出的實(shí)際代價(jià)；h(x)為從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的估計(jì)的最小路徑代價(jià)。

搜索信息主要由h(x)來(lái)體現(xiàn)，稱(chēng)為啟發(fā)函數(shù)。估價(jià)函數(shù)的要點(diǎn)啟發(fā)式搜索（續(xù)）3、有序搜索用估價(jià)函數(shù)f來(lái)排列OPEN表上的節(jié)點(diǎn)，選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索或最佳優(yōu)先搜索。它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。有序搜索又可分為兩種：局部最佳優(yōu)先搜索和全局最佳優(yōu)先搜索。有序搜索的算法1)把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S)并把其值與節(jié)點(diǎn)S聯(lián)系起來(lái)。

(2)如果OPEN是個(gè)空表，則失敗退出，無(wú)解。

(3)從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i。

有序搜索的算法(4)把節(jié)點(diǎn)i從OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。

(5)如果i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。

(6)擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j：有序搜索的算法(a)計(jì)算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。(c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對(duì)j計(jì)算過(guò)的f值和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的f值。如果新的f值較小，則

有序搜索的算法(i)以此新值取代舊值。

(ii)從j指向i，而不是指向它的父輩節(jié)點(diǎn)。(iii)如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表(7)轉(zhuǎn)向(2)，即GOTO(2)。

有序搜索的算法框圖估價(jià)函數(shù)例子——解決九宮問(wèn)題

采用簡(jiǎn)單的估價(jià)函數(shù)f(n)=d(n)+w(n),d(n)是搜索樹(shù)中節(jié)點(diǎn)n的深度；w(n)用來(lái)計(jì)算節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)Sg相比較，錯(cuò)位的數(shù)碼個(gè)數(shù)。估價(jià)函數(shù)例子——解決九宮問(wèn)題28316475初始狀態(tài)f值等于0+4=4

1（4）（6）

（6）

（7）4（5）

2（4）

（6）5（5）

6（5）

（5）

（7）

（7）

（7）（6）（5）估價(jià)函數(shù)例子結(jié)論估價(jià)函數(shù)的應(yīng)用顯著地減少了被擴(kuò)展的節(jié)點(diǎn)數(shù)用估價(jià)函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過(guò)程有序搜索寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索均是有序搜索的特例。寬度優(yōu)先搜索，f(i)是節(jié)點(diǎn)i的深度。等代價(jià)搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價(jià)。有序搜索的特點(diǎn)即使有解，不一定能找到解特點(diǎn)是使用啟發(fā)式信息（估價(jià)函數(shù)），可他有時(shí)也會(huì)騙人，使人誤入歧途。有序搜索即使能找到解，也不一定是最優(yōu)的有序搜索（續(xù)）

有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。

A算法定義：在圖搜索過(guò)程中，如果OPEN表節(jié)點(diǎn)順序是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，稱(chēng)該過(guò)程為A算法。A*算法一般搜索過(guò)程滿(mǎn)足了如下限制A*算法的定義如果對(duì)于所有的x，h(x)≤h*(x)成立。采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱(chēng)為A*算法。說(shuō)明：搜索算法的可采納性

在搜索圖存在從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)解答路徑的情況下，若一個(gè)搜索方法總能找到最短（代價(jià)最?。┑慕獯鹇窂?，則稱(chēng)該算法具有可采納性。A*算法為了考察啟發(fā)式搜索算法A的可采納性，首先引入估價(jià)函數(shù)f*：f*(x)=g*(x)+h*(x)f*(x)、g*(x)、h*(x)分別指示當(dāng)經(jīng)由節(jié)點(diǎn)x的最短（代價(jià)最小）解答路徑找到時(shí)實(shí)際的路徑代價(jià)（長(zhǎng)度）、該路徑前段（自初始節(jié)點(diǎn)到節(jié)點(diǎn)x）代價(jià)和后段（自節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)）代價(jià)。A*算法一般來(lái)講，g(x)的值容易從迄今已生成的搜索樹(shù)中計(jì)算出來(lái)，不必專(zhuān)門(mén)定義計(jì)算公式。這時(shí)g(x)≥g*(x)。然而h(x)的設(shè)計(jì)依賴(lài)于啟發(fā)式知識(shí)的應(yīng)用，所以如何挖掘貼切的啟發(fā)式知識(shí)是設(shè)計(jì)估價(jià)函數(shù)乃至A算法的關(guān)鍵?？梢宰C明，若確保對(duì)于搜索圖中的節(jié)點(diǎn)x，總是有h(x)≤h*(x)，則A算法具有可采納性，既總能搜索到最短（代價(jià)最小）的解答路徑。所以A*算法是可采納的。A*算法(1)把S放入OPEN表，記f=h，令CLOSED為空表。(2)重復(fù)下列過(guò)程，直至找到目標(biāo)節(jié)點(diǎn)止。若OPEN為空表，則宣告失敗。(3)選取OPEN表中未設(shè)置過(guò)的具有最小f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn)BESTNODE，并把它放入CLOSED表。(4)若BESTNODE為一目標(biāo)節(jié)點(diǎn)，則成功求得一解。(5)若BESTNODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn)SUCCSSOR。(6)對(duì)每個(gè)SUCCSSOR進(jìn)行下列過(guò)程：

A*算法(a)建立從SUCCSSOR返回BESTNODE的指針。(b)計(jì)算g(SUC)=g(BES)+g(BES,SUC)。(c)如果SUCCSSOR∈OPEN，則稱(chēng)此節(jié)點(diǎn)為OLD，并把它添至BESTNODE的后繼節(jié)點(diǎn)表中。(d)比較新舊路徑代價(jià)。如果g(SUC)＜g(OLD),則重新確定OLD的父輩節(jié)點(diǎn)為BESTNODE，記下較小代價(jià)g(OLD),并修正f(OLD)值。A*算法(e)若至OLD節(jié)點(diǎn)的代價(jià)較低或一樣，則停止擴(kuò)展節(jié)點(diǎn)。(f)若SUCCSSOR不在CLOSE表中，則看其是否在CLOSED表中。(g)若SUCCSSOR在CLOSE表中，則轉(zhuǎn)向c。(h)若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，則把它放入OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向(7)(i)計(jì)算f值。(7)GOLOOP

作業(yè)分別利用估價(jià)函數(shù)f(n)=d(n)+w(n)和f(n)=d(n)+p(n)，采用最佳優(yōu)先搜索方法求解下列八數(shù)碼問(wèn)題。初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，并畫(huà)出對(duì)應(yīng)搜索樹(shù)。1372468512384765S0Sg第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹(shù)搜索3.4遺傳算法3.5模擬退火算法3.3博弈樹(shù)搜索下棋、打牌、戰(zhàn)爭(zhēng)等一類(lèi)競(jìng)爭(zhēng)性智能活動(dòng)稱(chēng)為博弈。3.3博弈樹(shù)搜索1、概述討論最簡(jiǎn)單的“二人零和、全信息、非偶然”博弈，特征有：（1）對(duì)壘雙方輪流采取行動(dòng)，結(jié)果有3種：甲勝、乙勝、和局；（2）在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前的格局及過(guò)去的歷史；（3）雙方都是很理智的決定自己的行動(dòng)。博弈樹(shù)搜索（續(xù)）描述博弈過(guò)程的與或樹(shù)稱(chēng)為博弈樹(shù)，有如下特點(diǎn)：（1）博弈的初始格局是初始節(jié)點(diǎn)；（2）在博弈樹(shù)中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)。（3）所有自己一方獲勝的終局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都認(rèn)為是不可解節(jié)點(diǎn)。極大極小分析法（1）設(shè)博弈的雙方一方為MAX，另一方為MIN，然后為其中的一方（例如MAX）尋找一個(gè)最優(yōu)行動(dòng)方案；（2）考慮每一方案實(shí)施后，對(duì)方可能采取的所有行動(dòng)，計(jì)算可能的得分；（3）定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱(chēng)為靜態(tài)估值；博弈樹(shù)搜索（續(xù)）（4）推算出父節(jié)點(diǎn)的得分。對(duì)“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大的得分作為父節(jié)點(diǎn)的得分；對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為父節(jié)點(diǎn)的得分。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱(chēng)為倒推值；例：倒推值的計(jì)算（5）若一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好得行動(dòng)方案。博弈樹(shù)搜索（續(xù)）可行的辦法是只生成一定深度的博弈樹(shù)，然后進(jìn)行極大極小分析，找出當(dāng)前最好的行動(dòng)方案。此后，再在已選定的分支上擴(kuò)展一定深度，再選最好的行動(dòng)方案，如此進(jìn)行下去，直到取得勝敗的結(jié)果為止。至于每生成博弈樹(shù)深度，當(dāng)然是越大越好，具體視情況而定。博弈樹(shù)搜索（續(xù)）實(shí)例：“一”字棋游戲極大極小分析法九個(gè)空格，誰(shuí)先使自己的棋子構(gòu)成“三子成一線(xiàn)”（同一行或同一列或?qū)蔷€(xiàn)全是某人的棋子），誰(shuí)就取得了勝利。用叉號(hào)代表MAX，用圓圈代表MIN。如下圖為MIN取勝的棋局。博弈樹(shù)搜索（續(xù)）為了不致于生成太大的博弈樹(shù)，假設(shè)每次擴(kuò)展兩層。估價(jià)函數(shù)定義如下：設(shè)棋局為P，估價(jià)函數(shù)為e(P)；（1）若P對(duì)任何一方來(lái)說(shuō)都不是獲勝位置，則e(P)=e(那些仍為MIN空著的完全的行、列、對(duì)角線(xiàn)的總數(shù))-e(那些仍為MAX空著的完全行、列、對(duì)角線(xiàn)的總數(shù))；（2）若P是MAX必勝的棋局，則e(P)=+∞；（3）若P是MIN必勝的棋局，則e(P)=-∞。博弈樹(shù)搜索（續(xù)）比如P如右圖所示，則：e(P)=6-4=2要注意利用棋盤(pán)位置的對(duì)稱(chēng)性，在生成后繼節(jié)點(diǎn)位置時(shí)，下列結(jié)局都是相同的棋局。博弈樹(shù)搜索（續(xù)）下面是經(jīng)過(guò)兩層搜索生成的博弈樹(shù)，靜態(tài)估值記在端節(jié)點(diǎn)下面。博弈樹(shù)搜索例2剪枝技術(shù)剪枝原因博弈樹(shù)生成的工作量大，鑒于博弈樹(shù)具有“與”節(jié)點(diǎn)，“或”節(jié)點(diǎn)逐層交替出現(xiàn)的特點(diǎn)，若能邊生成節(jié)點(diǎn)邊計(jì)算估值及倒推值，則可刪除一些不必要的節(jié)點(diǎn)。減少搜索計(jì)算的工作量剪枝技術(shù)的基本思想在生成博弈樹(shù)的同時(shí)計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹(shù)上的一些分枝，從而節(jié)約了機(jī)器開(kāi)銷(xiāo)，提高了搜索效率。剪枝技術(shù)例α-β剪枝技術(shù)α-β剪枝的一般規(guī)律α-β剪枝例子第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹(shù)搜索3.4遺傳算法3.5模擬退火算法3.4遺傳算法遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理，通過(guò)人工方式所構(gòu)造的一類(lèi)搜索算法，是對(duì)生物進(jìn)化過(guò)程進(jìn)行的數(shù)學(xué)方式仿真。1965年由霍蘭德提出，現(xiàn)在國(guó)際上已經(jīng)形成了一個(gè)比較活躍的研究領(lǐng)域。遺傳算法已用于求解帶有應(yīng)用前景的一些問(wèn)題，例如遺傳程序設(shè)計(jì)、函數(shù)優(yōu)化、排序問(wèn)題、人工神經(jīng)網(wǎng)絡(luò)、分類(lèi)系統(tǒng)、計(jì)算機(jī)圖像處理和機(jī)器人運(yùn)動(dòng)規(guī)劃等。遺傳算法（續(xù)）生物種群的生存過(guò)程普遍遵循達(dá)爾文進(jìn)化準(zhǔn)則，群體中的個(gè)體根據(jù)對(duì)環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進(jìn)化過(guò)程的結(jié)果反映在個(gè)體的結(jié)構(gòu)上，其染色體包含若干基因，相應(yīng)的表現(xiàn)型和基因型的聯(lián)系體現(xiàn)了個(gè)體的外部特性與內(nèi)部機(jī)理間邏輯關(guān)系。通過(guò)個(gè)體之間的交叉、變異來(lái)適應(yīng)大自然環(huán)境。生物染色體用數(shù)學(xué)方式或計(jì)算機(jī)方式來(lái)體現(xiàn)就是一串?dāng)?shù)碼，仍叫染色體，有時(shí)也叫個(gè)體；適應(yīng)能力是對(duì)應(yīng)著一個(gè)染色體的一個(gè)數(shù)值來(lái)衡量；染色體的選擇或淘汰則按所面對(duì)的問(wèn)題是求最大還是最小來(lái)進(jìn)行。遺傳算法的基本原理霍蘭德(Holland)的遺傳算法通常被稱(chēng)為“簡(jiǎn)單遺傳算法”(簡(jiǎn)稱(chēng)SGA)，以此作為討論主要對(duì)象，加上適當(dāng)?shù)母倪M(jìn)，分析遺傳算法的結(jié)構(gòu)和機(jī)理。

1.編碼與譯碼將問(wèn)題結(jié)構(gòu)變換為位串形式編碼表示的過(guò)程叫編碼；而相反將位串形式編碼表示變換為原問(wèn)題結(jié)構(gòu)的過(guò)程叫譯碼。我們把位串形式編碼表示叫染色體，有時(shí)也叫個(gè)體。1.編碼與譯碼應(yīng)用舉例----貨郎擔(dān)問(wèn)題(TravellingSalesmanProblem，簡(jiǎn)記為T(mén)SP)：設(shè)有n個(gè)城市，城市i和城市j之間的距離為d(i，j)i,j=1,...,n．TSP問(wèn)題是要找遍訪(fǎng)每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短。

1.編碼與譯碼對(duì)TSP可以按一條回路城市的次序進(jìn)行編碼，比如碼串134567829表示從城市1開(kāi)始，依次是城市3,4,5,6,7,8,2,9，最后回到城市1。一般情況是從城市w1開(kāi)始，依次經(jīng)過(guò)城市w2,……，wn，最后回到城市w1，我們就有如下編碼表示：

w1w2……wn

由于是回路，記wn+1=w1。它其實(shí)是1，……，n的一個(gè)循環(huán)排列。要注意w1,w2,……，wn是互不相同的。

2.適應(yīng)度函數(shù)為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。通過(guò)適應(yīng)度函數(shù)來(lái)決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)勝劣汰原則。對(duì)優(yōu)化問(wèn)題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。TSP的目標(biāo)是路徑總長(zhǎng)度為最短，路徑總長(zhǎng)度的倒數(shù)就可以為T(mén)SP的適應(yīng)度函數(shù)：

請(qǐng)注意其中wn+1=w1。2.適應(yīng)度函數(shù)

適應(yīng)度函數(shù)要有效反映每一個(gè)染色體與問(wèn)題的最優(yōu)解染色體之間的差距，一個(gè)染色體與問(wèn)題的最優(yōu)解染色體之間的差距小，則對(duì)應(yīng)的適應(yīng)度函數(shù)值之差就小，否則就大。適應(yīng)度函數(shù)的取值大小與求解問(wèn)題對(duì)象的意義有很大的關(guān)系。

3.遺傳操作

簡(jiǎn)單遺傳算法的遺傳操作主要有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。

遺傳操作——選擇操作選擇操作也叫復(fù)制操作，根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說(shuō)，選擇將使適應(yīng)度較大(優(yōu)良)個(gè)體有較大的存在機(jī)會(huì)，而適應(yīng)度較小（低劣）的個(gè)體繼續(xù)存在的機(jī)會(huì)也較小。

遺傳操作——交叉操作交叉操作的簡(jiǎn)單方式是將被選擇出的兩個(gè)個(gè)體P1和P2作為父母?jìng)€(gè)體，將兩者的部分碼值進(jìn)行交換。假設(shè)有如下八位長(zhǎng)的二個(gè)體：

遺傳操作——交叉操作產(chǎn)生一個(gè)在1到7之間的隨機(jī)數(shù)c，假如現(xiàn)在產(chǎn)生的是3，將P1和P2的低三位交換：P1的高五位與P2的低三位組成數(shù)串10001001，這就是P1和P2的一個(gè)后代Q1個(gè)體；P2的高五位與P1的低三位組成數(shù)串11011110，這就是P1和P2的一個(gè)后代Q2個(gè)體。其交換過(guò)程如下圖所示：

遺傳操作——變異操作變異操作的簡(jiǎn)單方式是改變數(shù)碼串的某個(gè)位置上的數(shù)碼。我們先以最簡(jiǎn)單的二進(jìn)制編碼表示方式來(lái)說(shuō)明，二進(jìn)制編碼表示的每一個(gè)位置的數(shù)碼只有0與1這兩個(gè)可能，比如有如下二進(jìn)制編碼表示：

遺傳操作——變異操作其碼長(zhǎng)為8，隨機(jī)產(chǎn)生一個(gè)1至8之間的數(shù)k，假如現(xiàn)在k=5，對(duì)從右往左的第5位進(jìn)行變異操作，將原來(lái)的0變?yōu)?，得到如下數(shù)碼串：

二進(jìn)制編碼表示時(shí)的簡(jiǎn)單變異操作是將0與1互換：0變異為1，1變異為0。

TSP的變異操作隨機(jī)產(chǎn)生一個(gè)1至n之間的數(shù)k，決定對(duì)回路中的第k個(gè)城市的代碼wk作變異操作，又產(chǎn)生一個(gè)1至n之間的數(shù)w，替代wk，并將wk加到尾部，得到：w1w2……wk-1wwk+1……wnwk這個(gè)串有n+1個(gè)數(shù)碼，注意數(shù)w其實(shí)在此串中出現(xiàn)重復(fù)了，必須刪除與數(shù)w相重復(fù)的，得到合法的染色體。

4.控制參數(shù)（1）交叉操作和變異操作的概率

交叉概率取0.6至0.95之間的值；變異概率取0.001至0.01之間的值（2）種群規(guī)模

通常種群規(guī)模為30至100

（3）個(gè)體的長(zhǎng)度

有定長(zhǎng)和變長(zhǎng)兩種。它對(duì)算法的性能也有影響。

二、遺傳算法的結(jié)構(gòu)遺傳算法類(lèi)似于自然進(jìn)化，通過(guò)作用于染色體上的基因?qū)ふ液玫娜旧w來(lái)求解問(wèn)題。與自然界相似，遺傳算法對(duì)求解問(wèn)題的本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來(lái)選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。二、遺傳算法的結(jié)構(gòu)在遺傳算法中，通過(guò)隨機(jī)方式產(chǎn)生若干個(gè)所求解問(wèn)題的數(shù)字編碼，即染色體，形成初始群體；通過(guò)適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過(guò)遺傳操作后的個(gè)體集合形成下一代新的種群。對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化。這就是遺傳算法的基本原理。

簡(jiǎn)單遺傳算法框圖簡(jiǎn)單遺傳算法框圖程序的停止條件有二種完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個(gè)體在連續(xù)若干代沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒(méi)有改進(jìn)時(shí)停止。

三、遺傳算法的收斂性一般的遺傳算法不一定收斂，只有每代保存了最優(yōu)個(gè)體時(shí)才收斂。在實(shí)際應(yīng)用中，使用了上述結(jié)論來(lái)保證收斂性。采用優(yōu)秀個(gè)體保護(hù)法就是將每代中的最優(yōu)個(gè)體，直接進(jìn)入子代，相應(yīng)淘汰其子代中適應(yīng)度最差的個(gè)體，使種群規(guī)模不變。當(dāng)遺傳算法收斂時(shí)，求到的解通常只是所要解決問(wèn)題的最優(yōu)解的一個(gè)近似解，或者叫滿(mǎn)意解。

四、遺傳算法的性能（1）種群規(guī)模（2）適應(yīng)度函數(shù)的構(gòu)造（3）交叉和變異操作（影響最大）（4）交叉和變異概率（5）停止條件（與解的質(zhì)量有關(guān)）交叉和變異概率變異概率大會(huì)擴(kuò)大搜索范圍，使搜索過(guò)程不陷入局部極小，但也可能使正朝著最優(yōu)解緩慢前進(jìn)的個(gè)體改變方向，破壞好個(gè)體；變異概率大則對(duì)染色體的破壞大，因此常設(shè)定一大一小兩個(gè)變異概率，當(dāng)整個(gè)種群平均適應(yīng)度增長(zhǎng)較快時(shí)，使用小變異概率；反之使用較大變異概率。對(duì)整個(gè)種群使用相同的變異概率，并不利于優(yōu)良個(gè)體的成長(zhǎng)和劣個(gè)體的改良。

交叉或變異產(chǎn)生的新個(gè)體能否與父?jìng)€(gè)體進(jìn)行競(jìng)爭(zhēng)？按簡(jiǎn)單遺傳算法，交叉或變異產(chǎn)生的新個(gè)體不論優(yōu)劣都取代父?jìng)€(gè)體，并不科學(xué)。對(duì)新個(gè)體要有與父?jìng)€(gè)體進(jìn)行競(jìng)爭(zhēng)的機(jī)會(huì)，當(dāng)父?jìng)€(gè)體比新個(gè)體優(yōu)時(shí)，按一定的概率保留父?jìng)€(gè)體而舍去新個(gè)體。

停止條件按預(yù)設(shè)的進(jìn)化代數(shù)作停止條件，由于不同的問(wèn)題的復(fù)雜度不同，而且對(duì)同一問(wèn)題構(gòu)造的遺傳操作不同其算法性能不同，因此很難合理地預(yù)設(shè)。另一個(gè)常用的停止條件是種群中的最優(yōu)個(gè)體在連續(xù)若干代沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒(méi)有改進(jìn)時(shí)，這是一個(gè)比較合理的方式。但可能由于構(gòu)造的算法