基于ga的迷宮解決方案設(shè)計【開題報告】

1、<p><b>　　畢業(yè)設(shè)計開題報告</b></p><p><b>　　計算機科學(xué)與技術(shù)</b></p><p>　　基于GA的迷宮解決方案設(shè)計 </p><p>　　一、選題的背景、意義</p><p><b>　　歷史背景</b></p>&

2、lt;p>　　避障尋徑問題被證明是一類NP-Hard問題，一直以來都是計算機科學(xué)人工智能領(lǐng)域內(nèi)的熱門話題，滲透于我們?nèi)粘Ｉa(chǎn)生活中的各個領(lǐng)域，如無人機器偵查兵，無人駕駛運輸車，城市內(nèi)的車輛自動導(dǎo)航等等，其求解算法的研究，近年來受到廣泛的關(guān)注[1]。</p><p>　　二維迷宮求解從本質(zhì)上來講，是避障尋徑模型的一個簡單的數(shù)學(xué)描述。由于思想和方法的局限性，在現(xiàn)存的算法中，人們主要考慮比較簡單的靜態(tài)環(huán)境下的理想

3、情況[2]。然而，在實際環(huán)境中遇到的問題并不如想象中的那么簡單。</p><p>　　二維迷宮求解是在一個具有許多障礙物的迷宮里，尋找一條從起點避開障礙物到終點的路徑問題[3,4]。圖1就是一個二維迷宮，左邊的黃色為起點，右邊的紅色為終點，中間的黑色表示障礙物，白色則表示可以正常通過。圖2是一條從起點到終點的可行解（并非最優(yōu)解）。對于二維迷宮求解問題，從廣義上來講，就是一個尋找路徑的問題。二維迷宮求解使用遺傳算法

4、[5]，遺傳算法是一種隨機的種群搜索算法，它是對達爾文生物進化原理的計算機模擬。它通過用適應(yīng)度函數(shù)對每一代群體中的個體進行評估，按照優(yōu)勝劣汰的原則，保存較好的個體，淘汰較差的個體，并對個體進行繁殖，交叉，變異的遺傳操作，使整個群體不斷地進化。遺傳算法有著明確的搜索方向，它具有簡單，通用性強，效果顯著等特點，適合處理傳統(tǒng)的搜索方法難以解決的復(fù)雜問題。迷宮問題實際上也是一個組合優(yōu)化問題，本文研究使用遺傳算法求解該問題的可行性。它的難度在于染

5、色體如何編碼，評估函數(shù)如何設(shè)計以及遺傳操作的算子如何設(shè)計。本文在對這些問題進行研究的基礎(chǔ)上，給出了求解該問題的遺傳算法，并通過大量的實驗證明該算法是有效的。相信通過對遺傳算法求解迷宮問題的研究，能對其他一些用傳統(tǒng)方法難以解決的優(yōu)化</p><p><b>　　國內(nèi)外研究現(xiàn)狀</b></p><p>　　雖然在各種應(yīng)用領(lǐng)域中，算法的具體實施細節(jié)有各自的特點，但遺傳算法提

6、供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域。遺傳算法主要應(yīng)用于以下幾個主要領(lǐng)域：</p><p><b>　　（1）函數(shù)優(yōu)化 </b></p><p>　　函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性能評價的常用例子。很多人工構(gòu)造的各種各樣復(fù)雜形式的測試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有單峰函數(shù)也有多峰函數(shù)等，利用這些函數(shù)來評價遺傳算法的

7、性能。對于非線性、多目標的函數(shù)優(yōu)化問題，用其他算法通常較難求解，但使用遺傳算法卻很方便并可以得到較好的結(jié)果。</p><p><b>　　（2）組合優(yōu)化</b></p><p>　　隨著問題規(guī)模的擴大，組合優(yōu)化問題的搜索空間急劇增大，甚者有時無法求到精確最優(yōu)解。對于這類復(fù)雜問題，使用遺傳算法求解可行解就顯得更加有實際價值[7]。這類問題包括旅行商問題、背包問題、裝箱問

8、題和圖形劃分等。</p><p><b>　?。?）生成調(diào)度 </b></p><p>　　生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也因簡化太多而使得求解結(jié)果與實際相差甚遠。因此目前現(xiàn)實生產(chǎn)中也主要靠一些經(jīng)驗進行調(diào)度。遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分

9、配等方面遺傳算法都得到了有效的應(yīng)用。</p><p><b>　　（4）自動控制 </b></p><p>　　在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解。遺傳算法已在其中得到了初步的應(yīng)用，并顯示出良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則

10、的學(xué)習(xí)、利用遺傳算法進行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和“權(quán)值”學(xué)習(xí)等。都顯出了遺傳算法在這此領(lǐng)域中應(yīng)用的可能性[8]。</p><p><b>　?。?）機器人學(xué) </b></p><p>　　機器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。所以，機器人學(xué)理所當(dāng)然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(jīng)在移動機器人路徑

11、規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學(xué)求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用[9]。</p><p><b>　?。?）圖像處理 </b></p><p>　　圖像處理是計算機視覺中的一個重要研究領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一次誤差，從而影響圖像的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求

12、。遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地。目前已在模式識別(包括漢字識別)、圖像恢復(fù)、圖像邊緣特征提取等方而得到了應(yīng)用。</p><p><b>　　（7）人工生命 </b></p><p>　　人工生命是用計算機、機械等人下媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人下生命的兩大主要特征。人下生命與遺傳算法有著密切的

13、關(guān)系?；谶z傳算法的進化模型是研究人下生命現(xiàn)象的重要基礎(chǔ)理論。雖然人下生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人下生命的研究提供一個有效的下具，人下生命的研究也必將促進遺傳算法的進一步發(fā)展。</p><p><b>　?。?）遺傳編程 </b><

14、;/p><p>　　1989年，美國Standford大學(xué)的Koza教授發(fā)展了遺傳編程的概念，其基本思想是:采用樹型結(jié)構(gòu)表示計算機程序，運用遺傳算法的思想，通過自動生成計算機程序來解決問題。雖然遺傳編程的理論尚未成熱，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機器學(xué)習(xí)等領(lǐng)域。目前公開的遺傳編程實驗系統(tǒng)有十多個。</p><p><b>　?。?）機器學(xué)習(xí) </b>&l

15、t;/p><p>　　學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所具備的能力之一，基于遺傳算法的機器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則，利用遺傳算法來學(xué)習(xí)隸屬度函數(shù)，從而更好地改進了模糊系統(tǒng)的性能；基于遺傳算法的機器學(xué)習(xí)可用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)[10]，也可用于人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計；分類器系統(tǒng)也在學(xué)習(xí)式多機器人路徑規(guī)劃系統(tǒng)[11]中得到了成功的應(yīng)用。</p>

16、<p><b>　?。?0）數(shù)據(jù)挖掘</b></p><p>　　數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進行搜索，對隨機產(chǎn)生的一組規(guī)則進行進化.直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。Su

17、nil已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進行了數(shù)據(jù)挖掘?qū)嶒?，結(jié)果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一。</p><p><b>　　發(fā)展趨勢</b></p><p>　　遺傳算法發(fā)展方向其實就是和其他方法結(jié)合優(yōu)化問題，單方面改進遺傳算法的各種算子不能取得明顯進展。遺傳算法以其基本思想簡單、便于實現(xiàn)和并行搜索的優(yōu)點贏得

18、了眾多學(xué)者和各種工程人員的青睞，是目前應(yīng)用最廣的優(yōu)化搜索算法之一。但遺傳算法存在收斂速度慢和易于陷入局部最優(yōu)的問題，在需要優(yōu)化的參數(shù)較多時，更凸現(xiàn)了遺傳算法的不足。遺傳算法如何提高遺傳算法跳出局部最優(yōu)的能力和如何提高遺傳算法的收斂速度成為近年來遺傳算法的研究熱點。許多學(xué)者從不同的角度對遺傳算法進行了改進，使遺傳算法的尋優(yōu)能力有了不同程度的提高。和其它方法結(jié)合的遺傳算法才有生命力。目前，對遺傳算法的研究主要集中在數(shù)學(xué)基礎(chǔ)、各環(huán)節(jié)的實現(xiàn)方式

19、以及與其他算法的結(jié)合方面。其中，尤以遺傳算法與其他算法相結(jié)合方面的研究最為引人關(guān)注。由于遺傳算法具有開放式的結(jié)構(gòu)，與問題的關(guān)聯(lián)性不大，很容易和其他算法進行結(jié)合，所以融合了其他的算法思想和遺傳算法思想的混合遺傳算法成了目前改進遺傳算法研究的一個重要方向[12]?，F(xiàn)將比較常見的混合遺傳算法介紹如下。</p><p>　　（1）模擬退火遺傳算法</p><p>　　模擬退火算法的基本思想是通過模

20、擬高溫物體退火過程的方法來找到優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解。從統(tǒng)計物理學(xué)的觀點看，隨著溫度的降低，物質(zhì)的能量將逐漸趨近于一個較低的狀態(tài)，并最終達到某種平衡。遺傳算法的局部搜索能力較差，但把握搜索過程總體的能力較強；而模擬退火算法具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解，但它卻對整個搜索空間的了解不多，不便于使搜索過程進入最有希望的搜索區(qū)域，從而使得模擬退火算法的運算效率不高。但如果將遺傳算法和模擬退火算法相結(jié)合，互

21、相取長補短，則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法。目前，已有許多學(xué)者將退火機制引入到遺傳操作中，使遺傳操作產(chǎn)生優(yōu)良個體的概率增加，并使遺傳算法的尋優(yōu)能力有了明顯的提高。</p><p><b>　　（2）免疫遺傳算法</b></p><p>　　人工免疫算法受生物免疫系統(tǒng)原理的啟發(fā)，針對求解問題特征進行人工疫苗接種，可充分利用問題本身的信息，和遺傳算法結(jié)合時，遺傳

22、算法的全局搜索能力及免疫算法的局部優(yōu)化相配合，可大大提高搜索效率。我們可以通過注射疫苗的方法來減少遺傳操作的盲目性，加強遺傳算法收斂性能，多次的測試結(jié)果證明了該改進方法的有效性。</p><p>　?。?）小生境遺傳算法</p><p>　　生物學(xué)上，小生境指在特定環(huán)境中的一種組織功能，它將每一代個體劃分為若干類，每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表，組成一個新種群，再在同

23、一種群中以及不同種群之間進行雜交、變異，產(chǎn)生新一代個體群，同時采用“預(yù)選擇”機制或排擠機制或共享機制完成選擇操作[13]?！敖饪臻g”中峰周圍的子空間中的個體具有相對獨立生長繁衍的特性。常用的小生境遺傳算法大多在對群體進行選擇操作前，計算個體之間的海明距離，如小于事先設(shè)定值，則對“適應(yīng)值”低的個體處以罰函數(shù)，降低其適應(yīng)值。這樣可以保護解的多樣性，也可以避免大量重復(fù)的解充斥整個解空間。用小生境思想來實現(xiàn)遺傳算法的選擇操作，使遺傳算法的全局尋

24、優(yōu)能力得到了明顯提高。</p><p><b>　?。?）模糊遺傳算法</b></p><p>　　模糊遺傳算法，即融合模糊優(yōu)化設(shè)計思想的遺傳算法，它把模糊優(yōu)化和遺傳算法優(yōu)化結(jié)合起來，構(gòu)成一種混合優(yōu)化的設(shè)計方法。其目的是利用模糊優(yōu)化設(shè)計的優(yōu)點，克服一般遺傳算法優(yōu)化設(shè)計存在的不足，從而使得系統(tǒng)的優(yōu)化設(shè)計更靈活、方便，取得好的設(shè)計效果。首先，在模糊遺傳算法中引入“論域”的

25、概念。在這里，“論域”即指用隸屬函數(shù)來表示遺傳算法的優(yōu)化過程中所采用的約束條件的區(qū)間范圍[14]。用隸屬函數(shù)來表示遺傳算法的約束條件，以使約束條件能夠更容易得到表達，又能夠保證遺傳子代的選擇中能夠擁有更廣泛的群體組成。其次，在模糊遺傳算法中，采用權(quán)變理論中的以變應(yīng)變的思想。模糊遺傳算法運用模糊控制的思想來自適應(yīng)改變遺傳算法的種群規(guī)模、交叉概率、變異概率、適應(yīng)度函數(shù)以及控制策略等。</p><p><b>

26、;　　（5）混沌遺傳算法</b></p><p>　　混沌是自然界廣泛存在的一種非線性現(xiàn)象，它充分體現(xiàn)了系統(tǒng)的復(fù)雜性?；煦邕\動具有類似隨機變量的雜亂表現(xiàn)[15]，具有隨機性；“混沌”能在一定范圍內(nèi)按其自身特性不重復(fù)地歷經(jīng)所有狀態(tài)，具有遍歷性；初值條件極其微弱的變化會引起混沌系統(tǒng)行為的巨大變化，具有對初始條件的極度敏感性?；煦邕\動的上述性質(zhì)作為避免陷入局部極小的優(yōu)化搜索機制，恰好可以彌補遺傳算法易陷入局

27、部最優(yōu)、收斂速度慢的缺陷?？梢岳没煦绲谋闅v性產(chǎn)生初始種群，也可以運用混沌的遍歷性對優(yōu)良個體進行變異操作，混沌遺傳算法增強了遺傳算法的全局尋優(yōu)能力。</p><p>　　二、研究的基本內(nèi)容與擬解決的主要問題</p><p><b>　　研究的基本內(nèi)容</b></p><p>　　遺傳算法GA把“問題的解”表示成“染色體”，在算法中也即是以二進制

28、編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，“一代一代”地進化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。</p><p>　　在遺傳算法里，優(yōu)化問題的解被稱為個體，它表示為一個參數(shù)列表，叫做染色體或者基

29、因串。染色體一般被表達為簡單的字符串或數(shù)字串，不過也有其他的表示方法適用，這一過程稱為編碼。</p><p>　　一開始，算法隨機生成一定數(shù)量的個體，有時候操作者也可以對這個隨機產(chǎn)生過程進行干預(yù)，播下已經(jīng)部分優(yōu)化的種子。在每一代中，每一個個體都被評價，并通過計算適應(yīng)度函數(shù)得到一個適應(yīng)度數(shù)值。種群中的“個體”被按照適應(yīng)度排序，適應(yīng)度高的在前面。這里的“高”是相對于初始的種群的“低適應(yīng)度”來說的。</p>

30、<p>　　下一步是產(chǎn)生下一代個體并組成種群。這個過程是通過選擇和交叉完成的，其中繁殖包括(crossover)和突變(mutation)。選擇則是根據(jù)新個體的適應(yīng)度進行的，適應(yīng)度越高，被選擇的機會越高，而適應(yīng)度低的，被選擇的機會就低。初始的數(shù)據(jù)可以通過這樣的選擇過程組成一個相對優(yōu)化的群體。之后，被選擇的個體進入交叉過程。一般的遺傳算法都有一個交叉概率，范圍一般是0.01-1，這個交叉概率反映兩個被選中的個體進行交叉的概率

31、。例如，交叉概率為0.8，則80%的“夫妻”會生育后代。每兩個個體通過交叉產(chǎn)生兩個新個體，代替原來的“老”個體，而沒交叉的個體則保持不變。交叉父母的染色體相互交換，從而產(chǎn)生兩個新的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。不過這里的半段并不是真正的一半，這個位置叫做交叉點，也是隨機產(chǎn)生的，可以是染色體的任意位置。再下一步是突變，通過突變產(chǎn)生新的“子”個體。一般遺傳算法都有一個固定的突變常數(shù)，通常是0.

32、1或者更小，這代表變異發(fā)生的概率。根據(jù)這個概率，新個體的染色體隨機的突變，通常就是改變?nèi)旧w的一個字節(jié)（0變到1，或者1變到0）。</p><p>　　經(jīng)過這一系列的過程（選擇、交叉和突變），產(chǎn)生的新一代個體不同于初始的一代，并“一代一代”向增加整體適應(yīng)度的方向發(fā)展，因為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個體逐漸被淘汰掉。這樣的過程不斷的重復(fù)：每個“個體”被評價，計算出適應(yīng)度，兩個個體交叉，然后

33、突變，產(chǎn)生第三代。周而復(fù)始，直到終止條件滿足為止。</p><p><b>　　擬解決的主要問題</b></p><p><b>　　1.串的編碼方式</b></p><p>　　這本質(zhì)是問題編碼。一般把問題的各種參數(shù)用二進制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。串長度及編碼形式對算法收斂影響極大</p&g

34、t;<p><b>　　2.適應(yīng)函數(shù)的確定</b></p><p>　　適應(yīng)函數(shù)(fitness function)也稱對象函數(shù)(object function)，這是問題求解品質(zhì)的測量函數(shù)；往往也稱為問題的“環(huán)境”。一般可以把問題的模型函數(shù)作為對象函數(shù)；但有時需要另行構(gòu)造。</p><p>　　3.遺傳算法自身參數(shù)設(shè)定</p><p

35、>　　遺傳算法自身參數(shù)有3個，即群體大小n、交叉概率Pc和變異概率Pm。群體大小n太小時難以求出最優(yōu)解，太大則增長收斂時間。一般n＝30-160。交叉概率Pc太小時難以向前搜索，太大則容易破壞“高適應(yīng)值”的結(jié)構(gòu)。一般取Pc=0.25-0.75。變異概率Pm太小時難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機搜索。一般取Pm＝0.01-0.2。</p><p>　　三、研究的方法與技術(shù)路線、研究難點，預(yù)期

36、達到的目標</p><p>　　研究的方法與技術(shù)路線</p><p><b>　　1.初始化</b></p><p>　　選擇一個群體，即選擇一個串或個體的集合bi，i=1，2，...n。這個初始的群體也就是問題假設(shè)解的集合。一般取n＝30-160。通常以隨機方法產(chǎn)生串或個體的集合b,i＝1，2，...n。問題的最優(yōu)解將通過這些初始假設(shè)解進化而

37、求出。</p><p><b>　　2.選擇</b></p><p>　　根據(jù)適者生存原則選擇下一代的個體。在選擇時，以適應(yīng)度為選擇原則。適應(yīng)度選擇原則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。給出目標函數(shù)f，則f(bi)稱為個體bi的適應(yīng)度。適應(yīng)度較高的個體，繁殖下一代的數(shù)目較多。適應(yīng)度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。這樣，就產(chǎn)生了對環(huán)境適應(yīng)能力較強的后

38、代。對于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。</p><p><b>　　3.交叉</b></p><p>　　對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P交叉。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。交叉時，可實行單點交叉或多點交叉。</p><p&

39、gt;　　例如有個體S1=100101，S2=010111，選擇它們的左邊3位進行交叉操作，則有</p><p>　　S1=010101，S2=100111。一般而言，交叉概率P取值為0.25—0.75。</p><p><b>　　4.變異</b></p><p>　　根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些“位”執(zhí)行變異

40、。在變異時，對執(zhí)行變異的串的“對應(yīng)位”求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。</p><p>　　例如有個體S＝101011。對其的第1，4位置的基因進行變異，則有S1=001111</p><p>　　單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進化的單一群體。因為在所有的個體一樣時，交叉是

41、無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的個體。也就是說，變異增加了全局優(yōu)化的特質(zhì).</p><p>　　5.全局最優(yōu)收斂(Convergence to the global optimum)</p><p>　　當(dāng)最優(yōu)個體的適應(yīng)度達到給定的閥值，或者最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升時，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回

42、到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。</p><p><b>　　研究難點</b></p><p><b>　　1.群體設(shè)定</b></p><p>　　群體“個體數(shù)”只要設(shè)定為2n即可。所以在實際應(yīng)用中，群體個數(shù)的取值范圍一般在幾十到幾百。另外，群體規(guī)模的確定受遺傳操作中選擇操作的影響很大。群體規(guī)模越大，群體中個體的多樣性

43、越高，算法陷入局部解的危險就小。但是，群體過大，其適應(yīng)度評估次數(shù)增加，所以計算量也增加，從而影響算法效率。另一方面，如果群體規(guī)模太小，會使遺傳算法的搜索空間分布范圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。實驗中二維迷宮求解，考慮個方面因素，群體規(guī)模設(shè)為150。</p><p><b>　　2.適應(yīng)函數(shù)度</b></p><p>　　因為要找二維迷宮路徑，

44、所以適應(yīng)度函數(shù)就是移動到最后點和終點的距離</p><p><b>　　3.選擇算子的設(shè)計</b></p><p>　　從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫做選擇。選擇算子又叫再生算子（Reproduction Operator）。選擇的目的是把“優(yōu)化的解”直接遺傳到下一代或者通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上

45、的，目前常用的選擇算子有：</p><p>　　（1）適應(yīng)度比例方法（Fitness proportional model），適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法。它也叫賭輪（roulette wheel）或蒙特卡羅（Monte Carlo）選擇?！皞€體”被選擇的概率反映了個體的適應(yīng)度在整個群體的個體適應(yīng)度總和中所占的比例。個體適應(yīng)度越大，被選擇的概率就越高。</p><p&g

46、t;　?。?）最佳個體保存方法（Elitist model），此方法的思想是把群體中適應(yīng)度最高的個體不進行配對交叉而直接復(fù)制到下一代中。采用這種選擇方法的優(yōu)點是：進化過程中某一代的最優(yōu)解可以不被交叉和變異操作所破壞。但是，這是這樣可能隱含了一種危機——導(dǎo)致早熟，即局部最優(yōu)個體的遺傳基因會急速增加而使進化有可能限于局部解。</p><p>　?。?）排序選擇方法（Rank-based），排序選擇方法是指在計算每個個

47、體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個體排序，然后把事先設(shè)計好的概率表按順序分配給個體，作為各自的選擇概率。這種方法的不足之處在于選擇概率和序號的關(guān)系必須事先確定。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計誤差。 </p><p>　　總之，選擇的原則是盡可能保留好的個體，淘汰不好的個體?？紤]到求的是二維迷宮求解問題,我采用適應(yīng)度比例方法（Fitness prop

48、ortional model）</p><p><b>　　預(yù)期達到的目標</b></p><p>　　1.生成盡量少的無效路徑。使用遺傳算法求解二維迷宮時，容易產(chǎn)生大量無效的解，通過計算個體的有效路徑，評價個體，并在遺傳操作中不斷累積局部優(yōu)勢模式，可以對無效解進行遺傳操作并生成有效解。</p><p>　　2.在預(yù)期的繁衍代數(shù)內(nèi)找到最優(yōu)解。種

49、群繁衍的代數(shù)越多，越不利于計算，也難以找到最優(yōu)解</p><p>　　3.避免在角落徘徊的死解。在變異過程中，如果有死角情況，則在染色體前半部分選擇變異位置。</p><p>　　四、論文詳細工作進度和安排</p><p>　　第七學(xué)期第17周至期末： 熟悉設(shè)計任務(wù)相關(guān)知識，軟件環(huán)境和開發(fā)工具；</p><p>　　第八學(xué)期第01周至第0

50、3周：總體設(shè)計，撰寫論文（設(shè)計）提綱；</p><p>　　第八學(xué)期第04周至第11周：詳細設(shè)計；</p><p>　　第八學(xué)期第12周至第13周：完成應(yīng)用軟件系統(tǒng)的設(shè)計，完成畢業(yè)論文（設(shè)計）文檔；</p><p>　　第八學(xué)期第14周： 完善畢業(yè)論文（設(shè)計）文檔，完成答辯準備工作；</p><p>　　第八學(xué)期第15周：

51、 畢業(yè)論文（設(shè)計）答辯。</p><p><b>　　五、主要參考文獻：</b></p><p>　　[1] 蔡自興，徐光佑．人工智能及其應(yīng)用[M]．清華大學(xué)出版社，2003.9．</p><p>　　[2] 張曉，戴冠中，徐乃平．一種新的優(yōu)化搜索算法遺傳算法．控制理論與應(yīng)用[J]．1995，12(3):265-273．</p

52、><p>　　[3] 王斌，李元香．用遺傳算法解迷宮問題[J]．微型機與應(yīng)用，2002，(10):58-60．</p><p>　　[4] 廖國勇，王廣超．用遺傳算法解迷宮問題[J]．華東交通大學(xué)學(xué)報，2006，4(2):138-140．</p><p>　　[5] 陳根社，陳新海．遺傳算法的研究與進展[J]．信息與控制，1994，(4):215-222．</p&

53、gt;<p>　　[6] 陳國良．遺傳算法及其應(yīng)用[M]．北京：人民郵電出版社，1996．</p><p>　　[7] Sudhakaran M．GA and PSO culled hybrid technique for economic dispatch problem with prohibited operating zones[J]．Journal of Zhejiang Universi

54、ty，2007，8(6):896-903．</p><p>　　[8] 甄文祥，王文田．遺傳算法及其應(yīng)用[J]．計算機應(yīng)用研究，1994，(5)．</p><p>　　[9] 楊四海．多障礙離散路徑規(guī)劃的遺傳算法求解[J]．華僑大學(xué)學(xué)報(自然科學(xué)版)，2006(3)．</p><p>　　[10] 方建安，邵世煌．采用遺傳算法學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)控制器[J]．控制與決策，

55、1993，8(3):208-212．</p><p>　　[11] 蘇素珍，土屋喜一．使用遺傳算法的迷宮學(xué)習(xí)[J]．機器人，1994，(5):286-289．</p><p>　　[12] 姚新，陳國良，徐惠敏等．進化算法研究進展[J]．計算機學(xué)報，1995，18(9):694-706．</p><p>　　[13] John J.Grefenstette．Gene

56、tic algorithms for changing environments[J]．Parallel Problem Solving from Nature，1992:137-144．</p><p>　　[14 ]D.Abramson，J.Abela．A Parallel Genetic Algorithmforsolving the School Timetabling Problem[J]．Austra

57、lian Computer Science Conference，1992，(2):1-11．</p><p>　　[15] Ma Qi-ming，Wang Xuan-yin．Method and application of wavelet shrinkage denoising based on genetic algorithm[J]．Journal of Zhejiang University Scien