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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、代。對于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。</p><p><b>　　3.交叉</b></p><p>　　對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P交叉。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產生新的基因組合，也即產生新的個體。交叉時，可實行單點交叉或多點交叉。</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>　　根據生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些“位”執(zhí)行變異

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

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

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

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

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

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

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

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

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

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

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

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

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

53、gt;<p>　　[6] 陳國良．遺傳算法及其應用[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] 甄文祥，王文田．遺傳算法及其應用[J]．計算機應用研究，1994，(5)．</p><p>　　[9] 楊四海．多障礙離散路徑規(guī)劃的遺傳算法求解[J]．華僑大學學報(自然科學版)，2006(3)．</p><p>　　[10] 方建安，邵世煌．采用遺傳算法學習的神經網絡控制器[J]．控制與決策，

55、1993，8(3):208-212．</p><p>　　[11] 蘇素珍，土屋喜一．使用遺傳算法的迷宮學習[J]．機器人，1994，(5):286-289．</p><p>　　[12] 姚新，陳國良，徐惠敏等．進化算法研究進展[J]．計算機學報，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