開(kāi)題報(bào)告--帶互動(dòng)界面的遺傳算法演

1、<p>　　本科畢業(yè)設(shè)計(jì)開(kāi)題報(bào)告</p><p><b>　?。?012屆）</b></p><p>　　論文題目 帶互動(dòng)界面的遺傳算法演</p><p><b>　　示系統(tǒng)</b></p><p>　　一、選題的背景與意義</p><p>　　1.1 研究開(kāi)發(fā)的

2、目的</p><p>　　遺傳算法的應(yīng)用無(wú)論是用來(lái)解決實(shí)際問(wèn)題還是建模，其范圍不斷擴(kuò)展，這主要依賴于遺傳算法本身的逐漸成熟。近年來(lái)，許多冠以“遺傳算法”的研究與Holland最初提出的算法已少有雷同之處，不同的遺傳基因表達(dá)方式，不同的交叉和變異算子，特殊算子的引用，以及不同的再生和選擇方法，但這些改進(jìn)方法產(chǎn)生的靈感都來(lái)自于大自然的生物進(jìn)化，可以歸為一個(gè)“算法簇”。人們用進(jìn)化計(jì)算（EC）來(lái)包容這樣的遺傳“算法簇”。

3、它基本劃分為四個(gè)分支[1]：遺傳算法（GA）、進(jìn)化規(guī)劃（EP）、進(jìn)化策略（ES）和遺傳程序設(shè)計(jì)（GP）。有些學(xué)者甚至提出，進(jìn)化計(jì)算是人工智能的未來(lái)。其觀點(diǎn)是，雖然我們不能設(shè)計(jì)人工智能（即用機(jī)器代替人的自然智能），但我們可以利用進(jìn)化通過(guò)計(jì)算獲得智能[2]。目前，進(jìn)化計(jì)算與人工神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)理論一起已經(jīng)形成一個(gè)新的研究方向—計(jì)算智能（computational intelligence）。人工智能已經(jīng)從傳統(tǒng)的基于符號(hào)處理的符號(hào)主義，向以

4、神經(jīng)網(wǎng)絡(luò)為代表的連接主義和以進(jìn)化計(jì)算為代表的進(jìn)化主義方向發(fā)展[3]。</p><p>　　遺傳算法作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究，廣泛應(yīng)用于自動(dòng)控制、計(jì)算科學(xué)、模式識(shí)別、智能故障診斷管理科學(xué)和社會(huì)科學(xué)領(lǐng)域，適用于解決復(fù)雜的非線性和多維空間尋優(yōu)問(wèn)題。利用遺傳算法的搜索過(guò)程不受優(yōu)化函數(shù)的連續(xù)性約束，也沒(méi)有優(yōu)化函數(shù)的導(dǎo)數(shù)必須存在的要求；遺傳算法采用多點(diǎn)搜索或者說(shuō)是群體搜索，具有很高的隱含并行性

5、，因而可以提高計(jì)算速度；遺傳算法更適合大規(guī)模復(fù)雜問(wèn)題的優(yōu)化。鑒于遺傳算法有以上這些優(yōu)點(diǎn)，所以對(duì)它的研究將具有重要意義?？梢灶A(yù)料在不遠(yuǎn)的將來(lái)，隨著理論研究的不斷深入和應(yīng)用領(lǐng)域的不斷拓廣，遺傳算法將取得長(zhǎng)足的進(jìn)展。</p><p>　　1.2 國(guó)內(nèi)外研究發(fā)展現(xiàn)狀</p><p>　　在二十世紀(jì)60年代，美國(guó)Michigan大學(xué)的Holland教授及其他一些科學(xué)家分別獨(dú)立地通過(guò)對(duì)自然和人工系統(tǒng)的

6、研究，提出了遺傳算法的基本思想。1975年，Holland教授出版了關(guān)于遺傳算法的經(jīng)典著作《Adaptation in Nature and Artificial System》，標(biāo)志著遺傳算法的正式誕生。Holland教授在文獻(xiàn)中提出的遺傳算法后來(lái)被人們稱為簡(jiǎn)單遺傳算法(SGA)。簡(jiǎn)單遺傳算法的個(gè)體采取二進(jìn)制編碼方式，主要由交換算子產(chǎn)生新的個(gè)體，通過(guò)選擇操作體現(xiàn)“優(yōu)勝劣汰”的自然選擇機(jī)制。簡(jiǎn)單遺傳算法以圖式定理或稱型式定理、模式定理為

7、理論基礎(chǔ)，認(rèn)為遺傳算法具有隱含并行性和全局收斂性。這一結(jié)論現(xiàn)在被普遍認(rèn)為是值得懷疑的。經(jīng)過(guò)近三十年的發(fā)展，遺傳算法的理論研究取得了很大進(jìn)展，已有不少學(xué)術(shù)專著出版，有關(guān)人工智能的著作中一般也有關(guān)于遺傳算法的章節(jié)，其應(yīng)用研究更是取得了輝煌的成就。近年來(lái)，有不少博士學(xué)位論文對(duì)遺傳算法的理論和應(yīng)用作了專題論述?，F(xiàn)在，遺傳算法的實(shí)際應(yīng)用已經(jīng)滲透到了各行各業(yè)。</p><p>　　遺傳算法是建立在自然選擇和群體遺傳學(xué)基礎(chǔ)上的

8、一種非數(shù)值計(jì)算優(yōu)化方法[4]。遺傳算法將問(wèn)題的解表示成字符串，并把這樣的字符串當(dāng)作人工染色體或稱為個(gè)體，多個(gè)個(gè)體構(gòu)成一個(gè)群體。隨機(jī)產(chǎn)生若干個(gè)個(gè)體構(gòu)成初始群體，通過(guò)對(duì)群體的不斷進(jìn)化，利用“優(yōu)勝劣汰”的自然選擇機(jī)制，使群體中的個(gè)體不斷朝著最優(yōu)解的方向移動(dòng)，最終搜索到問(wèn)題的最優(yōu)解。個(gè)體通過(guò)遺傳算子的作用生成子代個(gè)體。通過(guò)定義個(gè)體的評(píng)價(jià)函數(shù)，稱為適應(yīng)度函數(shù)來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣。個(gè)體的適應(yīng)度反映個(gè)體適應(yīng)環(huán)境的能力，適應(yīng)度大的個(gè)體生存能力強(qiáng)。按照自然選

9、擇的基本原理，適應(yīng)度越大的個(gè)體被選擇用來(lái)繁殖后代的機(jī)會(huì)越大。遺傳算法是模擬遺傳行為的智能算法，而遺傳算法的理論研究?jī)?nèi)容主要包括染色體的編碼方法、遺傳算子、算法的運(yùn)行過(guò)程、遺傳控制參數(shù)的選擇、算法的收斂性和收斂速度以及遺傳算法的改進(jìn)和與其它方法的綜合等[5]。</p><p>　　遺傳算法雖然有諸多的優(yōu)點(diǎn)，也已在實(shí)際中得到了大量應(yīng)用 ,但它也存在著許多急待解決的問(wèn)題。例如，如何進(jìn)行算法本身的參數(shù)優(yōu)化選擇[6][7]

10、，即對(duì)群體的規(guī)模、交換概率和變異概率進(jìn)行優(yōu)化選擇。因?yàn)閷?shí)踐發(fā)現(xiàn)這些參數(shù)的選取直接關(guān)系著GA求解問(wèn)題的成敗。如何避免算法過(guò)早收斂的產(chǎn)生[8]，過(guò)早收斂是指GA在執(zhí)行過(guò)程中會(huì)出現(xiàn)群體中的個(gè)體過(guò)早地在一個(gè)非最優(yōu)點(diǎn)上達(dá)到完全相同或接近完全相同的現(xiàn)象。一旦出現(xiàn)該現(xiàn)象,利用GA就不能求得問(wèn)題的全域最優(yōu)解。對(duì)于動(dòng)態(tài)數(shù)據(jù)，用遺傳算法求最優(yōu)解比較困難，因?yàn)槿旧w種群很可能過(guò)早地收斂，而對(duì)以后變化了的數(shù)據(jù)不再變化。針對(duì)這一問(wèn)題，研究者提出了一些方法增加基因

11、的多樣性，從而防止過(guò)早地收斂。其中一種是觸發(fā)式超級(jí)變異，就是當(dāng)染色體群體的質(zhì)量下降（彼此區(qū)別減少）時(shí)增加變異概率；另一種是隨機(jī)外來(lái)染色體，是偶爾加入一些全新的隨機(jī)生成的染色體個(gè)體，從而增加染色體多樣性。還有如何改進(jìn)操作手段或引入新操作手段來(lái)提高算法的執(zhí)行效果，如何將該算法與其它傳統(tǒng)優(yōu)化方法有機(jī)結(jié)合起來(lái)等等問(wèn)題。以上存在的問(wèn)題有的已基本獲得解決,而有的則正在解決當(dāng)中。</p><p>　　二、研究開(kāi)發(fā)的基本內(nèi)容、目

12、標(biāo)，擬解決的主要問(wèn)題或技術(shù)關(guān)鍵</p><p><b>　　2.1 研究目標(biāo)</b></p><p>　　遺傳算法是一種模擬達(dá)爾文生物進(jìn)化理論的隨機(jī)的優(yōu)化方法，適于處理非線性，多極值，剛性甚至于不可微的目標(biāo)函數(shù)，適用于連續(xù)，離散或部分連續(xù)部分離散的混合解域空間，并且原則上可望達(dá)到真正的理論“最優(yōu)值”[9]；它是一種非常有競(jìng)爭(zhēng)性的，很有發(fā)展前途的優(yōu)化方法，在近十年來(lái)，獲

13、得了巨大的研究進(jìn)展。本課題在借鑒與研究國(guó)內(nèi)外有關(guān)遺傳算法所取得的豐碩成果的基礎(chǔ)上，擬用Java 實(shí)現(xiàn)帶互動(dòng)界面的遺傳算法演示系統(tǒng)，針對(duì)一個(gè)具體問(wèn)題如（背包問(wèn)題）來(lái)實(shí)現(xiàn)演示功能。</p><p>　　2.2 研究的基本內(nèi)容</p><p>　　背包問(wèn)題是一個(gè)典型的NP完全問(wèn)題，主要應(yīng)用于管理中的資源分配、投資決策、裝載問(wèn)題的建模。其求解主要依靠一些啟發(fā)式算法，也可用遺傳算法求解。遺傳算法應(yīng)用

14、于背包問(wèn)題，涉及到約束條件滿足下的遺傳編碼方法，以及交叉、變異操作算子的設(shè)計(jì)等方面[10]。</p><p>　　背包問(wèn)題的數(shù)學(xué)模型實(shí)際上是一個(gè)0-1規(guī)劃問(wèn)題[11]。假設(shè)有n個(gè)物件，其重量用表示，價(jià)值為(j=1,…,n)，背包的最大容納重量為b。如果物件j被選入背包時(shí)，定義變量=1，否則=0?？紤]n個(gè)物件的選擇與否，背包內(nèi)物件的總重量為，物件的總價(jià)值為，如何決定變量的值（即確定一個(gè)物件組合）使背包內(nèi)物件總價(jià)值為

15、最大。這個(gè)問(wèn)題解的總組合數(shù)有個(gè)，其數(shù)學(xué)模型表示如下：</p><p>　　其中=0或1，j=1,…,n。,,b均為正值。</p><p>　　遺傳算法應(yīng)用于背包問(wèn)題時(shí)，如果采用通常的二進(jìn)制編碼，一組0-1決策變量{(j=1,…,n)}直接表示n為二進(jìn)制字符串，作為一個(gè)個(gè)體的遺傳基因表示。在這樣的表示方法中，若第j位基因碼為1時(shí)，則第j個(gè)物件被選擇；若第j位基因碼為0時(shí)，則第j個(gè)物件不被選擇

16、。</p><p>　　處理約束條件有兩種方法[12]：一種方法是用罰函數(shù)法改造目標(biāo)函數(shù)；另一種方法是結(jié)合貪心算法改造染色體的解碼過(guò)程。后者實(shí)際上可以看做是一種混合遺傳算法。</p><p>　　罰函數(shù)法[13] 適應(yīng)度函數(shù)的計(jì)算用下式：</p><p>　　實(shí)際上，上述適應(yīng)度函數(shù)基于一個(gè)考慮違背約束條件的懲罰處理，當(dāng)問(wèn)題規(guī)模很大時(shí)，盡管方法可行，但搜索的效率很低

17、，甚至很多情況下所得到的結(jié)果比貪心算法的結(jié)果還差。</p><p>　　（2）混合遺傳算法[14] 將啟發(fā)式搜索算法“貪心算法”引入染色體的解碼過(guò)程中，具體做法很簡(jiǎn)單，對(duì)于那些不滿足約束的染色體編碼對(duì)應(yīng)的個(gè)體，優(yōu)先裝入價(jià)值密度較大且編碼值為1的物品，直至背包容量限制裝不下為止，并將未裝入的物品編碼值修正為0，形成個(gè)體新的染色體編碼。</p><p>　　2.3 需要解決的技術(shù)難點(diǎn)<

18、/p><p>　?。?）基于懲罰法來(lái)處理不可行性和背包承重利用不足可行解的思想，將使個(gè)體朝著充分利用背包的承重方向進(jìn)化，從而達(dá)到加快遺傳算法收斂速度的作用[15]。但是，隨著求解規(guī)模n的增大，簡(jiǎn)單遺傳算法得到的近似最優(yōu)解并不理想[16][17]。這是因?yàn)椋紫?，?duì)不可行解的懲罰在加快搜索速度的同時(shí)降低了局部搜索能力；其次，在運(yùn)行早期個(gè)體差異較大，后代產(chǎn)生的個(gè)數(shù)與父?jìng)€(gè)體適應(yīng)度大小成正比[18][19]，因此在早期容易使

19、個(gè)別好的個(gè)體的后代充斥整個(gè)種群，過(guò)快的收斂于某一局部極值，造成“早熟”[20]；而在簡(jiǎn)單遺傳算法后期，適應(yīng)度趨向一致，優(yōu)秀的個(gè)體在產(chǎn)生后代時(shí)，優(yōu)勢(shì)不明顯，從而使整個(gè)種群進(jìn)化停滯不前。</p><p>　　（2）用Java建立遺傳算法系統(tǒng)框架</p><p>　?。?）對(duì)系統(tǒng)界面模塊的實(shí)現(xiàn)</p><p>　　三、研究開(kāi)發(fā)的方法、技術(shù)路線和步驟</p>

20、<p>　　系統(tǒng)平臺(tái)：Microsoft Windows 7</p><p><b>　　編程語(yǔ)言：Java</b></p><p>　　Java是一種使用非常廣泛的計(jì)算機(jī)編程語(yǔ)言。Java是一種靜態(tài)數(shù)據(jù)類型檢查的、支持多重編程范式的通用程序設(shè)計(jì)語(yǔ)言。它支持過(guò)程化程序設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、制作圖標(biāo)等等泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。</p&

21、gt;<p>　　系統(tǒng)開(kāi)發(fā)工具：My Eclipse</p><p>　　My Eclipse企業(yè)級(jí)工作平臺(tái)（My Eclipse Enterprise Workbench，簡(jiǎn)稱My Eclipse）是對(duì)Eclipse IDE的擴(kuò)展，利用它可以在數(shù)據(jù)庫(kù)和J2EE的開(kāi)發(fā)、發(fā)布，以及應(yīng)用程序服務(wù)器的整合方面極大的提高工作效率。它是功能豐富的J2EE集成開(kāi)發(fā)環(huán)境，包括了完備的編碼、調(diào)試、測(cè)試和發(fā)布功能，完

22、整支持HTML，Struts，JSF，CSS，Javascript，SQL，Hibernate。 　　</p><p>　　在結(jié)構(gòu)上，My Eclipse的特征可以被分為7類：J2EE模型，WEB開(kāi)發(fā)工具，EJB開(kāi)發(fā)工具，應(yīng)用程序服務(wù)器的連接器，J2EE項(xiàng)目部署服務(wù)，數(shù)據(jù)庫(kù)服務(wù)，My Eclipse整合幫助。 </p><p>　　對(duì)于以上每一種功能上的類別，在Eclipse中都有相應(yīng)的功

23、能部件，并通過(guò)一系列的插件來(lái)實(shí)現(xiàn)它們。My Eclipse結(jié)構(gòu)上的這種模塊化，可以讓在不影響其他模塊的情況下，對(duì)任一模塊進(jìn)行單獨(dú)的擴(kuò)展和升級(jí)。簡(jiǎn)單而言，My Eclipse是Eclipse的插件，也是一款功能強(qiáng)大的J2EE集成開(kāi)發(fā)環(huán)境，支持代碼編寫、配置、測(cè)試以及除錯(cuò)。</p><p>　　(4) 實(shí)現(xiàn)步驟：采用二進(jìn)制0-1編碼[21]。裝入背包的物品用1表示，未裝入的用0表示，一種裝入方法用一個(gè)染色體表示，總共

24、產(chǎn)生的染色體個(gè)數(shù)等于群體規(guī)模。對(duì)各個(gè)染色體計(jì)算其適應(yīng)度值，淘汰適應(yīng)度值最低的，復(fù)制適應(yīng)度值最高的，用最高的代替最低的，這樣完成選擇；再隨機(jī)產(chǎn)生交叉點(diǎn)及相互交叉的染色體進(jìn)行交叉，計(jì)算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達(dá)到交叉最多次數(shù)未交叉成功則退出；交叉完成后就進(jìn)行變異，根據(jù)變異概率隨機(jī)選擇變異的染色體，隨機(jī)產(chǎn)生變異點(diǎn)進(jìn)行變異，變異后也需要計(jì)算染色體是否符合要求，若不符合則變異

25、失敗，重新變異，達(dá)到變異最多次數(shù)未變異成功則退出。這樣遺傳算法的基本步驟完成，重復(fù)以上步驟，直到設(shè)計(jì)的進(jìn)化次數(shù)才退出?？偨Y(jié)起來(lái)主要步驟如下[22]：群體的初始化、產(chǎn)生遺傳編碼，構(gòu)造適應(yīng)度函數(shù)，選擇操作，交叉操作，變異操作。 </p><p>　　四、研究工作總體安排與時(shí)間進(jìn)度</p><p><b>　　參考文獻(xiàn)</b></p><p>

26、　　L.Davis,Handbook of Genetic Algorithms[M], van Nostrand Rei－nhold, New York，1991.</p><p>　　李敏強(qiáng),寇繼松,林丹，李書(shū)全.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.3.</p><p>　　ooker,Goldberg L B,Holland J H. Classifier S

27、ystems and Genetic Algorithm Intelligence[J].1989,40:235-282.</p><p>　　Bosman P A N, Thierens D. The balance between proximity and diversity in multi-objective evolutionary algorithms[J].IEEE Transactions on

28、 Evolutionary Computation, 2003, 7(2): 174 -188.</p><p>　　Stender J (Ed).Parallel Genetic Algorithms[J].Theory and Application. ISO Press,1993.</p><p>　　Powll D. Tong S ,Skolnik M. EnGENEous:Dom

29、ain Independent , Machine for Design Optimization[J]. Proc of ICGA-89,1989.</p><p>　　Brawn H. On Solving Traveling Salesman Problems by Genetic Algorithms[J].</p><p>　　Pan Z J, Kang L S． An Adap

30、tive Evolutionary Algorithms for Numerical Optimization[J]．Proc．of SEAL＇96,Taejon, Korea, 1996:53－60.</p><p>　　王小平,曹立明.遺傳算法--理論應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.</p><p>　　Vose ,Michael D,簡(jiǎn)單遺傳算法：基礎(chǔ)和理論

31、[M]，MIT Press，Cambridge，MA，1999.</p><p>　　Schmitt，Lothar M，遺傳算法理論(二)[M]，Theoretical Computer Science(310)，pp.181-231,2004.</p><p>　　Schmitt，Lothar M，遺傳算法理論[M]，Theoretical Computer Science(259)，p

32、p.1-61,2001.</p><p>　　Goldberg,David E．創(chuàng)新的設(shè)計(jì):競(jìng)爭(zhēng)遺傳算法課程[M]，Addison-Wesley,Reading，MA.2002.</p><p>　　(美）卡倫著． 人工智能[M]． 黃厚寬，等譯． 北京：電子工業(yè)出版社， 2004.</p><p>　　Tom M．Michell．機(jī)器學(xué)習(xí)[M]．北京：機(jī)械工業(yè)出版

33、社，2003.</p><p>　　章曉級(jí)，戴冠中，徐乃平．一種新的優(yōu)化搜索算法-遺傳算法[J]．廣州：控制理論與應(yīng)用．1999，12（3）:365－273.</p><p>　　徐清振，肖成林．遺傳算法的研究與應(yīng)用[J]．廣州：現(xiàn)代計(jì)算機(jī)，2006.</p><p>　　陳文清．遺傳算法綜述[J]．洛陽(yáng)：洛陽(yáng)高等?？茖W(xué)校學(xué)報(bào)，2003.</p>&l

34、t;p>　　孫艷豐．王眾托．自然數(shù)編碼遺傳算法的最優(yōu)種群規(guī)模[J]．沈陽(yáng)：信息與控制，1996（5）.</p><p>　　陳國(guó)良，等．遺傳算法及應(yīng)用[M]．Behaviour of A Class of Genetic Adaptive Systems．PhD thesis，University of Michigan，1975.</p><p>　　劉勇，等．非數(shù)值并行算法（二）