《人工智能及其應(yīng)用》實(shí)驗(yàn)指導(dǎo)書

1、人工智能及其應(yīng)用實(shí)驗(yàn)指導(dǎo)書 人工智能及其應(yīng)用實(shí)驗(yàn)指導(dǎo)書浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工智能課程組2011年9月前 言本實(shí)驗(yàn)是為了配合人工智能及其應(yīng)用課程的理論學(xué)習(xí)而專門設(shè)置的。本實(shí)驗(yàn)的目的是鞏固和加強(qiáng)人工智能的基本原理和方法，并為今后進(jìn)一步學(xué)習(xí)更高級課程和信息智能化技術(shù)的研究與系統(tǒng)開發(fā)奠定良好的基礎(chǔ)。全書共分為八個(gè)實(shí)驗(yàn)：1.產(chǎn)生式系統(tǒng)實(shí)驗(yàn)；2.模糊推理系統(tǒng)實(shí)驗(yàn)；3.A*算法求解8數(shù)碼問題實(shí)驗(yàn)；4.A*算法求解迷宮問題實(shí)驗(yàn)；5.遺傳算法求解函數(shù)最值問題實(shí)驗(yàn)；6.遺傳算法求解TSP問題實(shí)驗(yàn)；7.基于神經(jīng)網(wǎng)絡(luò)的模式識(shí)別實(shí)驗(yàn)；8.基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化計(jì)算實(shí)驗(yàn)。每個(gè)實(shí)驗(yàn)包括有：實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)

2、條件、實(shí)驗(yàn)要求、實(shí)驗(yàn)步驟和實(shí)驗(yàn)報(bào)告等六個(gè)項(xiàng)目。本實(shí)驗(yàn)指導(dǎo)書包括兩個(gè)部分。第一個(gè)部分是介紹實(shí)驗(yàn)的教學(xué)大綱；第二部分是介紹八個(gè)實(shí)驗(yàn)的內(nèi)容。由于編者水平有限，本實(shí)驗(yàn)指導(dǎo)書的錯(cuò)誤和不足在所難免，歡迎批評指正。 人工智能課程組2011年9月 目錄實(shí)驗(yàn)教學(xué)大綱1實(shí)驗(yàn)一 產(chǎn)生式系統(tǒng)實(shí)驗(yàn)3實(shí)驗(yàn)二 模糊推理系統(tǒng)實(shí)驗(yàn)5實(shí)驗(yàn)三 A*算法實(shí)驗(yàn)I9實(shí)驗(yàn)四 A*算法實(shí)驗(yàn)II12實(shí)驗(yàn)五 遺傳算法實(shí)驗(yàn)I14實(shí)驗(yàn)六 遺傳算法實(shí)驗(yàn)II18實(shí)驗(yàn)七 基于神經(jīng)網(wǎng)絡(luò)的模式識(shí)別實(shí)驗(yàn)20實(shí)驗(yàn)八  基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化計(jì)算實(shí)驗(yàn)24第III頁實(shí)驗(yàn)教學(xué)大綱一、學(xué)時(shí)：16學(xué)時(shí)，一般安排在第9周至第16周。二、主要儀器設(shè)備及運(yùn)行環(huán)境：PC機(jī)、

3、Visual C+ 6.0、Matlab 7.0。三、實(shí)驗(yàn)項(xiàng)目及教學(xué)安排序號(hào)實(shí)驗(yàn)名稱實(shí)驗(yàn)平臺(tái)實(shí)驗(yàn)內(nèi)容學(xué)時(shí)類型教學(xué)要求1產(chǎn)生式系統(tǒng)應(yīng)用VC+設(shè)計(jì)知識(shí)庫，實(shí)現(xiàn)系統(tǒng)識(shí)別或分類等。2設(shè)計(jì)課內(nèi)2模糊推理系統(tǒng)應(yīng)用Matlab1）設(shè)計(jì)洗衣機(jī)的模糊控制器；2）設(shè)計(jì)兩車追趕的模糊控制器。2驗(yàn)證課內(nèi)3A*算法應(yīng)用IVC+設(shè)計(jì)與實(shí)現(xiàn)求解N數(shù)碼問題的A*算法。2綜合課內(nèi)4A*算法應(yīng)用IIVC+設(shè)計(jì)與實(shí)現(xiàn)求解迷宮問題的A*算法。2綜合課內(nèi)5遺傳算法應(yīng)用IMatlab1）求某一函數(shù)的最小值；2）求某一函數(shù)的最大值。2驗(yàn)證課內(nèi)6遺傳算法應(yīng)用IIVC+設(shè)計(jì)與實(shí)現(xiàn)求解不同城市規(guī)模的TSP問題的遺傳算法。2綜合課內(nèi)7基于神經(jīng)網(wǎng)絡(luò)

4、的模式識(shí)別Matlab1）基于BP神經(jīng)網(wǎng)絡(luò)的數(shù)字識(shí)別設(shè)計(jì)；2）基于離散Hopfiel神經(jīng)網(wǎng)絡(luò)的聯(lián)想記憶設(shè)計(jì)。2驗(yàn)證課內(nèi)8基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化計(jì)算VC+設(shè)計(jì)與實(shí)現(xiàn)求解TSP問題的連續(xù)Hopfield神經(jīng)網(wǎng)絡(luò)。2綜合課內(nèi)四、實(shí)驗(yàn)成績評定實(shí)驗(yàn)課成績單獨(dú)按五分制評定。凡實(shí)驗(yàn)成績不及格者，該門課程就不及格。學(xué)生的實(shí)驗(yàn)成績應(yīng)以平時(shí)考查為主，一般應(yīng)占課程總成績的50%，其平時(shí)成績又要以實(shí)驗(yàn)實(shí)際操作的優(yōu)劣作為主要考核依據(jù)。對于實(shí)驗(yàn)課成績，無論采取何種方式進(jìn)行考核，都必須按實(shí)驗(yàn)課的目的要求，以實(shí)際實(shí)驗(yàn)工作能力的強(qiáng)弱作為評定成績的主要依據(jù)。評定各級成績時(shí)，可參考以下標(biāo)準(zhǔn)：（一）優(yōu)秀能正確理解實(shí)驗(yàn)的目的要求，能獨(dú)立、

5、順利而正確地完成各項(xiàng)實(shí)驗(yàn)操作，會(huì)分析和處理實(shí)驗(yàn)中遇到的問題，能掌握所學(xué)的各項(xiàng)實(shí)驗(yàn)技能，能較好地完成實(shí)驗(yàn)報(bào)告及其它各項(xiàng)實(shí)驗(yàn)作業(yè)，有一定創(chuàng)造精神和能力。有良好的實(shí)驗(yàn)室工作作風(fēng)和習(xí)慣。（二）良好能理解實(shí)驗(yàn)的目的和要求，能認(rèn)真而正確地完成各項(xiàng)實(shí)驗(yàn)操作，能分析和處理實(shí)驗(yàn)中遇到的一些問題。能掌握所學(xué)實(shí)驗(yàn)技能的絕大部分，對難點(diǎn)較大的操作完成有困難。能一般完成實(shí)驗(yàn)報(bào)告和其它實(shí)驗(yàn)作業(yè)。有較好的實(shí)驗(yàn)習(xí)慣和工作作風(fēng)。（三）中等能粗淺理解實(shí)驗(yàn)?zāi)康囊?，能認(rèn)真努力進(jìn)行各項(xiàng)實(shí)驗(yàn)操作，但技巧較差。能分析和處理實(shí)驗(yàn)中一些較容易的問題，掌握實(shí)驗(yàn)技能的大部分。有30%掌握得不好。能一般完成各項(xiàng)實(shí)驗(yàn)作業(yè)和報(bào)告。處理問題缺乏條理。工

6、作作風(fēng)較好。能認(rèn)真遵守各項(xiàng)規(guī)章制度。學(xué)習(xí)努力。（四）及格只能機(jī)械地了解實(shí)驗(yàn)內(nèi)容，能一般按圖、或按實(shí)驗(yàn)步驟“照方抓藥”完成實(shí)驗(yàn)操作，能完成60%所學(xué)的實(shí)驗(yàn)技能，有些雖作但不準(zhǔn)確。遇到問題常常缺乏解決的辦法，在別人啟發(fā)下能作些簡單處理，但效果不理想。能一般完成實(shí)驗(yàn)報(bào)告，能認(rèn)真遵守實(shí)驗(yàn)室各項(xiàng)規(guī)章制度，工作中有小的習(xí)慣性毛?。ㄈ绻ぷ鳠o計(jì)劃，處理問題缺乏條理）。（五）不及格盲目地“照方抓藥”，只掌握50%的所學(xué)實(shí)驗(yàn)技能。有些實(shí)驗(yàn)雖能作，但一般效果不好，操作不正確。工作忙亂無條理。一般能遵守實(shí)驗(yàn)室規(guī)章制度，但常有小的錯(cuò)誤。實(shí)驗(yàn)報(bào)告較多的時(shí)候有結(jié)果，遇到問題時(shí)說不明原因，在教師指導(dǎo)下也較難完成各項(xiàng)實(shí)驗(yàn)作業(yè)。

7、或有些小聰明但不努力，不求上進(jìn)。2實(shí)驗(yàn)一 產(chǎn)生式系統(tǒng)實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模菏煜ひ浑A謂詞邏輯和產(chǎn)生式表示法，掌握產(chǎn)生式系統(tǒng)的運(yùn)行機(jī)制，以及基于規(guī)則推理的基本方法。二、實(shí)驗(yàn)內(nèi)容運(yùn)用所學(xué)知識(shí)，設(shè)計(jì)并編程實(shí)現(xiàn)一個(gè)小型人工智能系統(tǒng)（如分類、診斷、預(yù)測等類型）。三、實(shí)驗(yàn)條件：產(chǎn)生式系統(tǒng)實(shí)驗(yàn)程序，如下圖1所示。圖1 產(chǎn)生式系統(tǒng)實(shí)驗(yàn)程序界面四、實(shí)驗(yàn)要求1. 具體應(yīng)用領(lǐng)域自選，具體系統(tǒng)名稱自定；但所做系統(tǒng)絕對不能雷同。2. 用一階謂詞邏輯和產(chǎn)生式規(guī)則作為知識(shí)表示，利用如圖1所示的產(chǎn)生式系統(tǒng)實(shí)驗(yàn)程序，建立知識(shí)庫，分別運(yùn)行正、反向推理。3. 系統(tǒng)完成后，提交實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)步驟：1. 基于如圖1所示的產(chǎn)生式系統(tǒng)實(shí)驗(yàn)程

8、序，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)小型人工智能系統(tǒng)：1）系統(tǒng)設(shè)置，包括設(shè)置系統(tǒng)名稱和系統(tǒng)謂詞，給出謂詞名及其含義。2）編輯知識(shí)庫，通過輸入規(guī)則或修改規(guī)則等，完成整個(gè)規(guī)則庫的建立。3）建立事實(shí)庫（綜合數(shù)據(jù)庫），輸入多條事實(shí)或結(jié)論。4）運(yùn)行推理，包括正向推理和反向推理，給出相應(yīng)的推理過程、事實(shí)區(qū)和規(guī)則區(qū)。2. 撰寫實(shí)驗(yàn)報(bào)告。六、實(shí)驗(yàn)報(bào)告下面是實(shí)驗(yàn)報(bào)告的基本內(nèi)容和書寫格式。遞交的報(bào)告文件名：班級_學(xué)號(hào)_姓名_實(shí)驗(yàn)名稱實(shí)驗(yàn)名稱班級： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)內(nèi)容三、實(shí)驗(yàn)步驟四、實(shí)驗(yàn)結(jié)果1. 系統(tǒng)名稱及謂詞定義2. 系統(tǒng)知識(shí)庫3. 系統(tǒng)正、反向推理過程、事實(shí)區(qū)和規(guī)則區(qū)。五、實(shí)驗(yàn)總結(jié)26實(shí)驗(yàn)二 模糊推理系統(tǒng)

9、實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康睦斫饽：壿嬐评淼脑砑疤攸c(diǎn)，熟練應(yīng)用模糊推理，了解可能性理論。二、實(shí)驗(yàn)原理模糊推理所處理的事物自身是模糊的，概念本身沒有明確的外延，一個(gè)對象是否符合這個(gè)概念難以明確地確定，模糊推理是對這種不確定性，即模糊性的表示與處理。模糊邏輯推理是基于模糊性知識(shí)(模糊規(guī)則)的一種近似推理，一般采用Zadeh提出的語言變量、語言值、模糊集和模糊關(guān)系合成的方法進(jìn)行推理。三、實(shí)驗(yàn)條件Matlab 7.0 的Fuzzy Logic Tool。四、實(shí)驗(yàn)內(nèi)容及要求1. 設(shè)計(jì)洗衣機(jī)洗滌時(shí)間的模糊控制。已知人的操作經(jīng)驗(yàn)為：“污泥越多，油脂越多，洗滌時(shí)間越長”；“污泥適中，油脂適中，洗滌時(shí)間適中”；“污泥越

10、少，油脂越少，洗滌時(shí)間越短”。要求：（1）假設(shè)污泥、油脂、洗滌時(shí)間的論域分別為0,100、0,100和0,120，設(shè)計(jì)相應(yīng)的模糊推理系統(tǒng)，給出輸入、輸出語言變量的隸屬函數(shù)圖，模糊控制規(guī)則表和推論結(jié)果立體圖。（2）假定當(dāng)前傳感器測得的信息為，采用面積重心法反模糊化，給出模糊推理結(jié)果，并觀察模糊推理的動(dòng)態(tài)仿真環(huán)境，給出其動(dòng)態(tài)仿真環(huán)境圖。提示：模糊控制規(guī)則如下表1所示，其中SD（污泥少）、MD（污泥中）、LD（污泥多）、NG（油脂少）、MG（油脂中）、LG（油脂多）、VS（洗滌時(shí)間很短）、S（洗滌時(shí)間短）、M（洗滌時(shí)間中等）、L（洗滌時(shí)間長）、VL（洗滌時(shí)間很長）。圖1 洗衣機(jī)的模糊控制規(guī)則表xyz

11、SDNGVSSDMGMSDLGLMDNGSMDMGMMDLGLLDNGMLDMGLLDLGVL2假設(shè)兩汽車均為理想狀態(tài)，即，Y為速度，U為油門控制輸入。（1）設(shè)計(jì)模糊推理系統(tǒng)控制2號(hào)汽車由靜止啟動(dòng)，追趕200m外時(shí)速90km的1號(hào)汽車并與其保持30m的距離。（2）在25時(shí)刻1號(hào)汽車速度改為時(shí)速110km時(shí)，仍與其保持30m距離。（3）在35時(shí)刻1號(hào)汽車速度改為時(shí)速70km時(shí)，仍與其保持30m距離。要求：（1）如下圖1所示，設(shè)計(jì)兩輸入一輸出的模糊推理系統(tǒng)作為2號(hào)汽車的模糊控制器，其中輸入為誤差e和誤差的變化，輸出為1號(hào)汽車的油門控制u，采用面積等分法反模糊化，給出輸入、輸出語言變量的隸屬函數(shù)圖，

12、模糊控制規(guī)則表，推論結(jié)果立體圖和模糊推理的動(dòng)態(tài)仿真環(huán)境圖。圖1 兩車追趕的模糊控制系統(tǒng)框圖（2）用SIMULINK仿真兩車追趕的模糊控制系統(tǒng)，給出目標(biāo)車（1號(hào)汽車）的速度曲線圖，以及追趕車（2號(hào)汽車）的速度曲線圖和與目標(biāo)車（1號(hào)汽車）相對距離變化圖。提示：模糊控制規(guī)則如下表2所示，其中，r 、和油門控制u的論域分別為0,1、-3,3和-1,1，r的隸屬函數(shù)如圖2所示。表2 模糊控制規(guī)則表NBZEPBPBZENMNBPMZEPMPBZEZEPMPBNMZENMNBNBZENMNB圖2 r的隸屬函數(shù)圖五、實(shí)驗(yàn)報(bào)告要求：1. 按照實(shí)驗(yàn)要求，給出相應(yīng)結(jié)果。2分析隸屬度、模糊關(guān)系和模糊規(guī)則的相互關(guān)系。下

13、面是實(shí)驗(yàn)報(bào)告的基本內(nèi)容和書寫格式。實(shí)驗(yàn)名稱班級： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)內(nèi)容三、實(shí)驗(yàn)結(jié)果按照實(shí)驗(yàn)要求，給出相應(yīng)結(jié)果。四、實(shí)驗(yàn)總結(jié)1. 分析隸屬度、模糊關(guān)系和模糊規(guī)則的相互關(guān)系。 2. 總結(jié)實(shí)驗(yàn)心得體會(huì)實(shí)驗(yàn)三 A*算法實(shí)驗(yàn)I一、實(shí)驗(yàn)?zāi)康氖煜ず驼莆諉l(fā)式搜索的定義、估價(jià)函數(shù)和算法過程，并利用A*算法求解N數(shù)碼難題，理解求解流程和搜索順序。二、實(shí)驗(yàn)原理A*算法是一種啟發(fā)式圖搜索算法，其特點(diǎn)在于對估價(jià)函數(shù)的定義上。對于一般的啟發(fā)式圖搜索，總是選擇估價(jià)函數(shù)f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，所以，可考慮每個(gè)節(jié)點(diǎn)n的估價(jià)函數(shù)值為兩個(gè)分量：從

14、起始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)g(n)以及從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的估價(jià)代價(jià)h(n),且，為節(jié)點(diǎn)到目的結(jié)點(diǎn)的最優(yōu)路徑的代價(jià)。八數(shù)碼問題是在3×3的九宮格棋盤上，擺有8個(gè)刻有18數(shù)碼的將牌。棋盤中有一個(gè)空格，允許緊鄰空格的某一將牌可以移到空格中，這樣通過平移將牌可以將某一將牌布局變換為另一布局。針對給定的一種初始布局或結(jié)構(gòu)（目標(biāo)狀態(tài)），問如何移動(dòng)將牌，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。如下圖1表示了一個(gè)具體的八數(shù)碼問題求解。圖1 八數(shù)碼問題的求解三、實(shí)驗(yàn)內(nèi)容1. 參考A*算法核心代碼，以8數(shù)碼問題為例實(shí)現(xiàn)A*算法的求解程序（編程語言不限），要求設(shè)計(jì)兩種不同的估價(jià)函數(shù)。2. 設(shè)置相同的初始狀態(tài)和目

15、標(biāo)狀態(tài)，針對不同的估價(jià)函數(shù)，求得問題的解，并比較它們對搜索算法性能的影響，包括擴(kuò)展節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)等。3. 設(shè)置與上述2相同的初始狀態(tài)和目標(biāo)狀態(tài)，用寬度優(yōu)先搜索算法（即令估計(jì)代價(jià)h(n)0的A*算法）求得問題的解，以及搜索過程中的擴(kuò)展節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)。*4. 參考A*算法核心代碼，實(shí)現(xiàn)A*算法求解15數(shù)碼問題的程序，設(shè)計(jì)兩種不同的估價(jià)函數(shù)，然后重復(fù)上述2和3的實(shí)驗(yàn)內(nèi)容。5. 提交實(shí)驗(yàn)報(bào)告和源程序。四、實(shí)驗(yàn)報(bào)告要求1. 分析不同的估價(jià)函數(shù)對A*算法性能的影響。2. 根據(jù)寬度優(yōu)先搜索算法和A*算法求解8、15數(shù)碼問題的結(jié)果，分析啟發(fā)式搜索的特點(diǎn)。下面是實(shí)驗(yàn)報(bào)告的基本內(nèi)容和書寫格式。實(shí)驗(yàn)名稱班級

16、： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)原理三、實(shí)驗(yàn)結(jié)果按照實(shí)驗(yàn)內(nèi)容，把結(jié)果填入表1。表1 不同啟發(fā)函數(shù)h(n)求解8數(shù)碼問題的結(jié)果比較啟發(fā)函數(shù)h(n)不在位數(shù)0初始狀態(tài)目標(biāo)狀態(tài)123804765123804765123804765最優(yōu)解擴(kuò)展節(jié)點(diǎn)數(shù)生成節(jié)點(diǎn)數(shù)運(yùn)行時(shí)間*表2 不同啟發(fā)函數(shù)h(n)求解15數(shù)碼問題的結(jié)果比較啟發(fā)函數(shù)h(n)不在位數(shù)0初始狀態(tài)目標(biāo)狀態(tài)最優(yōu)解擴(kuò)展節(jié)點(diǎn)數(shù)生成節(jié)點(diǎn)數(shù)運(yùn)行時(shí)間四、實(shí)驗(yàn)總結(jié)1. 畫出A*算法求解N數(shù)碼問題的流程圖2. 完成實(shí)驗(yàn)報(bào)告要求1和2。 3. 總結(jié)實(shí)驗(yàn)心得體會(huì)實(shí)驗(yàn)四 A*算法實(shí)驗(yàn)II一、實(shí)驗(yàn)?zāi)康氖煜ず驼莆誂*算法實(shí)現(xiàn)迷宮尋路功能，要求掌握啟發(fā)式函數(shù)的編寫

17、以及各類啟發(fā)式函數(shù)效果的比較。二、實(shí)驗(yàn)原理 A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為：f(n)=g(n)+h(n)，其中f(n)是節(jié)點(diǎn)n從初始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。汗纼r(jià)值h(n)小于等于n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解。如果估價(jià)值大于實(shí)際值，搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。尋路問題常見于各類游戲中角色尋路、三維虛擬場景中運(yùn)動(dòng)

18、目標(biāo)的路徑規(guī)劃、機(jī)器人尋路等多個(gè)應(yīng)用領(lǐng)域。迷宮尋路問題是在以方格表示的地圖場景中，對于給定的起點(diǎn)、終點(diǎn)和障礙物（墻），如何找到一條從起點(diǎn)開始避開障礙物到達(dá)終點(diǎn)的最短路徑。假設(shè)在一個(gè)n*m的迷宮里，入口坐標(biāo)和出口坐標(biāo)分別為(1,1)和(5,5)，每一個(gè)坐標(biāo)點(diǎn)有兩種可能：0或1，其中0表示該位置允許通過，1表示該位置不允許通過。如地圖：0 0 0 0 01 0 1 0 10 0 1 1 10 1 0 0 00 0 0 1 0最短路徑應(yīng)該是A B 0 0 01 C 1 0 1E D 1 1 1F 1 J K LG H I 1 M即： (1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,

19、1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)三、實(shí)驗(yàn)內(nèi)容 1參考迷宮求解的核心代碼，觀察求解過程與思路，畫出用A*算法求解迷宮最短路徑的流程圖。 2設(shè)置不同的地圖，以及不同的初始狀態(tài)和目標(biāo)狀態(tài)，記錄A*算法的求解結(jié)果，包括最短路徑、擴(kuò)展節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)和算法運(yùn)行時(shí)間。3對于相同的初始狀態(tài)和目標(biāo)狀態(tài)，設(shè)計(jì)不同的啟發(fā)式函數(shù)，比較不同啟發(fā)式函數(shù)對迷宮尋路速度的提升效果，包括擴(kuò)展節(jié)點(diǎn)數(shù)、生成節(jié)點(diǎn)數(shù)和算法運(yùn)行時(shí)間。4提交實(shí)驗(yàn)報(bào)告和源程序。四、實(shí)驗(yàn)報(bào)告要求： 1畫出A*算法求解迷宮最短路徑問題的流程圖。 2試分析不同啟發(fā)式函數(shù)h(n)對迷宮尋路求解的速度提升效

20、果。 3分析A*算法求解不同規(guī)模迷宮最短路徑問題的性能。下面是實(shí)驗(yàn)報(bào)告的基本內(nèi)容和書寫格式。實(shí)驗(yàn)名稱班級： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)原理三、實(shí)驗(yàn)結(jié)果按照實(shí)驗(yàn)內(nèi)容，給出相應(yīng)結(jié)果。四、實(shí)驗(yàn)總結(jié)1. 完成實(shí)驗(yàn)報(bào)告要求2和3。 2. 總結(jié)實(shí)驗(yàn)心得體會(huì)實(shí)驗(yàn)五 遺傳算法實(shí)驗(yàn)I一、實(shí)驗(yàn)?zāi)康氖煜ず驼莆者z傳算法的原理、流程和編碼策略，并利用遺傳求解函數(shù)優(yōu)化問題，理解求解流程并測試主要參數(shù)對結(jié)果的影響。二、實(shí)驗(yàn)原理遺傳算法 ( Genetic Algorithms, GA )是基于生物界自然選擇和基因遺傳學(xué)原理的一種廣為應(yīng)用的、高效的隨機(jī)搜索算法，20世紀(jì)60年代由美國的密執(zhí)根大學(xué)的Holland教

21、授首先提出。該算法將優(yōu)化問題看作是自然界中生物的進(jìn)化過程，通過模擬大自然中生物進(jìn)化過程中的遺傳規(guī)律，來達(dá)到尋優(yōu)的目的。近年來，遺傳算法已廣泛地應(yīng)用于作業(yè)調(diào)度與排序、可靠性設(shè)計(jì)、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問題等等。用遺傳算法求解優(yōu)化問題，首先對優(yōu)化問題的解進(jìn)行編碼，編碼后的一個(gè)解稱為一個(gè)染色體，組成染色體的元素稱為基因。一個(gè)群體由若干個(gè)染色體組成，染色體的個(gè)數(shù)稱為群體的規(guī)模。在遺傳算法中用適應(yīng)度函數(shù)表示環(huán)境，它是已編碼的解的函數(shù)，是一個(gè)解適應(yīng)環(huán)境程度的評價(jià)。當(dāng)適應(yīng)度函數(shù)確定后，自然選擇規(guī)律以適應(yīng)度函數(shù)值的大小來決定一個(gè)染色體是否繼續(xù)生存下去的概率。生存下來的染色體成為種群

22、，它們中的部分或全部以一定的概率進(jìn)行交叉、變異，從而得到下一代群體。三、實(shí)驗(yàn)條件Matlab 7.X 的遺傳算法工具箱。四、實(shí)驗(yàn)內(nèi)容：1用遺傳算法求解下列函數(shù)的最大值，設(shè)定求解精度到15位小數(shù)。1） 給出適應(yīng)度函數(shù)（Fitness Function）的M文件（Matlab中要求適應(yīng)度函數(shù)最小化）。2） 設(shè)計(jì)及選擇上述問題的編碼、選擇操作、交叉操作、變異操作以及控制參數(shù)等，填入表1，給出最佳適應(yīng)度(Best fitness)和最佳個(gè)體（Best individual）圖。表1 遺傳算法參數(shù)的選擇編碼編碼方式（population type）種群參數(shù)種群規(guī)模（population size）初始種

23、群的個(gè)體取值范圍（Initial range）選擇操作個(gè)體選擇概率分配策略（對應(yīng)Fitness scaling）個(gè)體選擇方法（Selection function）最佳個(gè)體保存優(yōu)良個(gè)體保存數(shù)量（Elite count）交叉操作交叉概率（Crossover fraction）交叉方式（Crossover function）變異操作變異方式(Mutation function)停止參數(shù)最大迭代步數(shù)（Generations）最大運(yùn)行時(shí)間限制（Time limit）最小適應(yīng)度限制（Fitness limit）停滯代數(shù)（Stall generations）停滯時(shí)間限制（Stall time limit）

24、3） 使用相同的初始種群（Use random state from previous run），設(shè)置不同的種群規(guī)模（population size），例如5、20和100，初始種群的個(gè)體取值范圍（Initial range）為0;1，其他參數(shù)同表1，然后求得相應(yīng)的最佳適應(yīng)度(Best fitness)、平均適應(yīng)度（Mean fitness）和最佳個(gè)體（Best individual），填入下表2，分析種群規(guī)模對算法性能的影響。表2 不同的種群規(guī)模的GA運(yùn)行結(jié)果種群規(guī)模最佳適應(yīng)度平均適應(yīng)度最佳個(gè)體xy520100*4) 設(shè)置種群規(guī)模（population size）為20，初始種群的個(gè)體取值范

25、圍（Initial range）為0;10，選擇不同的選擇操作、交叉操作和變異操作，其他參數(shù)同表1，然后獨(dú)立運(yùn)行算法10次，完成下表3，并分析比較采用不同的選擇策略、交叉策略和變異策略的算法運(yùn)行結(jié)果。表3不同的選擇策略、交叉策略和變異策略的算法運(yùn)行結(jié)果遺傳算法參數(shù)設(shè)置（gaoptimset）1234選擇操作個(gè)體選擇概率分配FitnessScalingFcnRank（排序）fitscalingrankProportional（比率）fitscalingprop個(gè)體選擇SelectionFcnRoulette（輪盤賭選擇）selectionrouletteTournament（競標(biāo)賽選擇）sele

26、ctiontournament交叉操作CrossoverFcn單點(diǎn)交叉 crossoversinglepoint兩點(diǎn)交叉 crossovertwopoint變異操作MutationFcnUniform（均勻變異）mutationuniformGaussian（高斯變異）mutationgaussian最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度備注：1：options=gaoptimset('PopulationSize',20,'PopInitRange',0;10,'FitnessScalingFcn',fitscalingrank,'Select

27、ionFcn',selectionroulette,'CrossoverFcn',crossoversinglepoint,'MutationFcn',mutationuniform)2用遺傳算法求解下面一個(gè)Rastrigin函數(shù)的最小值，設(shè)定求解精度到15位小數(shù)。1）給出適應(yīng)度函數(shù)的M文件（Matlab中要求適應(yīng)度函數(shù)最小化）。2） 設(shè)計(jì)上述問題的編碼、選擇操作、交叉操作、變異操作以及控制參數(shù)等，填入表4，并畫出最佳適應(yīng)度(Best fitness)和最佳個(gè)體（Best individual）圖。表4 遺傳算法參數(shù)的選擇編碼編碼方式（populatio

28、n type）種群參數(shù)種群規(guī)模（population size）初始種群的個(gè)體取值范圍（Initial range）選擇操作個(gè)體選擇概率分配策略（對應(yīng)Fitness scaling）個(gè)體選擇方法（Selection function）最佳個(gè)體保存優(yōu)良個(gè)體保存數(shù)量（Elite count）交叉操作交叉概率（Crossover fraction）交叉方式（Crossover function）變異操作變異方式(Mutation function)停止參數(shù)最大迭代步數(shù)（Generations）最大運(yùn)行時(shí)間限制（Time limit）最小適應(yīng)度限制（Fitness limit）停滯代數(shù)（Stall g

29、enerations）停滯時(shí)間限制（Stall time limit）3） 設(shè)置種群的不同初始范圍，例如1;1.1、1;100和1;2，畫出相應(yīng)的最佳適應(yīng)度值(Best fitness)和平均距離（Distance）圖，比較分析初始范圍及種群多樣性對遺傳算法性能的影響。4） 設(shè)置不同的交叉概率（Crossover fraction=0、0.8、1），畫出無變異的交叉（Crossover fraction=1）、無交叉的變異(Crossover fraction=0)以及交叉概率為0.8時(shí)最佳適應(yīng)度值(Best fitness)和和平均距離（Distance）圖，分析交叉和變異操作對算法性能的影

30、響。五、實(shí)驗(yàn)報(bào)告要求：1畫出遺傳算法的算法流程圖。2根據(jù)實(shí)驗(yàn)內(nèi)容，給出相應(yīng)結(jié)果。3. 總結(jié)遺傳算法的特點(diǎn)，并說明適應(yīng)度函數(shù)在遺傳算法中的作用。下面是實(shí)驗(yàn)報(bào)告的基本內(nèi)容和書寫格式。實(shí)驗(yàn)名稱班級： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)原理三、實(shí)驗(yàn)結(jié)果按照實(shí)驗(yàn)內(nèi)容，給出實(shí)驗(yàn)結(jié)果以及結(jié)果分析。四、實(shí)驗(yàn)總結(jié)1. 完成實(shí)驗(yàn)報(bào)告要求3。 2. 總結(jié)實(shí)驗(yàn)心得體會(huì)實(shí)驗(yàn)六 遺傳算法實(shí)驗(yàn)II一、實(shí)驗(yàn)?zāi)康氖煜ず驼莆者z傳算法的原理、流程和編碼策略，理解求解TSP問題的流程并測試主要參數(shù)對結(jié)果的影響，掌握遺傳算法的基本實(shí)現(xiàn)方法。二、實(shí)驗(yàn)原理旅行商問題，即TSP問題（Traveling Salesman Problem）

31、是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，n個(gè)城市之間的相互距離已知，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。用圖論的術(shù)語來說，假設(shè)有一個(gè)圖g=(v,e)，其中v是頂點(diǎn)集，e是邊集，設(shè)d=(dij)是由頂點(diǎn)i和頂點(diǎn)j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過一次的具有最短距離的回路。TSP問題是一個(gè)典型的組合優(yōu)化問題，該問題可以被證明具有NPC計(jì)算復(fù)雜性，其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，本實(shí)驗(yàn)

32、采用遺傳算法求解。遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過程。它把問題的參數(shù)用基因代表，把問題的解用染色體代表（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由具有不同染色體的個(gè)體組成的群體。這個(gè)群體在問題特定的環(huán)境里生存競爭，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代。后代隨機(jī)化地繼承了父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過程。群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境的類似個(gè)體，即得到問題最優(yōu)的解。三、實(shí)驗(yàn)內(nèi)容1、參考實(shí)驗(yàn)系統(tǒng)給出的遺傳算法核心代碼，用遺傳算法求解不同規(guī)模（例如10個(gè)城市，20個(gè)城市，100個(gè)城市）的TSP問題，把結(jié)果填入表1。表1 遺傳算法求解

33、不同規(guī)模的TSP問題的結(jié)果城市規(guī)模最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度平均運(yùn)行時(shí)間10201002、對于同一個(gè)TSP問題（例如10個(gè)城市），設(shè)置不同的種群規(guī)模（例如10，20，100）、交叉概率（0，0.5，1）和變異概率（0，0.5，1），把結(jié)果填入表2。3、設(shè)置種群規(guī)模為100，交叉概率為0.85，變異概率為0.15，然后增加1種變異策略（例如相鄰兩點(diǎn)互換變異、逆轉(zhuǎn)變異或插入變異等）和1種個(gè)體選擇概率分配策略（例如按線性排序或者按非線性排序分配個(gè)體選擇概率）用于求解同一TSP問題（例如10個(gè)城市），把結(jié)果填入表3。表2 不同的種群規(guī)模、交叉概率和變異概率的求解結(jié)果種群規(guī)模交叉概率變異概率最好適應(yīng)

34、度最差適應(yīng)度平均適應(yīng)度平均運(yùn)行時(shí)間100.850.15200.850.151000.850.1510000.151000.50.1510010.151000.8501000.850.51000.851表3 不同的變異策略和個(gè)體選擇概率分配策略的求解結(jié)果變異策略個(gè)體選擇概率分配最好適應(yīng)度最差適應(yīng)度平均適應(yīng)度平均運(yùn)行時(shí)間兩點(diǎn)互換按適應(yīng)度比例分配兩點(diǎn)互換按適應(yīng)度比例分配 4、提交實(shí)驗(yàn)報(bào)告和源程序。四、實(shí)驗(yàn)報(bào)告要求： 1、畫出遺傳算法求解TSP問題的流程圖。2、分析遺傳算法求解不同規(guī)模的TSP問題的算法性能。3、對于同一個(gè)TSP問題，分析種群規(guī)模、交叉概率和變異概率對算法結(jié)果的影響。 4、增加1種變異

35、策略和1種個(gè)體選擇概率分配策略，比較求解同一TSP問題時(shí)不同變異策略及不同個(gè)體選擇分配策略對算法結(jié)果的影響。下面是實(shí)驗(yàn)報(bào)告的基本內(nèi)容和書寫格式。實(shí)驗(yàn)名稱班級： 學(xué)號(hào)： 姓名： 一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)原理三、實(shí)驗(yàn)結(jié)果按照實(shí)驗(yàn)內(nèi)容，給出相應(yīng)結(jié)果。四、實(shí)驗(yàn)總結(jié)1. 完成實(shí)驗(yàn)報(bào)告要求2, 3和4。 2. 總結(jié)實(shí)驗(yàn)心得體會(huì)實(shí)驗(yàn)七 基于神經(jīng)網(wǎng)絡(luò)的模式識(shí)別實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康睦斫釨P神經(jīng)網(wǎng)絡(luò)和離散Hopfield神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和原理，掌握反向傳播學(xué)習(xí)算法對神經(jīng)元的訓(xùn)練過程，了解反向傳播公式。通過構(gòu)建BP網(wǎng)絡(luò)和離散Hopfield網(wǎng)絡(luò)模式識(shí)別實(shí)例，熟悉前饋網(wǎng)絡(luò)和反饋網(wǎng)絡(luò)的原理及結(jié)構(gòu)。二、實(shí)驗(yàn)原理BP學(xué)習(xí)算法是通過

36、反向?qū)W習(xí)過程使誤差最小，其算法過程從輸出節(jié)點(diǎn)開始，反向地向第一隱含層(即最接近輸入層的隱含層)傳播由總誤差引起的權(quán)值修正。BP網(wǎng)絡(luò)不僅含有輸入節(jié)點(diǎn)和輸出節(jié)點(diǎn)，而且含有一層或多層隱(層)節(jié)點(diǎn)。輸入信號(hào)先向前傳遞到隱節(jié)點(diǎn)，經(jīng)過作用后，再把隱節(jié)點(diǎn)的輸出信息傳遞到輸出節(jié)點(diǎn)，最后給出輸出結(jié)果。離散Hopfield神經(jīng)網(wǎng)絡(luò)的聯(lián)想記憶過程分為學(xué)習(xí)和聯(lián)想兩個(gè)階段。在給定樣本的條件下，按照Hebb學(xué)習(xí)規(guī)則調(diào)整連接權(quán)值，使得存儲(chǔ)的樣本成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)，這就是學(xué)習(xí)階段。聯(lián)想是指在連接權(quán)值不變的情況下，輸入部分不全或者受了干擾的信息，最終網(wǎng)絡(luò)輸出某個(gè)穩(wěn)定狀態(tài)。三、實(shí)驗(yàn)條件Matlab 7.X 的神經(jīng)網(wǎng)絡(luò)工具箱：在M

37、atlab 7.X 的命令窗口輸入nntool，然后在鍵盤上輸入Enter鍵，即可打開神經(jīng)網(wǎng)絡(luò)工具箱。四、實(shí)驗(yàn)內(nèi)容1. 針對教材P243例8.1，設(shè)計(jì)一個(gè)BP網(wǎng)絡(luò)結(jié)構(gòu)模型（63-6-9），并以教材圖8.5 為訓(xùn)練樣本數(shù)據(jù)，圖8.6為測試數(shù)據(jù)。（1）從Matlab工作空間導(dǎo)入（Import）訓(xùn)練樣本數(shù)據(jù)（inputdata，outputdata）和測試數(shù)據(jù)（testinputdata），然后新建一個(gè)神經(jīng)網(wǎng)絡(luò)（New Network），選擇參數(shù)如下表1，給出BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖。表1 BP網(wǎng)絡(luò)結(jié)構(gòu)模型的各項(xiàng)參數(shù)設(shè)置Network Name（神經(jīng)網(wǎng)絡(luò)名稱）Network Type（神經(jīng)網(wǎng)絡(luò)類型）Fee

38、d-forward backprop（前饋反向傳播）Input ranges（輸入信息范圍）來自訓(xùn)練樣本的輸入數(shù)據(jù)（inputdata）Training function（訓(xùn)練函數(shù)）TRAINGD(梯度下降BP算法)Performance function（性能函數(shù)）MSE（均方誤差）Number of layers（神經(jīng)網(wǎng)絡(luò)層數(shù)）2Layer1（第1層）的Number of neurons (神經(jīng)元個(gè)數(shù))6Layer1（第1層）的Transfer Function (傳遞函數(shù))TANSIG(雙曲正切S型函數(shù))Layer2（第2層）的Number of neurons (神經(jīng)元個(gè)數(shù))9Laye

39、r2（第2層）的Transfer Function (傳遞函數(shù))LOGSIG（S型函數(shù)）（2）輸入訓(xùn)練樣本數(shù)據(jù)（inputdata，outputdata），隨機(jī)初始化連接權(quán)（Initialize Weights），給出BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練成功后的誤差變化曲線圖，訓(xùn)練參數(shù)設(shè)置如表2所示。表2 BP網(wǎng)絡(luò)訓(xùn)練參數(shù)訓(xùn)練次數(shù)（epochs）1000訓(xùn)練時(shí)間（time）Inf訓(xùn)練目標(biāo)（goal）0學(xué)習(xí)率（lr）0.3最大確認(rèn)失敗次數(shù)（max_fail）5最小性能梯度（min_grad）1e-025兩次顯示之間的訓(xùn)練步數(shù)（show）25（3）選擇不同的訓(xùn)練函數(shù)，例如TRAINGDM（梯度下降動(dòng)量BP算法）、TRAINLMM（Levenberg-Marquardt BP訓(xùn)練函數(shù)），然后輸入訓(xùn)練樣本數(shù)據(jù)（inputdata，outputdata），訓(xùn)練參數(shù)設(shè)置如表2所示，設(shè)置相同的初始連接權(quán)（Revert Weigh