人工智能基礎(chǔ)03--搜索技術(shù)【教育課件】

1、目錄,第一章緒論 第二章知識(shí)表示 第三章搜索技術(shù) 第四章推理技術(shù) 第五章機(jī)器學(xué)習(xí) 第六章專家系統(tǒng) 第七章自動(dòng)規(guī)劃系統(tǒng) 第八章 自然語(yǔ)言理解 第九章 智能控制 第十章 人工智能程序設(shè)計(jì),技術(shù)課件,3.1 盲目搜索,盲目搜索：即 無(wú)信息搜索 寬度優(yōu)先與深度優(yōu)先 3.1.1 圖搜索策略 圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。研究圖搜索的一般策略，能夠給出圖搜索過(guò)程的一般步驟,技術(shù)課件,3.1 盲目搜索,3.1.1 圖搜索策略 例3.1 從王某家族的四代中找王A

2、的后代且其壽命為X的人,A,47,B1,77,A3,52,B2,65,C2,87,C1,96,D1,77,E1,57,E2,92,F1,32,G1,27,H1,51,技術(shù)課件,3.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表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn)n。 (5) 若n為一目標(biāo)節(jié)點(diǎn)，則

3、有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置,技術(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)的

4、指針?lè)较颉?(8) 按某一任意方式或按某個(gè)探試值，重排OPEN表。 (9) GO LOOP,技術(shù)課件,3.1 盲目搜索,3.1.1 圖搜索策略 2.圖搜索算法的幾個(gè)重要名詞 （1）OPEN表與CLOSE表 OPEN表 CLOSED表,技術(shù)課件,3.1 盲目搜索,3.1.1 圖搜索策略 3. 搜索圖與搜索樹 搜索過(guò)程框圖,技術(shù)課件,3.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ā)

5、式搜索)。每當(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)搜索樹不再剩有未被擴(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),技術(shù)課件,3.1 盲目搜索,3.1.2 寬度優(yōu)先搜索 定義3.1 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索（breadth-first search,技術(shù)課件,3.1 盲目搜索,3.1.2 寬度優(yōu)先搜索 寬度優(yōu)先搜索算法 (1) 把起

6、始節(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)表中。 (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)步,技術(shù)課件,3.1 盲目搜索,3.1.2 寬度優(yōu)先搜索,例3.2 八數(shù)碼問(wèn)題 操作規(guī)定: 允許空格四周上、下、左、右的數(shù)碼塊移入空格中，不許斜方

7、向移動(dòng)，不許返回先輩結(jié)點(diǎn)。 初始布局S和目標(biāo)狀態(tài)D如下圖所示,技術(shù)課件,3.1 盲目搜索,3.1.2 寬度優(yōu)先搜索,例3.2 八數(shù)碼問(wèn)題,技術(shù)課件,3.1 盲目搜索,3.1.3 深度優(yōu)先搜索 深度優(yōu)先算法步驟： (1) 初始結(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)OPEN中； (2) 若OPEN為空，則搜索失敗，問(wèn)題無(wú)解； (3) 彈出OPEN表中最頂端結(jié)點(diǎn)放到CLOSE表中，并給出順序編號(hào)n； (4) 若n為目標(biāo)結(jié)點(diǎn)D，則搜索成功，問(wèn)題有解； (5) 若n無(wú)子結(jié)點(diǎn)，轉(zhuǎn)(2)； (6) 擴(kuò)展n結(jié)點(diǎn)，將其所有子結(jié)點(diǎn)配上返回n的指針，并按次序壓入OPEN堆棧，轉(zhuǎn)(2),技術(shù)課件,3.1 盲目搜索,3.1.3 深度優(yōu)先

8、搜索,技術(shù)課件,3.1 盲目搜索,3.1.3 深度優(yōu)先搜索 有界深度優(yōu)先搜索： 引入搜索深度限制值d，使深度優(yōu)先搜索過(guò)程具有完備性 。 設(shè)定搜索深度限制d=5，問(wèn)題同深度優(yōu)先算法中的八數(shù)碼問(wèn)題(2,技術(shù)課件,3.1 盲目搜索,3.1.3 深度優(yōu)先搜索,技術(shù)課件,3.1 盲目搜索,3.1.3 深度優(yōu)先搜索 有界深度優(yōu)先算法步驟： (1)初始結(jié)點(diǎn)S放入堆棧OPEN中； (2)若OPEN為空，則搜索失敗，問(wèn)題無(wú)解； (3)彈出OPEN中棧頂結(jié)點(diǎn)n，放入CLOSE表中，并給出順序編號(hào)n； (4)若n為目標(biāo)結(jié)點(diǎn)D，則搜索成功，問(wèn)題有解； (5)若n的深度d(n)=d，則轉(zhuǎn)(2) ； (6)若n無(wú)子結(jié)點(diǎn)，

9、即不可擴(kuò)展，轉(zhuǎn)(2) ； (7)擴(kuò)展結(jié)點(diǎn)n，將其所有子結(jié)點(diǎn)配上返回n的指針，并壓入OPEN堆棧，轉(zhuǎn)(2),技術(shù)課件,3.1 盲目搜索,3.1.4 等代價(jià)搜索 寬度優(yōu)先搜索可被推廣用來(lái)解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問(wèn)題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算法。 等代價(jià)搜索中的幾個(gè)記號(hào) 起始節(jié)點(diǎn)記為S； 從節(jié)點(diǎn)i到它的后繼節(jié)點(diǎn)j的連接弧線代價(jià)記為c(i，j)； 起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)記為g(i)。 如果所有的連接弧線具有相等的代價(jià)，那么等代價(jià)算法就簡(jiǎn)化為寬度優(yōu)先搜索算法,技術(shù)課件,3.2 啟發(fā)式搜索,盲目搜索的不足：效率低，耗費(fèi)空間與時(shí)間。 啟發(fā)式搜索：利用問(wèn)題

10、域特性的信息（啟發(fā)信息）進(jìn)行搜索。 3.2.1 啟發(fā)式搜索策略 啟發(fā)式信息按用途分為三種： （1）用于確定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，避免盲目擴(kuò)展。 （2）在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于確定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，避免盲目生成所有可能節(jié)點(diǎn)。 （3）用于確定某些應(yīng)該從搜索樹中拋棄或修剪得節(jié)點(diǎn),技術(shù)課件,3.2 啟發(fā)式搜索,有序搜索（ordered search）：利用第一種啟發(fā)信息，總是選擇“最有希望”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。 估價(jià)函數(shù)（evaluation function )：估算節(jié)點(diǎn)“希望”的量度，這種量度叫做估價(jià)函數(shù)。 建立估價(jià)函數(shù)的一般方法：試圖確定一個(gè)處在最佳路徑上的節(jié)點(diǎn)的概率；提

11、出任意節(jié)點(diǎn)與目標(biāo)集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點(diǎn)來(lái)決定棋局的得分?jǐn)?shù)。這些特點(diǎn)被認(rèn)為與向目標(biāo)節(jié)點(diǎn)前進(jìn)一步的希望程度有關(guān)。 f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索 用估價(jià)函數(shù)f來(lái)排列GRAPHSEARCH第8步中OPEN表上的節(jié)點(diǎn)。應(yīng)用某個(gè)算法(例如等代價(jià)算法)選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索或最佳優(yōu)先搜索(best-first search)，而其算法就叫做有序搜索算法或最佳優(yōu)先算法,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索 有序狀態(tài)空間搜索算法： (1

12、) 把起始節(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)表中,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索 (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表

13、中，則用估價(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值較小，則,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索 (i) 以此新值取代舊值。 (ii) 從j指向i，而不是指向它的父輩節(jié)點(diǎn)。 (iii) 如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表。 (7) 轉(zhuǎn)向(2)，即GO TO(2,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索,開始,把S放入OPEN表,OPEN為空表,失敗,選取OPEN表中f值最小

14、 的節(jié)點(diǎn)i，放入CLOSED表,i=Sg,成功,是,是,擴(kuò)展i得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提 供返回i的指針，利用f(j)對(duì)OPEN 表重新排序調(diào)整父子關(guān)系及指針,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索 寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。對(duì)于寬度優(yōu)先搜索，選擇f(i)作為節(jié)點(diǎn)i的深度。對(duì)于等代價(jià)搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價(jià)。 有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。如果沒(méi)有適用的準(zhǔn)確的希望量度，那么f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是一個(gè)時(shí)間和空間之間的折衷方案；另一方面

15、是保證有一個(gè)最優(yōu)的解或任意解,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索 例3.4：八數(shù)碼難題, 采用了簡(jiǎn)單的估價(jià)函數(shù) f(n)=d(n)+W(n) 其中：d(n)是搜索樹中節(jié)點(diǎn)n的深度；W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。因此，起始節(jié)點(diǎn)棋局 的f值等于0+4=4,2,8,3,1,6,4,7,5,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.2 有序搜索,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,

16、8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,3,1,8,4,7,6,5,2,3,3,1,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,7,8,4,6,5,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.3 A*算法 A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 1. A*算法的估價(jià)函數(shù) k(ni，nj)：表示任意兩個(gè)節(jié)點(diǎn)ni和nj之間最小代價(jià)路徑的實(shí)際代價(jià)(對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn)，函數(shù)k沒(méi)有定義)。 k(n,ti)：從節(jié)點(diǎn)n到某個(gè)具體的目標(biāo)節(jié)點(diǎn)ti，某一條最小代價(jià)路徑的代價(jià)。 h*(n)：表示整個(gè)目標(biāo)節(jié)點(diǎn)集合ti

17、上所有k(n,ti)中最小的一個(gè)，因此，h*(n)就是從n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從n到目標(biāo)節(jié)點(diǎn)能夠獲得h*(n)的任一路徑就是一條從n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑(對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，函數(shù)h*沒(méi)有定義,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.3 A*算法 定義g* 為g*(n)=k(S,n) 從已知起始節(jié)點(diǎn)S到任意節(jié)點(diǎn)n的一條最佳路徑代價(jià)。 定義函數(shù)f*， f*(n)=g*(n)+h*(n) 使得在任一節(jié)點(diǎn)n上其函數(shù)值f*(n)就是從節(jié)點(diǎn)S到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.3 A*算法 希

18、望估價(jià)函數(shù)f是f*的一個(gè)估計(jì)，此估計(jì)可由下式給出： f(n)=g(n)+h(n) 其中：g是g*的估計(jì)；h是h*的估計(jì)。 對(duì)于g(n)：一個(gè)明顯的選擇就是搜索樹中從S到n這段路徑的代價(jià)，這一代價(jià)可以由從n到S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價(jià)路徑)。這個(gè)定義包含了g(n)g*(n)。 h(n)：對(duì) h*(n)的估計(jì)，依賴于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù)W(n)所用的那種信息相似。把h叫做啟發(fā)函數(shù),技術(shù)課件,3.2 啟發(fā)式搜索,3.2.3 A*算法 2. A算法和A*算法的定義 定義3.3 在GRA

19、PHSEARCH過(guò)程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過(guò)程為A算法。 定義3.4 在A算法中，如果對(duì)所有的x存在h(x)h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義3.5 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?A算法和A*搜索算法的目標(biāo)有所不同： A搜索算法雖然希望能找到問(wèn)題的最優(yōu)解，但主要追求的是求解效率；而A*搜索算法直接目標(biāo)就在于要找到問(wèn)題的最優(yōu)解及其解的路徑，即便搜索效率有所降低也在所不惜,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.3 A*算法,開始

20、,把S放入OPEN表,記f=h,OPEN為空表,失敗,選取OPEN表中未設(shè)置過(guò)的具有最小f值 的節(jié)點(diǎn)BESTNODE，放入CLOSED表,BESTNODE=Sg,成功,是,是,擴(kuò)展BESTNODE，產(chǎn)生后繼節(jié)點(diǎn)SUVVESSOR 建立從SUCCESSOR返回BESTNODE的指針 計(jì)算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR,SUCCESSOROPEN,否,是,技術(shù)課件,3.2 啟發(fā)式搜索,3.2.3 A*算法,把SECCESSOR放入OPEN表， 加入BESTNODE的后裔表,g(SUCCESSOR)g(OLD),否,重新確定OLD的父輩節(jié)

21、點(diǎn)為BESTNODE， 并修正父輩節(jié)點(diǎn)的g值和f值，記下g(OLD,SUCCESSORCLOSED,否,是,SECCESSOR=OLD，把它添到 BESTNODE的后繼節(jié)點(diǎn)表中,是,否,計(jì)算f值,技術(shù)課件,3.3 博弈樹搜索,3.3.1 博弈概述 何謂博弈？博弈就是下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能活動(dòng)。 “二人零和非偶然性全信息”博弈 （1）二人零和：對(duì)壘的MAX、MIN雙方輪流采取行動(dòng)，博弈的結(jié)果只有三種情況：MAX方勝，MIN方勝，和局。 （2）全信息：在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前格局及過(guò)去的歷史。 （3）非偶然性：任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對(duì)

22、自己最為有利而對(duì)對(duì)方最為不利的對(duì)策，不存在“碰運(yùn)氣”，“僥幸”及“偶然失誤”等隨機(jī)因素,技術(shù)課件,3.3 博弈樹搜索,3.3.1 博弈概述 參加博弈的各方都希望己方取得勝利。因此，當(dāng)一方面臨多個(gè)行動(dòng)方案選擇時(shí)，博弈的各方總是要挑選對(duì)自己最為有利而對(duì)對(duì)方最不利的那個(gè)行動(dòng)方案。 假如MAX方的目標(biāo)：盡可能使自己達(dá)到最大（或最高）的分?jǐn)?shù)分枝節(jié)點(diǎn)，可用“或”關(guān)系來(lái)描述，稱之為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)方案或分?jǐn)?shù)分枝節(jié)點(diǎn)之間，可以用“與”關(guān)系來(lái)描述，是由MIN方自主進(jìn)行控制的，故又稱之為MIN節(jié)點(diǎn),

23、技術(shù)課件,3.3 博弈樹搜索,3.3.1 博弈概述 把上述雙方逐層交替的博弈過(guò)程用與/或樹（圖）描述表達(dá)出來(lái)，就得到了一棵具有“與/或”節(jié)點(diǎn)交替出現(xiàn)的博弈樹。 博弈樹有如下特點(diǎn)： （1）博弈的初始格局是初始節(jié)點(diǎn)。 （2）在博弈樹中，由于雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)逐層交替出現(xiàn)。如果自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，則對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。 （3）把本方獲勝的終局定義為本原問(wèn)題，相應(yīng)最優(yōu)搜索路徑上的節(jié)點(diǎn)是可解節(jié)點(diǎn)，而所有使對(duì)方獲勝的終局和屬于對(duì)方最優(yōu)搜索路徑上的節(jié)點(diǎn)則是不可解節(jié)點(diǎn)。此外，所有其它的節(jié)點(diǎn)則是具有風(fēng)險(xiǎn)的中間節(jié)點(diǎn),技術(shù)課件,3.3 博弈樹搜索,3.3.2 極小

24、極大分析法 在二人博弈過(guò)程中，最直觀而可靠的常用分析方法就是極小極大化搜索法。其主要描述思想和算法： （1）設(shè)博弈的一方為MAX方，其目標(biāo)是盡可能使自己得到最高分；另一方為MIN方, 其目標(biāo)是盡可能給MAX方送出最低分。所謂極小極大化分析法是一種要輪流為每一方尋找一個(gè)最優(yōu)行動(dòng)方案的方法。在圖中，方框形狀“”表示是MAX方控制的或節(jié)點(diǎn)；圓形框形狀“”表示MIN方控制與節(jié)點(diǎn)。 （2）考慮每一方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并為其計(jì)算可能的得分； （3）為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹所有端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱為的靜態(tài)估值,技術(shù)課件,3.3 博弈樹

25、搜索,3.3.2極小極大分析法 （4）當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算父輩節(jié)點(diǎn)的等分，推算方法是：對(duì)“或”節(jié)點(diǎn)，選擇其子節(jié)點(diǎn)中最大的得分作為父輩節(jié)點(diǎn)的得分（選擇對(duì)自己最有利的方案）；對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為作為父輩節(jié)點(diǎn)的得分（立足于最壞的情況）。這樣計(jì)算出的父輩節(jié)點(diǎn)的等分稱為倒推值。 （5）如果一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。 存儲(chǔ)受限問(wèn)題：先生成一定深度的博弈樹，進(jìn)行極小極大分析，找出當(dāng)前的最好的行動(dòng)方案。然后再已選定的分支上再擴(kuò)展一定的深度，如此反復(fù),技術(shù)課件,3.3.2極小極大分析法,4 -1 -1 8 1 2 -5 0 -4 -9 -1,

26、5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6 -4 10 9 -1 12 5,MAX-MIN博弈樹的倒推值計(jì)算,h(S0)=,4 8 2 0 -1,4 -1,3.3 博弈樹搜索,技術(shù)課件,3.3 博弈樹搜索,3.3.3 -剪枝技術(shù) 基本思想：邊生成博弈樹邊估算各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)。 具體剪枝方法： （1） 對(duì)于一個(gè)“與”節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值上界，并且這個(gè)值不大于MIN的父輩節(jié)點(diǎn)（一定是“或”節(jié)點(diǎn)）的估計(jì)倒推值的下界，即 ，則就不必要再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。這一過(guò)程稱為剪枝。 （2

27、）對(duì)于一個(gè)“或”節(jié)點(diǎn)MAX，若能估計(jì)出其倒推值下界 ，并且這個(gè) 值不小于MAX的父輩節(jié)點(diǎn)（一定是“與”節(jié)點(diǎn)）的估計(jì)倒推值的上界 ，即 ，則就不必要再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。這一過(guò)程稱為 剪枝,技術(shù)課件,3.3 博弈樹搜索,3.3.3 -剪枝技術(shù) 從算法中看到： （1）MAX節(jié)點(diǎn)（包括起始節(jié)點(diǎn)）的值永不減少。 （2）MIN節(jié)點(diǎn)（包括起始節(jié)點(diǎn)）的值永不增加。 在搜索期間， 和 值的計(jì)算如下： （1）一個(gè)MAX節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。 （2）一個(gè)MIN節(jié)點(diǎn)的 值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值,技術(shù)課件,3.3 博弈樹搜索,3.3.3 -剪枝技術(shù) 例3.5 一字棋搜索樹

28、和值計(jì)算 估價(jià)函數(shù)g(p)定義如下： （1）若當(dāng)前棋局對(duì)任何一方都不是獲勝的，則 g(p)=(所有空格都放上MAX的棋子之后3個(gè)棋子所組成的行列及對(duì)角線的總數(shù)）（所有空格都放上MIN的棋子之后3個(gè)棋子所組成的行列及對(duì)角線的總數(shù)） （2）若p是MAX獲勝，則 g(p)=+ （3）若p是MIN獲勝，則 g(p)=- 上圖中，g(p)=6-4=2，其中表示MAX方， 表示MIN方,技術(shù)課件,3.3.3 -剪枝技術(shù),3.3 博弈樹搜索,初始節(jié)點(diǎn),-1,A,B,C,1,-1,6-5=1,5-5=0,6-5=1,5-5=0,4-5=-1,5-6=-1,技術(shù)課件,3.3.3 -剪枝技術(shù),3.3 博弈樹搜索,

29、4 -1 -1 8 1 2 -5 0 -4 -9 -1,5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6 -4 10 9 -1 12 5,MAX-MIN博弈樹的倒推值計(jì)算,h(S0)=,4 8 2 0 -1,4 -1,技術(shù)課件,3.3.3 -剪枝技術(shù),3.3 博弈樹搜索,h(S0)=,4,4,11,3,3,1,1,8,8,10,8,2,2,5,5,2,2,4,4,x5,5,4,博弈樹的-剪枝實(shí)現(xiàn)過(guò)程,技術(shù)課件,3.3 博弈樹搜索,3.3.3 -剪枝技術(shù) 要進(jìn)行-剪枝，必須至少使某一部分的搜索樹生長(zhǎng)到最大深度，因?yàn)楹椭当仨氁远斯?jié)點(diǎn)的靜態(tài)估值為依據(jù)。因此采用-剪枝技術(shù)

30、通常都要使用某種深度優(yōu)先的搜索方法,技術(shù)課件,3.4 遺傳算法,生物群體的生存過(guò)程普遍遵循達(dá)爾文的物競(jìng)天擇、適者生存的進(jìn)化準(zhǔ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è)染色體的數(shù)值來(lái)衡量；染色體的選擇或淘汰問(wèn)題是按求最大還是最小問(wèn)題來(lái)進(jìn)行。 遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過(guò)人工方式構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過(guò)程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的一種最重要形式,技術(shù)課件,3.4 遺傳算法,遺傳算法提出：于20世紀(jì)60年代由密歇根(Michigan)大學(xué)Hollstien,

31、 Bagleyh和Rosenberg等人在其博士論文中首先加以研究；1975年，美國(guó)J.H.Holland教授在其著作“Adaptation in Natural and Artificial Systems”中系統(tǒng)地闡述了遺傳算法，給出了遺傳算法的基本定理和大量的數(shù)學(xué)理論證明。 遺傳算法發(fā)展：David E. Goldberg教授1989年出版了 “Genetic Algorichms”一書，這一著作通常被認(rèn)為是遺傳算法的方法、理論及應(yīng)用的全面系統(tǒng)的總結(jié)。從1985年起，國(guó)際上開始陸續(xù)舉行遺傳算法的國(guó)際會(huì)議，后來(lái)又更名為進(jìn)化計(jì)算。參加進(jìn)化計(jì)算國(guó)際會(huì)議的人數(shù)及收錄文章的數(shù)量、廣度和深度逐年擴(kuò)大

32、。從此，進(jìn)化計(jì)算逐漸成為人們用來(lái)解決高度復(fù)雜問(wèn)題的新思路和新方法,技術(shù)課件,3.4 遺傳算法,遺傳算法特點(diǎn)：遺傳算法是一種基于空間搜索的算法，它通過(guò)自然選擇、遺傳、變異等操作以及達(dá)爾文適者生存的理論，模擬自然進(jìn)化過(guò)程來(lái)尋找所求問(wèn)題的解答。遺傳算法具有以下特點(diǎn)： (1) 遺傳算法是對(duì)參數(shù)集合的編碼而非針對(duì)參數(shù)本身進(jìn)行進(jìn)化； (2) 遺傳算法是從問(wèn)題解的編碼組開始而非從單個(gè)解開始搜索； (3) 遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來(lái)指導(dǎo)搜索； (4) 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作,技術(shù)課件,3.4 遺傳算法,遺傳算法應(yīng)用： J.H.H

33、olland博士于1975年提出遺傳算法,當(dāng)時(shí)并沒(méi)有引起學(xué)術(shù)界足夠的重視。直到二十世紀(jì)80年代中期,隨著計(jì)算機(jī)技術(shù)日新月異高速發(fā)展與進(jìn)步,遺傳算法首先成功地應(yīng)用于AI機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)方面;后來(lái)又在諸如函數(shù)優(yōu)化、自動(dòng)控制、圖象識(shí)別、分子生物學(xué)、優(yōu)化調(diào)度以及機(jī)械、土木、電力工程等工業(yè)系統(tǒng)和許多領(lǐng)域中得到應(yīng)用,顯示出誘人的前景。從此，遺傳算法始才得到學(xué)術(shù)界普遍關(guān)注與認(rèn)可,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 霍蘭德提出的遺傳算法通常稱為簡(jiǎn)單遺傳算法（SGA）?，F(xiàn)以此作為討論主要對(duì)象，加上適應(yīng)的改進(jìn)，來(lái)分析遺傳算法的結(jié)構(gòu)和機(jī)理。在討論中會(huì)結(jié)合銷售員旅行問(wèn)題（TSP）來(lái)說(shuō)明。 1

34、. 編碼與解碼 許多應(yīng)用問(wèn)題的結(jié)構(gòu)很復(fù)雜，但可以化為簡(jiǎn)單的位串形式編碼表示。將問(wèn)題結(jié)構(gòu)變換為位串形式編碼表示的過(guò)程叫編碼；而相反將位串形式編碼表示變換為原問(wèn)題結(jié)構(gòu)的過(guò)程叫解碼或譯碼。把位串形式編碼表示叫染色體，有時(shí)也叫個(gè)體,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 例：對(duì)于銷售員旅行問(wèn)題（Travelling salesman Problem, TSP），設(shè)有n個(gè)城市，城市i和城市j之間的距離為d(i,j)，要求找到一條遍訪每個(gè)城市一次而且恰好一次的旅行線路，使其路徑總長(zhǎng)度為最短。按一條回路中城市的次序進(jìn)行編碼。從城市w1開始，依次經(jīng)過(guò)城市w2 ，wn，最后回到城市w1，我們

35、就有如下編碼表示： w1 w2 wn 由于是回路，記wn+1=w1。它其實(shí)是1，n的一個(gè)循環(huán)排列。要注意w1，w2，wn是互不相同的,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 2. 適應(yīng)度函數(shù) 為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)（fitness function）。TSP的目標(biāo)是路徑總長(zhǎng)度為最短，自然地，路徑總長(zhǎng)度的倒數(shù)就可作為TSP問(wèn)題的適應(yīng)度函數(shù): 其中wn+1=w1 適應(yīng)度函數(shù)要有效反映每一個(gè)染色體與問(wèn)題的最優(yōu)解染色體之間的差距。適應(yīng)度函數(shù)的取值大小與求解問(wèn)題對(duì)象的意義有很大的關(guān)系,技術(shù)課件,3.4 遺傳算法,3.4.

36、1 遺傳算法的基本原理 3. 遺傳操作 簡(jiǎn)單遺傳算法的遺傳操作主要有有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。 選擇操作也叫復(fù)制（reproduction）操作，根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。 簡(jiǎn)單遺傳算法采用賭輪選擇機(jī)制，令fi表示群體的適應(yīng)度值之總和， fi表示種群中第i個(gè)染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額fi /fi,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 3. 遺傳操作 交叉操作的簡(jiǎn)單方式是將被選擇出的

37、兩個(gè)個(gè)體P1和P2作為父母?jìng)€(gè)體，將兩者的部分碼值進(jìn)行交換。 產(chǎn)生一個(gè)17之間的隨機(jī)數(shù)c，假設(shè)為3，則將P1和P2的低3位交換,P1,P2,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 3. 遺傳操作,P1,P2,Q1,Q2,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 3. 遺傳操作 變異操作的簡(jiǎn)單方式是改變數(shù)碼串的某個(gè)位置上的數(shù)碼。二進(jìn)制編碼表示的簡(jiǎn)單變異操作是將0與1互換：0變異為1，1變異為0。 隨機(jī)產(chǎn)生一個(gè)18之間的數(shù)k，假設(shè)k=5，對(duì)從右往左第5位變異操作,1,技術(shù)課件,3.4 遺傳算法,3.4.1 遺傳算法的基本原理 4. 控制參數(shù) 交叉發(fā)生的概率：0.

38、60.95 變異的概率：0.0010.01 種群的個(gè)數(shù)：30100 個(gè)體的長(zhǎng)度：定長(zhǎng)和變長(zhǎng),技術(shù)課件,3.4 遺傳算法,3.4.2 遺傳算法的結(jié)構(gòu) 選擇：由個(gè)體適應(yīng)度值決定 的某個(gè)規(guī)則。 交叉：按概率Pc進(jìn)行 變異：按概率Pm進(jìn)行 終止條件： 完成了預(yù)先給定的進(jìn)化代數(shù) 種群中的最優(yōu)個(gè)體在連續(xù)若干代 沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若 干代基本沒(méi)有改進(jìn),開始,初始化種群,選擇操作,終止條件,否,適應(yīng)度最有優(yōu)個(gè)體,計(jì)算適應(yīng)度值,交叉操作,變異操作,結(jié)束,技術(shù)課件,3.4 遺傳算法,3.4.3 遺傳算法的性能 遺傳算法求得的解是一滿意解。影響解質(zhì)量的因素： 種群的數(shù)量：太小缺少多樣性，太多影響效率 適應(yīng)度

39、函數(shù)：提升優(yōu)良個(gè)體的適應(yīng)度 交叉和變異：不同的問(wèn)題需構(gòu)造性能更優(yōu)的交叉和變異操作 交叉概率和變異概率,技術(shù)課件,分析：對(duì)該問(wèn)題雖然也可以采用枚舉的方法來(lái)解決,但枚舉法卻是一種效率很低的方法.可運(yùn)用遺傳算法來(lái)求解該問(wèn)題. 解：首先對(duì)問(wèn)題進(jìn)行初始化，以獲得初始種群; （1） 確定適當(dāng)?shù)木幋a方案：將x編碼表示為染色體的數(shù)字符號(hào)串。針對(duì)本題自變量x定義域,取值范圍為0，31,考慮采用二進(jìn)制數(shù)來(lái)對(duì)其編碼,由25 = 32,故使用5位無(wú)符號(hào)二進(jìn)制數(shù)組成染色體數(shù)字字符串,用以表達(dá)變量x及問(wèn)題的解答過(guò)程,例: 設(shè)有函數(shù)f(x)=x2, 請(qǐng)用遺傳算法求其自變量x在區(qū)間0，31 取整數(shù)值時(shí)的最大值，并說(shuō)明此函數(shù)的

40、優(yōu)化問(wèn)題,3.4 遺傳算法,技術(shù)課件,2）選擇初始種群:通過(guò)隨機(jī)的方法來(lái)產(chǎn)生染色體的數(shù)字串，并組成初始種群。例如，為得到數(shù)字串的某位又稱之為基因(genes)，使用計(jì)算機(jī)在01之間產(chǎn)生隨機(jī)數(shù)K，并按照數(shù)K的變化區(qū)域來(lái)規(guī)定基因代碼如下： 0， （0K0.5） 1， （0.5K1,3.4 遺傳算法,技術(shù)課件,于是隨機(jī)生成4個(gè)染色體的數(shù)字符串為： 01101 11000 01000 10011 從而構(gòu)造了初始種群，完成了遺傳算法的準(zhǔn)備,3.4 遺傳算法,技術(shù)課件,表 初始種群染色體及對(duì)應(yīng)的適應(yīng)值,3.4 遺傳算法,技術(shù)課件,3）復(fù)制(選擇): 選擇適應(yīng)值大的串作為母本，使在下一代中有更多的機(jī)會(huì)繁殖其

41、子孫。 要在四個(gè)種子個(gè)體中做選擇，要求仍然得到四個(gè)染色體，可依據(jù)適應(yīng)度概率比例制定如下規(guī)則： 低于0.125以下的染色體被淘汰； 在0.1250.375之間的染色體被復(fù)制一個(gè)； 在0.3750.625之間的染色體被復(fù)制兩個(gè)； 在0.6250.875之間的染色體被復(fù)制三個(gè)； 在0.875以上的染色體可復(fù)制四個(gè),3.4 遺傳算法,技術(shù)課件,對(duì)應(yīng)于上例，按照適應(yīng)度的計(jì)算，經(jīng)復(fù)制操作后，得到新的染色體種群為 01101 11000 11000 10011,3.4 遺傳算法,技術(shù)課件,某個(gè)染色體是否被復(fù)制,可以通過(guò)概率決策法、適應(yīng)度比例法或“輪盤賭”的隨機(jī)方法來(lái)斷定。對(duì)應(yīng)輪盤賭轉(zhuǎn)盤的隨機(jī)方法,根據(jù)表6.

42、1數(shù)據(jù)，繪制出的輪盤賭轉(zhuǎn)盤,如圖所示,進(jìn)化計(jì)算基本遺傳算法原理,01101 11000 11000 10011,技術(shù)課件,3.4 遺傳算法,初始種群染色體準(zhǔn)備復(fù)制操作的各項(xiàng)計(jì)算數(shù)據(jù),技術(shù)課件,4）交叉: 交叉具體分兩步：將新復(fù)制產(chǎn)生的染色體隨機(jī)兩兩匹配,稱其為雙親染色體；再把雙親染色體進(jìn)行交叉繁殖。 交叉的實(shí)現(xiàn): 設(shè)染色體數(shù)字串長(zhǎng)度為L(zhǎng)，把L個(gè)數(shù)字位間空隙分別標(biāo)記為： 1，2，L1 隨機(jī)從1，L1中選取某一整數(shù)位置k，0kL 交換雙親染色體交換點(diǎn)位置k右邊的部分，就形成了兩個(gè)新的數(shù)字符串（也可以只交換其中的第k基因），得到了兩個(gè)新的染色體，又稱之為下一代染色體,3.4 遺傳算法,技術(shù)課件,例如

43、，將上例初始種群的兩個(gè)體 A1=01101 A2=11000 假定從1到4間選取兩個(gè)隨機(jī)數(shù)，得到1=2，2=4，那么經(jīng)過(guò)交叉操作之后將得到如下兩組新的數(shù)字符串 A1#=01000 A2#=11101,3.4 遺傳算法,A3#=01100 A4#=11001,前一組數(shù)字串是使用1=2,即將第2位后的35位交換得到； 后一組數(shù)字串是使用2=4，即僅將第5位因子進(jìn)行交換而得,技術(shù)課件,3.4 遺傳算法,復(fù)制、交叉操作的各項(xiàng)數(shù)據(jù),技術(shù)課件,5）變異: 設(shè)變異概率取為0.001,則對(duì)于種群總共有20個(gè)基因位. 期望的變異串位數(shù)計(jì)算:200.001 =0.02(位), 故一般來(lái)說(shuō),該例中無(wú)基因位數(shù)值的改變.從表11-2和11-3可以看出,每經(jīng)過(guò)一次復(fù)制、交叉和變異操作后,目標(biāo)函數(shù)的最優(yōu)值和平均值就會(huì)有所提高。 在上例中，種群的平均適應(yīng)值從293增至446.5;最大的適應(yīng)度數(shù)值從576增至841。 特點(diǎn)：每經(jīng)一次進(jìn)化計(jì)算步驟,問(wèn)題解答便向著最優(yōu)方向前進(jìn)了一步;若該過(guò)程一直進(jìn)行下去,就將最終走向全局的最優(yōu)解.可見進(jìn)化計(jì)算的每一步操作簡(jiǎn)單,并且系統(tǒng)的求解過(guò)程是依照計(jì)算方法與規(guī)律來(lái)決定,與本源問(wèn)題自身的特性很少相關(guān),3.4 遺傳算法,技術(shù)課件,固體