第3章-搜索原理

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

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

盲目搜索又稱無信息搜索，即在搜索過程中，只按預先規(guī)定的搜索控制策略進行搜索，而沒有任何中間信息來改變這些控制策略。即問題本身的特性對搜索控制策略沒有任何影響，這就使搜索帶有盲目性，效率不高。只用于解決比較簡單的問題。盲目搜索（續(xù)）

啟發(fā)式搜索又稱有信息搜索，指搜索求解過程中，根據(jù)問題本身的特性或搜索過程中產(chǎn)生的一些信息來不斷改變或調(diào)整搜索的方向，使搜索朝著最有希望的方向前進，加速問題的求解，并找到最優(yōu)解。求解的效率更高，更易于求解復雜的問題。盲目搜索（續(xù)）（1）寬度優(yōu)先搜索（2）深度優(yōu)先搜索（3）等代價搜索3.1.1圖搜索策略搜索法求解問題的基本思想:首先將問題的初始狀態(tài)(即狀態(tài)空間圖中的初始節(jié)點)當做當前狀態(tài)，選擇一適當?shù)乃惴饔糜诋斍盃顟B(tài)，生成一組后繼狀態(tài)（或稱后繼節(jié)點），然后檢查這組后繼狀態(tài)中有沒有目標狀態(tài)。如果有，則說明搜索成功，從初始狀態(tài)到目標狀態(tài)的一系列算符即是問題的解；若沒有，則按某種控制策略從已生成的狀態(tài)中再選一個狀態(tài)作為當前狀態(tài)，重復上述過程，直到目標狀態(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，沒有兒子

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

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

王C1：壽命27，沒有兒子

王H1：壽命51

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

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

OPEN表：

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

IFGOAL(N)THENEXIT(SUCCESS)狀態(tài)空間圖的一般搜索算法（6）擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M中的這些成員作為n的后繼節(jié)點加入圖G中。狀態(tài)空間圖的一般搜索算法（7）針對M中子節(jié)點的不同情況，分別進行如下處理對那些未曾在G中出現(xiàn)過的（既未曾在OPEN表上或CLOSED表上出現(xiàn)過的）M成員設置一個通向n的指針。把M的這些成員加進OPEN表。對已經(jīng)在OPEN表或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后繼節(jié)點的指針方向。狀態(tài)空間圖的一般搜索算法（8）按某種搜索策略對OPEN表中的節(jié)點進行排序。（9）轉第（3）步。

GOLOOP一般搜索過程框圖例子例子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、搜索圖與搜索樹

圖搜索過程生成一個明確的圖G（稱為搜索圖）和一個G的子集T（稱為搜索樹），樹T上的每個節(jié)點也在圖G中。例：二階Hanoi塔問題。狀態(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)目標狀態(tài)SS1S2S3S4S5S6S7S8圖搜索策略（續(xù)）搜索圖G為：搜索樹T為：SS1S2S3S4S5S6S7S8S8SS1S2S3S4S5S6S7圖搜索策略（續(xù)）4、圖搜索方法的幾點分析（1）對OPEN表進行排序（盲目或啟發(fā)式搜索）。（2）被選作擴展的節(jié)點為目標節(jié)點時，成功，回溯，可找到路徑。否則，失敗終止情況下沒有解路徑。

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

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

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

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

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

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

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

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

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

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

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

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

(6)如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解，成功退出；否則，轉向(2)。

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

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

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

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

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

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

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

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

(3)從OPEN表中選擇一個f值最小的節(jié)點i。結果有幾個節(jié)點合格，當其中有一個為目標節(jié)點時，則選擇此目標節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點i。

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

(5)如果i是個目標節(jié)點，則成功退出，求得一個解。

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

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

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

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

采用簡單的估價函數(shù)f(n)=d(n)+w(n),d(n)是搜索樹中節(jié)點n的深度；w(n)用來計算節(jié)點n與目標狀態(tài)節(jié)點Sg相比較，錯位的數(shù)碼個數(shù)。估價函數(shù)例子——解決九宮問題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）估價函數(shù)例子結論估價函數(shù)的應用顯著地減少了被擴展的節(jié)點數(shù)用估價函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程有序搜索寬度優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索均是有序搜索的特例。寬度優(yōu)先搜索，f(i)是節(jié)點i的深度。等代價搜索，f(i)是從起始節(jié)點至節(jié)點i這段路徑的代價。有序搜索的特點即使有解，不一定能找到解特點是使用啟發(fā)式信息（估價函數(shù)），可他有時也會騙人，使人誤入歧途。有序搜索即使能找到解，也不一定是最優(yōu)的有序搜索（續(xù)）

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

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

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

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

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

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

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

w1w2……wn

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

2.適應度函數(shù)為了體現(xiàn)染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數(shù)，叫適應度函數(shù)。通過適應度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進化中的優(yōu)勝劣汰原則。對優(yōu)化問題，適應度函數(shù)就是目標函數(shù)。TSP的目標是路徑總長度為最短，路徑總長度的倒數(shù)就可以為TSP的適應度函數(shù)：

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

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

3.遺傳操作

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

遺傳操作——選擇操作選擇操作也叫復制操作，根據(jù)個體的適應度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應度較大(優(yōu)良)個體有較大的存在機會，而適應度較?。ǖ土樱┑膫€體繼續(xù)存在的機會也較小。

遺傳操作——交叉操作交叉操作的簡單方式是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值進行交換。假設有如下八位長的二個體：

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

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

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

二進制編碼表示時的簡單變異操作是將0與1互換：0變異為1，1變異為0。

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

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

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

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

（3）個體的長度

有定長和變長兩種。它對算法的性能也有影響。

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

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

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

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

交叉或變異產(chǎn)生的新個體能否與父個體進行競爭？按簡單遺傳算法，交叉或變異產(chǎn)生的新個體不論優(yōu)劣都取代父個體，并不科學。對新個體要有與父個體進行競爭的機會，當父個體比新個體優(yōu)時，按一定的概率保留父個體而舍去新個體。

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