基于引入強制變異的改進遺傳算法性能研究【開題報告】

1、<p><b>　　畢業(yè)設計開題報告</b></p><p><b>　　計算機科學與技術</b></p><p>　　基于引入強制變異的改進遺傳算法性能研究</p><p>　　綜述本課題國內(nèi)外研究動態(tài)，說明選題的依據(jù)和意義</p><p>　　遺傳算法GA（Genetic Algori

2、thm）是最近這些年來發(fā)展速度比較快的一種模擬自然界中適者生存、優(yōu)勝劣汰的生物進化過程的原理與機制的用以求解極值問題的一類自組織、自適應的人工智能技術。遺傳算法主要是借用了生物遺傳學中自然選擇遺傳和變異等作用機制，而開發(fā)出來的一種全局優(yōu)化的自適應概率搜索算法。</p><p>　　遺傳算法采用了群體搜索技術，對當前代的種群進行選擇、交叉、變異等一系列遺傳操作，從而產(chǎn)生出新一代的群體，然后經(jīng)過一定代的不斷操作使群體

3、進化到包含或接近最優(yōu)解的狀態(tài)。遺傳算法呈現(xiàn)的是一個通用的框架，該框架對問題的種類沒有具體要求或者說遺傳算法對求解問題無可微性及其他要求，所以遺傳算法是一類具有較強魯棒性的優(yōu)化算法，可以廣泛的應用于許多學科之中。特別是對于一些大型、復雜非線性系統(tǒng)，遺傳算法表現(xiàn)出了比其他傳統(tǒng)優(yōu)化方法更加獨特和優(yōu)越的性能[1-8]。</p><p>　　遺傳算法與其他一些優(yōu)化算法相比，它主要有以下幾個特點：</p>&l

4、t;p>　　遺傳算法把決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法一般是直接利用決策變量的實際值本身來進行優(yōu)化計算，但遺傳算法不是直接以決策變量的值，而是把決策變量的編碼成染色體的形式進行運算。這種對決策變量的編碼處理方式，為我們在優(yōu)化計算過程中可以借鑒生物學中染色體和基因等概念創(chuàng)造了可能性，使得我們可以模仿自然界中生物的遺傳和進化等機理，也使得我們可以方便地應用遺傳算子。特別是對一些無數(shù)值概念或者很難有數(shù)值概念，而只有代碼概念的優(yōu)

5、化問題，編碼處理方式更顯示出了其獨特的優(yōu)越性。</p><p>　　遺傳算法直接以目標函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法不但需要利用目標函數(shù)值，而且往往需要目標函數(shù)的導數(shù)值等其他一些輔助信息才能確定搜索方向。而遺傳算法僅使用由目標函數(shù)值變換來的適應度函數(shù)值，就可以確定進一步的搜索方向和搜索范圍，無需目標函數(shù)的導數(shù)值等其他一些輔助信息</p><p>　　遺傳算法能夠同時使用多個搜索點的搜索

6、信息。傳統(tǒng)的優(yōu)化算法往往是從解空間中的一個初始點開始最優(yōu)解的迭代搜索過程。不會出現(xiàn)單個搜索點提供的一個初始點開始最優(yōu)解而停滯不前這種情況。遺傳算法從由很多個體所組成的一個初始群體開始最優(yōu)解的搜索過程，而不是從一個單一的個體開始搜索。這一定程度上也避免了算法出現(xiàn)局部最優(yōu)解的情況。</p><p>　　遺傳算法使用概率搜索技術。很多傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，一個搜索點到另一個搜索點的轉(zhuǎn)移由確定的轉(zhuǎn)移

7、方法和轉(zhuǎn)移關系，這種確定性往往也有可能使得搜索永遠達不到最優(yōu)點，因而也限制了算法的應用范圍。而遺傳算法屬于一種自適應概率搜索技術，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，從而增加了其搜索過程的靈活性。雖然這種概率特性也會使群體中產(chǎn)生一些使用度不高的個體，但隨著進化過程的進行，新的群體中總會更多地產(chǎn)生出許多優(yōu)良的個體，實踐和理論都已經(jīng)證明了在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解[2]。</p>&l

8、t;p>　　遺傳算法由于具有原理簡單易懂、實現(xiàn)方便、應用效果顯著等優(yōu)點而被眾多應用領域所接受，而且在自適應控制、組合優(yōu)化、模式識別、機器學習、人工生命、管理決策等領域得到了廣泛的應用。隱含并行性和全局搜索特性是遺傳算法的兩大顯著特性。但是在簡單遺傳算法搜索過程中，進化初期的某些性狀突出的個體可能限制了其他個體進化，從而造成早熟收斂現(xiàn)象。因為經(jīng)典的遺傳算法不是一個完全遍歷的Markov[3]過程，它存在收斂速度慢、收斂過程中穩(wěn)定性差

9、、可控制性差和早熟收斂等缺陷，阻礙了遺傳算法走向?qū)嵱?。另外，在簡單遺傳算法中，對于交叉和變異的概率等參數(shù)，到目前為止仍然沒有合理的行之有效的指導性綱要來作為理論依據(jù)，都需要人為地預先指定，無論解的好壞，其遺傳操作的概率和值的變化范圍都是一樣的。這樣使得遺傳操作的適應性較差，在解決復雜問題或解空間很大時，會發(fā)生收斂速度慢或局部收斂的情況。</p><p>　　在標準遺傳算法的過程中，選擇算子和交叉變異算子之間存在著

10、收斂速度和全局收斂的矛盾。通過改變選擇壓力可以調(diào)整適應度高的個體被選中的機會。進化初期選擇壓力較大，適應度高的個體容易很快控制進化過程，造成群體的早熟，在進化過程的后期，群體差異變小，使得收斂速度降低。交叉和變異算子是對解空間新區(qū)域進行搜索的有效方法。但交叉和變異操作概率要依靠經(jīng)驗獲得，且對不同問題，情況亦不相同。交叉率高，會使群體中原高適應度的個體的淘汰速度大于交叉算子產(chǎn)生高適應度個體的速度；交叉率低，又會使得搜索過程停滯不前。變異率

11、也存在類似的問題。因此，必須對利用確定交叉變異概率的簡單遺傳算法進行改進。</p><p>　　為克服在標準遺傳算法和一般自適應遺傳算法中存在的容易陷入局域值點的難題，我們用引入強制變異，并與最佳解保留和自適應交叉變異參數(shù)調(diào)整相結(jié)合的方式，將進化過程中群體的平均適應度與最大適應度進行比較，以確定是否需要對群體實施強制變異或采用自適應交叉、變異概率調(diào)整。期望得到 一種改進的遺傳算法，從而有效地避免早熟現(xiàn)象，實現(xiàn)全局

12、優(yōu)化。這種做法在一定程度上改善了算法的搜索能力和收斂速度，但很多具體的問題還沒有考慮，對問題的解決過于固定化。因為遺傳算法參數(shù)的設定本身就是需要根據(jù)不同問題的特性而決定。設計中需要解決的問題有許多，通過對標準遺傳算法的改進盡可能達到克服過早收斂的目的，這對遺傳算法的進化性能研究是具有一定指導意義的。</p><p>　　二、研究的基本內(nèi)容，擬解決的主要問題：</p><p>　　研究基本內(nèi)

13、容：利用C++語言編程實現(xiàn)算法功能。</p><p><b>　　擬解決的主要問題：</b></p><p>　　強制變異的設計和實現(xiàn) 2、算法的設計與實現(xiàn)。</p><p>　　三、研究步驟、方法及措施：</p><p>　　研究步驟： 1.查閱相關資料，做好筆記；仔細閱讀研究文獻資料；</p>&l

14、t;p>　　2.理清整個課題的思路，撰寫開題報告和文獻綜述；翻譯英文資料；</p><p>　　3.根據(jù)需求分析，編寫算法，實現(xiàn)算法功能；</p><p>　　4. 撰寫論文；上交論文初稿；</p><p>　　5.反復修改論文；論文定稿。</p><p>　　方法、措施：充分利用好學校和網(wǎng)絡資源，搜集與蟻群算法相關的資料，仔細閱讀、分

15、析、總結(jié)。在老師指導下，與同組同學研究討論，解決設計中所碰到的問題。</p><p><b>　　四、參考文獻</b></p><p>　　[1] 孔祥蕾，張先燚，羅曉琳，李海洋。一種引入強制變異的改進遺傳算法。中國科學院研究生學報，2003.20.3</p><p>　　[2] 周明，孫樹棟。遺傳算法原理及應用。2005.3</p>

16、;<p>　　[3] Radford M. Neal, Probabilistic Inference Using Markov Chain Monte Carlo Methods , Technical Report CRG-TR-93-1 1993.36-46</p><p>　　[4] 金朝紅,吳漢松,李臘梅,王樹人。一種基于自適應遺傳算法的神經(jīng)網(wǎng)絡學習算法。微計算機信息，</p>

17、<p>　　2005， vol18,54-56</p><p>　　[5] 陳國良，王煦法，莊鎮(zhèn)泉等。遺傳算法及應用。1996.1-26</p><p>　　[6] 閆潔，曹秉剛，史維祥。一種快速收斂的遺傳算法及應用。西安交通大學報，2001.35</p><p>　　[7] 涂承媛，涂承宇。一種新的收斂于全局最優(yōu)解的遺傳算法。信息與控制，2001.3

18、0 </p><p>　　[8] 潘美芹，賀國平，馬學強?；诟倪M遺傳算法的參數(shù)調(diào)整及并行方法。武漢大學學報，2001.47</p><p>　　[9] 揚啟文，蔣靜坪，張國宏。遺傳算法速度改進。軟件學報，2001.12</p><p>　　[10] 張燁，崔杜武，黑新宏，王若峻。一種改進變異控制策略的遺傳算法研究。西安理工大學學報，2002.18.1</p&