1、人工智能實驗指導(dǎo)書專業(yè)年級姓名學(xué)號指導(dǎo)老師實驗室使用日期實驗一啟發(fā)式搜索一、實驗?zāi)康模菏煜ず驼莆諉l(fā)式搜索的定義、估價函數(shù)和算法過程，并利用A算法求解九宮問題，理解求解流程和搜索順序。二、實驗方法：先熟悉啟發(fā)式搜索算法；用C、C+或JAVA語言編程實現(xiàn)實驗內(nèi)容。三、實驗背景知識：估價函數(shù)在對問題的狀態(tài)空間進(jìn)行搜索時，為提高搜索效率需要和被解問題的解有關(guān)的大量控制性知識作為搜索的輔助性策略。這些控制信息反映在估價函數(shù)中。估價函數(shù)的任務(wù)就是估計待搜索節(jié)點的重要程度，給這些節(jié)點排定次序。估價函數(shù)可以是任意一種函數(shù)，如有的定義它是節(jié)點x處于最佳路徑的概率上，或是x節(jié)點和目標(biāo)節(jié)點之間的距離等等。在此，我

2、們把估價函數(shù)f(n)定義為從初始節(jié)點經(jīng)過n節(jié)點到達(dá)目標(biāo)節(jié)點的最小代價路徑的代價估計值，它的一般形式是：f(n)=g(n)+h(n)其中g(shù)(n)是從初始節(jié)點到節(jié)點n的實際代價，g(n)可以根據(jù)生成的搜索樹實際計算出來；h(n)是從n到目標(biāo)節(jié)點的最佳路徑的代價估計，h(n)主要體現(xiàn)了搜索的啟發(fā)信息。啟發(fā)式搜索過程的特性可采納性當(dāng)一個搜索算法在最短路徑存在的時候能保證能找到它，我們就稱該算法是可米納的。所有A*算法都是可米納的。單調(diào)性一個啟發(fā)函數(shù)h是單調(diào)的，如果對所有的狀態(tài)n.和n.,其中n.是n.的子孫，h(n.)-h(n.)ijjiijSst(n已),其中cost(吧)是從n.到n.實際代價。目

3、標(biāo)狀態(tài)的啟發(fā)函數(shù)值為0,即h(Goal)=0.具有單調(diào)性的啟發(fā)式搜索算法在對狀態(tài)進(jìn)行擴(kuò)展時能保證所有被擴(kuò)展的狀態(tài)的f值是單調(diào)遞增(不減)。信息性比較兩個啟發(fā)策略hl和h2,如果對搜索空間中的任何一個狀態(tài)n都有hl(n)Wh2(n),就說h2比hl具有更多的信息性。一般而言，若搜索策略h2比hl有更多的信息性，則h2比hl考察的狀態(tài)要少。但必須注意的是更多信息性需要更多的計算時間,從而有可能抵消減少搜索空間所帶來的益處。常用的啟發(fā)式搜索算法(1)局部擇優(yōu)搜索算法(瞎子爬山法)瞎子爬山法是最簡單的啟發(fā)式算法之一。該算法在搜索過程中擴(kuò)展當(dāng)前節(jié)點并估價它的子節(jié)點。最優(yōu)的子節(jié)點別選擇并進(jìn)一步擴(kuò)展；該子節(jié)

4、點的兄弟節(jié)點和父節(jié)點都不再被保留。當(dāng)搜索到達(dá)一種狀態(tài)，該狀態(tài)比它的所有子狀態(tài)都要好，則搜索停止。因此，該算法的估價函數(shù)可表示為f(n)=h(n)。在一個限定的環(huán)境下，瞎子爬山法可能會極大的提高搜索的效率，但是對整個搜索空間而言，可能得不到全局最優(yōu)解。(2)最好優(yōu)先搜索法(有序搜索法)該算法的估價函數(shù)采用f(n)=g(n)+h(n),在搜索過程中算法使用OPEN表和CLOSE表來記錄節(jié)點信息：OPEN表中保留所有已生成而未考察的節(jié)點；CLOSE表中保留所有已訪問過的節(jié)點。算法在每一次搜索過程中都會對OPEN表中的節(jié)點按照每個節(jié)點的f值進(jìn)行排序，選擇f值最小節(jié)點進(jìn)行擴(kuò)展。算法的描述如下：把起始節(jié)點

5、S放到OPEN表中，計算f(S),并把其值與節(jié)點S聯(lián)系起來。若OPEN是個空表，則算法失敗退出，無解。從OPEN表中選擇一個f值最小的節(jié)點i。結(jié)果有幾個節(jié)點合格，當(dāng)其中有一個為目標(biāo)節(jié)點時，則選擇此目標(biāo)節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點i。把節(jié)點i從OPEN表中移出，并把它放入到CLOSED的擴(kuò)展節(jié)點表中。若節(jié)點i是個目標(biāo)節(jié)點，則成功退出，求得一個解。擴(kuò)展i，生成其全部后繼節(jié)點。對i的每個后繼節(jié)點j：計算f(j)。如果j既不在OPEN表中，也不在CLOSED表中，則用估價函數(shù)f將其添加到OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標(biāo)節(jié)點時記住一個解答路徑。如果j已則OPEN表中

6、或CLOSED表中，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f的值。若新的f值較小，則(i)以此值取代舊值。從j指向i,而不是指向它的父輩節(jié)點。若節(jié)點j在CLOSED表中，則把它移回OPEN表。轉(zhuǎn)向。四、實驗內(nèi)容：問題描述：用啟發(fā)式搜索方法求解下列九宮問題狀態(tài)表示的數(shù)據(jù)結(jié)構(gòu)狀態(tài)擴(kuò)展規(guī)則的表示搜索產(chǎn)生的狀態(tài)空間圖(4)OPEN表和CLOSE表變化過程程序清單實驗結(jié)果討論a你所采用的估價函數(shù)f(n)=g(n)+h(n)中，g(n)和h(n)的主要作用是什么？b結(jié)合本實驗舉例說明不同啟發(fā)策略對實驗的效果有何影響？c若問題的初始狀態(tài)是隨機(jī)產(chǎn)生的，你的實驗程序應(yīng)該如何改進(jìn)？實驗二基于產(chǎn)生式

7、系統(tǒng)的問題求解一、實驗?zāi)康模菏煜ず驼莆债a(chǎn)生式系統(tǒng)的構(gòu)成和運行機(jī)制，掌握基于規(guī)則推理的基本方法和技術(shù)。二、實驗方法：1.先熟悉產(chǎn)生式系統(tǒng)的基本概念；2.用C、C+或JAVA語言編程實現(xiàn)實驗內(nèi)容。三、實驗背景知識：產(chǎn)生式系統(tǒng)（Productionsystem）首先由波斯特（Post）于1943年提出的產(chǎn)生式規(guī)則（Productionrule）而得名，他們用這種規(guī)則對符號串進(jìn)行置換運算，后來，美國的紐厄爾和西蒙利用這個原理建立了一個人類的認(rèn)知模型（1965年），同年，斯坦福大學(xué)利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設(shè)計出第一個專家系統(tǒng)DENDRAL。產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概念為基礎(chǔ)的系統(tǒng)。這個基本概念

8、就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對象的概念。在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部份：（1）事實：用于表示靜態(tài)知識，如事物、事件和它們之間的關(guān)系；（2）規(guī)則：用于表示推理過程和行為一個產(chǎn)生式系統(tǒng)由三個部分組成，如圖所示：1）總數(shù)據(jù)庫：用來存放與求解問題有關(guān)的數(shù)據(jù)以及推理過程環(huán)境的當(dāng)前狀態(tài)的描述。2）產(chǎn)生式規(guī)則庫：主要存放問題求解中的規(guī)則。（3）控制策略：其作用是說明下一步應(yīng)該選用什么規(guī)則，也就是說如何應(yīng)用規(guī)則。通常從選擇規(guī)則到執(zhí)行操作分三步：（1）匹配：把當(dāng)前數(shù)據(jù)庫和規(guī)則的條件部分相匹配。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。（2）沖突解決：當(dāng)有一個以上的規(guī)則條件部分和當(dāng)前數(shù)據(jù)庫相匹配時，就

9、需要解決首先使用哪一條規(guī)則沖突解決。1）專一性排序：如果某一規(guī)則的條件部分比另一條規(guī)則的條件部分所規(guī)定的情況更為專門，則這條規(guī)則有較高的優(yōu)先權(quán)。2）規(guī)則排序：如果規(guī)則編排順序就表示了啟用的優(yōu)先級，則稱之為排序。3）數(shù)據(jù)排序：把規(guī)則條件部分的所有條件按優(yōu)先級次序編排起來，運行時首先使用在條件部分包含較高優(yōu)先級數(shù)據(jù)的規(guī)則。4）規(guī)模排序：按規(guī)則的條件部分的規(guī)模排列優(yōu)先級，優(yōu)先使用被滿足的條件較多的規(guī)則。5）就近排序：把最近使用的規(guī)則放在最優(yōu)先的位置。6）上下文限制：把產(chǎn)生式規(guī)則按他們所描述的上下文分組，也就是說按上下文對規(guī)則分組，在某種上下文條件下，只能從與其相對應(yīng)的那組規(guī)則中選擇可應(yīng)用的規(guī)則。7）

10、使用次數(shù)排序：把使用頻率較高的排在前面。（3）操作：執(zhí)行規(guī)則的操作部分，經(jīng)過修改以后，當(dāng)前數(shù)據(jù)庫將被修改。四、實驗內(nèi)容：問題描述：用基于產(chǎn)生式系統(tǒng)的方法求解傳教士和野人問題有N個傳教士和N個野人來到河邊準(zhǔn)備渡河，河岸有一條船，每次至多可供K個乘渡，問傳教士為了安全起見，應(yīng)如何規(guī)劃擺渡方案，使得任何時刻，河岸兩邊以及船上的野人數(shù)目總是不超過傳教土的數(shù)目，即求解傳教士和野人從左岸全部擺渡到右岸的過程中，任何時刻滿足M（傳教士數(shù)）$C（野人數(shù)）和M+CWK的擺渡方案。五、問題（1）問題狀態(tài)的表示（2）數(shù)據(jù)庫描述（3）規(guī)則庫的描述（4）控制機(jī)制（5）狀態(tài)空間圖（6）程序清單（7）實驗結(jié)果討論a.你采用

11、何種策略來控制產(chǎn)生式系統(tǒng)的搜索？b你能否對產(chǎn)生式系統(tǒng)進(jìn)行改進(jìn)，若能請把你的想法寫下來。實驗三歸結(jié)原理一、實驗?zāi)康氖煜ず驼莆諝w結(jié)原理的基本思想和基本方法，通過實驗培養(yǎng)學(xué)生利用邏輯方法表示知識，并掌握采用機(jī)器推理來進(jìn)行問題求解的基本方法。二、實驗要求1.先熟悉歸結(jié)原理的基本思想和歸結(jié)否證的步驟；用C、C+、JAVA或Prolog語言編程實現(xiàn)實驗內(nèi)容；利用所學(xué)的知識及實驗結(jié)果，來完成實驗報告的各項內(nèi)容。三、實驗背景知識歸結(jié)是一種應(yīng)用于謂詞演算中的定理證明技術(shù)，從60年代中期開始，它就成為人工智能問題求解研究的一個組成部分。歸結(jié)原理描述了如何用最少的合一次數(shù)在一個子句數(shù)據(jù)庫中發(fā)現(xiàn)矛盾的方法。歸結(jié)否證定

12、理證明的方法是，對所要證明的命題取反，把它加到一個已知為真的公里集中，然后用歸結(jié)推理規(guī)則證明這將導(dǎo)致一個矛盾，一旦定理證明程序證明了否定目標(biāo)與已知的公理集合不一致，就能推導(dǎo)出原來的目標(biāo)與公理集是一致的。這就證明了該定理。歸結(jié)否證包含以下步驟：（1）把前提或公理轉(zhuǎn)換成子句形式；（2）把求證目標(biāo)的否定的子句形式加到公理集合中；（3）對所有這些子句進(jìn)行歸結(jié)，產(chǎn)生它們的邏輯結(jié)果子句；（4）用產(chǎn)生空子句的方法來得出矛盾；（5）否定目標(biāo)的否證在用于產(chǎn)生空子句的代換下為真。如何把前提或公理化為子句形式是進(jìn)行歸結(jié)的前提，其過程包含如下步驟：（1）消去蘊(yùn)涵符號用PVQ替換P-Q（2）減少否定符號的轄域每個否定符

13、號最多只作用在一個謂詞符號上（3）對變量標(biāo)準(zhǔn)化每個變量僅受一個量詞作用（4）消去存在量詞若存在量詞前沒有全稱量詞，則直接消去;否則，要Skolem。化。（5）化為前束范式前束范式：一個公式，如果量詞均非否定地出現(xiàn)在公式最前面，其轄域延伸到整個公式的末尾，且在公式中僅含有聯(lián)結(jié)詞，V,A，則稱此種形式為前束范式。前束范式=（前綴）（母式）（6）化母式為合取范式（7）消去全稱量詞（8）消去連接詞符號人用A,B替代（AAB）（9）將分離的變元歸一化四、實驗內(nèi)容問題描述：四對夫婦中，王結(jié)婚時，周送了禮；周和錢是同一排球隊的隊員；李的愛人是陳的愛人的表哥；陳夫婦與鄰居吵架時，徐、周、吳的愛人都去助戰(zhàn)；李、

14、徐、周結(jié)婚前住在同一宿舍，試用歸結(jié)原理求王、周、錢、陳、李、徐、吳、孫幾人誰和誰是夫婦。五、問題（1）利用邏輯表達(dá)式對問題的前提和結(jié)論進(jìn)行描述。（2）將前提和結(jié)論的否定化為子句形式。（3）寫出問題的子句集形式。（4）利用歸結(jié)原理對問題進(jìn)行求解，寫出求解過程。（5）編寫程序進(jìn)行問題求解，列出程序清單。（6）寫出實驗結(jié)果。（7）實驗結(jié)果討論：你在實驗中采用的歸結(jié)策略是何種策略，能否有該進(jìn)？如何改進(jìn)？實驗四簡單遺傳算法一、實驗?zāi)康模菏煜ず驼莆者z傳算法的基本思想和基本方法，通過實驗培養(yǎng)學(xué)生利用遺傳算法進(jìn)行問題求解的基本技能，并且了解進(jìn)化計算其他分支的基本思想和基本方法。二、實驗方法：1.先熟悉進(jìn)化計算

15、中遺傳算法的基本思想和流程；2.用C、C+、JAVA或Prolog語言編程實現(xiàn)實驗內(nèi)容。三、實驗背景知識：生物群體的生存過程普遍遵循達(dá)爾文的物競天擇、適者生存的進(jìn)化準(zhǔn)則。群體中的個體根據(jù)對環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進(jìn)化計算(evolutionarycomputation,EC)就是通過模擬自然物群進(jìn)化的一類非常魯棒的優(yōu)化算法，它們模擬群體(其中組成群體的每個個體表示搜索問題解空間中的一個解)的集體學(xué)習(xí)過程，從任意初始群體出發(fā)，通過隨機(jī)選擇、變異和交叉過程，使群體進(jìn)化學(xué)習(xí)到搜索空間中越來越好的區(qū)域。進(jìn)化計算中選擇過程使群體中適應(yīng)性好的個體比適應(yīng)性差的個體有更多的機(jī)會遺傳到下一代中，交

16、叉算子將父代信息結(jié)合在一起并他們遺傳給下一代個體，而變異過程在群體中引入新的變種。進(jìn)化計算包括遺傳算法(evolutionaryalgorithm,EA)、進(jìn)化策略(evolutionstrategy,ES)、進(jìn)化編程(evolutionaryprogramming,EP)、遺傳編程(geneticprogramming,GP）。遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對生物進(jìn)化過程的一種數(shù)學(xué)仿真，是進(jìn)化計算的一種最重要形式。遺傳算法為那些那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題找出了一個解決方法。自從Holland于1975年在其著作AdaptationinNat

17、uralandArtificialSystem中首次提出遺傳算法以來，經(jīng)過近30年的研究，現(xiàn)在已發(fā)展到一個比較成熟的階段，并且在實際中已經(jīng)得到了很好的應(yīng)用。1.簡單遺傳算法的構(gòu)成要素（1）染色體編碼和解碼方法在實現(xiàn)對一個問題用遺傳算法之前，我們必須先對問題的解空間進(jìn)行編碼，以便使得它能夠由遺傳算法進(jìn)行操作。解碼就是把遺傳算法操作的個體轉(zhuǎn)換成原來問題結(jié)構(gòu)的過程。常見的編碼方法有：二進(jìn)制編碼、浮點數(shù)編碼、格雷碼等。以二進(jìn)制為例：假設(shè)某一參數(shù)的取值范圍是A,B,AVB，我們有長度為l的二進(jìn)制編碼串來表示該參數(shù)，將A，B等分成21-1個子部分，每個等分的長度為&則它能夠產(chǎn)生2l種不同的編碼。00000

18、0000000000000000=0fA000000000000000000001=1fA+S111111111111111111111=1B二進(jìn)制編碼的最大缺點是使得遺傳算法操作的個體位串太長，這容易降低遺傳算法的運行效率，很多問題采用其他編碼方法可能更有利。如對于函數(shù)優(yōu)化問題，浮點數(shù)編碼方法就更有效，而二進(jìn)制編碼方法不但容易降低遺傳算法的運行效率，而且會產(chǎn)生精度損失。浮點數(shù)編碼方法是指個體的每個染色體用某一范圍內(nèi)的一個浮點數(shù)表示，個體的編碼長度就等于問題變量的個數(shù)。在實際運用遺傳算法解決問題時，一般都需要根據(jù)具體的問題采用合適的編碼方法，這樣更有利于遺傳算法搜索到問題的最優(yōu)解。（2）適應(yīng)度

19、函數(shù)遺傳算法在進(jìn)化搜索中基本上不用外部信息，僅用目標(biāo)函數(shù)也就是適應(yīng)度函數(shù)為依據(jù)。適應(yīng)度函數(shù)是用于度量問題中每一個染色體優(yōu)劣程度的函數(shù)，體現(xiàn)了染色體的適應(yīng)能力。遺傳算法的目標(biāo)函數(shù)不受連續(xù)可微的約束且定義域可以是任意集合。但對適應(yīng)度函數(shù)有一個要求就是針對輸入可以計算出的能加以比較的結(jié)果必須是非負(fù)的。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而設(shè)計。因為適應(yīng)度函數(shù)對個體的評估是遺傳算法進(jìn)行個體選擇的唯一依據(jù)，因此適應(yīng)度函數(shù)的設(shè)計直接影響到遺傳算法的性能。對于很多問題，可以直接把求解問題的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)使用，但也存在很多問題需要進(jìn)行一定的轉(zhuǎn)換才能使得目標(biāo)函數(shù)可以用作遺傳算法的適應(yīng)度

20、函數(shù)。（3）遺傳算子遺傳算法主要有三種操作算子：選擇（selection）、交叉(crossover)、變異(mutation)。Q選擇算子選擇算子根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度選擇下一代個體。一般地，選擇算子將使適應(yīng)度函數(shù)值較大的個體有較大的機(jī)會被遺傳到下一代，而適應(yīng)度函數(shù)值較小的個體被遺傳到下一代的機(jī)會較小。一般常采用的選擇算子是賭輪選擇機(jī)制。賭輪選擇算子的基本原理如下。令工f表示種群的適應(yīng)度值之總和，f表示群體中第i個染色體ii的適應(yīng)度值，則第i個個體產(chǎn)生后代的能力正好為其適應(yīng)度值與群體適應(yīng)度值的比值fj工f。賭輪選擇算子在個體數(shù)不太多時，有可能出現(xiàn)不正確反映個體適應(yīng)度的選擇過程

21、，也就是說適應(yīng)度高的個體有可能反而被淘汰了。為了改進(jìn)賭輪選擇算子的這種缺點，有很多改進(jìn)的交叉選擇算子。如：最佳個體保存法、期望值方法、排序選擇方法、聯(lián)賽選擇方法、排擠方法等。交叉算子在自然界生物進(jìn)化過程中，起核心作用的是生物遺傳基因的重組（加上變異）。同樣，遺傳算法中，起核心作用的是遺傳操作的交叉算子。所謂交叉算子就是把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉算子設(shè)計一般與所求解的具體問題有關(guān)，但都應(yīng)該考慮以下兩點：設(shè)計的交叉算子必須能保證前一代中優(yōu)秀個體的性狀能在后一代的新個體中盡可能得到遺傳和繼承。交叉算子與問題的編碼是相互聯(lián)系的

22、，因此，交叉算子設(shè)計和編碼設(shè)計需協(xié)調(diào)操作，也就是所謂的編碼交叉設(shè)計。對于字符串編碼的遺傳算法，交叉算子主要有一點交叉、兩點交叉、多點交叉和一致交叉等。其中一點交叉的主要操作過程如下。假設(shè)兩個配對個體為P1、P2分別如下所示。經(jīng)過一點交叉后，得到兩個新的個體P1、P2。001PlP2J110P2交叉點交叉點對于實數(shù)編碼的遺傳算法，交叉算子主要是采用算術(shù)交叉算子。假設(shè)兩個配對個體分別為Pl=（xl,y1）和P2=（x2,y2）。在Pl和P2進(jìn)行算術(shù)交叉后得到的兩個新個體P和P分別可由下式計算得到。12P=（九P+（1九）P112P=（1九）P+九P212Q變異算子變異算子是改變數(shù)碼串中某個位置上的

23、數(shù)碼。遺傳算法中引入變異算子有兩個目的：其一是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解領(lǐng)域時，利用變異算子的這種局部隨機(jī)搜索能力可以加速遺傳算法向最優(yōu)解收斂。一般在這種情況下，遺傳算法的變異概率應(yīng)取較小的值，否則接近最優(yōu)解的積木塊會因為變異而遭到破壞。其二是使遺傳算法可以維持較好的群體多樣性，以防止遺傳算法出現(xiàn)未成熟收斂現(xiàn)象。此時，遺傳算法的變異概率應(yīng)取較大的值。遺傳算法中，交叉算子具有很好的全局搜索能力，是法的主要操作算子。變異算子具有較好的局部搜索能力，是算法的輔助操作算子。遺傳算法通過交叉和變異這一對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能

24、力。變異算子除了基本的變異算子壞，還有很多有效的變異算子。如逆轉(zhuǎn)變異算子、自適應(yīng)變異算子等。對于字符串編碼的遺傳算法，基本變異算子就是隨機(jī)的從個體中選擇某些基因位，然后以一定的概率對這些基因位進(jìn)行翻轉(zhuǎn)變異，也就是把這些基因位中為0的基因位以概率Pm變?yōu)?，為1的基因為以概率Pm變?yōu)?。對于實數(shù)編碼的遺傳算法，一般采用隨機(jī)變異的方式，使變異個體的每一個變量分量加上一個隨機(jī)數(shù)，一般使用均為分布的隨機(jī)數(shù)或者是高斯分別的隨機(jī)數(shù)?；具z傳算法運行參數(shù)N：群體大小，即群體中所含個體的數(shù)量，一般取20100T：遺傳算法的終止進(jìn)化代數(shù)，一般取100500pc:雜交概率，一般取0.40.99pm:變異概率，一般

25、取0.00010.1pr:復(fù)制概率算法過程：簡單遺傳算法的基本流程如下：初始化群體：隨機(jī)產(chǎn)生一個由確定長度的特征串組成的初始群體計算群體上每個個體的適應(yīng)度值（3）按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體，也就是選擇算子操作。（4）按概率Pc對配對池中的個體進(jìn)行交叉算子操作。（5）按概率Pm對交叉算子產(chǎn)生的所有新個體進(jìn)行變異操作。（6）若沒有滿足某種停止條件，則轉(zhuǎn)（2），否則進(jìn)入下一步。（7）輸出群體中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。四、實驗內(nèi)容：問題描述：用遺傳算法求解函數(shù)f（x）二x*sin（10n+x）+1.0在區(qū)間T,2的最大值。五、問題（1）問題的編碼和解碼

26、表示（2）適應(yīng)度函數(shù)確定（3）算法參數(shù)設(shè)置（4）選擇算子的設(shè)計（5）交叉算子的設(shè)計（6）變異算子的設(shè)計（7）算法的結(jié)束條件（8）程序清單（9）實驗結(jié)果討論a.什么是過早收斂和過慢結(jié)束？造成上述狀況的原因有哪些？b.你的程序有沒有要改進(jìn)之處？如何改進(jìn)？實驗五示例學(xué)習(xí)一、實驗?zāi)康模菏煜ず驼莆帐纠龑W(xué)習(xí)的基本思想和基本方法，通過實驗培養(yǎng)學(xué)生利用示例學(xué)習(xí)進(jìn)行問題求解的基本技能。二、實驗方法：1.先熟悉示例學(xué)習(xí)中常見算法的基本思想和流程；用C、C+、JAVA或Prolog語言編程實現(xiàn)實驗內(nèi)容。利用所學(xué)的知識及實驗結(jié)果，來完成實驗報告的各項內(nèi)容。三、實驗背景知識：示例學(xué)習(xí)（Learningfromexamp

27、les）又稱為實例學(xué)習(xí)或從例子中學(xué)習(xí)，它是通過從環(huán)境中取得若干與某概念有關(guān)的例子，經(jīng)歸納得出一般性概念的一種學(xué)習(xí)方法。在這種學(xué)習(xí)方法中，外部環(huán)境（教師）提供的是一組例子（正例和反例），這些例子實際上是一組特殊的知識，每一個例子表達(dá)了僅適用于該例子的知識，示例學(xué)習(xí)就是要從這些特殊知識中歸納出適用于更大范圍的一般性知識，它將覆蓋所有的正例并排除所有反例。其任務(wù)是：給定函數(shù)f（未知）的實例集合，返回一個近似于f的函數(shù)hh稱為假設(shè)，所有h的集合稱為假設(shè)空間。Simon于1974年在一篇論文中，把從示例學(xué)習(xí)的問題描述為使用示教例子來指導(dǎo)對規(guī)則的搜索，并提出了兩空間模型。其中，實例空間模型為所有示教例子的集合。規(guī)則空間模型為所有規(guī)則的集合。兩者的關(guān)系是：系統(tǒng)對實例空間的搜索完成實例選擇，并將這些選中的活躍實例提交解釋過程；解釋過程對實例經(jīng)過適當(dāng)?shù)霓D(zhuǎn)化，將這些實例變換為規(guī)則空間中的特定概念，以引導(dǎo)規(guī)則空間的搜索。對實例空間而言示教例子的質(zhì)量和實例空間的搜索是兩個值得注意的問題：（1）高質(zhì)量的例子是無二義性的，它可以為規(guī)則空間的搜索提供可靠的指導(dǎo)；另外示教例子的排列次序也會影響學(xué)習(xí)。（2）搜索實例空間的目