基于引入強(qiáng)制變異的改進(jìn)遺傳算法性能研究【開(kāi)題報(bào)告】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、析、總結(jié)。在老師指導(dǎo)下，與同組同學(xué)研究討論，解決設(shè)計(jì)中所碰到的問(wèn)題。</p><p><b>　　四、參考文獻(xiàn)</b></p><p>　　[1] 孔祥蕾，張先燚，羅曉琳，李海洋。一種引入強(qiáng)制變異的改進(jìn)遺傳算法。中國(guó)科學(xué)院研究生學(xué)報(bào)，2003.20.3</p><p>　　[2] 周明，孫樹(shù)棟。遺傳算法原理及應(yīng)用。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] 金朝紅,吳漢松,李臘梅,王樹(shù)人。一種基于自適應(yīng)遺傳算法的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法。微計(jì)算機(jī)信息，</p>

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

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