人工智能入門 課件 劉峽壁3.符號智能與問題求解、4.進化計算

搜索與問題求解AI:SearchandProblemSolving2大綱什么是搜索?問題表示–狀態(tài)空間與與或圖

–

它們體現(xiàn)了兩種問題求解的思路!博弈搜索–極大極小算法–α-β剪枝AI:SearchandProblemSolving3PartⅠ:什么是搜索?AI:SearchandProblemSolving4Theseus怎樣找到逃出Minotaur的迷宮的路?Ariadne的線索:AI:SearchandProblemSolving5什么是搜索?以可以接受的計算代價，在問題所有解答中找出最優(yōu)解或可行解。理想的搜索算法：盡可能快地找到最優(yōu)解.求解的效果與效率之間存在矛盾完備性,最優(yōu)性,復雜性AI:SearchandProblemSolving6PartⅡ:問題表示AI:SearchandProblemSolving7例子:2-階梵塔問題初始狀態(tài)目標狀態(tài)1目標狀態(tài)2規(guī)則:1.每次移動一個金片2.大的金片不能放在小的金片上面.AI:SearchandProblemSolving8步驟1表示所有的狀態(tài),包括初始狀態(tài)和目標狀態(tài)初始狀態(tài)目標狀態(tài)步驟2表示狀態(tài)轉(zhuǎn)換函數(shù)AI:SearchandProblemSolving9將金片A從柱i移動到柱

j

將金片B從柱i移動到柱

j

所有函數(shù):步驟3構(gòu)造狀態(tài)空間AI:SearchandProblemSolving10步驟4

搜索該圖以找到問題解答AI:SearchandProblemSolving112.1狀態(tài)空間S:狀態(tài)集合F:狀態(tài)轉(zhuǎn)換函數(shù)（或行動）的集合

C:狀態(tài)轉(zhuǎn)換函數(shù)代價的集合(如果不求最優(yōu)解，可以不考慮此因素)I:初始狀態(tài)集合G:目標狀態(tài)集合一個狀態(tài)空間對應于一個圖,其中從初始狀態(tài)到目標狀態(tài)的路徑就是問題的一個解。AI:SearchandProblemSolving12基于狀態(tài)空間的問題求解步驟1

表示所有狀態(tài)，標出其中的初始狀態(tài)和目標狀態(tài).步驟2

表示所有狀態(tài)轉(zhuǎn)換函數(shù)步驟3

以狀態(tài)為節(jié)點，以狀態(tài)轉(zhuǎn)換函數(shù)為邊，構(gòu)成一個圖。步驟4

搜索該圖以發(fā)現(xiàn)對應于最優(yōu)解或可行解的路徑。AI:SearchandProblemSolving13例子:八數(shù)碼問題狀態(tài)?

動作?

初始與目標狀態(tài)?

動作代價?

AI:SearchandProblemSolving14例子:八數(shù)碼問題狀態(tài)?

數(shù)字與空格的位置動作?

空格上、下、左、右移動初始與目標狀態(tài)?

如圖動作代價?

每移動一下代價為1AI:SearchandProblemSolving15與或圖實現(xiàn)問題歸約的數(shù)據(jù)結(jié)構(gòu)-每一個節(jié)點對應于一個問題-“與”節(jié)點=分解-“或”節(jié)點=轉(zhuǎn)換-端節(jié)點*終止節(jié)點=本原問題*其他端節(jié)點=不可解問題-可解節(jié)點與不可解節(jié)點

AI:SearchandProblemSolving16基于與或圖的問題求解找出一個解圖，它是代表原始問題求解方案的一個子圖步驟1.表示每個問題。步驟2.對問題進行歸約，用與或圖表示歸約過程。步驟3.從端節(jié)點向上回溯，直到根節(jié)點，標注各個節(jié)點可解或不可解。步驟4.如果根節(jié)點被標注為可解，輸出相應的解圖。AI:SearchandProblemSolving17例子:3-階梵塔問題初始狀態(tài)目標狀態(tài)AI:SearchandProblemSolving18步驟1.表示問題

問題狀態(tài):

原始問題:(1,1,1)(3,3,3)步驟2.問題歸約

將原始問題分解為:-子問題1=(1,1,1)(1,2,2)-子問題2=(1,2,2)(3,2,2)√-子問題3=(3,2,2)(3,3,3)

繼續(xù)分解子問題2和3

AI:SearchandProblemSolving19步驟3.搜索該圖，以決定根節(jié)點可解或不可解.步驟4.輸出整個圖作為解答.(如何解釋?)AI:SearchandProblemSolving20PartⅣ:博弈搜索圖片來自：/DL88250AI:SearchandProblemSolving213.1博弈樹代表博弈過程的數(shù)據(jù)結(jié)構(gòu)

-2個玩家(MAX和MIN)-確定性的-輪流進行-零和的-信息完備AI:SearchandProblemSolving22游戲狀態(tài)：(K1,K2,….,Kn,MINorMAX)每堆錢幣個數(shù)當前走步方每次MIN或MAX選擇一堆錢幣并且把它分成數(shù)目不等的兩堆。

當MIN或MAX不能完成任務時,就輸了。

首先,n=1,k1=7,MIN為走步方例：分錢幣游戲AI:SearchandProblemSolving23(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)分錢幣游戲的博弈樹MAX的必勝招?AI:SearchandProblemSolving24游戲中的每一步MAX

和

MIN

總是采取對自己最有利的行動。為了能夠勝利,MAX應該每一步選擇最有利的行動,同時認為

MIN

也會每一步都采取對MIN最好的行動(也就是說，對MAX最壞)

在想象對手為最強對手的情況下采取最好的行動！在結(jié)構(gòu)上，博弈樹是與或圖！AI:SearchandProblemSolving25(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)作為與或圖進行搜索作為與或圖進行搜索?AI:SearchandProblemSolving26

實際條件的限制

如中國象棋:共有

10160

種狀態(tài)。假設每秒搜索

103

個節(jié)點，需要

10145

年找到一個最優(yōu)走步。(最新估計宇宙年齡為

1010年)解決辦法

截斷策略:限制博弈樹的搜索深度

估價函數(shù):從MAX的角度出發(fā)估計博弈狀態(tài)，值越大，該狀態(tài)對MAX越有利。

3.2極大極小搜索AI:SearchandProblemSolving27選擇移動到具有最高極大極小值的位置!例：兩個玩家的游戲AI:SearchandProblemSolving28例:一字棋估價函數(shù):e(P)=e(+P)－e(-P)

對于對稱狀態(tài)只存儲其中一種e(P)＝6-4＝2AI:SearchandProblemSolving29MAX第一次走步AI:SearchandProblemSolving30MAX第二次走步AI:SearchandProblemSolving31最后狀態(tài)AI:SearchandProblemSolving323.3α-β剪枝通過剪掉博弈樹中不必要的分支提高搜索的效率。使用深度限制搜索(DLS)策略AI:SearchandProblemSolving33α-β剪枝例1AI:SearchandProblemSolving34α-β剪枝例1AI:SearchandProblemSolving35α-β剪枝例1AI:SearchandProblemSolving36α-β剪枝例1AI:SearchandProblemSolving37α-β剪枝例1α-β剪枝例2AI:SearchandProblemSolving38S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≤0≥0＝0≤-6＝0≤0＝4＊＊＊＊＊＊AI:SearchandProblemSolving39什么是α-β?α

是MAX頂點倒推值的最小邊界如果

v

比α更小,MAX將不搜索它。

剪掉這一枝β

定義方式類似，但針對MIN節(jié)點AI:SearchandProblemSolving40確定性博弈程序現(xiàn)狀

西洋跳棋:1994年，Chinook終結(jié)了人類世界冠軍MarionTinsley長達40年的統(tǒng)治。

國際象棋:1997年，DeepBlue在六回合制比賽中打敗了人類世界冠軍GarryKasparov.

黑白棋:人類高手拒絕與機器比賽，因為機器下棋水平實在是太好了。

圍棋:人類高手同樣拒絕與機器比賽，因為機器下棋水平實在是太差了。AI:SearchandProblemSolving41深藍AI:SearchandProblemSolving42總結(jié)狀態(tài)空間-五個要素(S,F,C,I,G)-問題的解是從初始頂點到目標頂點的一條路徑與或圖-問題規(guī)約

-目標是確定根節(jié)點是否可解-問題的解是讓根節(jié)點可解的一個子圖AI:SearchandProblemSolving43搜索算法的效果和效率是一對矛盾。在設計和評價搜索算法時，需要綜合考慮算法的完備性、最優(yōu)性和復雜性。具體設計策略有盲目搜索與啟發(fā)式搜索之分，全局搜索和局部搜索之分，以及搜索最優(yōu)解和可行解之分。

圖搜索算法的一般結(jié)構(gòu)是不斷擴展頂點，直到發(fā)現(xiàn)目標頂點（狀態(tài)空間）或者確定初始頂點的可解性（與或圖）?？偨Y(jié)AI:SearchandProblemSolving44不同圖搜索算法的主要區(qū)別在于頂點的擴展順序不同。盲目搜索不考慮問題特性,包括廣度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索和迭代加深深度優(yōu)先搜索。啟發(fā)式搜索算法根據(jù)問題所提供的啟發(fā)式信息，用估價函數(shù)估計頂點的搜索效率，選擇估計效率最高的頂點進行擴展。A*算法是影響最大的，應用于狀態(tài)空間的啟發(fā)式搜索算法。它通過對估價函數(shù)施加一定約束，可以保證搜索到最優(yōu)解?？偨Y(jié)AI:SearchandProblemSolving45博弈樹

表示博弈過程的數(shù)據(jù)結(jié)構(gòu)

在想象對手是最強對手的情況下采取最好的行動，這在結(jié)構(gòu)上表現(xiàn)為與或圖極大極小算法

-限制博弈樹的深度-評價博弈狀態(tài)-選擇移動到具有最高極大極小值的位置!α-β剪枝

在有界深度優(yōu)先搜索過程中，通過剪掉一些不必要的分枝達到提高搜索效率的目的?？偨Y(jié)進化計算01AI:EC47大綱生命對搜索方法的啟示什么是進化計算(EC)?進化算法(EA)遺傳算法進化規(guī)劃進化策略AI:EC48

一個啟發(fā)式搜索的新思路?進化計算確定還是隨機?若確實如此啟發(fā)式搜索（優(yōu)化）方法是數(shù)學和計算機科學的核心主題AI:EC49PartⅠ:生物對搜索的啟示AI:EC50Q.什么是搜索問題最好的解決方案?.人類的大腦

能產(chǎn)生“汽車,紐約,戰(zhàn)爭,等”

(afterDouglasAdams)

神經(jīng)計算

.進化機制

導致人腦的產(chǎn)生(afterDarwinetal.)

進化計算

AI:EC51達爾文進化基于群體的進化，而非個體的變化適者生存:有限的資源導致激烈的競爭,那些能最有效的占有資源的個體(最適應環(huán)境的個體)有更高的概率被繁殖下去(被選擇)AI:EC52達爾文進化多樣性引起變化:如果表現(xiàn)特征:有更高的概率被繁殖下去可以繼承則他們往往會形成更多的后代，從而導致新的組合特征.

隨機性的作用最優(yōu)的解不一定都能生存下去AI:EC53自然遺傳學遺傳信息需要通過有機體的DNA編碼遺傳下去基因的微小變化導致生物體的微小變化(如身高,頭發(fā)，顏色)對于一個特定的物種，其遺傳物質(zhì)是基本相同的AI:EC54基因和基因組由DNA鏈編碼的基因稱為染色體在大多數(shù)細胞中，有兩條染色體排成雙螺旋結(jié)構(gòu)(diploidy)一個個體的全部遺傳物質(zhì)的集合稱為基因組AI:EC55個體遺傳物質(zhì)改變的主要手段:重組從至少兩個父代個體中獲得遺傳物質(zhì)產(chǎn)生新的個體,如,在一對染色體的交叉點上連接交換染色體:

重組前

重組后圖片來源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC56個體遺傳物質(zhì)改變的主要手段:突變一些遺傳物質(zhì)會發(fā)生輕微的改變，這個過程偶爾發(fā)生這意味著子代個體可能擁有父代個體所沒有的遺傳物質(zhì)這種改變極有可能是災難性的AI:EC57進化理論突變,重組

新的遺傳物質(zhì)或者新的組合.繁殖的越多則基因的性能可以得到更多的改進

好的基因得到更多被遺傳的機會壞的基因則會在遺傳的過程中減少在其生存環(huán)境中，有機體作為一個整體得到進化.采用進化的方法計算或求解問題能夠幫助我們找到問題的最優(yōu)解：進化計算AI:EC58PartⅡ:什么是進化計算?AI:EC59以這樣的方式放置8皇后一個8x8的棋盤上，他們不能互相卡到對方，例子:8皇后問題

[AfterA.E.EibenandJ.E.Smith,IntroductiontoEvolutionaryComputing]

AI:EC6012345678遺傳物質(zhì):

一列數(shù)字1-8表現(xiàn)特性:

一個棋局配置Obviousmapping8皇后問題:表示AI:EC61一個皇后的懲罰:

它能卡住的皇后個數(shù).

一種棋局的懲罰:

對每一個皇后的懲罰值求和.

目標:使得懲罰值最小

最優(yōu)棋局:

懲罰值的倒數(shù)最大時8皇后問題:適應度評價AI:EC62

突變:

交換兩個隨機選擇的點

(概率:80%)1234567812345678

重組:

交叉(概率:100%)876425311352467887645123135628748皇后問題:遺傳算子5432126478AI:EC63父代選擇:挑選五個父代個體，并選擇其中最優(yōu)的兩個執(zhí)行重組操作生存選擇(替換策略)當一個新的子代個體要插入種群中時，選擇種群中將被替換的一個個體，選擇規(guī)則為:將種群中的個體按適應度降序排列將個體由高到低列舉替換排列中第一個適應度比當前子代適應度低的個體8皇后問題:選擇AI:EC64初始化:隨機終止:根據(jù)適應度的評價問題得到了解決或者循環(huán)迭代次數(shù)達到最大（比如10，000）8皇后問題:初始化\終止條件AI:EC658皇后問題:總結(jié)注意：操作和參數(shù)的選擇不只有這一種可能AI:EC66生物進化與搜索的類比進化個體適應度環(huán)境搜索候選解解的質(zhì)量待求解的問題AI:EC67進化算法構(gòu)成tt+1突變重組繁殖選擇圖片來源IdaSprinkhuizen-Kuyper:Introductionto

EvolutionaryComputation,2000.AI:EC68進化機制遺傳增加了多樣性突變重組選擇減少了多樣性父代選擇：選擇用于繁殖的父代子代選擇：選擇保留下來的子代AI:EC69進化中的循環(huán)過程重組突變種群子代父代父代選擇子代選擇圖片來源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC70表示基因表示:編碼:表型=>基因(不一定是一一對應的)解碼:基因=>表型(必須是一一對應的)表型表示:問題的特定編碼AI:EC71進化(適應度)函數(shù)表示對種群（解）的要求，即質(zhì)量函數(shù)

或

目標函數(shù)為每一個表型計算一個代表其適應度的實數(shù)，這樣構(gòu)成了遺傳選擇的基礎(chǔ)因此該函數(shù)的判斷能力越大越好AI:EC72基因操作產(chǎn)生新的候選解

通常根據(jù)父代個體數(shù)分為兩類:=1:突變操作>1:重組操作=2:交叉操作有很多關(guān)于重組和突變重要性的爭論現(xiàn)在大多數(shù)進化算法兩者都有AI:EC73父代選擇機制個體作為父代的概率是根據(jù)其適應度得出來的高質(zhì)量的解有更高的概率被作為父代個體出現(xiàn)，但它并不是一定會作為父代個體出現(xiàn)，即使是種群中最差的個體也不是完全沒有機會作為父代個體出現(xiàn)這種隨機性可以在一定程度上避免陷入局部最優(yōu)解.AI:EC74子代選擇或稱為替換策略從子代+父代的種群中產(chǎn)生新的種群的方法兩種方法適應度準則

:例如挑選種群中一定數(shù)量適應度最好的個體作為新的種群年齡準則:

產(chǎn)生和父代個體一樣多的子代個體，淘汰所有的父代個體AI:EC75初始化/終止條件初始化

通常采用隨機初始化的策略。終止條件

檢查每一代種群個體，看以下條件是否滿足：

達到給定的或期望的適應度達到最大的種群更新次數(shù)種群中的多樣性水平最小連續(xù)幾代更新都沒有使得種群中的適應度得到改進AI:EC76PartⅢ:進化算法AI:EC77主要進化算法遺傳算法(GA)J.Holland1962(AnnArbor,MI)進化規(guī)劃(EP)L.Fogel1962(SanDiego,CA)進化策略(ES)I.Rechenberg&H.-P.Schwefel1965(Berlin)遺傳規(guī)劃(GP)J.Koza1989(PaloAlto,CA)算法之間的相似性比差異更重要AI:EC78分類圖片來源:Introductionto

EvolutionaryComputationbyIdaSprinkhuizen-KuyperAI:EC79技術(shù)總結(jié)GAEPESGP表示基因型表現(xiàn)型表現(xiàn)型基因型突變√√√√重組√×√√父代選擇概率選擇確定選擇概率選擇概率選擇子代選擇排斥,確定混合，隨機混合，確定排斥，確定AI:EC803.1遺傳算法(GA)Holland最初提出的遺傳算法現(xiàn)在被稱作簡單遺傳算法(SGA)現(xiàn)在還常常被用作新的遺傳算法的測試基準其他遺傳算法可能應用不同的:表示方法突變方法交叉方法選擇機制AI:EC81表示基因組通常被用來表示候選解定長二進制編碼(SGA)Holland傳統(tǒng)的

其收斂性有理論上的保證實值基因組人工進化收斂性的證明很困難AI:EC82貪婪選擇:選擇適應度最好的解按概率選擇:概率與適應度成正比例如采用輪盤賭的方法(SGA)GA操作:選擇例如適應度為：(2200,1800,1200,950,400,100)AI:EC83GA操作:交叉對于給定的父代個體，交叉以特定的概率

Pc

1發(fā)生(Pc

的典型范圍為(0.6,0.9))否則父代個體直接作為子代個體(克隆)例如,A.One-pointcrossover(SGA)

B.Two-pointcrossover

圖片來源:IntroductiontoStochasticSearchandOptimization(ISSO)byJ.C.SpallAI:EC84GA操作:突變獨立地改變每一個基因的概率

pmpm稱為

突變概率典型值介于（1/種群規(guī)模）和（1/

染色體長度）之間例如