人工智能基礎(chǔ)及應(yīng)用 課件 第3、4章 搜索策略、機(jī)器學(xué)習(xí)

人工智能基礎(chǔ)及應(yīng)用

第3章

搜索策略3.1圖搜索策略3.2盲目的圖搜索策略3.2.1深度優(yōu)先搜索（DFS）

3.2.2寬度優(yōu)先搜索（BFS）3.3啟發(fā)式圖搜索策略3.3.1ASearch，即最佳優(yōu)先搜索3.3.2A*Search3.4

局部搜索：爬山法、模擬退火法、遺傳算法2本章學(xué)習(xí)目標(biāo)理解搜索的基本概念。掌握盲目搜索算法：深度優(yōu)先搜索和寬度優(yōu)先搜索。掌握啟發(fā)式搜索算法：A搜索和A*搜索。掌握局部搜索算法：爬山法、模擬退火法和遺傳算法。3

第3章搜索策略4在求解許多問題時都采用試探的搜索方法，搜索就是一個不斷嘗試和探索的過程。當(dāng)我們終于找到了一種解決辦法，又會想：這個方案是不是最優(yōu)方案。若不是，怎樣才能找到最優(yōu)方案?如何用計算機(jī)代替人類完成這樣的搜索？為模擬這些試探性的問題求解過程而發(fā)展的一種技術(shù)，就稱為搜索技術(shù)。搜索技術(shù)是人工智能中的一個核心技術(shù)，它直接關(guān)系到智能系統(tǒng)的性能和運行效率。以狀態(tài)空間表示法描述問題空間，已知初始狀態(tài)和目標(biāo)狀態(tài)，搜索問題就是求解一個操作序列使得智能體能從初始狀態(tài)轉(zhuǎn)移到目標(biāo)狀態(tài)。

搜索問題的主要任務(wù)是找到正確的搜索策略。

搜索策略是指在搜索過程中確定擴(kuò)展?fàn)顟B(tài)順序的規(guī)則。

所求得的從初始狀態(tài)轉(zhuǎn)移到目標(biāo)狀態(tài)的一個操作序列就是問題的一個解，若某操作序列可以使總代價最低，則該方案稱為最優(yōu)解。3.1圖搜索策略很多搜索問題都可以轉(zhuǎn)化為圖搜索問題，即在圖結(jié)構(gòu)中搜索該問題的解決方案。為了進(jìn)行搜索，首先需要采用某種形式表示所要求解的問題，表示方法是否適當(dāng)，將直接影響搜索效率。一般常用狀態(tài)空間表示法描述所求解的問題空間。然后在狀態(tài)空間中搜索，以求得一個從初始狀態(tài)到目標(biāo)狀態(tài)的操作算子序列，即問題的解。對于一個確定的問題，與求解有關(guān)的狀態(tài)空間往往只是整個狀態(tài)空間的一部分，只要能生成并存儲這部分狀態(tài)空間，就可求得問題的解。在狀態(tài)空間圖中，求解一個問題就是從初始狀態(tài)出發(fā)，不斷運用可使用的操作，在滿足約束的條件下達(dá)到目標(biāo)狀態(tài)，故搜索技術(shù)又稱為“狀態(tài)圖搜索”方法。53.1圖搜索策略通過圖搜索求解問題的基本過程如下：（1） 采用狀態(tài)空間表示法描述所有狀態(tài)，并給出問題的初始狀態(tài)和目標(biāo)狀態(tài)。（2）規(guī)定一組操作（算子），每個操作（算子）都能夠?qū)⒁粋€狀態(tài)轉(zhuǎn)換到另一個狀態(tài)。（3）選擇一種搜索策略，用于遍歷或搜索該問題的狀態(tài)圖空間。（4）將問題的初始狀態(tài)（即初始節(jié)點）作為當(dāng)前狀態(tài)。（5）按已確定的搜索策略選擇適用的操作（算子），對當(dāng)前狀態(tài)進(jìn)行操作，生成一組后繼狀態(tài)（或稱為后繼節(jié)點、子節(jié)點）。（6）檢查新生成的后繼狀態(tài)中是否包含目標(biāo)狀態(tài)。若包含，則搜索到了問題的解，從初始狀態(tài)到達(dá)達(dá)目標(biāo)狀態(tài)的操作序列即為解，算法結(jié)束；若不包含，則按已確定的搜索策略，從已生成的狀態(tài)中選擇一個狀態(tài)作為當(dāng)前狀態(tài)，若已無可操作的狀態(tài)，則未搜索到解，算法結(jié)束。（7）返回至第（5）步。63.1圖搜索策略在實現(xiàn)圖搜索的算法中，需建立兩個數(shù)據(jù)結(jié)構(gòu)：OPEN表和CLOSED表。OPEN表用于存放待擴(kuò)展的節(jié)點，CLOSED表用于存放已擴(kuò)展的節(jié)點。所謂擴(kuò)展節(jié)點，是指用合適的操作（算子）對該節(jié)點進(jìn)行操作，生成一組后繼節(jié)點。一個節(jié)點經(jīng)過一個算子操作后，一般只生成一個后繼節(jié)點，但對于一個節(jié)點，適用的算子可能有多個，故此時會生成一組后繼節(jié)點。需要注意的是：在這些后繼節(jié)點中，可能包含當(dāng)前擴(kuò)展節(jié)點的父節(jié)點、祖父節(jié)點，則這些祖先節(jié)點不能作為當(dāng)前擴(kuò)展節(jié)點的子節(jié)點。圖搜索不允許重復(fù)訪問節(jié)點，即OPEN表和CLOSED表的交集為空。圖搜索策略就是選擇下一個被擴(kuò)展節(jié)點的規(guī)則。78基于狀態(tài)空間圖的搜索算法的步驟G=G0(G0=s),OPEN:=(s);//G是生成的搜索圖，OPEN表用來存儲待擴(kuò)展的節(jié)點，每次循環(huán)從OPEN表中取出一個節(jié)點加以擴(kuò)展，并把新生成的節(jié)點加入OPEN表；2.CLOSED:=();//CLOSED表用來存儲已擴(kuò)展的節(jié)點，其用途是檢查新生成的節(jié)點是否已被擴(kuò)展過。//圖搜索不允許重復(fù)訪問節(jié)點，即OPEN表∩CLOSED表=?.3.LOOP:IFOPEN=()THENEXIT(FAIL);4.n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);//將n從OPEN中刪除，加入CLOSED中，即將n歸入已被擴(kuò)展的節(jié)點5.IFGOAL(n)THENEXIT(SUCCESS);96.EXPAND(n)→{mi},G:=ADD(mi,G);//擴(kuò)展節(jié)點n，建立集合{mi},使其包含n的后繼節(jié)點，而不包含n的祖先，并將這些后繼節(jié)點加入G中。注：n的后繼節(jié)點有三類：{mi}={mj}∪

{mk}∪

{ml},（1）n的后繼節(jié)點mj

既不包含于OPEN，也不包含于CLOSED；（2）n的后繼節(jié)點mk包含在OPEN中；（3）n的后繼節(jié)點ml包含在CLOSED中；n的后繼節(jié)點集合{mi}OPENCLOSED{mj}{mk}{ml}107.Forallnodesin{mi};

//對{mi}中所有節(jié)點，標(biāo)記和修改其前驅(qū)指針：(1)ADD(mj,OPEN）,并令mj的前驅(qū)指針指向n

；(2)判斷是否需要修改

mk

或

ml

的前驅(qū)指針（都已有前驅(qū)），使其指向指向n；(3)判斷是否需要修改

ml

后繼節(jié)點的前驅(qū)指針，使其指向ml本身；8.按某種搜索策略對OPEN中的節(jié)點重新排序；9.GOLOOP（語句3）；n的后繼節(jié)點集合{mi}OPENCLOSED{mj}{mk}{ml}兩種方式的搜索策略（1）在不具備任何與給定問題有關(guān)的知識或信息的情況下，系統(tǒng)按照某種固定的規(guī)則依次或隨機(jī)地調(diào)用操作算子，這種搜索方法稱為盲目搜索策略（BlindSearchStrategy），又稱為無信息引導(dǎo)的搜索策略（UninformedSearchStrategy）；（2）可應(yīng)用與給定問題有關(guān)的領(lǐng)域知識，動態(tài)地優(yōu)先選擇當(dāng)前最合適的操作算子，這種搜索方法稱為啟發(fā)式搜索策略（HeuristicSearchStrategy）或有信息引導(dǎo)的搜索策略（InformedSearchStrategy）。11不同搜索策略的搜索性能也不同。搜索策略性能的評價標(biāo)準(zhǔn)完備性當(dāng)問題有解時，保證能找到一個解，具有完備性。當(dāng)問題有解，卻找不到，就不具有完備性。最優(yōu)性當(dāng)問題有最優(yōu)解時，保證能找到最優(yōu)解（最小損耗路徑），具有最優(yōu)性。當(dāng)問題有最優(yōu)解，但找不到，找到的只是次優(yōu)解，則不具有最優(yōu)性。123.2盲目的圖搜索策略13常用的兩種盲目搜索方法：

（1）深度優(yōu)先搜索（Depth-firstsearch，DFS）

（2）寬度優(yōu)先搜索（Breadth-firstsearch，BFS）

盲目搜索也被稱為無信息搜索、通用搜索。在盲目搜索的過程中，沒有任何與問題有關(guān)的先驗知識或者啟發(fā)信息可以利用，算法只能判斷當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)，而無法比較兩個非目標(biāo)狀態(tài)的好壞。（1）深度優(yōu)先搜索DFS深度優(yōu)先搜索(Depth-firstSearchAlgorithm)是從圖搜索算法變化來的。深度優(yōu)先搜索的基本思想是優(yōu)先擴(kuò)展當(dāng)前深度最深的節(jié)點，是樹的先根遍歷。在一個圖中，初始節(jié)點的深度定義為0，其他節(jié)點的深度定義為其父節(jié)點的深度加1。140123（1）深度優(yōu)先搜索DFSDFS總是選擇深度最深的節(jié)點進(jìn)行擴(kuò)展，若有多個相同深度的節(jié)點，則按照指定的規(guī)則從中選擇一個；若該節(jié)點沒有子節(jié)點，則選擇一個除了該節(jié)點之外的深度最深的節(jié)點進(jìn)行擴(kuò)展。以此類推，直到找到問題的解為止；或者直到找不到可擴(kuò)展的節(jié)點，結(jié)束搜索，此種情況說明沒有找到問題的解。15（1）深度優(yōu)先搜索DFSDFS是將OPEN表中的節(jié)點按搜索樹中節(jié)點深度的降序排序，深度最大的節(jié)點排在棧頂，深度相同的節(jié)點可以任意排列。DFS總是擴(kuò)展搜索樹中當(dāng)前OPEN表中最深的節(jié)點（即棧頂元素）。搜索很快推進(jìn)到搜索樹的最深層，那里的節(jié)點沒有后繼。當(dāng)那些節(jié)點被擴(kuò)展完之后，就從表OPEN中去掉（出棧），然后搜索算法回溯到下一個還有未擴(kuò)展后繼的深度稍淺的節(jié)點。16DFS的實現(xiàn)方法使用LIFO(Last-InFirst-Out)的棧存儲OPEN表，把后繼節(jié)點放在棧頂。DFS：類似于樹的先根遍歷17DFS訪問的順序：即擴(kuò)展順序，為

{A,B,D,H,I,E,J,K,C,F,L,M,G,N,O}.DFS算法18深度優(yōu)先搜索算法的過程如下：（1）將初始節(jié)點S放入OPEN表的棧頂；（2）若OPEN表為空，表示再也沒有可擴(kuò)展的節(jié)點，即未能找到問題的解，則算法結(jié)束；（3）將OPEN表的棧頂元素（記為節(jié)點n）取出，放入CLOSED表中；（4）若節(jié)點n是目標(biāo)節(jié)點，則已求得問題的解，算法結(jié)束；（5）若節(jié)點n不可擴(kuò)展，即n沒有后繼節(jié)點，則轉(zhuǎn)至步驟（2）；（6）擴(kuò)展節(jié)點n，將其所有未被訪問過的子節(jié)點依次放入OPEN表的棧頂，并將這些子節(jié)點的前驅(qū)指針設(shè)為指向父節(jié)點n，然后轉(zhuǎn)至步驟（2）。19深度優(yōu)先搜索的性質(zhì)若狀態(tài)空間有限，DFS是完備的，因為它最多擴(kuò)展所有節(jié)點，直到找到一個解。但在無限狀態(tài)空間中，若沿著一個“錯誤”的路徑搜索下去而陷入“深淵”，則會導(dǎo)致無法到達(dá)目標(biāo)節(jié)點，在這種情況下，DFS是不完備的。為避免此情況發(fā)生，在DFS中往往會加上一個深度限制，稱為深度受限的深度優(yōu)先搜索，即若一個節(jié)點的深度達(dá)到了事先指定的深度閾值k，強(qiáng)制進(jìn)行回溯，選擇一個比它淺的節(jié)點進(jìn)行擴(kuò)展，而不是沿著當(dāng)前節(jié)點繼續(xù)擴(kuò)展。當(dāng)深度限制過深時，會陷入“深淵”，求解效率低，未必會找到最優(yōu)解；

若深度限制過淺，可能找不到解，即不完備。所以，應(yīng)該根據(jù)具體問題合理地設(shè)定深度限制值，或在搜索過程中逐步加大深度限制值，反復(fù)搜索，直到找到解。DFS不一定是完備的，也未必能找到最優(yōu)解。最壞情況時，DFS的搜索空間等同于窮舉。DFS是一個通用的、與問題無關(guān)的方法。DFS無法避免冗余路徑，不具有最優(yōu)性。20圖3.2采用深度限制為4的深度優(yōu)先搜索算法求解八數(shù)碼問題的搜索圖（2）寬度優(yōu)先搜索BFS寬度優(yōu)先搜索也稱為廣度優(yōu)先搜索?；舅枷胧牵簝?yōu)先擴(kuò)展深度最淺的節(jié)點。先擴(kuò)展根節(jié)點，再擴(kuò)展根節(jié)點的所有后繼，然后再擴(kuò)展它們的后繼，依此類推。如果有多個節(jié)點深度是相同的，則按照事先約定的規(guī)則，從深度最淺的幾個節(jié)點中選擇一個，進(jìn)行擴(kuò)展。一般地，在下一層的任何節(jié)點擴(kuò)展之前，搜索樹上本層深度的所有節(jié)點都應(yīng)該已經(jīng)擴(kuò)展過。21寬度優(yōu)先搜索：類似于樹的層次遍歷22BFS訪問的順序：即擴(kuò)展順序，為{A,B,C,D,E,F,G}.寬度優(yōu)先搜索的實現(xiàn)方法采用FIFO(First-InFirst-Out)的隊列存儲OPEN表。BFS是將OPEN表中的節(jié)點按搜索樹中節(jié)點深度的增序排序，深度最淺的節(jié)點排在最前面（隊頭），深度相同的節(jié)點可以任意排列。新節(jié)點（深度比其父節(jié)點深）總是加入到隊尾，深度相同的節(jié)點可按某種事先約定的規(guī)則排列，這意味著淺層的老節(jié)點會在深層的新節(jié)點之前被擴(kuò)展。23BFS算法24寬度優(yōu)先搜索算法的過程如下：（1）將初始節(jié)點S放入OPEN表的隊頭；（2）若OPEN表為空，表示再也沒有可擴(kuò)展的節(jié)點，即未能找到問題的解，則算法結(jié)束；（3）將OPEN表的隊頭元素（記為節(jié)點n）取出，放入CLOSED表中；（4）若節(jié)點n是目標(biāo)節(jié)點，則已求得問題的解，算法結(jié)束；（5）若節(jié)點n不可擴(kuò)展，即n沒有后繼節(jié)點，則轉(zhuǎn)至步驟（2）。（6）擴(kuò)展節(jié)點n，將其所有未被訪問過的子節(jié)點依次放入OPEN表的隊尾，并將這些子節(jié)點的前驅(qū)指針設(shè)為指向父節(jié)點n，然后轉(zhuǎn)至步驟（2）。采用寬度優(yōu)先搜索算法求解八數(shù)碼問題的搜索圖2526寬度優(yōu)先搜索的性質(zhì)BFS是完備的（complete），即當(dāng)問題有解時，一定能找到解。若路徑代價是節(jié)點深度的非遞減函數(shù)，或者每步代價都相等，則寬度優(yōu)先搜索一定能找到最優(yōu)解，即BFS具有最優(yōu)性。BFS是一個通用的、與問題無關(guān)的方法.缺點：求解問題的效率較低。BFS與DFS的比較DFS總是首先擴(kuò)展最深的未擴(kuò)展節(jié)點；BFS總是首先擴(kuò)展最淺的未擴(kuò)展節(jié)點。BFS是完備的，且是最優(yōu)的；DFS既不完備，也不最優(yōu)。DFS節(jié)省大量時間和空間。BFS需占用較大的存儲空間。在不要求求解速度且目標(biāo)節(jié)點的層次較深的情況下,BFS優(yōu)于DFS,因為BFS一定能求得問題的解，而DFS在一個擴(kuò)展得很深但又沒有解的分支上進(jìn)行搜索，是一種無效搜索,降低了求解的效率,有時甚至不一定能找到問題的解；在要求求解速度且目標(biāo)節(jié)點的層次較淺的情況下,DFS優(yōu)于BFS。因為DFS可快速深入較淺的分支，找到解。27盲目搜索的特點盲目搜索策略采用“固定”的搜索模式，不針對具體問題。優(yōu)點：適用性強(qiáng)，幾乎所有問題都能通過深度優(yōu)先或者寬度優(yōu)先搜索來求得全局最優(yōu)解。缺點：搜索范圍比較大，效率比較低在許多不太復(fù)雜的情況下，使用盲目搜索策略也能夠取得很好的效果。283.3啟發(fā)式圖搜索策略盲目搜索策略在搜索過程中，僅采用固定搜索模式，不針對具體問題。沒有利用所求解問題的任何先驗信息，既不對待擴(kuò)展的狀態(tài)的優(yōu)劣進(jìn)行判斷，也不考慮所求的解是否為最優(yōu)解。但很多時候我們?nèi)祟悓蓚€狀態(tài)的優(yōu)劣是有判斷的。29VSB.錯位3個A.錯位6個人解決問題的“啟發(fā)性”：對兩個可能的狀態(tài)A和B，選擇“從目前狀態(tài)到最終狀態(tài)”更好的一個作為搜索方向。盲目搜索策略會導(dǎo)致所需擴(kuò)展的節(jié)點數(shù)很多，產(chǎn)生很多無用節(jié)點，搜索效率較低。30圖3.4八數(shù)碼問題中節(jié)點⑤比節(jié)點①的狀態(tài)好如何高效率地搜索？啟發(fā)式搜索將人解決問題的“知識”告訴機(jī)器，使得搜索算法能夠利用啟發(fā)式信息，更“聰明”地進(jìn)行搜索，盡可能地縮小搜索范圍，減少試探的次數(shù)，提高搜索效率，避免大海撈針。啟發(fā)式搜索策略的基本思想：在搜索過程中利用與所求解問題有關(guān)的特征信息，指導(dǎo)搜索向最有希望到達(dá)目標(biāo)節(jié)點的方向前進(jìn)。啟發(fā)式搜索的每一步都選擇最優(yōu)的操作，以最快速度找到問題的解。為了盡快找到從初始節(jié)點到目標(biāo)節(jié)點的一條代價比較小的路徑，在搜索的每一步，我們都希望選擇在最佳路徑（即代價最小的路徑）上的節(jié)點進(jìn)行擴(kuò)展。31評價函數(shù)（evaluationfunction）如何評價一個節(jié)點在最佳路徑上的可能性呢?我們采用評價函數(shù)來進(jìn)行估計:32f(n)=g(n)+h(n).其中，n為當(dāng)前節(jié)點，即待評價節(jié)點。f(n)

是從初始節(jié)點s出發(fā)、經(jīng)過節(jié)點n、到達(dá)目標(biāo)節(jié)點的最佳路徑代價值的估計值.(1)g(n)為從初始節(jié)點到節(jié)點n的最佳路徑代價值的實際值；(2)h(n)

為從節(jié)點n到目標(biāo)節(jié)點的最佳路徑代價值的估計值，稱為啟發(fā)式函數(shù)33評價函數(shù)f(n)=g(n)+h(n)h(n)g(n)f(n)g(n)：為從初始狀態(tài)S到達(dá)節(jié)點n的最佳路徑上代價的實際值h(n)

：從節(jié)點n到目標(biāo)狀態(tài)E的最佳路徑上代價的估計值，稱為啟發(fā)函數(shù)。f(n)

為從初始狀態(tài)S經(jīng)過節(jié)點n到達(dá)目標(biāo)狀態(tài)E的最佳路徑上代價的估計值，稱為評價函數(shù)。nSE常用的啟發(fā)式搜索算法3.3.1ASearch

（亦稱為最佳優(yōu)先搜索，Best-firstSearch）3.3.2A*Search

（亦稱為最佳圖搜索算法）343.3.1A搜索算法A搜索又稱為最佳優(yōu)先搜索（Best-FirstSearch），是一種貪心算法。核心思想是：每一步都選擇距離目標(biāo)最近的節(jié)點進(jìn)行擴(kuò)展。搜索策略：選擇評價函數(shù)f(n)值最低的節(jié)點作為下一個將要被擴(kuò)展的節(jié)點。實現(xiàn)方法A搜索采用隊列存放OPEN表，其中所有節(jié)點按照評價函數(shù)f值進(jìn)行升序排列，最佳節(jié)點排在最前面，因此稱為“最佳優(yōu)先搜索”。35評價函數(shù)的情況f(n)=g(n)+h(n)Iff(n)=g(n),i.e.

h(n)=0時，A搜索退化為盲目搜索；Iff(n)=g(n)=d(n)，即n的深度,則為

BFS(盲目搜索).Iff(n)=h(n),即g(n)=0，稱為貪婪最佳優(yōu)先搜索，簡稱貪婪搜索.

36貪婪最佳優(yōu)先搜索的搜索策略：在每一步，它總是優(yōu)先擴(kuò)展與目標(biāo)最接近的節(jié)點。貪婪搜索策略不考慮整體最優(yōu)，僅求取局部最優(yōu)。貪婪搜索是不完備的，也不具有最優(yōu)性，但其搜索速度非常快。37用A算法解決八數(shù)碼問題首先，需要設(shè)計評價函數(shù)：f(n)=g(n)+h(n)，令：

g(n)為移動數(shù)碼牌的步數(shù)，即節(jié)點n的深度.

h(n)為當(dāng)前狀態(tài)中“錯位數(shù)碼牌”的個數(shù)。12384765(a)初始狀態(tài)s

(b)目標(biāo)狀態(tài)g(s)=0,

h(s)=3832147

65832147

65例3.338圖3.6采用A算法解決八數(shù)碼問題示例3.3.2A*搜索算法A搜索算法沒有對啟發(fā)函數(shù)h(n)做任何限制。實際上，啟發(fā)函數(shù)對于搜索過程十分重要的，如果選擇不當(dāng)，則有可能找不到問題的解（A搜索不完備），或者找到的不是問題的最優(yōu)解（A搜索不具有最優(yōu)性）。如果f(n)=g(n)+0，此時啟發(fā)函數(shù)為0，退化為盲目搜索。如果在f中添加“一點點”啟發(fā)，搜索效率就會提高；如果啟發(fā)函數(shù)h(n)過大，會忽略g(n)，導(dǎo)致脫離實際情況，反而不能保證總能找到最優(yōu)解了。因此需要對啟發(fā)函數(shù)加以限制，這就是本節(jié)要介紹的A*搜索算法。40A*算法h*(n)定義為從當(dāng)前狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑上的實際代價，即最小代價。若啟發(fā)函數(shù)h(n)滿足如下條件：h(n)

≤h*(n)則可以證明當(dāng)問題有解時，A算法一定能找到一個代價值最小的解，即最優(yōu)解。滿足該條件的A算法稱作A*算法。A*搜索是最佳優(yōu)先搜索的最廣為人知的形式，也稱為最佳圖搜索算法。如何判斷h(n)≤h*(n)是否成立一般來說，h*(n)

是未知的，那么如何判斷h(n)≤h*(n)是否成立呢?這就要根據(jù)具體問題具體分析了。例如，所求問題是在地圖上找到一條從地點A到地點B的距離最短的路徑，可以采用當(dāng)前節(jié)點到目標(biāo)節(jié)點的歐氏距離作為啟發(fā)函數(shù)h(n)。雖然不知道h*(n)是什么，但由于兩點間直線距離最近，所以無論怎樣定義h*(n)，肯定有h(n)≤h*(n)。只要滿足此限定條件，就可以用A*算法找到該問題的一條最優(yōu)路徑。41可證明：若問題有解，則利用A*算法一定能找到一個代價值最小的解，即最優(yōu)解。因此，A*算法比A算法好。A*算法與A算法沒有本質(zhì)區(qū)別，只是規(guī)定了啟發(fā)函數(shù)的上限，A搜索既不是完備，也不是最優(yōu)的。A*搜索既是完備的，也是最優(yōu)的。42用

A*算法解決八數(shù)碼問題要用A*算法解決八數(shù)碼問題，需要一個啟發(fā)式函數(shù)，通常有兩個候選的啟發(fā)式函數(shù)。h1(n)=“錯位數(shù)碼牌”的個數(shù)

h2(n)=所有數(shù)碼牌與其目標(biāo)位置之間的曼哈頓距離之和。h3(n)=h2(n)+顛倒兩張相鄰牌的固定步數(shù)Distance：“1”：1“2”：1“8”：212384765

目標(biāo)狀態(tài)2

8

31

4765

h2(s)=4初始狀態(tài)

s

h1(s)=3h*(n)的意義是：“把當(dāng)前錯位的數(shù)碼牌移動到正確的位置上所需要的最小步數(shù)”?？梢宰C明：以上3個啟發(fā)函數(shù)均滿足：h(n)≤h*(n)，均為A*算法。采用啟發(fā)函數(shù)h1(n)，證明A算法為A*算法令

d(n)=已移動數(shù)碼牌的步數(shù)，即節(jié)點n在搜索樹中的深度

w(n)=節(jié)點n所表示的狀態(tài)中“錯位數(shù)碼牌”的個數(shù)將w(n)個“錯位”的數(shù)碼牌放在其各自的目標(biāo)位置上，至少需要移動w(n)步。h*(n)是節(jié)點n從當(dāng)前狀態(tài)移動到目標(biāo)狀態(tài)的最少需要的實際步數(shù)，

顯然w(n)

≤h*(n)以w(n)作為啟發(fā)式函數(shù)h(n)，可以滿足對h(n)

的上界的要求，

即有h(n)=

w(n)≤h*(n).因此，當(dāng)選擇w(n)作為啟發(fā)式函數(shù)解決八數(shù)碼問題時，A算法就是A*算法。43思考題：采用啟發(fā)函數(shù)h2(n)，證明A算法為

A*算法。4412384765

(a)goalstate(b)12384765

(a)goalstate(b)(a)為目標(biāo)狀態(tài),分別計算圖（b）中的h1andh2g=2,f=6h1=4,h2=4g=1h1=3，h2=512384765

(a)goalstate(b)g=1,f=4h1=3,h2=3h1(n)=“錯位數(shù)碼牌”的個數(shù)h2(n)=所有數(shù)碼牌與其目標(biāo)位置之間的曼哈頓距離之和。4512384765

goalstateg=0,h=4,f=4g=1,h=5,f=6g=1,h=5,f=6g=4,h=0,f=4g=4,h=2,f=6g=3,h=1,f=4g=2,h=2,f=4g=2,h=4,f=6g=1,h=5,f=6g=1,h=3,f=4

h(n)=所有數(shù)碼牌與其目標(biāo)位置之間的曼哈頓距離之和經(jīng)過4步，找到最優(yōu)解，cost=4例：用A*算法解決“修道士與野人渡河”問題在河的左岸有K個傳教士、K個野人和1條船，傳教士們想用這條船將所有成員都從河左岸運到河右岸去，但有下面條件和限制：(1)所有傳教士和野人都會劃船。(2)船的容量為r，即一次最多運送r個人過河。(3)任何時刻，在河的兩岸以及船上的野人數(shù)目不能超過傳教士的數(shù)目，否則野人將吃掉傳教士。(4)允許在河的某一岸或船上只有野人而沒有傳教士。(5)野人會服從傳教士的任何過河安排。請采用A*算法搜索出一個確保全部成員安全過河的合理方案。46用A*算法解決“修道士與野人渡河”問題Step1設(shè)計狀態(tài)空間表示，采用三元組形式表示一個狀態(tài)，令S=(m,c,b)，其中：47左岸右岸m為未過河的傳教士人數(shù)，m∈[0,K]，已過河的傳教士人數(shù)為K－m。c為未過河的野人數(shù)，c∈[0,K]，已過河的野人數(shù)為K－c。b為未過河的船數(shù)，b∈[0,1]，已過河的船數(shù)為1－b。初始狀態(tài)為S0=（K，K，1），表示全部成員及船都在河的左岸，目標(biāo)狀態(tài)為Sg=（0,0,0），表示全部成員及船都已到達(dá)了河右岸。用A*算法解決“修道士與野人渡河”問題Step2設(shè)計操作集合，即過河操作。設(shè)計兩類操作算子：Lij操作表示將船從左岸劃向右岸，第一下標(biāo)i表示船載的傳教士人數(shù)，第二下標(biāo)j表示船載的野人數(shù)；Rij操作表示將船從右岸劃回左岸，下標(biāo)的定義同前。這兩類操作需滿足如下限制：(1)1≤i+j≤r；(2)i≠0時，i≥j。假設(shè)K=5，r=3，則合理的操作共有16種，其中船從左岸到右岸的操作有：L01、L02、L03、L10、L11、L20、L21、L30；船從右岸到左岸的操作有：R01、R02、R03、R10、R11、R20、R21、R30。48用A*算法解決“修道士與野人”問題Step3

設(shè)計滿足A*算法的啟發(fā)函數(shù)在初始狀態(tài)(5,5,1)下，若不考慮限制(3)--野人吃人，則至少要操作9次（初始時，船與人在河同側(cè)，每次運3人過去，然后1人回來，重復(fù)4.5個來回）相當(dāng)于：1個人固定作為船夫,每擺渡一次,只運1個人過河（即往返一趟，運送2人過河）。4910人0人初始狀態(tài)：3人0人7人擺渡1：1人2人7人擺渡2：河3人2人5人擺渡3：3人4人3人擺渡5：1人4人5人擺渡4：1人6人3人擺渡6：3人6人1人擺渡7：1人8人1人擺渡8：2人8人0人擺渡9：用A*算法解決“修道士與野人”問題Step3設(shè)計滿足A*算法的啟發(fā)函數(shù)是否可以令h(x)=m+c？稍分析就可以發(fā)現(xiàn)，不可以，因為h(x)=m+c不滿足h(x)≤h*(x)。如:對狀態(tài)x=(1,1,1)，h(x)=m+c=2，而此時最短路徑上的代價h*(x)=1，即只需1步就可完成。按要求，應(yīng)該：h(n)≤

h*(n)但此刻，h*(x)=1<h(x)=2，不滿足A*算法的條件，實際上：h*(x)應(yīng)該有一個上限：h*(x)≤m+c，即過河次數(shù)不高于2K次，因為一共才2K個人，擺渡次數(shù)不可能超過2K次，取h*(n)=m+c。50用A*算法解決“修道士與野人”問題Step3

設(shè)計滿足A*算法的啟發(fā)函數(shù)分情況討論（r=3）：假設(shè)船與人同在左岸，b=1（船未過河），狀態(tài)為(m,c,1)。不考慮“野人會吃人”的約束條件，當(dāng)最后一次恰好3人同船過河時，效率最高，單獨算1次擺渡。

剩下m+c-3個人運過河，需要運送故：一共需要運送/擺渡m+c-3+1=m+c-2次（單向擺渡次數(shù)）。51用A*算法解決“修道士與野人”問題Step3

設(shè)計滿足A*算法的啟發(fā)函數(shù)分情況討論：假設(shè)船在右岸，即船與人在河的不同側(cè)，b=0，初始狀態(tài)為(m,c,0)。則首先需要額外有1個人把船劃從右岸劃回左岸，消耗1次，同時左岸人數(shù)增多1，即總?cè)藬?shù)變?yōu)椋?/p>

m+c+1轉(zhuǎn)變成第一種情況，即：(m+c,0)?(m+c+1,1)第一種情況的初始狀態(tài)為（m+c,1），一共需要運送

m+c-2次現(xiàn)在，用m+c+1代替上式中的m+c，則一共需要運送

m+c-1次再加上最開始“消耗1次”，則第二種情況共需要運送(m+c-1)+1=m+c次。52Step3

設(shè)計滿足A*算法的啟發(fā)函數(shù)兩種情況結(jié)合，得到：可寫作：此時，h(n)=m+c-2b≤h*(n)=m+c，滿足A*算法的條件。用A*算法解決“修道士與野人”問題53

圖3.7采用A*算法解決傳教士與野人渡河問題示例543.4局部搜索算法55前面介紹的搜索算法都在內(nèi)存中保留一條或多條路徑，記錄路徑中在每個節(jié)點處的擴(kuò)展選擇。。當(dāng)找到目標(biāo)時，從初始節(jié)點到達(dá)此目標(biāo)的路徑就是這個問題的一個解。但在許多問題中，人們并不關(guān)注到達(dá)目標(biāo)的路徑。例如，在八皇后問題中，重要的是最終皇后在棋盤上的布局，而不是擺放皇后的先后次序。許多重要的應(yīng)用都具有這樣的性質(zhì)，例如集成電路設(shè)計、工廠場地布局等。因此，考慮另外一類算法，它不關(guān)心從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的路徑，只對一個（當(dāng)前狀態(tài)）或多個（鄰近）狀態(tài)進(jìn)行評價和修改，稱為局部搜索算法。局部搜索算法適用于那些只關(guān)注解狀態(tài)而不關(guān)注路徑代價的問題，該類算法從單個當(dāng)前節(jié)點（而不是多條路徑）出發(fā)，通常只移動到它的鄰近狀態(tài)。一般情況下，不保留搜索路徑。局部搜索算法：爬山法模擬煺火法遺傳算法56局部搜索局部搜索的基本思想：在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。目標(biāo)可以是最大值，也可以是最小值局部搜索算法有如下兩個主要優(yōu)點：

使用很少的內(nèi)存；在大的或無限（連續(xù)）狀態(tài)空間中，能發(fā)現(xiàn)合理的解。3.4.1爬山法爬山法是最基本的局部搜索技術(shù)。最陡上升版的爬山法是簡單的循環(huán)過程，在每個狀態(tài)，都不斷向值增加的方向持續(xù)移動，即登高。爬山法的過程如下：算法從指定的初始狀態(tài)開始，或任意選擇問題的一個初始狀態(tài)。然后，在每一步，爬山法都將當(dāng)前狀態(tài)n與周圍相鄰節(jié)點的值進(jìn)行比較，若當(dāng)前節(jié)點值最大，則返回當(dāng)前節(jié)點，作為最大值，即山峰最高點；否則，從n的所有相鄰狀態(tài)中找到n的最佳鄰接節(jié)點，用以代替節(jié)點n，成為新的當(dāng)前狀態(tài)（此處，最佳鄰接節(jié)點是啟發(fā)函數(shù)h值最低的相鄰節(jié)點）。重復(fù)上述過程，直到找到目標(biāo)為止；或者無法找到進(jìn)一步改善的狀態(tài)，算法結(jié)束。573.4.1爬山法在爬山法中，當(dāng)前節(jié)點都會被它的最佳鄰接節(jié)點所代替。爬山法不保存搜索樹，當(dāng)前節(jié)點的數(shù)據(jù)結(jié)構(gòu)只記錄當(dāng)前狀態(tài)和目標(biāo)函數(shù)值。爬山法有時被稱為貪婪局部搜索，因為它不考慮與當(dāng)前狀態(tài)不相鄰的狀態(tài)，總是在相鄰節(jié)點（局部范圍內(nèi)）中選擇狀態(tài)最好的一個，也不考慮這個最好狀態(tài)是否是全局最優(yōu)的。爬山法往往很有效，它能很快地朝著解（目標(biāo)狀態(tài)）的方向進(jìn)展，因為它可以很容易地改善一個不良狀態(tài)。58爬山法59如果把山頂作為目標(biāo)，h(n)表示當(dāng)前位置n與山頂之間的高度差，則該算法相當(dāng)于總是登向山頂。在單峰的條件下，必能到達(dá)山頂。爬山法的三種困境（1）在多個山峰的情況下，爬山法經(jīng)常會陷入如下三種困境：（1）局部最大值：是指一個比所有相鄰狀態(tài)值都要高、但卻比全局最大值要小的狀態(tài)。爬山法到達(dá)局部極大值附近，就會被拉向峰頂，然后就卡在局部極大值處，無處可走。（2）高原：是一塊平原區(qū)域，是平的局部極大值，不存在上山的出口；或者是山肩，從山肩還有可能取得進(jìn)展（見圖3.8）。爬山法在高原處可能會迷路。爬山法的三種困境（2）（3）山脊：是由一系列局部極大值構(gòu)成的，形成了一個不直接相連的局部極大值序列。在這樣的情況下非常難爬行。61為什么山脊會使爬山法困難？圖中的狀態(tài)（黑色圓點）疊加在從左到右上升的山脊上。從每個局部極大點出發(fā)，可能的行動都是指向下山方向的。搜索可能會在山脊的兩面來回震蕩，前進(jìn)步伐很小。采用爬山法解決n皇后問題將n個皇后放在n×

n的棋盤上。使得任意兩個皇后不能互相攻擊，即任意兩個皇后都不在同一行、同一列或同一斜線上。設(shè)任意兩個皇后的坐標(biāo)分別是（i，j）和（k，l），為使得任意兩個皇后不在同一行上，要求j≠l；為使得任意兩個皇后不在同一列上，要求i≠k，也可以規(guī)定在棋盤的每一列上只能放置一個皇后；任意兩個皇后在同一斜線上的充要條件是|i-k|=|j-l|，即兩個皇后的行號之差與列號之差的絕對值相等，則為使得任意兩皇后不在同一斜線上，只需要求|i-k|≠|(zhì)j-l|。62例：四皇后問題采用爬山法解決N皇后問題，首先需定義啟發(fā)函數(shù)，令

h(n)=相互攻擊的皇后對的數(shù)量該函數(shù)的全局最小值是h=0，即沒有任意兩個皇后是互相攻擊的，僅在找到解時，h值才會等于零。如果有多個最佳后繼，爬山算法通常會從一組最佳后繼中隨機(jī)選擇一個。63解采用爬山法解決n皇后問題的步驟假設(shè)在初始狀態(tài)中每列只擺放一個皇后。(1)針對當(dāng)前狀態(tài)，計算啟發(fā)函數(shù)h的值。(2)若h=0，即找到一個解，算法結(jié)束。否則，計算各個方格里的h值。(3)若無法找到比當(dāng)前狀態(tài)的h值更小的相鄰狀態(tài)，說明已陷入局部極值，找不到解，則算法結(jié)束。否則，從若干個小于當(dāng)前h值的最佳后繼中隨機(jī)挑選一個，將該列的皇后移到此位置，并轉(zhuǎn)到步驟(2)。64例：已知八皇后的一個狀態(tài)圖，計算其啟發(fā)函數(shù)h的值當(dāng)前狀態(tài)的啟發(fā)函數(shù)h=形成相互攻擊的皇后對的數(shù)量，h=17

每個方格中顯示的數(shù)字表示：將這一列中的皇后移到該方格后得到的后繼的h

值。當(dāng)前棋盤中最小的h值為12，一共有8個，均用粉色方框圈起來了，表示是最佳移動。如果有多個最佳移動，即多個最小值，爬山法會從中隨機(jī)選擇一個后繼進(jìn)行擴(kuò)展。=3對=6對C23C241對1對1對=31對C231對65例：八皇后問題的一個局部極小值八皇后問題狀態(tài)空間中的一個局部極小值：該狀態(tài)的h=l,但是它的每個后繼的h

值都比它高.此時，爬山法無法找到全局的最優(yōu)解（即h=0），即爬山法是不完備的。圖3.11八皇后問題陷入局部極小值的示例66爬山法67采用最陡上升版爬山法求解八皇后問題，從隨機(jī)生成的初始狀態(tài)開始搜索，有實驗證明：在86%的情況下會被卡住，只有14%的問題實例能求得解。算法求解速度快，成功找到解的平均步數(shù)是4步，被卡住的平均步數(shù)是3步。到現(xiàn)在為止，我們描述的爬山法是不完備的——它們經(jīng)常會在存在目標(biāo)的情況下，因為被局部極（大、小）值卡住而找不到目標(biāo)。隨機(jī)爬山法68隨機(jī)爬山法是最陡上升版爬山法的變種，是一種局部貪心的最優(yōu)算法。該算法的主要思想是：在向上移動的過程中，隨機(jī)地選擇下一步，每個狀態(tài)被選中的概率可能隨向上移動陡峭程度的不同而發(fā)生變化。與最陡上升算法相比，收斂速度通常較慢。隨機(jī)爬山法仍然不完備，還會被局部極大值卡住。隨機(jī)重啟爬山法69隨機(jī)重啟爬山法隨機(jī)生成一個初始狀態(tài)，開始搜索，執(zhí)行一系列這樣的爬山搜索，直到找到目標(biāo)為止；若找不到目標(biāo)，則再隨機(jī)生成一個初始狀態(tài)，開始新一輪搜索，……隨機(jī)重啟爬山法依然不完備，但以它能以逼近1的概率接近完備，因為它最終將生成一個目標(biāo)狀態(tài)作為初始狀態(tài)。如果每次爬山搜索成功的概率為p，則重啟需要的期望值是1/p，即成功的概率越高，需要重啟的概率越小。對于八皇后問題，隨機(jī)重啟爬山法實際上是有效的。即使有300萬個皇后，這個方法找到解的時間不超過1分鐘。爬山法成功與否嚴(yán)重依賴于狀態(tài)空間地形圖的形狀：如果在圖中幾乎沒有局部極大值和高原，隨機(jī)重啟爬山法會很快找到一個好的解。3.4.2模擬退火法爬山法搜索從來不“下山”，即不會向值比當(dāng)前節(jié)點低的（或代價高的）方向搜索，它肯定是不完備的，因為可能卡在局部極大值上。與之相反，純粹的隨機(jī)行走是從后繼集合中完全等概率地隨機(jī)選取后繼，即可能選擇向比當(dāng)前節(jié)點差的方向搜索。隨機(jī)行走法是完備的，但是效率極低。因此，將爬山法和隨機(jī)行走法以某種方式結(jié)合，希望兼顧高效率和完備性。模擬退火就是這樣的算法。70模擬退火法退火是借用冶金中的一個術(shù)語。模擬退火是一種逼近全局最優(yōu)解的概率方法，發(fā)表于1953年。模擬退火算法是允許“下山”的隨機(jī)爬山法?；舅悸罚涸谕嘶鸪跗冢跋律健保础白儔摹保┮苿尤菀妆徊杉{，以便擺脫局部極值；71隨時間推移，“下山”的次數(shù)越來越少，即逐漸減少向“壞”的方向移動的頻率。模擬退火法的本質(zhì)模擬退火法本質(zhì)上也是一種貪心算法，只不過是以一定的概率來接受更差的狀態(tài)，這種概率會隨著時間的推移變得越來越小；其優(yōu)點是可能會讓算法跳出局部最優(yōu)解，最終找到全局最優(yōu)解。72模擬退火算法的過程73模擬退火法模擬退火算法的內(nèi)層循環(huán)與爬山法類似，只是它不選擇最佳移動，而是進(jìn)行隨機(jī)移動。如果該移動能改善情況，則接受該移動；否則，算法以某個小于1的概率接受該（變壞的）移動。如果移動導(dǎo)致狀態(tài)“變壞”，接受概率會呈指數(shù)級下降——根據(jù)能量差值ΔE判斷。這個概率也隨“溫度”T的

降低而下降：開始T高的時候，可能允許“壞的”移動；當(dāng)T降低時，則不可能允許“壞的”移動。如果調(diào)度讓溫度T下降得足夠慢，算法找到全局最優(yōu)解的概率接近于1。采用模擬退火算法求解八皇后問題，關(guān)鍵是設(shè)計啟發(fā)函數(shù)。令啟發(fā)函數(shù)h(n)=相互攻擊的皇后對的數(shù)量

h(n)值越小，說明狀態(tài)越好。用h(n)代替ΔE計算公式中的Value即可。743.4.3

遺傳算法1960年代末，受達(dá)爾文“物競天擇，適者生存”進(jìn)化論思想的啟發(fā)，提出了模擬自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，通過模仿自然進(jìn)化過程來搜索復(fù)雜問題的最優(yōu)解，這就是求解優(yōu)化問題的遺傳算法。遺傳算法是一種啟發(fā)式隨機(jī)搜索算法，它通過數(shù)學(xué)的方式，利用計算機(jī)仿真運算，模仿生物遺傳和進(jìn)化過程中的染色體基因選擇、交叉、變異機(jī)理，來完成自適應(yīng)搜索問題最優(yōu)解的過程。在遺傳算法中,后繼節(jié)點是由兩個父輩狀態(tài)組合而成的，而不是對單一狀態(tài)修改而得到的。其處理過程是有性繁殖，而不是無性繁殖。遺傳算法借鑒生物進(jìn)化中“適者生存”的理論，定義了一些術(shù)語。753.4.3.1遺傳算法的基本概念（1）個體（Individual）：就是遺傳算法要處理的染色體（Chromosome），組成染色體的元素稱為基因。染色體中的每一位就是一個基因，基因的位置稱為基因座，基因的取值稱為等位基因。例如：11011為一個染色體或個體，每一位上的0或1表示基因。（2）種群（Population）：是由若干個個體（即染色體）組成的集合。一個種群中個體的個數(shù)稱為該種群的規(guī)模。種群規(guī)模會影響遺傳優(yōu)化的結(jié)果和效率。大的種群中含有豐富的個體模式，可以改進(jìn)遺傳算法的搜索質(zhì)量，防止早熟收斂（算法較早地收斂于局部最優(yōu)解，稱為早熟收斂）。但大的種群也增加了個體適應(yīng)度函數(shù)的計算量，從而降低了收斂速度。一般種群規(guī)模選取在[20,100]區(qū)間的值。763.4.3.1遺傳算法中的基本概念（3）適應(yīng)度（Fitness）函數(shù)：適應(yīng)度是指個體對環(huán)境的適應(yīng)程度。在的適應(yīng)度優(yōu)化問題中，用一個估計函數(shù)來度量個體的適應(yīng)度，這個函數(shù)稱為適應(yīng)度函數(shù)。其函數(shù)值是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據(jù)。個體的值越大，說明該個體的狀態(tài)越好，競爭能力越強(qiáng)，被選擇參與遺傳操作來產(chǎn)生新個體的可能性就越大，以此體現(xiàn)生物遺傳中適者生存的原理。773.4.3.2編碼（1）二進(jìn)制編碼二進(jìn)制編碼就是用一個二進(jìn)制的字符串表示一個個體，其中每個0或1為等位基因。染色體上由若干個基因構(gòu)成的一個有效信息段稱為基因組。例如：一個染色體11011，0/1表示基因，前3個基因就是一個基因組110。二進(jìn)制編碼使得交叉、變異等遺傳操作易于實現(xiàn)，但在求解高維優(yōu)化問題時，二進(jìn)制編碼串會很長，將導(dǎo)致遺傳算法的搜索效率很低。（2）實數(shù)編碼為了克服二進(jìn)制編碼的缺點，在問題變量是實向量的情況下，可直接采用十進(jìn)制編碼，即為實數(shù)編碼。實數(shù)編碼就是用一個十進(jìn)制的字符串表示一個個體，然后在實數(shù)空間上進(jìn)行遺傳操作。近年來，遺傳算法在求解高維或復(fù)雜優(yōu)化問題時，一般都采用實數(shù)編碼。783.4.3.2編碼（3）有序編碼有序編碼也叫序列編碼、排列編碼，是針對一些特殊問題的特定編碼方式。該編碼方式排列有限集合內(nèi)的元素。若集合內(nèi)包含m個元素，則存在m!種排列方法，當(dāng)m不大時，m!也不會太大，可采用窮舉法解決問題。當(dāng)m比較大時，m!就會非常大，窮舉法失效，遺傳算法在解決這類問題上具有優(yōu)勢。針對很多組合優(yōu)化問題，目標(biāo)函數(shù)的值不僅與表示解的字符串中各字符的值有關(guān)，而且與其所在字符串中的位置有關(guān)。這樣的問題稱為有序問題。若目標(biāo)函數(shù)的值只與表示解的字符串中各字符的位置有關(guān)，而與具體的字符值無關(guān)，則稱為純有序問題，如八皇后問題。有序編碼的優(yōu)點是使問題簡潔，易于理解，編碼自然、合理。793.4.3.3種群設(shè)定由于遺傳算法是對種群進(jìn)行操作的，因此需要為遺傳操作構(gòu)造一個由若干個個體組成的初始種群。初始種群中的個體一般是隨機(jī)產(chǎn)生的。假設(shè)設(shè)定種群規(guī)模為M，首先隨機(jī)生成一定數(shù)目（通常為2M）的個體，然后從中挑選較好的M個個體，構(gòu)成初始種群。803.4.3.4適應(yīng)度函數(shù)的設(shè)計81適應(yīng)度函數(shù)的設(shè)計直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解，因為遺傳算法僅根據(jù)適應(yīng)度函數(shù)來評價種群中每個個體適應(yīng)性的優(yōu)劣。在遺傳算法中，適應(yīng)度函數(shù)值規(guī)定為非負(fù)，并且在任何情況下都希望其值越大越好。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合待求解問題本身的要求而定。一般而言，適應(yīng)度函數(shù)是由待求解優(yōu)化問題的目標(biāo)函數(shù)變換得到的。若問題的目標(biāo)函數(shù)f(x)為最大化問題，則適應(yīng)度函數(shù)可以取為Fit(f(x))=f(x)若問題的目標(biāo)函數(shù)f(x)為最小化問題，則適應(yīng)度函數(shù)可以取為Fit(f(x))=1/f(x)3.4.3.5遺傳操作82遺傳操作（GeneticOperator）：可作用于種群，用于產(chǎn)生新的種群。標(biāo)準(zhǔn)的遺傳操作包括以下三種基本形式：選擇（Selection）交叉（Crossover）變異（Mutation）（1）選擇操作選擇（Selection）操作，也稱作復(fù)制（Reproduction），它是從當(dāng)前種群中按照一定概率選出的優(yōu)良個體，使它們有機(jī)會作為父代繁殖下一代。選擇操作的目的是使種群優(yōu)勝劣汰、不斷進(jìn)化，并且提高種群的收斂速度和搜索效率。根據(jù)個體的適應(yīng)度值來判斷其優(yōu)劣，適應(yīng)度值越高，越具有優(yōu)良性，該個體被選擇的機(jī)會就越大，顯然這一操作借鑒了達(dá)爾文“適者生存”的進(jìn)化原則。實現(xiàn)選擇操作的方法有很多，不同的選擇策略對算法的性能也有較大的影響。最常用的選擇方法稱為“輪盤賭”方法。83個體被選擇的概率為（2）交叉操作交叉（Crossover）算子，也稱為重組操作，是遺傳算法中的核心操作。交叉是分別用兩個父代個體的部分基因片段重組為新的子代的操作，使父代的優(yōu)良特征能傳遞給子代，并產(chǎn)生新的特性。由交叉操作得到的子代個體，構(gòu)成了新種群，其中個體適應(yīng)度的平均值和最大值均比父代有明顯提高。交叉是遺傳算法中獲得比父代更優(yōu)秀的個體的最重要手段。最常見的是單點交叉。例如，對于兩個父代染色體：x1=10110011、x2=01100101，隨機(jī)產(chǎn)生交配位“3”，則交叉產(chǎn)生兩個子代染色體：y1=10100101、y2=01110011。84（2）交叉操作85在進(jìn)化過程中，交叉并非百分之百地發(fā)生，而是以某一概率發(fā)生，這個概率稱為交叉概率Pc

。一般Pc在[0.6,1.00]取值，實驗表明Pc取0.7左右時，搜索結(jié)果比較理想。Pc控制著交叉操作的應(yīng)用頻率，在每代種群中，都需要對M×Pc個個體的染色體結(jié)構(gòu)進(jìn)行交叉操作。交叉概率越大，在種群中引入新的染色體結(jié)構(gòu)的速度就越快，但優(yōu)良基因結(jié)構(gòu)遭到破壞的可能性也相應(yīng)增大。若交叉概率太低，則可能導(dǎo)致早熟收斂。當(dāng)交叉操作產(chǎn)生的后代的適應(yīng)度不再比其父代高、且未找到全局最優(yōu)解時，算法會較早地收斂于局部最優(yōu)解，稱為早熟收斂。早熟收斂的根源是發(fā)生了有效等位基因的缺失，即缺失了最優(yōu)解位串上的等位基因。若想要跳出局部最優(yōu)，只有進(jìn)行變異操作，才能改變這種情況。（3）變異操作變異是隨機(jī)改變個體編碼中某些位的基因值的操作，從而產(chǎn)生新一代的個體。變異操作是按位進(jìn)行的，即對某一位的內(nèi)容進(jìn)行變異。變異的主要目的是保持種群的多樣性，對選擇、交叉過程中可能丟失的某些遺傳基因進(jìn)行修復(fù)和補(bǔ)充，當(dāng)發(fā)生早熟收斂時，可利用變異跳出局部最優(yōu)解的陷阱。變異操作不僅可以保證實現(xiàn)搜索的目標(biāo)，而且可以提高搜索的效率。變異操作是在交叉操作后進(jìn)行的，在子代某個個體中隨機(jī)選擇基因座，然后按變異概率Pm進(jìn)行變異。Pm不能取很大的值。若變異概率太大，則種群中重要的、單一的基因可能會丟失，且使遺傳算法趨于純粹的隨機(jī)搜索。一般Pm在[0.001,0.01]取值。變異與選擇、交叉結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機(jī)搜索能力，同時使得遺傳算法保持種群的多樣性，以防止早熟收斂。865種變異方法（1）位點變異。在個體位串中隨機(jī)擇選一個或多個基因座，并對這些基因座的基因值按變異概率Pm作變動。對于以二進(jìn)制位串表示的染色體而言，若某位原來的值為1，變異操作就是將其值變?yōu)?，反之亦然。對于實數(shù)編碼，可將被選擇的基因座的值變?yōu)榘锤怕蔬x擇的其他基因值。為了消除非法性，再將其他基因所在的基因座上的基因變?yōu)楸贿x擇的基因。（2）互換變異。隨機(jī)擇選某個個體的兩個基因進(jìn)行簡單互換。（3）插入變異。在某個個體中隨機(jī)選擇一個基因，然后將此基因插入隨機(jī)選擇的基因座。（4）移動變異。在某個個體中隨機(jī)擇選一個基因，向左或者向右移動隨機(jī)的位數(shù)。（5）逆轉(zhuǎn)變異。在某個個體中隨機(jī)選擇兩點（稱為逆轉(zhuǎn)點），然后將兩點之間的基因值以逆序插入原位置。873.4.3.6遺傳算法的基本過程883.4.3.7采用遺傳算法求解八皇后問題采用有序編碼表示每個棋盤布局：某八皇后狀態(tài)需要指明8個皇后的位置，每列有一個皇后，每個狀態(tài)可用8個數(shù)字表示，每個數(shù)字表示該列中皇后所在的行號，其值在1到8之間。89圖3.15八皇后問題的一個解，fitness=28

圖3.16八皇后問題的一個布局，fitness=2582417536在八皇后問題中，我們用不相互攻擊的皇后對的數(shù)目來表示適應(yīng)度。最優(yōu)解的適應(yīng)度是28。右圖中，這四個狀態(tài)的適應(yīng)度分別是24(4對攻擊)、23(5對攻擊)、20和11。設(shè)計適應(yīng)度函數(shù)90在這個特定的遺傳算法實現(xiàn)中，被選擇進(jìn)行繁殖的概率直接與個體的適應(yīng)度成正比，其百分比標(biāo)在旁邊。（即適應(yīng)度越高，越好。）第一個狀態(tài)被選擇的概率為：24/（24+23+20+11）=24/78=30.8%=28C28例1：一個八皇后狀態(tài)圖，計算其適應(yīng)度fitness的值當(dāng)前狀態(tài)的啟發(fā)式代價評估h=形成相互攻擊的皇后對的數(shù)量，h=4適應(yīng)度=28-4=2491例2：一個八皇后狀態(tài)圖，計算其適應(yīng)度fitness的值當(dāng)前狀態(tài)的啟發(fā)式代價評估h=形成相互攻擊的皇后對的數(shù)量，h=3適應(yīng)度=28-3=2592交叉示意圖

這3個八皇后的狀態(tài)分別對應(yīng)于“選擇”中的兩個父輩和“雜交”中它們的后代。陰影的若干列在雜交步驟中被丟掉，而無陰影的若干列則被保留下來。93(a)為初始種群(b)計算適應(yīng)度函數(shù)(c)

選擇(d)交叉產(chǎn)生的后代

(e)解決沖突

(f)變異94由于子代個體中存在重復(fù)的基因，需要解決沖突（e），即把子代中重復(fù)的基因按照某種映射關(guān)系（例如，1?4?7，3?6,5?8）處理成不含重復(fù)基因的個體。圖(f)中每個位置都會按照某個小的獨立概率隨機(jī)變異。在變異過程中，需要保證不造成任何基因的缺失和重復(fù)，即每個編碼都是一個沒有重復(fù)基因值的8位數(shù)字的排列。例如，采用交換變異方法，隨機(jī)生成兩個隨機(jī)數(shù)k1和k2（1<=k1<k2<=8)，交換該個體編碼中第k1位和k2位上的值，完成變異。3.5本章小結(jié)95搜索的基本概念：搜索、搜索策略、搜索技術(shù)、解、最優(yōu)解、完備性、最優(yōu)性盲目的圖搜索策略深度優(yōu)先搜索（DFS）寬度優(yōu)先搜索（BFS）

啟發(fā)式圖搜索策略ASearch，即最佳優(yōu)先搜索A*Search局部搜索：爬山法、模擬退火法、遺傳算法96人工智能基礎(chǔ)及應(yīng)用97第4章機(jī)器學(xué)習(xí)4.1機(jī)器學(xué)習(xí)概述4.2監(jiān)督學(xué)習(xí)4.3無監(jiān)督學(xué)習(xí)4.4弱監(jiān)督學(xué)習(xí)98本章學(xué)習(xí)目標(biāo)

理解機(jī)器學(xué)習(xí)的定義、基本術(shù)語及三個視角。掌握監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)的基礎(chǔ)知識和典型算法。了解弱監(jiān)督學(xué)習(xí)的三種方法和應(yīng)用場景。991004.1機(jī)器學(xué)習(xí)概述4.1.1

機(jī)器學(xué)習(xí)的定義機(jī)器學(xué)習(xí)主要有以下幾種定義。（1） 機(jī)器學(xué)習(xí)主要研究如何在經(jīng)驗學(xué)習(xí)中改善計算機(jī)算法的性能。（2）機(jī)器學(xué)習(xí)是研究用數(shù)據(jù)或以往的經(jīng)驗來優(yōu)化計算機(jī)程序性能的科學(xué)。（3）機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識和新技能，并識別現(xiàn)有知識的學(xué)問。（4）機(jī)器學(xué)習(xí)研究算法和數(shù)學(xué)模型，用以逐步提高計算機(jī)系統(tǒng)在特定任務(wù)上的性能。深度學(xué)習(xí)=大數(shù)據(jù)+高性能計算+靈巧的算法人工智能機(jī)器學(xué)習(xí)深度學(xué)習(xí)成功實現(xiàn)AI應(yīng)用的三要素：算法（菜譜）算力（廚具）數(shù)據(jù)（食材）AI、MachineLearning(ML)、DeepLearning(DL)的關(guān)聯(lián)1024.1.1機(jī)器學(xué)習(xí)的定義目前為止，尚未有一個公認(rèn)的機(jī)器學(xué)習(xí)定義。而作者認(rèn)為：機(jī)器學(xué)習(xí)是研究如何使機(jī)器模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為，以獲取知識和技能，并不斷改善系統(tǒng)自身性能的學(xué)科。機(jī)器學(xué)習(xí)是一門多領(lǐng)域交叉學(xué)科，涵蓋概率論、統(tǒng)計學(xué)、逼近論、凸分析、算法復(fù)雜度理論等多門學(xué)科的知識、理論和方法。它的根本任務(wù)是數(shù)據(jù)的智能分析與建模，并從數(shù)據(jù)中挖掘出有價值的信息。其目標(biāo)是要構(gòu)建可以從數(shù)據(jù)中學(xué)習(xí)、并對數(shù)據(jù)進(jìn)行預(yù)測的系統(tǒng)。1034.1.1機(jī)器學(xué)習(xí)的定義機(jī)器學(xué)習(xí)是AI的一個分支，是其中最具智能特征、最前沿的研究領(lǐng)域之一，是AI的核心和研究熱點。機(jī)器學(xué)習(xí)是實現(xiàn)人工智能的關(guān)鍵和重要途徑。機(jī)器學(xué)習(xí)理論和方法在基于知識的系統(tǒng)、自然語言理解、語音識別、計算機(jī)視覺、機(jī)器人、模式識別、生物信息學(xué)等許多領(lǐng)域得到了廣泛應(yīng)用。一個系統(tǒng)是否具有學(xué)習(xí)能力已成為評判其是否具有“智能”的一個標(biāo)準(zhǔn)。機(jī)器學(xué)習(xí)的研究主要分為兩大類：基于統(tǒng)計學(xué)的傳統(tǒng)機(jī)器學(xué)習(xí)：主要研究學(xué)習(xí)機(jī)制，注重探索模擬人的學(xué)習(xí)機(jī)制，研究方向包括：支持向量機(jī)、決策樹、隨機(jī)森林等?；诖髷?shù)據(jù)和人工神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)：主要研究如何充分利用大數(shù)據(jù)時代下的海量數(shù)據(jù)，采用深度學(xué)習(xí)技術(shù)構(gòu)建深度神經(jīng)網(wǎng)絡(luò)，從中獲取隱藏的、有效的、可理解的知識。人工智能與機(jī)器學(xué)習(xí)人類學(xué)習(xí)人類是從觀察中積累經(jīng)驗來獲取技能。機(jī)器學(xué)習(xí)機(jī)器是從數(shù)據(jù)中積累或者計算的經(jīng)驗中獲取技能。機(jī)器模擬人類的學(xué)習(xí)行為.Text,value,video,audio,image,etc1041054.1.2機(jī)器學(xué)習(xí)的基本術(shù)語1.數(shù)據(jù)集（Dataset）

數(shù)據(jù)集是指數(shù)據(jù)的集合。例如（20301001，張三，175cm，70kg）。2.樣本（Sample）樣本也稱為實例（Instance），指待研究對象的個體，包括屬性已知或未知的個體。例如，每個學(xué)生所對應(yīng)的一條記錄就是一個“樣本”。數(shù)據(jù)集即為若干樣本的集合。3.標(biāo)簽（Label）標(biāo)簽是為樣本指定的數(shù)值或類別。在分類問題中，標(biāo)簽是樣本被指定的特定類別；在回歸問題中，標(biāo)簽是樣本所對應(yīng)的實數(shù)值。已知樣本是指標(biāo)簽已知的樣本，未知樣本是指標(biāo)簽未知的樣本。1064.1.2機(jī)器學(xué)習(xí)的基本術(shù)語4.特征（Feature）特征是指樣本的一個獨立可觀測的屬性或特性。它反映樣本在某方面的表現(xiàn)或性質(zhì)，例如“姓名”“身高”是“特征”或“屬性”。特征的取值，例如“張三”“175cm”是“特征值”或“屬性值”。5.特征向量（FeatureVector）特征向量是由樣本的n個屬性組成的n維向量，第i個樣本Xi表示為：特征分為手工式特征也稱為設(shè)計式特征,是指由學(xué)者構(gòu)思或設(shè)計出來的特征,如SIFT、HOG等。學(xué)習(xí)式特征是指由機(jī)器從原始數(shù)據(jù)中自動生成的特征。例如，通過卷積神經(jīng)網(wǎng)絡(luò)獲得的特征就屬于學(xué)習(xí)式特征。手工式特征/設(shè)計的特征例如：用邊緣檢測算子提取的邊緣特征。HOG(HistogramofOrientedGradients，定向梯度直方圖)HOG特征107學(xué)習(xí)式特征邊緣特征1084.1.2機(jī)器學(xué)習(xí)的基本術(shù)語6.特征空間（FeatureSpace）特征空間是指特征向量所在的p維空間，每一個樣本是該空間中的一個點。特征空間也稱為樣本空間。例如，將“身高”“體重”作為兩個坐標(biāo)軸，它們就形成了用于描述學(xué)生體態(tài)的二維空間，每個學(xué)生在此特征空間中都能找到自己的位置坐標(biāo)。1094.1.2機(jī)器學(xué)習(xí)的基本術(shù)語通常將數(shù)據(jù)集分成訓(xùn)練集、驗證集和測試集，需要保證這三個集合是不相交的。（1）訓(xùn)練集（TrainingDataset）訓(xùn)練過程中使用的數(shù)據(jù)稱為“訓(xùn)練數(shù)據(jù)”，其中每個訓(xùn)練數(shù)據(jù)稱為一個“訓(xùn)練樣本”;每個訓(xùn)練樣本都有一個已知標(biāo)簽，由所有訓(xùn)練樣本及其標(biāo)簽組成的集合稱為“訓(xùn)練集”。訓(xùn)練集包括一個樣本集和一個對應(yīng)的標(biāo)簽集，用于學(xué)習(xí)得到擬合樣本的模型。一般地，訓(xùn)練集中的標(biāo)簽都是正確的，稱為真實標(biāo)簽（Ground-Truth）。例如，在圖像分類任務(wù)中，訓(xùn)練集包括一個由特定圖像組成的樣本集合一組由語義概念（如山、水、樓等）組成的標(biāo)簽集合，標(biāo)簽即為Ground-Truth。1104.1.2機(jī)器學(xué)習(xí)的基本術(shù)語（2）驗證集（ValidationDataset）在實際訓(xùn)練中，有時模型在訓(xùn)練集上的結(jié)果很好，但對于訓(xùn)練集之外的數(shù)據(jù)的結(jié)果并不好。此時，可單獨留出一部分樣本，不參加訓(xùn)練，而是用于調(diào)整模型的超參數(shù)，并對模型的能力進(jìn)行初步評估，這部分?jǐn)?shù)據(jù)稱為驗證集。超參數(shù)（hyperparameter）是指模型中人為設(shè)定的、無法通過訓(xùn)練得到的參數(shù)，如NN的層數(shù)、卷積的尺寸、濾波器的個數(shù)、KNN和K-Means算法中的K值等。（3）測試集（TestDataset）：測試過程中使用的數(shù)據(jù)稱為“測試數(shù)據(jù)”，被預(yù)測的樣本稱為“測試樣本”，測試樣本的集合稱為“測試集”。測試集不參與模型的訓(xùn)練過程，僅用于評估最終模型的泛化能力。1114.1.2機(jī)器學(xué)習(xí)的基本術(shù)語7.泛化能力（GeneralizationAbility）泛化能力是指訓(xùn)練得到的模型對未知樣本正確處理的能力，即模型對新樣本的適應(yīng)能力，亦稱為推廣能力或預(yù)測能力。

1124.1.2機(jī)器學(xué)習(xí)的基本術(shù)語9.學(xué)習(xí)算法（learningalgorithm）希望為每個樣本x預(yù)測的標(biāo)簽與其所對應(yīng)的真實標(biāo)簽都相同，這就需要有一組好的模型參數(shù)θ。為了獲得這樣的參數(shù)θ，則需要有一套學(xué)習(xí)算法來優(yōu)化函數(shù)f

，此優(yōu)化過程稱為學(xué)習(xí)(Learning)或者訓(xùn)練(Training)，擬合函數(shù)f稱為模型（Model）。10.假設(shè)空間（hypothesisspace）從輸入空間至輸出空間的映射可以有多個，它們組成的映射集合稱為假設(shè)空間。學(xué)習(xí)的目的：在此假設(shè)空間中選取最好的映射，即最優(yōu)的模型。用訓(xùn)練好的最優(yōu)模型對測試樣本進(jìn)行預(yù)測的過程稱為測試。1134.1.2機(jī)器學(xué)習(xí)的基本術(shù)語

1144.1.2機(jī)器學(xué)習(xí)的基本術(shù)語12.風(fēng)險函數(shù)（RiskFunction）風(fēng)險函數(shù)又稱期望損失（ExpectedLoss）或期望風(fēng)險（ExpectedRisk），是所有數(shù)據(jù)集（包括訓(xùn)練集和預(yù)測集）上損失函數(shù)的期望值，用于度量平均意義下模型預(yù)測的好壞。機(jī)器學(xué)習(xí)的目標(biāo)是選擇風(fēng)險函數(shù)最小的模型。1154.1.2機(jī)器學(xué)習(xí)的基本術(shù)語

1164.1.2機(jī)器學(xué)習(xí)的基本術(shù)語14.機(jī)器學(xué)習(xí)的基本流程是：數(shù)據(jù)預(yù)處理→模型學(xué)習(xí)→模型評估→新樣本預(yù)測。①數(shù)據(jù)預(yù)處理收集并處理數(shù)據(jù)，有時還需要完成數(shù)據(jù)增強(qiáng)、裁剪等工作，劃分訓(xùn)練集、驗證集、測試集。②模型學(xué)習(xí)，即模型訓(xùn)練