找回密碼
 立即注冊(cè)

QQ登錄

只需一步，快速開始

搜索
查看: 4099|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

啟發(fā)式搜索,簡單遺傳算法,候選消除算法源碼 人工智能實(shí)驗(yàn)報(bào)告

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:365689 發(fā)表于 2018-7-5 16:13 | 只看該作者 回帖獎(jiǎng)勵(lì) |倒序?yàn)g覽 |閱讀模式
本科實(shí)驗(yàn)報(bào)告
課程名稱：   人工智能        
實(shí)驗(yàn)項(xiàng)目：1.啟發(fā)式搜索2.基于產(chǎn)生式系統(tǒng)的問
題求解3簡單遺傳算法4候選消除算法
實(shí)驗(yàn)地點(diǎn)：實(shí)驗(yàn)樓110
專業(yè)班級(jí)：物聯(lián)網(wǎng)1501 學(xué)號(hào)：2015001962
學(xué)生姓名：程*
指導(dǎo)教師：強(qiáng)*   

實(shí)驗(yàn)一 啟發(fā)式搜索
一 實(shí)驗(yàn)?zāi)康?br /> 熟悉和掌握啟發(fā)式搜索的定義、估價(jià)函數(shù)和算法過程，并利用A算法求解相關(guān)問題，理解求解流程和搜索順序。
先熟悉啟發(fā)式搜索算法；
     用C、C++、JAVA或python             語言編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。
二 實(shí)驗(yàn)內(nèi)容以及原理
估價(jià)函數(shù)
在對(duì)問題的狀態(tài)空間進(jìn)行搜索時(shí)，為提高搜索效率需要和被解問題的解有關(guān)的大量控制性知識(shí)作為搜索的輔助性策略。這些控制信息反映在估價(jià)函數(shù)中。
估價(jià)函數(shù)的任務(wù)就是估計(jì)待搜索節(jié)點(diǎn)的重要程度，給這些節(jié)點(diǎn)排定次序。估價(jià)函數(shù)可以是任意一種函數(shù)，如有的定義它是節(jié)點(diǎn)x處于最佳路徑的概率上，或是x節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離等等。在此，我們把估價(jià)函數(shù)f(n)定義為從初始節(jié)點(diǎn)經(jīng)過n節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)估計(jì)值，它的一般形式是：
     f(n) = g(n) + h(n)
其中g(shù)(n)是從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，g(n)可以根據(jù)生成的搜索樹實(shí)際計(jì)算出來；h(n)是從n到目標(biāo)節(jié)點(diǎn)的最佳路徑的代價(jià)估計(jì)，h(n)主要體現(xiàn)了搜索的啟發(fā)信息。
啟發(fā)式搜索過程的特性
（1）可采納性
當(dāng)一個(gè)搜索算法在最短路徑存在的時(shí)候能保證能找到它，我們就稱該算法是可采納的。所有A*算法都是可采納的。
（2）單調(diào)性
一個(gè)啟發(fā)函數(shù)h是單調(diào)的，如果

    對(duì)所有的狀態(tài)ni和nj，其中nj是ni的子孫，h(ni)- h(nj)≤cost(ni,nj),其中cost(ni,nj)是從ni到nj實(shí)際代價(jià)。
    目標(biāo)狀態(tài)的啟發(fā)函數(shù)值為0，即h(Goal)=0.

具有單調(diào)性的啟發(fā)式搜索算法在對(duì)狀態(tài)進(jìn)行擴(kuò)展時(shí)能保證所有被擴(kuò)展的狀態(tài)的f值是單調(diào)遞增（不減）。
（3）信息性
比較兩個(gè)啟發(fā)策略h1和h2，如果對(duì)搜索空間中的任何一個(gè)狀態(tài)n都有h1(n)≤h2(n)，就說h2比h1具有更多的信息性。
一般而言，若搜索策略h2比h1有更多的信息性，則h2比h1考察的狀態(tài)要少。但必須注意的是更多信息性需要更多的計(jì)算時(shí)間，從而有可能抵消減少搜索空間所帶來的益處。

3.常用的啟發(fā)式搜索算法
（1）局部擇優(yōu)搜索算法（瞎子爬山法）
瞎子爬山法是最簡單的啟發(fā)式算法之一。該算法在搜索過程中擴(kuò)展當(dāng)前節(jié)點(diǎn)并估價(jià)它的子節(jié)點(diǎn)。最優(yōu)的子節(jié)點(diǎn)別選擇并進(jìn)一步擴(kuò)展；該子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)都不再被保留。當(dāng)搜索到達(dá)一種狀態(tài)，該狀態(tài)比它的所有子狀態(tài)都要好，則搜索停止。因此，該算法的估價(jià)函數(shù)可表示為f(n) = h(n)。
在一個(gè)限定的環(huán)境下，瞎子爬山法可能會(huì)極大的提高搜索的效率，但是對(duì)整個(gè)搜索空間而言，可能得不到全局最優(yōu)解。
（2）最好優(yōu)先搜索法（有序搜索法）
該算法的估價(jià)函數(shù)采用f(n) = g(n) + h(n)，在搜索過程中算法使用OPEN表和CLOSE表來記錄節(jié)點(diǎn)信息：OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)；CLOSE表中保留所有已訪問過的節(jié)點(diǎn)。算法在每一次搜索過程中都會(huì)對(duì)OPEN表中的節(jié)點(diǎn)按照每個(gè)節(jié)點(diǎn)的f值進(jìn)行排序，選擇f值最小節(jié)點(diǎn)進(jìn)行擴(kuò)展。算法的描述如下：
①把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S),并把其值與節(jié)點(diǎn)S聯(lián)系起來。
②若OPEN是個(gè)空表，則算法失敗退出，無解。
③從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。
④把節(jié)點(diǎn)i從OPEN表中移出，并把它放入到CLOSED的擴(kuò)展節(jié)點(diǎn)表中。
⑤若節(jié)點(diǎn)i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。
⑥擴(kuò)展i，生成其全部后繼節(jié)點(diǎn)。對(duì)i的每個(gè)后繼節(jié)點(diǎn)j：

    計(jì)算f(j)。
    如果j既不在OPEN表中，也不在CLOSED表中，則用估價(jià)函數(shù)f將其添加到OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。
    如果j已則OPEN表中或CLOSED表中，則比較剛剛對(duì)j計(jì)算過的f值和前面計(jì)算過的該節(jié)點(diǎn)在表中的f的值。若新的f值較小，則
        以此值取代舊值。
        從j指向i，而不是指向它的父輩節(jié)點(diǎn)。
        若節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表。

⑦轉(zhuǎn)向②。
三 實(shí)驗(yàn)儀器
macOS操作系統(tǒng)
四 實(shí)驗(yàn)步驟/設(shè)計(jì)實(shí)現(xiàn)
設(shè)計(jì)估價(jià)函數(shù)
設(shè)計(jì)算法步驟
編寫實(shí)驗(yàn)程序
2
8
3
1
6
4
7

5
  • 用啟發(fā)式搜索方法求解九宮問題。
1
2
3
8

4
7
6
5

五 實(shí)驗(yàn)代碼
六 實(shí)驗(yàn)結(jié)果以及分析
實(shí)驗(yàn)二 基于產(chǎn)生式系統(tǒng)的問題求解
一 實(shí)驗(yàn)?zāi)康?/font>
熟悉和掌握產(chǎn)生式系統(tǒng)的構(gòu)成和運(yùn)行機(jī)制，掌握基于規(guī)則推理的基本方法和技術(shù)。
1.先熟悉產(chǎn)生式系統(tǒng)的基本概念；
    2.用C、C++或JAVA             語言編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。

二 實(shí)驗(yàn)內(nèi)容以及原理
產(chǎn)生式系統(tǒng)（Production system）首先由波斯特（Post）于1943年提出的產(chǎn)生式規(guī)則（Production rule）而得名，他們用這種規(guī)則對(duì)符號(hào)串進(jìn)行置換運(yùn)算，后來，美國的紐厄爾和西蒙利用這個(gè)原理建立了一個(gè)人類的認(rèn)知模型（1965年），同年，斯坦福大學(xué)利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)出第一個(gè)專家系統(tǒng)DENDRAL。
產(chǎn)生式系統(tǒng)用來描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的系統(tǒng)。這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對(duì)象的概念。
在產(chǎn)生式系統(tǒng)中，論域的知識(shí)分為兩部份：
  • 事實(shí)：用于表示靜態(tài)知識(shí)，如事物、事件和它們之間的關(guān)系；
（2）規(guī)則：用于表示推理過程和行為


一個(gè)產(chǎn)生式系統(tǒng)由三個(gè)部分組成，如圖所示：
  • 總數(shù)據(jù)庫：用來存放與求解問題有關(guān)的數(shù)據(jù)以及推理過程環(huán)境的當(dāng)前狀態(tài)的描述。
產(chǎn)生式規(guī)則庫：主要存放問題求解中的規(guī)則。（3）控制策略：其作用是說明下一步應(yīng)該選用什么規(guī)則，也就是說如何應(yīng)用規(guī)則。




通常從選擇規(guī)則到執(zhí)行操作分三步：
  • 匹配：把當(dāng)前數(shù)據(jù)庫和規(guī)則的條件部分相匹配。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。
（2）沖突解決：當(dāng)有一個(gè)以上的規(guī)則條件部分和當(dāng)前數(shù)據(jù)庫相匹配時(shí)，就需要解決首先使用哪一條規(guī)則——沖突解決。
1）專一性排序：如果某一規(guī)則的條件部分比另一條規(guī)則的條件部分所規(guī)定的情況更為專門，則這條規(guī)則有較高的優(yōu)先權(quán)。
2）規(guī)則排序：如果規(guī)則編排順序就表示了啟用的優(yōu)先級(jí)，則稱之為排序。
3）數(shù)據(jù)排序：把規(guī)則條件部分的所有條件按優(yōu)先級(jí)次序編排起來，運(yùn)行時(shí)首先使用在條件部分包含較高優(yōu)先級(jí)數(shù)據(jù)的規(guī)則。4）規(guī)模排序：按規(guī)則的條件部分的規(guī)模排列優(yōu)先級(jí)，優(yōu)先使用被滿足的條件較多的規(guī)則。
5）就近排序：把最近使用的規(guī)則放在最優(yōu)先的位置。
6）上下文限制：把產(chǎn)生式規(guī)則按他們所描述的上下文分組，也就是說按上下文對(duì)規(guī)則分組，在某種上下文條件下，只能從與其相對(duì)應(yīng)的那組規(guī)則中選擇可應(yīng)用的規(guī)則。
7）使用次數(shù)排序：把使用頻率較高的排在前面。


（3）操作：執(zhí)行規(guī)則的操作部分，經(jīng)過修改以后，當(dāng)前數(shù)據(jù)庫將被修改。
問題描述：用基于產(chǎn)生式系統(tǒng)的方法求解傳教士和野人問題
有N個(gè)傳教士和N個(gè)野人來到河邊準(zhǔn)備渡河，河岸有一條船，每次至多可供K個(gè)乘渡，問傳教士為了安全起見，應(yīng)如何規(guī)劃擺渡方案，使得任何時(shí)刻，河岸兩邊以及船上的野人數(shù)目總是不超過傳教土的數(shù)目，即求解傳教士和野人從左岸全部擺渡到右岸的過程中，任何時(shí)刻滿足M（傳教士數(shù)）≥C（野人數(shù)）和M+C≤K的擺渡方案。

三 實(shí)驗(yàn)儀器
macos
四 實(shí)驗(yàn)步驟/設(shè)計(jì)實(shí)現(xiàn)
設(shè)計(jì)估價(jià)函數(shù)
設(shè)計(jì)算法步驟
編寫實(shí)驗(yàn)程序
五 實(shí)驗(yàn)代碼

六 實(shí)驗(yàn)結(jié)果以及分析
實(shí)驗(yàn)三 遺傳算法
一 實(shí)驗(yàn)?zāi)康?/font>
熟悉和掌握遺傳算法的基本思想和基本方法，通過實(shí)驗(yàn)培養(yǎng)學(xué)生利用遺傳算法進(jìn)行問題求解的基本技能，并且了解進(jìn)化計(jì)算其他分支的基本思想和基本方法。


先熟悉進(jìn)化計(jì)算中遺傳算法的基本思想和流程；
   用C、C++、JAVA或Prolog             語言編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。

二 實(shí)驗(yàn)內(nèi)容以及原理
生物群體的生存過程普遍遵循達(dá)爾文的物競天擇、適者生存的進(jìn)化準(zhǔn)則。群體中的個(gè)體根據(jù)對(duì)環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進(jìn)化計(jì)算(evolutionary computation, EC)就是通過模擬自然物群進(jìn)化的一類非常魯棒的優(yōu)化算法，它們模擬群體(其中組成群體的每個(gè)個(gè)體表示搜索問題解空間中的一個(gè)解)的集體學(xué)習(xí)過程，從任意初始群體出發(fā)，通過隨機(jī)選擇、變異和交叉過程，使群體進(jìn)化學(xué)習(xí)到搜索空間中越來越好的區(qū)域。進(jìn)化計(jì)算中選擇過程使群體中適應(yīng)性好的個(gè)體比適應(yīng)性差的個(gè)體有更多的機(jī)會(huì)遺傳到下一代中，交叉算子將父代信息結(jié)合在一起并他們遺傳給下一代個(gè)體，而變異過程在群體中引入新的變種。進(jìn)化計(jì)算包括遺傳算法(evolutionary algorithm,EA)、進(jìn)化策略(evolution strategy, ES)、進(jìn)化編程(evolutionary programming, EP)、遺傳編程(genetic programming, GP)。
遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對(duì)生物進(jìn)化過程的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的一種最重要形式。遺傳算法為那些那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題找出了一個(gè)解決方法。自從Holland于1975年在其著作《Adaptation in Natural and Artificial Systems》中首次提出遺傳算法
以來，經(jīng)過近30年的研究，現(xiàn)在已發(fā)展到一個(gè)比較成熟的階段，并且在實(shí)際中已經(jīng)得到了很好的應(yīng)用。
1.簡單遺傳算法的構(gòu)成要素
（1）染色體編碼和解碼方法
在實(shí)現(xiàn)對(duì)一個(gè)問題用遺傳算法之前，我們必須先對(duì)問題的解空間進(jìn)行編碼，以便使得它能夠由遺傳算法進(jìn)行操作。解碼就是把遺傳算法操作的個(gè)體轉(zhuǎn)換成原來問題結(jié)構(gòu)的過程。常見的編碼方法有：二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、格雷碼等。以二進(jìn)制為例：假設(shè)某一參數(shù)的取值范圍是[A，B]，A＜B，我們有長度為l的二進(jìn)制編碼串來表示該參數(shù)，將[A，B]等分成2l-1個(gè)子部分，每個(gè)等分的長度為δ，則它能夠產(chǎn)生2l種不同的編碼。
         00000000000…0000000000 = 0  →A
         00000000000…0000000001 = 1     →A + δ
         11111111111……1111111111 =→B
二進(jìn)制編碼的最大缺點(diǎn)是使得遺傳算法操作的個(gè)體位串太長，這容易降低遺傳算法的運(yùn)行效率，很多問題采用其他編碼方法可能更有利。如對(duì)于函數(shù)優(yōu)化問題，浮點(diǎn)數(shù)編碼方法就更有效，而二進(jìn)制編碼方法不但容易降低遺傳算法的運(yùn)行效率，而且會(huì)產(chǎn)生精度損失。浮點(diǎn)數(shù)編碼方法是指個(gè)體的每個(gè)染色體用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)表示，個(gè)體的編碼長度就等于問題變量的個(gè)數(shù)。
在實(shí)際運(yùn)用遺傳算法解決問題時(shí)，一般都需要根據(jù)具體的問題采用合適的編碼方法，這樣更有利于遺傳算法搜索到問題的最優(yōu)解。
（2）適應(yīng)度函數(shù)
遺傳算法在進(jìn)化搜索中基本上不用外部信息，僅用目標(biāo)函數(shù)也就是適應(yīng)度函數(shù)為依據(jù)。適應(yīng)度函數(shù)是用于度量問題中每一個(gè)染色體優(yōu)劣程度的函數(shù)，體現(xiàn)了染色體的適應(yīng)能力。遺傳算法的目標(biāo)函數(shù)不受連續(xù)可微的約束且定義域可以是任意集合。但對(duì)適應(yīng)度函數(shù)有一個(gè)要求就是針對(duì)輸入可以計(jì)算出的能加以比較的結(jié)果必須是非負(fù)的。
在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問題本身的要求而設(shè)計(jì)。因?yàn)檫m應(yīng)度函數(shù)對(duì)個(gè)體的評(píng)估是遺傳算法進(jìn)行個(gè)體選擇的唯一依據(jù)，因此適應(yīng)度函數(shù)的設(shè)計(jì)直接影響到遺傳算法的性能。對(duì)于很多問題，可以直接把求解問題的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)使用，但也存在很多問題需要進(jìn)行一定的轉(zhuǎn)換才能使得目標(biāo)函數(shù)可以用作遺傳算法的適應(yīng)度函數(shù)。
（3）遺傳算子
遺傳算法主要有三種操作算子：選擇(selection)、交叉(crossover)、變異(mutation)。
○1選擇算子
選擇算子根據(jù)個(gè)體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度選擇下一代個(gè)體。一般地，選擇算子將使適應(yīng)度函數(shù)值較大的個(gè)體有較大的機(jī)會(huì)被遺傳到下一代，而適應(yīng)度函數(shù)值較小的個(gè)體被遺傳到下一代的機(jī)會(huì)較小。一般常采用的選擇算子是賭輪選擇機(jī)制。賭輪選擇算子的基本原理如下。
令表示種群的適應(yīng)度值之總和，表示群體中第i個(gè)染色體的適應(yīng)度值，則第i個(gè)個(gè)體產(chǎn)生后代的能力正好為其適應(yīng)度值與群體適應(yīng)度值的比值。
賭輪選擇算子在個(gè)體數(shù)不太多時(shí)，有可能出現(xiàn)不正確反映個(gè)體適應(yīng)度的選擇過程，也就是說適應(yīng)度高的個(gè)體有可能反而被淘汰了。為了改進(jìn)賭輪選擇算子的這種缺點(diǎn)，有很多改進(jìn)的交叉選擇算子。如：最佳個(gè)體保存法、期望值方法、排序選擇方法、聯(lián)賽選擇方法、排擠方法等。
○2交叉算子
在自然界生物進(jìn)化過程中，起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中，起核心作用的是遺傳操作的交叉算子。所謂交叉算子就是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。
交叉算子設(shè)計(jì)一般與所求解的具體問題有關(guān)，但都應(yīng)該考慮以下兩點(diǎn)：○A設(shè)計(jì)的交叉算子必須能保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承�！養(yǎng)交叉算子與問題的編碼是相互聯(lián)系的，因此，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作，也就是所謂的編碼—交叉設(shè)計(jì)。
對(duì)于字符串編碼的遺傳算法，交叉算子主要有一點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和一致交叉等。其中一點(diǎn)交叉的主要操作過程如下。假設(shè)兩個(gè)配對(duì)個(gè)體為P1、P2分別如下所示。經(jīng)過一點(diǎn)交叉后，得到兩個(gè)新的個(gè)體P1’、P2’。

對(duì)于實(shí)數(shù)編碼的遺傳算法，交叉算子主要是采用算術(shù)交叉算子。假設(shè)兩個(gè)配對(duì)個(gè)體分別為P1＝(x1,y1)和P2=(x2,y2)。在P1和P2進(jìn)行算術(shù)交叉后得到的兩個(gè)新個(gè)體和分別可由下式計(jì)算得到。
      



○3變異算子
變異算子是改變數(shù)碼串中某個(gè)位置上的數(shù)碼。遺傳算法中引入變異算子有兩個(gè)目的：其一是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解領(lǐng)域時(shí)，利用變異算子的這種局部隨機(jī)搜索能力可以加速遺傳算法向最優(yōu)解收斂。一般在這種情況下，遺傳算法的變異概率應(yīng)取較小的值，否則接近最優(yōu)解的積木塊會(huì)因?yàn)樽儺惗獾狡茐�。其二是使遺傳算法可以維持較好的群體多樣性，以防止遺傳算法出現(xiàn)未成熟收斂現(xiàn)象。此時(shí)，遺傳算法的變異概率應(yīng)取較大的值。
遺傳算法中，交叉算子具有很好的全局搜索能力，是算法的主要操作算子。變異算子具有較好的局部搜索能力，是算法的輔助操作算子。遺傳算法通過交叉和變異這一對(duì)相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。變異算子除了基本的變異算子外，還有很多有效的變異算子。如逆轉(zhuǎn)變異算子、自適應(yīng)變異算子等。對(duì)于字符串編碼的遺傳算法，基本變異算子就是隨機(jī)的從個(gè)體中選擇某些基因位，然后以一定的概率對(duì)這些基因位進(jìn)行翻轉(zhuǎn)變異，也就是把這些基因位中為0的基因位以概率Pm變?yōu)?，為1的基因?yàn)橐愿怕蔖m變?yōu)?。對(duì)于實(shí)數(shù)編碼的遺傳算法，一般采用隨機(jī)變異的方式，使變異個(gè)體的每一個(gè)變量分量加上一個(gè)隨機(jī)數(shù)，一般使用均勻分布的隨機(jī)數(shù)或者是高斯分布的隨機(jī)數(shù)。
（4）基本遺傳算法運(yùn)行參數(shù)
N：群體大小，即群體中所含個(gè)體的數(shù)量，一般取20～100
T：遺傳算法的終止進(jìn)化代數(shù)，一般取100～500
pc：雜交概率，一般取0.4～0.99
pm：變異概率，一般取0.0001～0.1
pr：復(fù)制概率


三 實(shí)驗(yàn)儀器
macos
四 實(shí)驗(yàn)步驟/設(shè)計(jì)實(shí)現(xiàn)
設(shè)計(jì)估價(jià)函數(shù)
設(shè)計(jì)算法步驟
編寫實(shí)驗(yàn)程序
五 實(shí)驗(yàn)代碼


六 實(shí)驗(yàn)結(jié)果以及分析

實(shí)驗(yàn)四 候選消除算法
一 實(shí)驗(yàn)?zāi)康?/font>
熟悉和掌握示例學(xué)習(xí)的基本思想和基本方法，通過實(shí)驗(yàn)培養(yǎng)學(xué)生利用示例學(xué)習(xí)進(jìn)行問題求解的基本技能。
先熟悉示例學(xué)習(xí)中常見算法的基本思想和流程；
用C、C++、JAVA或Prolog             語言編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。
利用所學(xué)的知識(shí)及實(shí)驗(yàn)結(jié)果，來完成實(shí)驗(yàn)報(bào)告的各項(xiàng)內(nèi)容。


二 實(shí)驗(yàn)內(nèi)容以及原理
示例學(xué)習(xí)(Learning from examples)又稱為實(shí)例學(xué)習(xí)或從例子中學(xué)習(xí)，它是通過從環(huán)境中取得若干與某概念有關(guān)的例子，經(jīng)歸納得出一般性概念的一種學(xué)習(xí)方法。在這種學(xué)習(xí)方法中，外部環(huán)境(教師)提供的是一組例子(正例和反例)，這些例子實(shí)際上是一組特殊的知識(shí)，每一個(gè)例子表達(dá)了僅適用于該例子的知識(shí)，示例學(xué)習(xí)就是要從這些特殊知識(shí)中歸納出適用于更大范圍的一般性知識(shí)，它將覆蓋所有的正例并排除所有反例。其任務(wù)是：給定函數(shù)f(未知)的實(shí)例集合，返回一個(gè)近似于f的函數(shù)h—h稱為假設(shè)，所有h的集合稱為假設(shè)空間。
Simon于1974年在一篇論文中，把從示例學(xué)習(xí)的問題描述為使用示教例子來指導(dǎo)對(duì)規(guī)則的搜索，并提出了兩空間模型。



其中，實(shí)例空間模型為所有示教例子的集合。規(guī)則空間模型為所有規(guī)則的集合。兩者的關(guān)系是：系統(tǒng)對(duì)實(shí)例空間的搜索完成實(shí)例選擇，并將這些選中的活躍實(shí)例提交解釋過程；解釋過程對(duì)實(shí)例經(jīng)過適當(dāng)?shù)霓D(zhuǎn)化，將這些實(shí)例變換為規(guī)則空間中的特定概念，以引導(dǎo)規(guī)則空間的搜索。
對(duì)實(shí)例空間而言示教例子的質(zhì)量和實(shí)例空間的搜索是兩個(gè)值得注意的問題：
（1）高質(zhì)量的例子是無二義性的，它可以為規(guī)則空間的搜索提供可靠的指導(dǎo)；另外示教例子的排列次序也會(huì)影響學(xué)習(xí)。
（2）搜索實(shí)例空間的目的在于選擇合適的例子，使得這些例子能證實(shí)或否定規(guī)則空間中假設(shè)的集合H。常見的搜索方法有：選擇對(duì)劃分規(guī)則空間最有利的實(shí)例；利用H中的假設(shè)過濾掉與那些期望為真的實(shí)例；選擇新實(shí)例等。
對(duì)規(guī)則空間而言推理方法和規(guī)則表示是兩個(gè)值得注意的問題：
（1）常見的歸納推理方法有：a.常量轉(zhuǎn)化成變量；b.取消部分條件；c.放松條件；d.形成閉合區(qū)域；e.沿概念樹上溯等。
（2）規(guī)則表示要注意：a.對(duì)規(guī)則的表示應(yīng)適合歸納推理b.規(guī)則的表示與實(shí)例的表示一致；c.規(guī)則空間中應(yīng)包含要求的規(guī)則。
常見的示例學(xué)習(xí)的算法有，尋找極大特殊假設(shè)法、候選消除算法、精練算子法、產(chǎn)生測試法等。這里我們主要介紹一下候選消除算法。
*候選消除算法
該方法以整個(gè)規(guī)則空間為初始的假設(shè)規(guī)則集合H。依據(jù)實(shí)例中的信息，系統(tǒng)對(duì)集合H進(jìn)行一般化或特殊化處理，逐步縮小H。最后H收斂到只含有要求的規(guī)則。上述過程可稱為H的變型過程，該過程主要是利用了H中規(guī)則與規(guī)則之間的偏序關(guān)系來進(jìn)行規(guī)則的搜索。其算法如下：
（1）初始化G和S，G包含最一般假設(shè)，S包含最特殊假設(shè)。
（2）接受一個(gè)新的實(shí)例x，若x是正例，則從G中刪除不包含x的概念，更新S，盡可能對(duì)S進(jìn)行一般化以覆蓋x；若x是反例，則從S中刪除包含x的概念，更新G，盡可能對(duì)G進(jìn)行特殊化使之不覆蓋x。
（3）重復(fù)2，直到G=S
（4）輸出G和S
如果G和S都為空，表示沒有找到學(xué)習(xí)的概念描述;如果G和S相等且不為空，表示找到了學(xué)習(xí)的概念描述，且算法停止。


三 實(shí)驗(yàn)儀器
macOS
四 實(shí)驗(yàn)步驟/設(shè)計(jì)實(shí)現(xiàn)
設(shè)計(jì)估價(jià)函數(shù)
設(shè)計(jì)算法步驟
編寫實(shí)驗(yàn)程序
五 實(shí)驗(yàn)代碼

六 實(shí)驗(yàn)結(jié)果以及分析


部分源碼：
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #include <iostream>

  7. typedef struct Chrom                           // 結(jié)構(gòu)體類型，為單個(gè)染色體的結(jié)構(gòu)；
  8. {
  9.         short int bit[6];//一共6bit來對(duì)染色體進(jìn)行編碼，其中1位為符號(hào)位。取值范圍-64~+64
  10.         int fit ;//適應(yīng)值
  11.         double rfit;//相對(duì)的fit值，即所占的百分比
  12.         double cfit;//積累概率
  13. }chrom;                                       
  14. //定義將會(huì)用到的幾個(gè)函數(shù)；
  15. void *evpop (chrom popcurrent[4]);//進(jìn)行種群的初始化
  16. int x (chrom popcurrent);
  17. int y (int x);
  18. void *pickchroms (chrom popcurrent[4]);//選擇操作
  19. void *pickchroms_new (chrom popcurrent[4]); // 基于概率分布
  20. void *crossover (chrom popnext[4]);//交叉操作
  21. void *mutation (chrom popnext[4]);//突變
  22. double r8_uniform_ab ( double a, double b, int &seed );//生成a~b之間均勻分布的數(shù)字
  23. chrom popcurrent [4];                        // 初始種群規(guī)模為；
  24. chrom popnext [4];                           // 更新后種群規(guī)模仍為；
  25. void main ()                                    // 主函數(shù)；
  26. {
  27.         int num ;                                    // 迭代次數(shù)；
  28.         int i ,j, l,Max ,k;
  29.         Max=0;                                      // 函數(shù)最大值

  31.         printf("\nWelcome to the Genetic Algorithm！\n");  //
  32.         printf("The Algorithm is based on the function y = -x^2 + 5 to find the maximum value of the function.\n");

  34. enter:printf ("\nPlease enter the no. of iterations\n請(qǐng)輸入您要設(shè)定的迭代數(shù) : ");
  35.         scanf("%d" ,&num);                           // 輸入迭代次數(shù)，傳送給參數(shù) num；

  37.         if(num <1)                                 
  38.                 goto enter ;                                 // 判斷輸入的迭代次數(shù)是否為負(fù)或零，是的話重新輸入；
  39.         //不同的隨機(jī)數(shù)可能結(jié)果不同？？那是當(dāng)所設(shè)置的迭代次數(shù)過少時(shí)，染色體的基因型過早地陷入局部最優(yōu)
  40.         srand(time(0));  
  41.         evpop(popcurrent );    // 隨機(jī)產(chǎn)生初始種群；
  42.         //是否需要指定x的取值范圍呢？6bit來表示數(shù)字，第一位為符號(hào)位，5bit表示數(shù)字大小。所以，取值范圍為-32~+31
  43.         Max = popcurrent[0].fit;//對(duì)Max值進(jìn)行初始化

  45.         for(i =0;i< num;i ++)                          // 開始迭代；
  46.         {

  48.                 printf("\ni = %d\n" ,i);                 // 輸出當(dāng)前迭代次數(shù)；

  50.                 for(j =0;j<4; j++)
  51.                 {
  52.                         popnext[j ]=popcurrent[ j];           // 更新種群；
  53.                 }

  55.                 pickchroms(popnext );                    // 挑選優(yōu)秀個(gè)體；
  56.                 crossover(popnext );                     // 交叉得到新個(gè)體；
  57.                 mutation(popnext );                      // 變異得到新個(gè)體；

  59.                 for(j =0;j<4; j++)
  60.                 {
  61.                         popcurrent[j ]=popnext[ j];              // 種群更替；
  62.                 }

  64.         }  // 等待迭代終止；
  65. //對(duì)于真正隨機(jī)數(shù)是需要注意取較大的迭代次數(shù)
  66.         for(l =0;l<3; l++)
  67.         {
  68.                 if(popcurrent [l]. fit > Max )
  69.                 {
  70.                         Max=popcurrent [l]. fit;
  71.                         k=x(popcurrent [l]);//此時(shí)的value即為所求的x值
  72.                 }

  74.         }
  75.         printf("\n 當(dāng)x等于 %d時(shí)，函數(shù)得到最大值為： %d ",k ,Max);
  76.         printf("\nPress any key to end ! " );

  78.         flushall();                                 // 清除所有緩沖區(qū)；
  79.         getche();                                   // 從控制臺(tái)取字符，不以回車為結(jié)束；

  81. }                                             



  85. void *evpop (chrom popcurrent[4])   // 函數(shù)：隨機(jī)生成初始種群；
  86. {
  87.         int i ,j, value1;
  88.         int random ;
  89.         double sum=0;
  90.         
  91.         for(j =0;j<4; j++)                            // 從種群中的第1個(gè)染色體到第4個(gè)染色體
  92.         {
  93.                 for(i =0;i<6; i++)                       // 從染色體的第1個(gè)基因位到第6個(gè)基因位
  94.                 {
  95.                         random=rand ();                     // 產(chǎn)生一個(gè)隨機(jī)值
  96.                         random=(random %2);                 // 隨機(jī)產(chǎn)生0或者1
  97.                         popcurrent[j ].bit[ i]=random ;       // 隨機(jī)產(chǎn)生染色體上每一個(gè)基因位的值，或；
  98.                 }  

  100.                 value1=x (popcurrent[ j]);                // 將二進(jìn)制換算為十進(jìn)制，得到一個(gè)整數(shù)值；
  101.                 popcurrent[j ].fit= y(value1); // 計(jì)算染色體的適應(yīng)度值
  102.                 sum = sum + popcurrent[j ].fit;
  103.                 printf("\n popcurrent[%d]=%d%d%d%d%d%d  value=%d  fitness = %d",j, popcurrent[j ].bit[5], popcurrent[j ].bit[4], popcurrent[j ].bit[3], popcurrent[j ].bit[2], popcurrent[j ].bit[1], popcurrent[j ].bit[0], value1,popcurrent [j]. fit);
  104.                 // 輸出整條染色體的編碼情況，
  105.         }
  106.         //計(jì)算適應(yīng)值得百分比，該參數(shù)是在用輪盤賭選擇法時(shí)需要用到的
  107.         for (j = 0; j < 4; j++)
  108.         {
  109.                 popcurrent[j].rfit = popcurrent[j].fit/sum;
  110.                 popcurrent[j].cfit = 0;//將其初始化為0
  111.         }
  112.         return(0);               
  113. }                                       


  116. int x (chrom popcurrent)  // 函數(shù)：將二進(jìn)制換算為十進(jìn)制；
  117. {//此處的染色體長度為，其中個(gè)表示符號(hào)位
  118.         
  119.         int z ;
  120.         z=(popcurrent .bit[0]*1)+( popcurrent.bit [1]*2)+(popcurrent. bit[2]*4)+(popcurrent .bit[3]*8)+( popcurrent.bit [4]*16);

  122.         if(popcurrent .bit[5]==1)  // 考慮到符號(hào)；
  123.         {
  124.                 z=z *(-1);                             
  125.         }

  127.         return(z );                           
  128. }                                    
  129. //需要能能夠從外部直接傳輸函數(shù)，加強(qiáng)魯棒性
  130. int y (int x)// 函數(shù)：求個(gè)體的適應(yīng)度；
  131. {
  132.         int y ;
  133.         y=-(x *x)+5;                                // 目標(biāo)函數(shù)：y= - ( x^ 2 ) +5；
  134.         return(y );            
  135. }
  136. //基于輪盤賭選擇方法，進(jìn)行基因型的選擇
  137. void *pickchroms_new (chrom popnext[4])//計(jì)算概率
  138. {
  139.         int men;
  140.         int i;int j;
  141.         double p;
  142.         double sum=0.0;
  143.         //find the total fitness of the population
  144.         for (men = 0; men < 4; men++ )
  145.         {
  146.                 sum = sum + popnext[men].fit;
  147.         }
  148.         //calculate the relative fitness of each member
  149.         for (men = 0; men < 4; men++ )
  150.         {
  151.                 popnext[men].rfit = popnext[men].fit / sum;
  152.         }
  153.         //calculate the cumulative fitness,即計(jì)算積累概率
  154.         popcurrent[0].cfit = popcurrent[0].rfit;
  155.         for ( men = 1; men < 4; men++)
  156.         {
  157.                 popnext[men].cfit = popnext[men-1].cfit + popnext[men].rfit;
  158.         }
  159.         
  160.         for ( i = 0; i < 4; i++ )
  161.         {//產(chǎn)生0~1之間的隨機(jī)數(shù)
  162.                 //p = r8_uniform_ab ( 0, 1, seed );//通過函數(shù)生成0~1之間均勻分布的數(shù)字
  163.                 p =rand()%10;//
  164.                 p = p/10;
  165.                 if ( p < popnext[0].cfit )
  166.                 {
  167.                         popcurrent[i] = popnext[0];      
  168.                 }
  169.                 else
  170.                 {
  171.                         for ( j = 0; j < 4; j++ )
  172.                         {
  173.                                 if ( popnext[j].cfit <= p && p < popnext[j+1].cfit )
  174.                                 {
  175.                                         popcurrent[i] = popcurrent[j+1];
  176.                                 }
  177.                         }
  178.                 }
  179.         }
  180.         //  Overwrite the old population with the new one.
  181.         //
  182.         for ( i = 0; i < 4; i++ )
  183.         {
  184.                 popnext[i] = popcurrent[i];
  185.         }
  186.         return(0);
  187. }
  188. void *pickchroms (chrom popnext[4])          // 函數(shù)：選擇個(gè)體；
  189. {
  190.         int i ,j;
  191.         chrom temp ;                                // 中間變量
  192.         //因此此處設(shè)計(jì)的是個(gè)個(gè)體，所以參數(shù)是
  193.         for(i =0;i<3; i++)                           // 根據(jù)個(gè)體適應(yīng)度來排序；（冒泡法）
  194.         {
  195.                 for(j =0;j<3-i; j++)
  196.                 {
  197.                         if(popnext [j+1]. fit>popnext [j]. fit)
  198.                         {
  199.                                 temp=popnext [j+1];
  200.                                 popnext[j +1]=popnext[ j];
  201.                                 popnext[j ]=temp;

  203.                         }  
  204.                 }               
  205.         }
  206.         for(i =0;i<4; i++)
  207.         {
  208.                 printf("\nSorting:popnext[%d] fitness=%d" ,i, popnext[i ].fit);
  209.                 printf("\n" );                     
  210.         }
  211.         flushall();/* 清除所有緩沖區(qū) */                     
  212.         return(0);
  213. }   
  214. double r8_uniform_ab( double a, double b, int &seed )
  215. {
  216.         {
  217.                 int i4_huge = 2147483647;
  218.                 int k;
  219.                 double value;

  221.                 if ( seed == 0 )
  222.                 {
  223.                         std::cerr << "\n";
  224.                         std::cerr << "R8_UNIFORM_AB - Fatal error!\n";
  225.                         std::cerr << "  Input value of SEED = 0.\n";
  226.                         exit ( 1 );
  227.                 }

  229.                 k = seed / 127773;

  231.                 seed = 16807 * ( seed - k * 127773 ) - k * 2836;

  233.                 if ( seed < 0 )
  234.                 {
  235.                         seed = seed + i4_huge;
  236.                 }

  238.                 value = ( double ) ( seed ) * 4.656612875E-10;

  240.                 value = a + ( b - a ) * value;

  242.                 return value;
  243.         }
  244. }
  245. void *crossover (chrom popnext[4])              // 函數(shù)：交叉操作；
  246. {

  248.         int random ;
  249.         int i ;
  250.         //srand(time(0));
  251.         random=rand ();                             // 隨機(jī)產(chǎn)生交叉點(diǎn)；
  252.         random=((random %5)+1);                     // 交叉點(diǎn)控制在0到5之間；
  253.         for(i =0;i< random;i ++)                  
  254.         {
  255.                 popnext[2].bit [i]= popnext[0].bit [i];   // child 1 cross over
  256.                 popnext[3].bit [i]= popnext[1].bit [i];   // child 2 cross over
  257.         }

  259.         for(i =random; i<6;i ++)                      // crossing the bits beyond the cross point index
  260.         {
  261.                 popnext[2].bit [i]= popnext[1].bit [i];    // child 1 cross over
  262.                 popnext[3].bit [i]= popnext[0].bit [i];    // chlid 2 cross over
  263.         }  

  265.         for(i =0;i<4; i++)
  266.         {
  267.                 popnext[i ].fit= y(x (popnext[ i]));        // 為新個(gè)體計(jì)算適應(yīng)度值；
  268.         }

  270.         for(i =0;i<4; i++)
  271.         {
  272.                 printf("\nCrossOver popnext[%d]=%d%d%d%d%d%d    value=%d    fitness = %d",i, popnext[i ].bit[5], popnext[i ].bit[4], popnext[i ].bit[3], popnext[i ].bit[2], popnext[i ].bit[1], popnext[i ].bit[0], x(popnext [i]), popnext[i ].fit);
  273.                 // 輸出新個(gè)體；
  274.         }
  275.         return(0);
  276. ……………………

  278. …………限于本文篇幅 余下代碼請(qǐng)從51黑下載附件…………
復(fù)制代碼

全部資料51hei下載地址（內(nèi)含完整源碼）：
強(qiáng)彥.doc (712.88 KB, 下載次數(shù): 14)



分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏1 分享淘帖 頂頂1 踩踩
回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

手機(jī)版|小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表