人工智能試驗(yàn)指導(dǎo)書-15級(jí)物聯(lián)網(wǎng)

1、«人工智能技術(shù)導(dǎo)論實(shí)驗(yàn)指導(dǎo)書智控學(xué)院物聯(lián)網(wǎng)工程一實(shí)驗(yàn)綱要1二上機(jī)要求2三實(shí)驗(yàn)內(nèi)容3實(shí)驗(yàn)一圖搜索與問題求解3實(shí)驗(yàn)1.1啟發(fā)式搜索3實(shí)驗(yàn)1.2A*算法搜索9實(shí)驗(yàn)1.3其他應(yīng)用問題12實(shí)驗(yàn)二產(chǎn)生式系統(tǒng)推理14實(shí)驗(yàn)三TSP問題的遺傳算法實(shí)現(xiàn)20四實(shí)驗(yàn)報(bào)告模板27人工智能實(shí)驗(yàn)一實(shí)驗(yàn)報(bào)告錯(cuò)誤！未定義書簽。人工智能實(shí)驗(yàn)二實(shí)驗(yàn)報(bào)告28人工智能實(shí)驗(yàn)三實(shí)驗(yàn)報(bào)告29附件1TSP問題的遺傳算法程序模板30一實(shí)驗(yàn)綱要一實(shí)驗(yàn)教學(xué)的目的、任務(wù)與要求將人工智能基礎(chǔ)理論應(yīng)用于實(shí)際問題的解決當(dāng)中，加深學(xué)生對(duì)所學(xué)知識(shí)的理解，提高學(xué)生的實(shí)際動(dòng)手能力。二實(shí)驗(yàn)項(xiàng)目?jī)?nèi)容1圖搜索策略實(shí)驗(yàn)用啟發(fā)式搜索方法/A*算法求解重排九宮問題/

2、八數(shù)碼問題。2產(chǎn)生式系統(tǒng)的推理以動(dòng)物識(shí)別系統(tǒng)為例，實(shí)現(xiàn)基于產(chǎn)生式規(guī)則的推理系統(tǒng)。3TSP問題的遺傳算法實(shí)現(xiàn)以N個(gè)結(jié)點(diǎn)的TSP問題為例，用遺傳算法加以求解。三參考教材人工智能技術(shù)導(dǎo)論-第3版，廉師友編著，西安電子科技大學(xué)出版社，2007。四使用主要儀器設(shè)備說明在Windows2000/XP上，選用Java/C/C+/Matlab/Pr010go等語(yǔ)言進(jìn)行實(shí)現(xiàn)。五實(shí)驗(yàn)考核實(shí)驗(yàn)為16學(xué)時(shí)，分4次課完成。每個(gè)實(shí)驗(yàn)題目在課堂上分別按百分制給出。其中包括課堂紀(jì)律、程序運(yùn)行結(jié)果、課堂回答問題及實(shí)驗(yàn)報(bào)告成績(jī)等。實(shí)驗(yàn)課總成績(jī)?yōu)?個(gè)實(shí)驗(yàn)題目的平均成績(jī)。1考核方法每個(gè)題目完成后把源代碼和實(shí)驗(yàn)報(bào)告提交，由任課老師檢查

3、實(shí)驗(yàn)報(bào)告并給出報(bào)告成績(jī)。2評(píng)分標(biāo)準(zhǔn)（實(shí)驗(yàn)報(bào)告）每個(gè)實(shí)驗(yàn)題目根據(jù)以下標(biāo)準(zhǔn)進(jìn)行考核：1）考勤分20分。按時(shí)到課，無違紀(jì)現(xiàn)象20分；遲到或事假扣5分；無故缺勤，0分;2）預(yù)習(xí)情況10分。認(rèn)真完成課前預(yù)習(xí)者10分；不預(yù)習(xí)，0分；其他情況酌情給分。3）程序內(nèi)容成績(jī)30分。程序運(yùn)行正確，達(dá)到規(guī)定要求，20分；能在規(guī)定的要求上完成更完善的功能，或具有一定的界面效果，25分；特別優(yōu)秀者，30。具體在此基礎(chǔ)上酌情給分。4）實(shí)驗(yàn)報(bào)告成績(jī)30分。實(shí)驗(yàn)報(bào)告達(dá)到要求，最高分為30分。互相抄襲，記0分；其他情況酌情給分。5）回答問題成績(jī)10分?；卮饐栴}正確最高分為10分；回答問題均不正確，0分；其他情況酌情給分。6）第一

4、次實(shí)驗(yàn)課只記考勤，無故缺勤者總成績(jī)中扣5分。3實(shí)驗(yàn)報(bào)告在每個(gè)實(shí)驗(yàn)完成后，在規(guī)定時(shí)間內(nèi)提交實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)報(bào)告格式，參見學(xué)校實(shí)驗(yàn)報(bào)告模板。提交內(nèi)容：1）實(shí)驗(yàn)報(bào)告2）源代碼提交形式：將實(shí)驗(yàn)報(bào)告和源代碼壓縮成zip文件，命名為AI-班號(hào)-學(xué)號(hào)-姓名.zip二上機(jī)要求1 上機(jī)之前上機(jī)之前做好相關(guān)知識(shí)復(fù)習(xí)，上課時(shí)捎帶課本或參考書。提前了解實(shí)驗(yàn)內(nèi)容，并準(zhǔn)備好自己的算法。2 上機(jī)過程1 .根據(jù)提前設(shè)計(jì)的算法，進(jìn)行上機(jī)驗(yàn)證并調(diào)試，遇到問題及時(shí)解決；2 .上機(jī)時(shí)間，遵守實(shí)驗(yàn)室紀(jì)律；3 .在規(guī)定的時(shí)間內(nèi)向指導(dǎo)教師提交作業(yè)。各自保存好每次實(shí)驗(yàn)的源代碼，并在規(guī)定時(shí)間內(nèi)將源代碼和實(shí)驗(yàn)報(bào)告壓縮后提交。:實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一基礎(chǔ)實(shí)

5、驗(yàn)-熟悉PROLOG語(yǔ)言和上機(jī)運(yùn)行環(huán)境實(shí)驗(yàn)二圖搜索與問題求解本次實(shí)驗(yàn)主要用來熟悉圖搜索技術(shù)在具體問題中的求解過程，下面主要以八數(shù)碼問題展開，也可以以其它題目展開實(shí)驗(yàn)。實(shí)驗(yàn)2.1啟發(fā)式搜索一實(shí)驗(yàn)?zāi)康?熟悉和掌握啟發(fā)式搜索的定義、估價(jià)函數(shù)和算法過程；2理解和掌握啟發(fā)式搜索過程，能夠用選定的編程語(yǔ)言求解八數(shù)碼問題，理解求解流程和搜索順序；3比較并分析圖搜索策略的實(shí)質(zhì)，通過實(shí)驗(yàn)理解啟發(fā)式搜索的意義。二實(shí)驗(yàn)內(nèi)容以重排九宮問題/八數(shù)碼問題為例，以啟發(fā)式搜索方法求解給定初始狀態(tài)和目標(biāo)狀態(tài)的最優(yōu)搜索路徑。1重排九宮問題在一個(gè)3*3的方格棋盤上放置8個(gè)標(biāo)有1、2、3、4、5、6、7、8數(shù)字的將牌，留下一個(gè)空格（

6、一般用0表示），規(guī)定與空格上下左右相鄰的將牌可以移入空格。問題的解是要求尋找一條從某初始狀態(tài)S0到目標(biāo)狀態(tài)Sg的將牌移動(dòng)路線。如:28316475卜面給出初始狀態(tài)和目標(biāo)狀態(tài),初始棋局12384765目標(biāo)棋局1八數(shù)碼問題示例2問題描述要求用某種啟發(fā)式搜索方法求解從給定的初始狀態(tài)到目標(biāo)狀態(tài)的移動(dòng)路線。三實(shí)驗(yàn)要求1自己定義啟發(fā)式函數(shù)，能正確求解出從初始狀態(tài)到目標(biāo)狀態(tài)的移動(dòng)路線;2要求界面顯示初始狀態(tài)、目標(biāo)狀態(tài)和中間搜索步驟;3對(duì)不可達(dá)狀態(tài)能進(jìn)行正確識(shí)別；4對(duì)所采用的啟發(fā)式函數(shù)做出性能分析。四實(shí)驗(yàn)背景知識(shí)1圖搜索技術(shù)圖搜索技術(shù)是人工智能中的一個(gè)核心技術(shù)之一，人工智能的許多分支領(lǐng)域都涉及到圖搜索，在狀態(tài)

7、圖中尋找目標(biāo)或路徑的基本方法就是搜索。由于搜索具有探索性，所以要提高搜索效率(盡快地找到目標(biāo)節(jié)點(diǎn))，或要找最佳路徑(最佳解)就必須注意搜索策略。對(duì)于狀態(tài)圖搜索，已經(jīng)提出了許多策略，它們大體可分為盲目搜索和啟發(fā)式搜索兩大類。用計(jì)算機(jī)來實(shí)現(xiàn)狀態(tài)圖的搜索，有兩種最基本的方式：樹式搜索和線式搜索。樹式盲目搜索就是窮舉式搜索，而線式盲目搜索，對(duì)于不回溯的就是隨機(jī)碰撞式搜索，對(duì)于回溯的則也是窮舉式的搜索。樹式窮舉式搜索主要有廣度優(yōu)先搜索和深度優(yōu)先搜索。實(shí)踐表明，窮舉搜索只能解決一些狀態(tài)空間很小的簡(jiǎn)單問題，而對(duì)于那些大狀態(tài)空間問題，窮舉搜索就不能勝任了。因?yàn)榇罂臻g問題，往往會(huì)導(dǎo)致“組合爆炸”。所以必須探索更

8、有效的搜索方法，如啟發(fā)式搜索策略。2啟發(fā)式搜索啟發(fā)式搜索就是利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。一般來說，啟發(fā)信息強(qiáng)，可以降低搜索的工作量，但可能導(dǎo)致找不到最優(yōu)解；而啟發(fā)信息弱，一般會(huì)導(dǎo)致搜索的工作量加大，極端情況下演變?yōu)槊つ克阉?，但有可能找到最?yōu)解。我們希望，通過引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。按其用途劃分，啟發(fā)性信息可分為以下三類：(1)用于擴(kuò)展節(jié)點(diǎn)的選擇(2)用于生成節(jié)點(diǎn)的選擇節(jié)點(diǎn)。(3)用于刪除節(jié)點(diǎn)的選擇費(fèi)。,即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn),即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn),即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn)在啟發(fā)式搜索中，通常用所

9、謂啟發(fā)函數(shù)來表示啟發(fā)性信息。上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一種函數(shù)，通常記為h(x)。,以免盲目擴(kuò)展。,以免盲目地生成過多無用,以免造成進(jìn)一步的時(shí)空浪啟發(fā)函數(shù)是用來估計(jì)搜索樹啟發(fā)函數(shù)并無固定的模式，需要具體問題具體分析。通?？梢詤⒖嫉乃悸酚校阂粋€(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的度量；一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率；或者根據(jù)經(jīng)驗(yàn)的主觀打分等等。在八數(shù)碼問題種，啟發(fā)函數(shù)h(x)可定義為目標(biāo)狀態(tài)與當(dāng)前狀態(tài)相同的節(jié)點(diǎn)個(gè)數(shù)，或者當(dāng)前狀態(tài)每個(gè)節(jié)點(diǎn)到目標(biāo)狀態(tài)相應(yīng)節(jié)點(diǎn)所需步數(shù)的總和(水平的距離與豎直的距離和，也稱為曼哈頓路徑)。3八數(shù)碼問題的有解和無解判定將九宮格中數(shù)字順序排列后，形成一個(gè)包含0在內(nèi)的9位數(shù)字

10、序列，該字串可用來表示九宮格的當(dāng)前狀態(tài)，其中0表示空格所在位置。當(dāng)空格上下、左右移動(dòng)時(shí)，易知序列的逆序值奇偶性不會(huì)發(fā)生改變。由此可知，九宮問題的362,880種狀態(tài)被分成逆序值為奇數(shù)和逆序值為偶數(shù)兩部分，每一部分內(nèi)任意兩種狀態(tài)相互可達(dá)。在八數(shù)碼問題中，有些狀態(tài)之間是不可達(dá)的。如果我們能在一開始先判斷初始狀態(tài)和目標(biāo)狀態(tài)之間是否可達(dá)，這樣可以避免不可達(dá)狀態(tài)之間的盲目求解。兩個(gè)狀態(tài)之間是否可達(dá)可以通過兩個(gè)狀態(tài)逆序值的奇偶性進(jìn)行判斷。我們把每個(gè)狀態(tài)看作一個(gè)數(shù)列，然后計(jì)算數(shù)列的逆序值，若兩個(gè)數(shù)列逆序值的奇偶性相同，則對(duì)應(yīng)的兩個(gè)狀態(tài)是可達(dá)的，否則不可達(dá)。（注：求逆序值不把空格算在內(nèi)）。如圖2所示狀態(tài)：它對(duì)

11、應(yīng)的數(shù)列是：23158467（不包括空格）。對(duì)于一個(gè)數(shù)列，數(shù)列中每個(gè)數(shù)的逆序值是指位于這個(gè)數(shù)前面的比這個(gè)數(shù)大的數(shù)的個(gè)數(shù)。數(shù)列的逆序值就是數(shù)列中每個(gè)數(shù)的逆序值之和。逆序值求法：例：23158467的逆序值為6,求解過程為:0+0+2(1<2,1<3)+0+0+2(4<5,4<8)+1(6<8)+1(7<8)=6而狀態(tài)12345678的逆序值自然就是0。4曼哈頓路徑曼哈頓距離（ManhattanDistance）,又稱為出租車距離，是由十九世紀(jì)的赫爾曼閔可夫斯基所創(chuàng)詞匯，是種使用在幾何度量空間的幾何學(xué)用語(yǔ)，用以標(biāo)明兩個(gè)點(diǎn)上在標(biāo)準(zhǔn)坐標(biāo)系上的絕對(duì)軸距總和。圖3曼哈頓

12、距離示意圖我們可以定義曼哈頓距離的正式意義為L(zhǎng)1-距離或城市區(qū)塊距離，也就是在歐幾里德空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)軸產(chǎn)生的投影的距離總和。例如在平面上，坐標(biāo)（x1,y1）的點(diǎn)P1與坐標(biāo)（x2,y2）的點(diǎn)P2的曼哈頓距離為：|x1-x2|+|y1-y2|.要注意的是，曼哈頓距離依賴坐標(biāo)系統(tǒng)的轉(zhuǎn)度，而非系統(tǒng)在坐標(biāo)軸上的平移或映射。5康托展開(1)康托展開的公式：把一個(gè)整數(shù)X展開成如下形式：X=an*(n-1)!+an-1*(n-2)!+ai*(i-1)!+a2*1!+a1*0!其中，a為整數(shù)，并且0<=ai<i(1<=i<=n)(2)康托展開的應(yīng)用實(shí)例(1,2,

13、3,4,.,n)表示1,2,3,.,n的排列如1,2,3)按從小到大排列一共6個(gè)。123132213231312321。代表的數(shù)字123456也就是把10進(jìn)制數(shù)與一個(gè)排列對(duì)應(yīng)起來。他們間的對(duì)應(yīng)關(guān)系可由康托展開來找到，如想知道321是1,2,3)中第幾個(gè)大的數(shù)可以這樣考慮：第一位是3,當(dāng)?shù)谝晃坏臄?shù)小于3時(shí)，那排列數(shù)小于321如123、213，小于3的數(shù)有1、2。所以有2*2!個(gè)。再看小于第二位2的：小于2的數(shù)只有一個(gè)就是1,所以有1*1!=1所以小于321的1,2,3)排列數(shù)有2*2!+1*1!=5個(gè)。所以321是第6個(gè)大的數(shù)。2*2!+1*1!是康托展開。再舉個(gè)例子：1324是1,2,3,4)

14、排列數(shù)中第幾個(gè)大的數(shù)：第一位是1小于1的數(shù)沒有，是0個(gè)0*3!第二位是3小于3的數(shù)有1和2,但1已經(jīng)在第一位了，所以只有一個(gè)數(shù)21*2!。第三位是2小于2的數(shù)是1,但1在第一位，所以有0個(gè)數(shù)0*1!,所以比1324小的排列有0*3!+1*2!+0*1!=2個(gè)，1324是第三個(gè)大數(shù)。(3)康托展開的啟示圖搜索求解中，對(duì)于頻繁訪問的OPEN!和CLOSER,有時(shí)需要判斷兩個(gè)節(jié)點(diǎn)是否相同，求節(jié)點(diǎn)序列的康托展開是個(gè)不錯(cuò)的方法。五實(shí)驗(yàn)關(guān)鍵技術(shù)1全局擇優(yōu)啟發(fā)式算法步1把初始節(jié)點(diǎn)S0放入OPE破中，計(jì)算h(S0);步2若OPEN1為空，則搜索失敗，退出。步3移出OPEN1中第一個(gè)節(jié)點(diǎn)N放入CLOSER中，并

15、冠以序號(hào)n；步4若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功，結(jié)束。步5若N不可擴(kuò)展，則轉(zhuǎn)步2;步6擴(kuò)展N,計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值h(x),并將所有子節(jié)點(diǎn)配以指向N的返回指針后放入OPEN1中，再對(duì)OPEN!中的所有子節(jié)點(diǎn)按其函數(shù)值大小以升序排序，轉(zhuǎn)步2。2CLOSED和OPEN1的設(shè)計(jì)CLOSED1和OPEN1的設(shè)計(jì)是圖搜索程序?qū)崿F(xiàn)中一個(gè)關(guān)鍵問題。我們用一個(gè)稱為CLOSED1的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來專門記錄考查過的節(jié)點(diǎn)。對(duì)于樹式搜索來說，CLOSED1中存儲(chǔ)的正是一棵不斷成長(zhǎng)的搜索樹；采用一個(gè)稱為OPEN1的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，來專門登記當(dāng)前待考查的節(jié)點(diǎn)。CLOSED1和OPE破的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)比較靈活，和具體采用的算

16、法密切相關(guān)，這里列舉兩個(gè)示例：(1)采用結(jié)構(gòu)體數(shù)組示例typedefstruct(intindex;/結(jié)點(diǎn)序號(hào)intParent;/父結(jié)點(diǎn)序號(hào)intGridSIZESIZE;/八數(shù)碼狀態(tài)intH;/啟發(fā)式函數(shù)值State;StateOPENMAXSIZE;/存放已經(jīng)生成的未考察的節(jié)點(diǎn)StateCLOSEMAXSIZE;/存放已經(jīng)考察過得節(jié)點(diǎn)(2)采用鏈表存儲(chǔ)示例structLNode/(intindex;/intH;/intGrid9;/intzeroposition;/structLNode*parent;/structLNode*child4;/structLNode*next;typed

17、efstructLHead/(intnum;structLNode*first;普通結(jié)點(diǎn)，存儲(chǔ)八數(shù)碼信息結(jié)點(diǎn)序號(hào)啟發(fā)式函數(shù)值八數(shù)碼狀態(tài)空格的位置指向父節(jié)點(diǎn)指向子節(jié)點(diǎn)(最多有四個(gè))頭結(jié)點(diǎn)LinkListLopen,Lclose;/定義才旨向open、close表的指針LHead,*LinkList;六實(shí)驗(yàn)檢查要求1界面顯示要求：(1)包含初始狀態(tài)和目標(biāo)狀態(tài)的顯示，可由指導(dǎo)老師隨機(jī)輸入狀態(tài)進(jìn)行檢查；(2)對(duì)不可達(dá)狀態(tài)應(yīng)給出提示；(3)每次搜索過程的步驟，不要求顯示樹型結(jié)構(gòu)，只要求(動(dòng)畫)表現(xiàn)，每走一步的狀態(tài)變化；(4)每走一次搜索步，需要有步數(shù)的累積顯示；（5）最后有完成一次搜索完畢的結(jié)果顯示。2

18、 代碼要求檢查時(shí)要求提供源代碼。3 講解要求open要求學(xué)生講解自己設(shè)計(jì)代碼的構(gòu)架，具體實(shí)現(xiàn)方法（包含使用了何種數(shù)據(jù)結(jié)構(gòu),表和close表的結(jié)構(gòu)等）；要求學(xué)生說明自己所使用的搜索算法，以及程序運(yùn)行效果。4 回答輔導(dǎo)老師提出的問題。5 提交實(shí)驗(yàn)報(bào)告（課后把實(shí)驗(yàn)報(bào)告和源代碼在規(guī)定的時(shí)間內(nèi)提交到指定郵箱里）實(shí)驗(yàn)2.2A*算法搜索一實(shí)驗(yàn)?zāi)康?加深對(duì)各種狀態(tài)圖搜索策略概念的理解；2熟悉和掌握A搜索的定乂、估價(jià)函數(shù)和算法過程；*、一一.一.、3理解和掌握A搜索過程，能夠用選定的編程語(yǔ)言求解八數(shù)碼問題，理解求解流程和搜索順序；4通過實(shí)驗(yàn)掌握估價(jià)函數(shù)的計(jì)算方法，理解估價(jià)函數(shù)定義的意義。二實(shí)驗(yàn)內(nèi)容_一一.*.-

19、.,.一.以重排九宮問題/八數(shù)碼問題為例，以A搜索算法求解給定初始狀態(tài)和目標(biāo)狀態(tài)的最優(yōu)搜索路徑。三實(shí)驗(yàn)要求1自己定義估價(jià)函數(shù)，能正確求解出從初始狀態(tài)到目標(biāo)狀態(tài)的移動(dòng)路線；2要求界面顯示初始狀態(tài)、目標(biāo)狀態(tài)和中間搜索步驟；3對(duì)不可達(dá)狀態(tài)能進(jìn)行正確識(shí)別；4對(duì)所采用的估價(jià)函數(shù)做出性能分析，分析g(n)和h(n)的主要作用是什么，以及不同取值的實(shí)驗(yàn)效果，并進(jìn)行分析。四實(shí)驗(yàn)背景知識(shí)一一.*.-.-一.A算法和A算法是圖搜索的兩種典型的啟發(fā)式搜索算法。1 A算法A算法是在圖搜索算法中的樹式搜索算法中增加了估價(jià)函數(shù)f(x)的一種啟發(fā)式搜索算法。估價(jià)函數(shù)的一般形式為：f(x)=g(x)+h(x)其中g(shù)(x)為從

20、初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)付出的代價(jià)，h(x)是啟發(fā)函數(shù)，表示估計(jì)搜索樹上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度。估價(jià)函數(shù)f(x)是從初始節(jié)點(diǎn)So到達(dá)節(jié)點(diǎn)x處已付出的代價(jià)與節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計(jì)值之總和。有時(shí)估價(jià)函數(shù)還可以表示為f(x)=d(x)+h(x)其中d(x)表示節(jié)點(diǎn)x的深度。f(x)中的g(x)或d(x)有利于搜索的橫向發(fā)展，h(x)則有利于搜索的縱向發(fā)展，因而可提高搜索的效率和搜索的完備性。但在確定f(x)時(shí)，要權(quán)衡利弊，使g(x)(或d(x)與h(x)的比重適當(dāng)，這樣才能取得理想的效果。2 A*算法對(duì)A算法限制其估價(jià)函數(shù)中的啟發(fā)函數(shù)h(x),使其滿足：對(duì)所有的節(jié)點(diǎn)x均有：h(x

21、)<h*(x)其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)(若有多個(gè)目標(biāo)節(jié)點(diǎn)則為其中最小的一個(gè))，則匕就稱為A算法。A算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于一般的有序搜索，總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，所以，可考慮每個(gè)節(jié)點(diǎn)x的估價(jià)函數(shù)值為兩個(gè)分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn)x的代價(jià)以及從節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)的代價(jià)。3估價(jià)函數(shù)示例f(x)=g(x)+h(x),其中g(shù)(x)為初始節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)的所花步數(shù)，h(x)為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的曼哈頓距離。估計(jì)函數(shù)為到達(dá)當(dāng)前節(jié)點(diǎn)步數(shù)和Manhattan距離之和，由相關(guān)*資料得Ma

22、nhattan距離h(x)滿足h(x)-h(x)，其中h(x)是當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小.-*代價(jià)，所以此估價(jià)函數(shù)對(duì)應(yīng)為A算法?？梢杂梅醋C法來證明上述估計(jì)函數(shù)滿足A*算法要求。若存在最佳路徑且長(zhǎng)度為L(zhǎng)1,a為最佳路徑上的任意一節(jié)點(diǎn)，假設(shè)A*沒有得出最優(yōu)解，其求出路徑長(zhǎng)度為L(zhǎng)2>L1,b為其求解路徑上的終結(jié)點(diǎn)。因?yàn)楣纼r(jià)函數(shù)f(n)=step+h(n),h(n)<=n(n為到目標(biāo)的實(shí)際路徑)。所以f(a)<=L1,f(b)=L2,推出f(a)<f(b),在小頂堆中是不可能先發(fā)展b而不發(fā)展a的。與A*算法矛盾。五實(shí)驗(yàn)關(guān)鍵技術(shù)下面給出A算法的具體步驟：步1把附有f(S0)的初

23、始節(jié)點(diǎn)S0放入OPEN1;步2若OPEN1為空，則搜索失敗，退出。步3移出OPEN1中第一個(gè)節(jié)點(diǎn)N放入CLOSED1中，并冠以順序編號(hào)n；步4若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功，結(jié)束。步5若N不可擴(kuò)展，則轉(zhuǎn)步2;步6擴(kuò)展N,生成一組附有f(x)的子節(jié)點(diǎn)，對(duì)這組子節(jié)點(diǎn)作如下處理：(1)考察是否有已在OPEN或CLOSED!中存在的節(jié)點(diǎn)；若有則再考察其中有無N的先輩節(jié)點(diǎn)，若有則刪除之；對(duì)于其余節(jié)點(diǎn)，也刪除之，但由于它們又被第二次生成，因而需考慮是否修改已經(jīng)存在于OPEN!或CLOSER中的這些節(jié)點(diǎn)及其后裔的返回指針和f(x)值，修改原則是“抄f(x)值小的路走”；(2)對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針

24、后放入OPEN1中，并對(duì)OPEN1按f(x)值以升序排序，轉(zhuǎn)步2。六實(shí)驗(yàn)檢查要求1界面顯示要求：(1)包含初始狀態(tài)和目標(biāo)狀態(tài)的顯示，可由指導(dǎo)老師隨機(jī)輸入狀態(tài)進(jìn)行檢查；10(2)每次搜索過程的步驟，不要求樹型結(jié)構(gòu)，只要求(動(dòng)畫)表現(xiàn)，每走一步的狀態(tài)變化；(3)每走一次搜索步，需要有步數(shù)的累積顯示；(4)最后有完成一次搜索完畢的結(jié)果顯示。2 代碼要求檢查時(shí)要求提供源代碼。3 講解要求open要求學(xué)生講解自己設(shè)計(jì)代碼的構(gòu)架，如何實(shí)現(xiàn)的(包含使用了何種數(shù)據(jù)結(jié)構(gòu)，表和close表的結(jié)構(gòu)等)；要求學(xué)生說明自己所使用的估價(jià)函數(shù)，以及程序運(yùn)行效果。4 回答輔導(dǎo)老師提出的問題。5提交實(shí)驗(yàn)報(bào)告(課后把實(shí)驗(yàn)報(bào)告和源

25、代碼在規(guī)定的時(shí)間內(nèi)提交到指定郵箱里)11實(shí)驗(yàn)2.3其他應(yīng)用問題一迷宮問題走迷宮是人們熟悉的一種游戲，如下圖就是一個(gè)迷宮。如果我們把該迷宮的每一個(gè)格子以及入口和出口都作為節(jié)點(diǎn)，把通道作為邊，則該迷宮可以由一個(gè)有向圖表示(如圖4所示)。那么，走迷宮其實(shí)就是從該有向圖的初始節(jié)點(diǎn)S0(入口)出發(fā)，尋找目標(biāo)節(jié)點(diǎn)Sg(出口)的問題，或者是尋找通向目標(biāo)節(jié)點(diǎn)(出口)的路徑的問題。11SiS2S3+S4S5S6+S7S8S91|So*圖4迷宮圖請(qǐng)用圖搜索算法進(jìn)行求解。二八皇后問題八皇后問題，是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八

26、個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后，有多種方法可以解決此問題。請(qǐng)用圖搜索算法進(jìn)行求解。三一字棋游戲設(shè)有一個(gè)三行三列的棋盤，兩個(gè)棋手A,B輪流走步，每個(gè)棋手走步時(shí)往空格上擺一個(gè)自己的棋子，誰先使自己的棋子成三子一線為贏。初始棋盤各走一步后棋盤圖5一字棋設(shè)A的棋子用“a”表示，B的棋子用“b”表示。為了不致于生成太大的博弈樹，假設(shè)每次僅擴(kuò)展兩層。估價(jià)函數(shù)定義如下：設(shè)棋局為P,估價(jià)函數(shù)為e(P)。(1) 若P是A

27、必勝的棋局，則e(P)=+8。(2) 若P是B必勝的棋局，則e(P)=-»(3)若P是勝負(fù)未定的棋局，則e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使a成為三子成一線的數(shù)目；e(-P)表示棋局P上有可能使b成為三子成一線的數(shù)目。例如，對(duì)于上圖所示的棋局，則12e(P)=6-4=2另外，我們假定具有對(duì)稱性的兩個(gè)棋局算作一個(gè)棋局。還假定A先走棋，我們站在A的立場(chǎng)上。下圖給出了A的第一著走棋生成的博弈樹。圖中節(jié)點(diǎn)旁的數(shù)字分別表示相應(yīng)節(jié)點(diǎn)的靜態(tài)估值或倒推值。由圖可以看出，對(duì)于A來說最好的一著棋是與，因?yàn)镾3比S和S2有較大的倒推值。圖6一字棋極小極大搜索請(qǐng)用圖搜索算法進(jìn)行

28、求解，并要求應(yīng)用a-3剪枝技術(shù)。13實(shí)驗(yàn)三產(chǎn)生式系統(tǒng)推理一實(shí)驗(yàn)?zāi)康?熟悉和掌握產(chǎn)生式系統(tǒng)的構(gòu)成和運(yùn)行機(jī)制；2掌握基于規(guī)則推理的基本方法和技術(shù)，掌握正確的正向推理和逆向推理方法；3熟悉在具體問題中如何實(shí)現(xiàn)正向推理和逆向推理的求解流程。二實(shí)驗(yàn)內(nèi)容以動(dòng)物識(shí)別系統(tǒng)為例，用選定的編程語(yǔ)言建造規(guī)則庫(kù)和綜合數(shù)據(jù)庫(kù)，并能對(duì)它們進(jìn)行增加、刪除和修改操作，開發(fā)能進(jìn)行正確的正向推理或反向推理的推理機(jī)。1動(dòng)物分類規(guī)則集(I)(1)若某動(dòng)物有奶，則它是哺乳動(dòng)物。(2)若某動(dòng)物有毛發(fā)，則它是哺乳動(dòng)物。(3)若某動(dòng)物有羽毛，則它是鳥。(4)若某動(dòng)物會(huì)飛且生蛋，則它是鳥。(5)若某動(dòng)物是哺乳動(dòng)物且有爪且有犬齒且目盯前方，則它

29、是食肉動(dòng)物。(6)若某動(dòng)物是哺乳動(dòng)物且吃肉，則它是食肉動(dòng)物。(7)若某動(dòng)物是哺乳動(dòng)物且有蹄，則它是有蹄動(dòng)物。(8)若某動(dòng)物是有蹄動(dòng)物且反芻食物，則它是偶蹄動(dòng)物。(9)若某動(dòng)物是食肉動(dòng)物且黃褐色且有黑色條紋，則它是老虎。(10)若某動(dòng)物是食肉動(dòng)物且黃褐色且有黑色斑點(diǎn)，則它是金錢豹。(11)若某動(dòng)物是有蹄動(dòng)物且長(zhǎng)腿且長(zhǎng)脖子且黃褐色且有暗斑點(diǎn)，則它是長(zhǎng)頸鹿。(12)若某動(dòng)物是有蹄動(dòng)物且白色且有黑色條紋，則它是斑馬。(13)若某動(dòng)物是鳥且不會(huì)飛且長(zhǎng)腿且長(zhǎng)脖子且黑白色，則它是駝鳥。(14)若某動(dòng)物是鳥且不會(huì)飛且會(huì)游泳且黑白色，則它是企鵝。(15)若某動(dòng)物是鳥且善飛且不怕風(fēng)浪，則它是海燕。下面是該規(guī)則集所

30、形成的(部分)推理網(wǎng)絡(luò)：14老虎金錢豹長(zhǎng)頸鹿2問題描述由上述動(dòng)物識(shí)別規(guī)則組成規(guī)則庫(kù)，推理機(jī)分別采用正向推理算法或反向推理算法，實(shí)現(xiàn)對(duì)動(dòng)物的查詢。如給出初始事實(shí)：F1:某動(dòng)物有毛發(fā)F2:吃肉F3:黃褐色F4:有黑色條紋目標(biāo)條件為：該動(dòng)物是什么？3規(guī)則庫(kù)擴(kuò)充在上述規(guī)則集(I)基礎(chǔ)上增加以下規(guī)則集(n)：(1)兔子：有毛發(fā)，有奶，善跳躍，唇裂；(2)貓：有毛發(fā)，有奶，善捕鼠，腳有肉墊；(3)犀牛：有毛發(fā)，有奶，鼻子上有角，褐色，皮糙肉后，皮糙肉厚，有蹄；(4)熊貓：有毛發(fā)，有奶，黑眼圈，四肢短小；(5)鸚鵡：鳥類，上嘴鷹鉤，會(huì)模仿人說話；(6)鴨子：鳥類，腿短，嘴扁平，善潛水游泳；(7)鷹：鳥類，上

31、嘴鷹鉤，有爪，吃肉；(8)鴨子：有羽毛，卵生，善游泳，嘴扁平，腿短；(9)鵝：有羽毛，卵生，善潛水游泳，白色或黑色，頸長(zhǎng)，嘴大，腿長(zhǎng)，頸部有肉只凸起；(10)鴉：有羽毛，卵生，黑色，嘴大；(11)鷹：有羽毛，卵生，有爪，吃肉，上嘴鷹鉤；(12)鸚鵡：有羽毛，卵生，上嘴鷹鉤，能模仿人說話；(13)青蛙：卵生，生活在水中，生活在陸地，有皮膚呼吸，用肺呼吸，皮膚光滑，吃昆蟲，15會(huì)變色；(14)蛛螂：卵生，生活在水中，生活在陸地，有皮膚呼吸，用肺呼吸，吃昆蟲，皮膚粗糙,四肢扁，背部黑色；(15)蟾蛛：卵生，生活在水中，生活在陸地，有皮膚呼吸，用肺呼吸，吃昆蟲，皮膚粗糙;(16)比目魚：用鯉呼吸，身體

32、有鰭，生活在海洋中，身體扁平，兩眼在頭部同側(cè)；(17)鯽魚：用鯉呼吸，身體有鰭，生活在淡水中，身體扁平，頭高尾部窄；(18)蛇：生活在陸地，用肺呼吸，胎生，身體有鱗或甲，身體圓而細(xì)長(zhǎng)，吃小動(dòng)物；(19)壁虎：生活在陸地，用肺呼吸，胎生，身體有鱗或甲，有四肢，尾巴細(xì)長(zhǎng)易斷，吃昆蟲；(20)烏龜：生活在陸地，用肺呼吸，胎生，身體有鱗或甲，身體圓而扁，有堅(jiān)硬的殼；(21)玳瑁：生活在陸地，用肺呼吸，胎生，身體有鱗或甲，殼為黃褐色，皮膚光滑，有黑斑；(22)鱷魚：生活在陸地，用肺呼吸，胎生，身體有鱗或甲，有四肢，善游泳，皮硬黑褐色。要求在動(dòng)物分類規(guī)則集(I)的基礎(chǔ)上添加上述22條知識(shí)，共構(gòu)成29種動(dòng)物

33、的知識(shí)庫(kù)系統(tǒng)，對(duì)原有動(dòng)物分類系統(tǒng)進(jìn)行擴(kuò)充和修改。三實(shí)驗(yàn)要求1以產(chǎn)生式推理模式為基礎(chǔ)，實(shí)現(xiàn)小型動(dòng)物分類系統(tǒng)，推理方法可以采用正向推理或反向推理；2要求表示規(guī)則的語(yǔ)言必須能體現(xiàn)出規(guī)則前提和結(jié)論的對(duì)應(yīng)關(guān)系，必須能體現(xiàn)出前提和結(jié)論中的邏輯關(guān)系；3要求能對(duì)規(guī)則庫(kù)進(jìn)行動(dòng)態(tài)地增加、刪除和修改操作；4要求用界面顯示要查詢的初始事實(shí)、推理方法、推理中用到的規(guī)則和結(jié)論。四實(shí)驗(yàn)背景知識(shí)1產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)是人工智能系統(tǒng)的一種最典型最普遍的結(jié)構(gòu)形式，許多專家系統(tǒng)都是以產(chǎn)生式系統(tǒng)的形式實(shí)現(xiàn)的，有的機(jī)器學(xué)習(xí)系統(tǒng)也是用產(chǎn)生式系統(tǒng)實(shí)現(xiàn)的。產(chǎn)生式系統(tǒng)由三部分組成：產(chǎn)生式規(guī)則庫(kù)、推理機(jī)和動(dòng)態(tài)數(shù)據(jù)庫(kù)，其結(jié)構(gòu)如圖所示：圖8產(chǎn)生式系

34、統(tǒng)結(jié)構(gòu)2產(chǎn)生式的一般形式產(chǎn)生式的一般形式為：16前件-后件其中，前件就是前提，后件是結(jié)論或動(dòng)作，前件和后件可以是由邏輯運(yùn)算符ANDORNOT組成的表達(dá)式。產(chǎn)生式規(guī)則的語(yǔ)義是：如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動(dòng)作，即后件由前件來觸發(fā)。所以，前件是規(guī)則的執(zhí)行條件，后件是規(guī)則體。3產(chǎn)生式規(guī)則的程序語(yǔ)言實(shí)現(xiàn)在實(shí)踐中人們往往把規(guī)則的前提部分作成形如：條件iAN陳彳2AN0AN陳彳n或條件iOR條彳2OR-OR條件m的形式（其中的條件可以帶否定詞）；把規(guī)則結(jié)論部分作成形如斷言i/動(dòng)作iANE®T言2/動(dòng)作2ANED-ANE®t言k/動(dòng)作k或斷言i/動(dòng)作iOR斷言2/動(dòng)作2OR-O

35、即言k/動(dòng)作k的形式，或者進(jìn)一步簡(jiǎn)化成斷言/動(dòng)作即僅有一項(xiàng)的形式。如果推理機(jī)不能直接支持上述的謂詞或元組表示形式，那么，可用通常的記錄、數(shù)組、結(jié)構(gòu)、函數(shù)等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)規(guī)則中的條件和斷言，用通常的賦值式、運(yùn)算式、函數(shù)、過程等形式實(shí)現(xiàn)規(guī)則中的動(dòng)作。表示規(guī)則的語(yǔ)言在程序執(zhí)行時(shí)必須能體現(xiàn)出規(guī)則前提和結(jié)論的對(duì)應(yīng)關(guān)系，必須能體現(xiàn)出前提和結(jié)論中的邏輯關(guān)系。例如我們完全可以用一個(gè)二元組：（<前件>,<后件>）表示一個(gè)產(chǎn)生式規(guī)則。五實(shí)驗(yàn)關(guān)鍵技術(shù)i產(chǎn)生式系統(tǒng)推理算法產(chǎn)生式系統(tǒng)的推理可分為正向推理和反向推理兩種基本方式。（i）正向推理步i將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫(kù)；步2用動(dòng)態(tài)數(shù)據(jù)庫(kù)中的

36、事實(shí)/數(shù)據(jù)，匹配/測(cè)試目標(biāo)條件，若目標(biāo)條件滿足，則推理成功，結(jié)束。步3用規(guī)則庫(kù)中各規(guī)則的前提匹配動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí)/數(shù)據(jù)，將匹配成功的規(guī)則組成待用規(guī)則集；步4若待用規(guī)則集為空，則運(yùn)行失敗，退出。步5將待用規(guī)則集中各規(guī)則的結(jié)論加入動(dòng)態(tài)數(shù)據(jù)庫(kù)，或者執(zhí)行其動(dòng)作，轉(zhuǎn)步2;i7(2)反向推理步1將初始事實(shí)/數(shù)據(jù)置入動(dòng)態(tài)數(shù)據(jù)庫(kù)，將目標(biāo)條件置入目標(biāo)鏈；步2若目標(biāo)鏈為空，則推理成功，結(jié)束。步3取出目標(biāo)鏈中第一個(gè)目標(biāo)，用動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí)/數(shù)據(jù)同其匹配，若匹配成功，轉(zhuǎn)步2;步4用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配成功，則將第一個(gè)匹配成功且未用過的規(guī)則的前提作為新的目標(biāo)，并取代原來的父目標(biāo)而加入目標(biāo)鏈，轉(zhuǎn)

37、步3;步5若該目標(biāo)是初始目標(biāo)，則推理失敗，退出。步6將該目標(biāo)的父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄弟目標(biāo)，轉(zhuǎn)步3;2事實(shí)和規(guī)則程序代碼示例事實(shí)多用數(shù)字來表征。規(guī)則集在程序中可用數(shù)組來存放，如：boolenfactfactnum;structrule(intcon10;intres;rulerulesrulenum=2,-1,24,3,-1,24,7,-1,23,8,9,-1,23,24,0,1,4,-1,22,24,5,-1,22,24,6,-1,25,22,21,20,-1,26,22,21,19,-1,27,25,15,16,21,17,-1,28,25,18,20,-1,29,23,10,

38、15,16,11,-1,30,23,10,12,11,-1,31,23,13,14,-1,32規(guī)則集也可以記錄在.txt文件中，在程序中讀入文件，.txt文件示例如下:1 242 243 254,62524, 6,7,82624,92624,102727,112826,12,132926,12,143027,15,16,12,173127,18,133225, 19,16,16,203325,19,21,203425,22,2335圖9規(guī)則集文件示例上述示例中的數(shù)字代表的是規(guī)則中的一些知識(shí)，這里只作示例，具體代表內(nèi)容不詳細(xì)介紹。18六實(shí)驗(yàn)檢查要求1界面顯示要求(1)有若干選擇動(dòng)物特征的選擇列表

39、；(2)表現(xiàn)判斷動(dòng)物時(shí)，使用了哪些規(guī)則；(3)顯示規(guī)則的調(diào)用次序；(4)顯示最后的結(jié)果，包含動(dòng)物能識(shí)別出來和動(dòng)物不能識(shí)別出來兩種情況；(5)至少檢查兩個(gè)例子來檢驗(yàn)推理系統(tǒng)的正確與全面性。2代碼要求要求學(xué)生展示如何表征事實(shí)和特征的知識(shí)、所有規(guī)則的代碼、控制策略的代碼。3講解要求要求學(xué)生講解采用的推理算法，規(guī)則的程序表示方法，規(guī)則庫(kù)如何動(dòng)態(tài)修改等，并說明程序運(yùn)行效果。4回答輔導(dǎo)老師提出一些問題。5提交實(shí)驗(yàn)報(bào)告(課后把實(shí)驗(yàn)報(bào)告和源代碼在規(guī)定的時(shí)間內(nèi)提交到指定郵箱里)。19實(shí)驗(yàn)四TSP問題的遺傳算法實(shí)現(xiàn)一實(shí)驗(yàn)?zāi)康?熟悉和掌握遺傳算法的基本概念和基本思想；2理解和掌握遺傳算法的各個(gè)操作算子，能夠用選定的

40、編程語(yǔ)言設(shè)計(jì)簡(jiǎn)單的遺傳優(yōu)化系統(tǒng)；3通過實(shí)驗(yàn)培養(yǎng)學(xué)生利用遺傳算法進(jìn)行問題求解的基本技能。二實(shí)驗(yàn)內(nèi)容以N個(gè)節(jié)點(diǎn)的TSP(旅行商問題)問題為例，應(yīng)用遺傳算法進(jìn)行求解，求出問題的最優(yōu)解。1旅行商問題旅行商問題(TravelingSalesmanProblem,TSP),又譯為旅行推銷員問題、貨擔(dān)郎問題，簡(jiǎn)稱為TSP問題，是最基本的路線問題。假設(shè)有n個(gè)可直達(dá)的城市，一銷售商從其中的某一城市出發(fā)，不重復(fù)地走完其余n-1個(gè)城市并回到原出發(fā)點(diǎn)，在所有可能的路徑中求出路徑長(zhǎng)度最短的一條。TSP問題是組合數(shù)學(xué)中一個(gè)古老而又困難的問題，也是一個(gè)典型的組合優(yōu)化問題，現(xiàn)已歸入NP完備問題類。NP問題用窮舉法不能在有效時(shí)

41、間內(nèi)求解，所以只能使用啟發(fā)式搜索。遺傳算法是求解此類問題比較實(shí)用、有效的方法之一。下面給出30個(gè)城市的位置信息：表1OliverTSP問題的30個(gè)城市位置坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)城市編號(hào)坐標(biāo)1(87,7)11(58,69)21(4,50)2(91,38)12(54,62)22(13,40)3(83,46)13(51,67)23(18,40)4(71,44)14(37,84)24(24,42)5(64,60)15(41,94)25(25,38)6(68,58)16(2,99)26(41,26)7(83,69)17(7,64)27(45,21)8(87,76)18(22,60)28(44,35

42、)9(74,78)19(25,62)29(58,35)10(71,71)20(18,54)30(62,32)最優(yōu)路徑為：123465789101112131415161719182021222324252826272930其路徑長(zhǎng)度為：424.869292也可取前10個(gè)城市的坐標(biāo)進(jìn)行測(cè)試：20表2OliverTSP問題的10個(gè)城市位置坐標(biāo)城市編號(hào)坐標(biāo)1(87,7)2(91,38)3(83,46)4(71,44)5(64,60)6(68,58)7(83,69)8(87,76)9(74,78)10(71,71)有人求得的最優(yōu)路徑為：03549876210路徑長(zhǎng)度是166.541336上述10個(gè)城市

43、的求解中編號(hào)從0開始，把所有路徑搜索完又返回到出發(fā)節(jié)點(diǎn)。2問題描述應(yīng)用遺傳算法求解30/10個(gè)節(jié)點(diǎn)的TSP(旅行商問題)問題，求問題的最優(yōu)解。三實(shí)驗(yàn)要求1掌握遺傳算法的基本原理、各個(gè)遺傳操作和算法步驟；2要求求出問題最優(yōu)解，若得不出最優(yōu)解，請(qǐng)分析原因；3對(duì)實(shí)驗(yàn)中的幾個(gè)算法控制參數(shù)進(jìn)行仔細(xì)定義，并能通過實(shí)驗(yàn)選擇參數(shù)的最佳值；4要求界面顯示每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。四實(shí)驗(yàn)背景知識(shí)遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過程的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的一種最重要形式。遺傳算法為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題找出了一個(gè)解決方法。自從

44、Holland于1975年在其著作AdaptationinNaturalandArtificialSystems»中首次提出遺傳算法以來，經(jīng)過近30年的研究，現(xiàn)在已發(fā)展到一個(gè)比較成熟的階段，并且在實(shí)際中已經(jīng)得到了很好的應(yīng)用。1遺傳算法基本步驟(1)初始化群體；(2)計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值；(3)按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體；(4)按概率Pc進(jìn)行交叉操作；(5)按概率Pm進(jìn)行變異操作；(6)沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7);(7)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。212參數(shù)編碼把待求解問題的解空間中的每個(gè)可行解看

45、作一個(gè)染色體，并用編碼的方式來表示，通常編碼中的每一位都看作是一個(gè)組成該染色體的基因。在TSP問題中，多采用以遍歷城市的次序排列進(jìn)行編碼。如對(duì)于8個(gè)城市的TSP問題，123456781就表示一個(gè)可行解。還有其它編碼方法如Grefenstette編碼，其他可以查閱相關(guān)參考文獻(xiàn)。3初始群體初始群體是指問題的一組初始可行解，可行解的數(shù)量(可定義為變量popsize)和分布對(duì)于遺傳算法的運(yùn)行有著很大的影響。實(shí)際求解中，初始群體往往采用隨機(jī)生成的方法。在TSP問題中，隨機(jī)生成popsize條可行路徑序列。4評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)即適應(yīng)度函數(shù)，在遺傳算法中用來計(jì)算一個(gè)染色體優(yōu)劣的函數(shù)。在進(jìn)行遺傳操作和種群進(jìn)化的

46、時(shí)候，每個(gè)染色體的適應(yīng)值是決定它是否進(jìn)入下一輪種群進(jìn)化的關(guān)鍵因素。適應(yīng)值高的函數(shù)被選作新一代個(gè)體的可能性就會(huì)大。TSP問題中適應(yīng)度函數(shù)常取路徑長(zhǎng)度的倒數(shù)(或倒數(shù)的相關(guān)函數(shù))，如：/n'、d(Xi,Xi1)d(XnXi)i1其中，N是個(gè)調(diào)節(jié)參數(shù)，根據(jù)實(shí)驗(yàn)情況進(jìn)行確定。5選擇算子賭輪算法是選擇算子中常用的一種方法。它的名稱來源于賭博中的輪盤賭，輪盤賭是一種隨機(jī)性賭博游戲，我們這里就是由它的隨機(jī)性來選擇出某些個(gè)體，這些個(gè)體相對(duì)來說具有較優(yōu)良的適應(yīng)性。我們定義f(xi)為第i(i=1,2,3.popsize)個(gè)染色體的適應(yīng)度，則每個(gè)個(gè)體被選中的概率popsize是：P(Xi)=f(Xi)%f(

47、Xj)-jT圖10賭輪盤示意圖在算法中賭輪選擇法可用下面的子過程來模擬：(1) 在0,1區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r。(2) 若r<=q1,則染色體X1被選中。22(3) 若qk4<rwqk(2wkEpopsize),則染色體Xk被選中。其中qi稱為染色體xi(i=1,2,.,popsize)的積累概率，其計(jì)算公式為：q=£P(Xj)jw賭輪選擇算子在個(gè)體數(shù)不太多時(shí)，有可能出現(xiàn)不正確反映個(gè)體適應(yīng)度的選擇過程，也就是說適應(yīng)度高的個(gè)體有可能反而被淘汰了。為了改進(jìn)賭輪選擇算子的這種缺點(diǎn)，有很多改進(jìn)的交叉選擇算子，如：最佳個(gè)體保存法、期望值方法、排序選擇方法、聯(lián)賽選擇方法、

48、排擠方法等。6交叉算子在自然界生物進(jìn)化過程中，起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中，起核心作用的是遺傳操作的交叉算子。所謂交叉算子就是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉算子設(shè)計(jì)一般與所求解的具體問題有關(guān)。下面列舉幾種在TSP問題中常見的交叉方法：(1) 部分匹配交叉(PMXpartiallymappedcrossover)由Goldberg于1985年提出。在PMXB作時(shí)，先依據(jù)均勻隨機(jī)分布產(chǎn)生兩個(gè)位串交叉點(diǎn)，定義這兩點(diǎn)之間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并交換兩父串的匹配區(qū)域。如父串及匹配區(qū)域?yàn)椋篈=984|56

49、7|1320B=871|230|9546首先交換AB的匹配區(qū)域，得：A=984|230|1320B=871|567|9546.''一、一再對(duì)A、B兩子串匹配區(qū)域以外的地方出現(xiàn)的遍歷重復(fù)，依據(jù)匹配區(qū)域內(nèi)的位置映射關(guān)系，逐一交換。如A區(qū)域外的2,3,0分別以5,6,7交換，得：-0一-A=984|230|1657B=801|567|9243(2)順序交叉(OX,ordercrossover)Davis在1985年提出。此方法開始也是選擇一個(gè)匹配區(qū)域：A=984|567|1320B=871|230|9546根據(jù)匹配區(qū)域的映射關(guān)系，在其匹配區(qū)域外的相應(yīng)位置標(biāo)記HA=984|567|1H

50、HHB=8H1|230|9H4H再移動(dòng)匹配區(qū)域至起點(diǎn)位置，且在其后預(yù)留相應(yīng)于匹配區(qū)域的空間(H數(shù)目)，然后將其余的碼按相對(duì)次序排列在預(yù)留區(qū)后面''一一一A=567|HHH|1984一''一一一一一B=230|HHH|948123.一.一.''一.一.最后將父串A、B的匹配區(qū)域互換，并放置到A、B的預(yù)留區(qū)域，得到子代：'''-A=567|230|1984B=230|567|9481(3)改進(jìn)的啟發(fā)式順序交叉與OX法有點(diǎn)類似。隨機(jī)在串中選擇一個(gè)交配區(qū)域，如兩父串及交配區(qū)域選定為：A=12|3456|789B=98|7654|3

51、21將B的交配區(qū)域加到A的前面或后面，A的交配區(qū)域加到B的前面或后面得到：A=7654|123456789B=3456|987654321.在A中自交配區(qū)域后依次刪除與交配區(qū)相同的城市碼，得到最終的兩子串為：A=765412389B=3456987217變異算子TSP問題中，經(jīng)常采取的變異操作主要有：(1)位點(diǎn)變異變異僅以一定的概率(通常較小)對(duì)串的某些位作值的變異。(2)逆轉(zhuǎn)變異在串中，隨機(jī)選擇兩點(diǎn)，再將這兩點(diǎn)內(nèi)的子串按反序插入到原位置中，如選擇A的你.一、一'轉(zhuǎn)點(diǎn)為3,6,則經(jīng)逆轉(zhuǎn)后，變?yōu)锳。如A=123|456|789A=123|654|789這種變異操作對(duì)于TSP問題，就調(diào)整前

52、后引起的TSP圈的長(zhǎng)度變化而言屬于最細(xì)微的調(diào)整，因而局部?jī)?yōu)化的精度較高；但碼串絕對(duì)位置所呈現(xiàn)的“模式”變化較大。(3)對(duì)換變異隨機(jī)選擇串中的兩點(diǎn)，交換其值(碼)。對(duì)于串AA=1234|567|89一一'一若對(duì)換點(diǎn)便4,7,則經(jīng)對(duì)換后，A為：A=1237|564|89這種變異操作在求解TSP問題優(yōu)化算法中常被采用。在遺傳算法中，對(duì)換變異操作對(duì)碼串絕對(duì)位置所呈現(xiàn)的“模式”變化影響較大，所需的計(jì)算也簡(jiǎn)單一些，但局部?jī)?yōu)化精度稍差一點(diǎn)。(4) 插入變異從串中隨機(jī)選擇1個(gè)碼，將此碼插入隨機(jī)選擇的插入點(diǎn)中間，對(duì)于上述A而言，若取插入碼為5,選取插入點(diǎn)位23之間，則A=12534678924此外，還有一些有關(guān)上述變異操作的變體形式，如引入連續(xù)逆轉(zhuǎn)，進(jìn)化變異(爬山法)和混合變異等。8Grefenstette編碼在TSP問題中，以遍歷城市的次序進(jìn)