帶互動界面的遺傳算法演示系統

本科畢業(yè)設計說明書（論文）（2012屆）論文題目帶互動界面的遺傳算法演示系統I PAGEI摘要遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索方法。它最早由美國密執(zhí)安大學的Holland教授提出，起源于60年代對自然和人工自適應系統的研究。遺傳算法作為具有系統優(yōu)化、適應和學習的高性能計算和建模方法的研究，廣泛應用于自動控制、計算科學、模式識別、智能故障診斷管理科學和社會科學領域，適用于解決復雜的非線性和多維空間尋優(yōu)問題。帶互動界面的遺傳算法演示系統主要是演示運用遺傳算法解決背包問題，對簡單遺傳算法的交叉算子和變異算子做了改進，通過實驗驗證了改進之后遺傳算法在解決背包問題方面準確度以及效率的提高。帶互動界面的遺傳算法演示系統使用MyEclipse作為開發(fā)工具，使用面向對象的Java語言進行編程設計，通過鍵盤輸入或者讀取特定文件來處理數據以達到互動演示效果。帶互動界面的遺傳算法演示系統主要包括從文件讀取數據，從鍵盤輸入數據，參數曲線演示，關于演示系統，退出演示系統五大功能模塊，其中演示的主要模塊為從文件中讀取數據，從鍵盤輸入數據以及參數曲線演示。從文件中讀取數據要求用戶輸入將要處理的有效文件名，系統將給出最終運算結果；從鍵盤輸入數據需要用戶手動輸入要處理的數據，系統將給出最終運算結果；參數曲線演示模塊展示了最優(yōu)值關于種群大小、交叉概率、變異概率的變化曲線；關于演示系統主要介紹了本系統的一些基本信息；用戶通過退出演示系統模塊來退出該系統。經過各方面測試，該系統運行穩(wěn)定，對于利用遺傳算法解決背包問題來說，能夠實現良好的互動演示效果并能給出正確的結果。關鍵詞：遺傳算法演示系統，背包問題，MyEclipse，JavaAbstractGeneticalgorithmisanadaptiveandgloballyoptimizedandprobabilisticsearchingmethodwhichformsintheprocessofsimulatingtheorganisms’geneticsandevolutioninthenaturalenvironment.ItwasfirstlyproposedbyHollandwhowastheprofessorofUniversityofMichigan.Geneticalgorithmoriginatedfromtheresearchonnaturalandartificialadaptivesysteminthe1960s.Asaresearchwiththeabilityofsystemoptimizing,adaptiveandself-learninghigh-performancecomputingandmodeling,Geneticalgorithmiswidelyusedinthefieldofautomaticcontrol,computingscience,patternrecognition,intelligentfaultdiagnosismanagementsciencesandsocialsciences.Itissuitableforsolvingthecomplexnon-linearproblemandthemulti-dimensionalspaceoptimizationproblem.TheGeneticalgorithmdemonstrationsystemwithinteractiveinterfaceistodemonstratetheuseofGeneticalgorithmtosolvetheknapsackproblem.Ithasmadesomeimprovementsoncrossoveroperatorandmutationoperator.Itisverifiedthattheimprovedgeneticalgorithmindeedimprovedtheaccuracyandefficiencyinsolvingtheknapsackproblem.TheGeneticalgorithmdemonstrationsystemwithinteractiveinterfaceuseMyEclipseasadevelopmenttool,theobject-orientedJavalanguagetoprogramanddesign,inputtingviathekeyboardorreadingaparticularfiletoprocessthedatainordertoachieveinteractivedemoeffect.TheGeneticalgorithmdemonstrationsystemwithinteractiveinterfacemainlyincludesthefollowingfunctionalmodules:readingfromaparticularfile,inputtingviathekeyboard,thedemonstrationofparametriccurves，aboutdemosystemandquit.Readingfromaparticularfile,inputtingviathekeyboardarethemainfunctionalmodules.Readingfromaparticularfilerequirestheusertoinputavalidfilenameandthesystemwillgivethefinalresultoftheoperation.Inputtingviathekeyboardrequirestheusertoinputthevaliddataandthesystemwillgivethefinalresultoftheoperationthedemonstrationofparametriccurvesdemonstratetheoptimalvaluesforpopulationsize,crossoverprobability,mutationprobabilitycurve.Theaboutdemosystemintroducessomebasicinformationofthesystem.Thequitallowstheusertoexitthesystem.Afterthecarefultest,thesystemisstable,anditcanachievegoodinteractivedemonstrationeffectandgivesthecorrectresult.Keywords：Geneticalgorithmdemonstrationsystem,knapsackproblem,myeclipse,java目錄TOC\o"1-3"\f\u摘要 IAbstract I第一章緒論 11.1 研究開發(fā)的目的 11.2 國內外研究發(fā)展現狀 21.3 公式 31.4 本文的主要工作 41.5 本文的組織結構 41.6 本章小結 5第二章研究開發(fā)的基本內容、方法 62.1 背包問題的基本內容 62.2 研究目標 72.3 開發(fā)工具簡介 72.4 主要開發(fā)語言簡介 82.5 整體開發(fā)設計簡介 82.6 本章小結 9第三章遺傳算法的基本原理與實現技術 103.1 模式定理 103.1.1 模式 103.1.2 模式定理 103.2 編碼技術 113.2.1 群體設定 113.2.2 適應度函數 123.2.3 適應度尺度變換 123.2.4 遺傳操作 123.3 本章小結 14第四章背包問題描述與實現以及對簡單遺傳算法的改進 154.1 背包問題描述 154.2 編碼選擇 154.2.1 群體設定 154.2.2 適應度函數 154.2.3 約束條件 154.2.4 選擇算子的設計 164.2.5 交叉算子的設計 164.2.6 變異算子的設計 164.3 對利用遺傳算法解決背包問題的改進 164.3.1 參數實驗 164.3.2 改進的交叉算子：單點交叉與均勻交叉結合的算子 194.3.3 改進的變異算子：不降低適應度的變異方式 234.4 本章小結 24第五章帶互動界面的遺傳算法演示系統詳細設計 265.1 系統功能模塊詳細設計 265.2 系統性能優(yōu)化設計 285.3 本章小結 28第六章帶互動界面的遺傳算法演示系統實現 296.1 系統界面實現 296.2 系統功能模塊實現 316.3 本章小結 34第七章總結 357.1完成的工作 357.2 存在的問題及下一步工作 357.2.1 存在問題 357.2.2 下一步工作 35參考文獻 36致謝 38附錄 39圖目錄TOC\c"圖"圖41最優(yōu)值-變異概率曲線圖 18圖42最優(yōu)值-交叉概率曲線圖 18圖43最優(yōu)值-群體大小曲線 19圖44改進的交叉算子所得最優(yōu)結果圖 21圖45改進的交叉算子所得最優(yōu)值-進化代數曲線圖 21圖46未改進的交叉算子所得最優(yōu)結果圖 22圖47未改進的交叉算子所得最優(yōu)值-進化代數曲線圖 23圖48改進的變異算子所得最優(yōu)結果圖 24圖49改進的變異算子所得最優(yōu)值-進化代數曲線圖 24圖51處理文件流程 26圖52從鍵盤輸入數據流程 27圖61從文件讀取數據模塊主界面 29圖62從鍵盤輸入數據模塊界面 30圖63參數曲線演示模塊界面 30圖64關于演示系統模塊界面 31圖65文件不存在時發(fā)出警告 32圖66文件數據有誤時發(fā)出警告 32圖67顯示處理結果 33圖68進化曲線圖 33圖69進化詳情圖 34表目錄TOC\c"表"表41參數實驗表 17表42參數表 20表43改進的交叉算子所得結果統計表 21表44未改進的交叉算子所得結果統計表 22表45改進的變異算子所得結果統計表 23PAGE41第一章緒論研究開發(fā)的目的遺傳算法的應用無論是用來解決實際問題還是建模，其范圍不斷擴展，這主要依賴于遺傳算法本身的逐漸成熟。近年來，許多冠以“遺傳算法”的研究與Holland最初提出的算法已少有雷同之處，不同的遺傳基因表達方式，不同的交叉和變異算子，特殊算子的引用，以及不同的再生和選擇方法，但這些改進方法產生的靈感都來自于大自然的生物進化，可以歸為一個“算法簇”。人們用進化計算（EC）來包容這樣的遺傳“算法簇”。它基本劃分為四個分支：遺傳算法（GA）、進化規(guī)劃（EP）、進化策略（ES）和遺傳程序設計（GP）[1]。有些學者甚至提出，進化計算是人工智能的未來。其觀點是，雖然我們不能設計人工智能（即用機器代替人的自然智能），但我們可以利用進化通過計算獲得智能[2]。目前，進化計算與人工神經網絡、模糊系統理論一起已經形成一個新的研究方向—計算智能（computationalintelligence）。人工智能已經從傳統的基于符號處理的符號主義，向以神經網絡為代表的連接主義和以進化計算為代表的進化主義方向發(fā)展。遺傳算法作為具有系統優(yōu)化、適應和學習的高性能計算和建模方法的研究，廣泛應用于自動控制、計算科學、模式識別、智能故障診斷管理科學和社會科學領域，適用于解決復雜的非線性和多維空間尋優(yōu)問題。利用遺傳算法的搜索過程不受優(yōu)化函數的連續(xù)性約束，也沒有優(yōu)化函數的導數必須存在的要求；遺傳算法采用多點搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計算速度；遺傳算法更適合大規(guī)模復雜問題的優(yōu)化[3]。鑒于遺傳算法有以上這些優(yōu)點，所以對它的研究將具有重要意義?？梢灶A料在不遠的將來，隨著理論研究的不斷深入和應用領域的不斷拓廣，遺傳算法將取得長足的進展。本文旨在就具體的背包問題來展示利用遺傳算法對其解決的具體過程與結果，以顯示遺傳算法在解決該類問題方面的良好性能，并在簡單遺傳算法的基礎上對交叉算子和遺傳算子進行改進，進一步提高遺傳算法的解決問題的準確度和效率。國內外研究發(fā)展現狀在20世紀60年代，美國密歇根（Michigan）大學的Holland教授及其他一些科學家分別獨立地對人工系統和自然的研究之后，提出了遺傳算法的基本思想。1975年，Holland教授出版了經典著作《AdaptationinNatureandArtificialSystem》，象征著遺傳算法的正式誕生。Holland教授提出的遺傳算法即是后來的簡單遺傳算法。簡單遺傳算法主要由交叉算子產生新個體，個體采取二進制編碼方式，通過選擇操作體現“優(yōu)勝劣汰”的自然選擇機制。簡單遺傳算法以模式定理為其理論基礎，認為遺傳算法具有全局收斂性和隱含并行性。經過幾十年的研究與發(fā)展，遺傳算法的理論研究取得了重大進展，其應用研究更是取得了輝煌的成就，已經滲透到了各行各業(yè)。有關人工智能的著作中一般也有關于遺傳算法的章節(jié)，現已有不少學術專著出版。近年來，有不少博士學位論文對遺傳算法的理論和應用作了專題論述。遺傳算法是一種非數值計算優(yōu)化方法，它建立在群體遺傳學和自然選擇基礎之上[4]。遺傳算法將問題的解表示成字符串，并把這樣的字符串當作染色體，許多個體便構成了一個種群。通過隨機方式產生若干個個體構成初始種群，然后對群體不斷進化，利用“優(yōu)勝劣汰”的選擇機制，使種群中的個體朝著最優(yōu)值的方向進化，最終搜索到問題的近似最優(yōu)解或者最優(yōu)解。個體通過選擇、交叉和變異算子的作用生成子代個體。通過定義個體的評價函數，也稱為適應度函數，來評價個體的優(yōu)劣。個體的適應度反映個體適應環(huán)境的能力，適應度大的個體生存能力強。按照自然選擇的基本原理，適應度越大的個體被選擇用來繁殖后代的機會越大。遺傳算法是模擬遺傳進化的智能算法，而遺傳算法的理論研究內容主要包括染色體的遺傳控制參數的選擇、編碼方法、遺傳算子、算法的運行過程、算法的收斂性和收斂速度以及遺傳算法的改進和與其它方法的綜合等[5]。遺傳算法雖然有諸多的優(yōu)點，也已在實際中得到了大量應用,但它也存在著許多急待解決的問題。例如，如何進行算法本身的參數優(yōu)化選擇[6][7]，即對群體的規(guī)模、交換概率和變異概率進行優(yōu)化選擇。因為實踐發(fā)現這些參數的選取直接關系著GA求解問題的成敗。如何避免算法過早收斂的產生[8]，過早收斂是指GA在執(zhí)行過程中會出現群體中的個體過早地在一個非最優(yōu)點上達到完全相同或接近完全相同的現象。一旦出現該現象,利用GA就不能求得問題的全域最優(yōu)解。對于動態(tài)數據，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過早地收斂，而對以后變化了的數據不再變化。針對這一問題，研究者提出了一些方法增加基因的多樣性，從而防止過早地收斂。其中一種是觸發(fā)式超級變異，就是當染色體群體的質量下降（彼此區(qū)別減少）時增加變異概率；另一種是隨機外來染色體，是偶爾加入一些全新的隨機生成的染色體個體，從而增加染色體多樣性。還有如何改進操作手段或引入新操作手段來提高算法的執(zhí)行效果，如何將該算法與其它傳統優(yōu)化方法有機結合起來等等問題。以上存在的問題有的已基本獲得解決,而有的則正在解決當中。公式背包問題的數學模型[9]：其中=0或1，j=1,…,n。,,b均為正值（1-1）利用罰函數法時適應度函數的計算公式[9]：（1-2）求目標函數的全局最大值的轉換公式[10]：（1-3）求目標函數的全局最小值的轉換公式[10]：（1-4）本文的主要工作本文的主要工作是在深入理解與掌握遺傳算法的基礎上，詳細的分析與設計利用該算法來解決背包問題，闡述在設計與開發(fā)過程中所用到的相關技術以及所遇到的技術難題與解決方案，并解析該系統的具體實現過程與結果。本系統對交叉算子和遺傳算子做了改進，然后對改進的遺傳算法做了實驗，得出結果并分析了數據。本文的組織結構本文共分為七章，以“帶互動界面的遺傳算法演示系統”為背景，研究討論了遺傳算法的原理及實現，針對于具體的背包問題，設計了利用遺傳算法的解決方案，并在傳統遺傳算法上進行了改進。各章內容如下：第一章，介紹了課題研究的背景，國內外相關領域的研究及應用，課題研究的主要任務和本文的主要工作。第二章，詳細介紹了研究開發(fā)的基本內容和方法。第三章，重點介紹了遺傳算法的基本原理和實現技術。第四章，具體介紹了背包問題的描述與實現，重點講解了對簡單遺傳算法在交叉算子和變異算子方面的改進，并且通過數據分析了改進的效果。第五章，詳細介紹了帶互動界面的遺傳算法演示系統在演示界面方面的詳細設計。第六章，著重闡述了帶互動界面的遺傳算法演示系統在演示界面方面的具體實現，針對第五章提出的詳細設計要求，在本章給出系統的技術實現。第七章，對系統開發(fā)進行總結并提出下一步工作。本章小結本章簡要介紹項目的研究背景、在國內外相關領域的開發(fā)和應用現狀以及項目的研究的任務和意義。最后，給出了本文的主要工作及本文的組織結構。第二章研究開發(fā)的基本內容、方法背包問題的基本內容背包問題是一個典型的NP完全問題[10]，主要應用于管理中的資源分配、投資決策、裝載問題的建模。其求解主要依靠一些啟發(fā)式算法，也可用遺傳算法求解。遺傳算法應用于背包問題，涉及到約束條件滿足下的遺傳編碼方法，以及交叉、變異操作算子的設計等方面。背包問題的數學模型實際上是一個0-1規(guī)劃問題。假設有n個物件，其重量用表示，價值為(j=1,…,n)，背包的最大容納重量為b。如果物件j被選入背包時，定義變量=1，否則=0。考慮n個物件的選擇與否，背包內物件的總重量為，物件的總價值為，如何決定變量的值（即確定一個物件組合）使背包內物件總價值為最大。這個問題解的總組合數有個，其數學模型表示如公式（1-1）所示。遺傳算法應用于背包問題時，如果采用通常的二進制編碼，一組0-1決策變量{(j=1,…,n)}直接表示為二進制字符串，作為一個個體的遺傳基因表示。在這樣的表示方法中，若第j位基因碼為1時，則第j個物件被選擇；若第j位基因碼為0時，則第j個物件不被選擇。處理約束條件有三種方法[11]：一種方法是用罰函數法改造目標函數；第二種方法是結合貪心算法改造染色體的解碼過程；第三種是搜索空間限定法。第二種實際上可以看做是一種混合遺傳算法。（1）罰函數法[12]適應度函數的計算用公式（1-2），實際上，上述適應度函數基于一個考慮違背約束條件的懲罰處理，當問題規(guī)模很大時，盡管方法可行，但搜索的效率很低，甚至很多情況下所得到的結果比貪心算法的結果還差。（2）混合遺傳算法[13]將啟發(fā)式搜索算法“貪心算法”引入染色體的解碼過程中，具體做法很簡單，對于那些不滿足約束的染色體編碼對應的個體，優(yōu)先裝入價值密度較大且編碼值為1的物品，直至背包容量限制裝不下為止，并將未裝入的物品編碼值修正為0，形成個體新的染色體編碼。（3）搜索空間限定法[14]本論文所采用的即是該方法。它用程序來保證直到產生出在解空間中有對應可行解的染色體之前，一直進行交叉運算和變異運算。雖然這個實現方法對編碼方法的要求不高，但它有可能反復地進行交叉運算和變異運算才能產生出一個滿足約束條件的可行解，這樣有可能會降低遺傳算法的運行效率。但就解決背包問題來說，該方法相對來說是簡單而高效的。研究目標遺傳算法是一種模擬達爾文生物進化理論的隨機的優(yōu)化方法，適于處理非線性，多極值，剛性甚至于不可微的目標函數，適用于連續(xù)，離散或部分連續(xù)部分離散的混合解域空間，并且原則上可望達到真正的理論“最優(yōu)值”。它是一種非常有競爭性的、很有發(fā)展前途的優(yōu)化方法，在近十年來，獲得了巨大的研究進展。本課題在借鑒與研究國內外有關遺傳算法所取得的豐碩成果的基礎上，對簡單遺傳算法在交叉算子以及變異算子兩個方面進行改進，擬用Java實現帶互動界面的遺傳算法演示系統，針對具體的背包問題來實現演示功能。開發(fā)工具簡介本系統采用MyEclipse作為開發(fā)工具，MyEclipse企業(yè)級工作平臺（MyEclipseEnterpriseWorkbench，簡稱MyEclipse）是對EclipseIDE的擴展，利用它可以在數據庫和J2EE的開發(fā)、發(fā)布，以及應用程序服務器的整合方面極大的提高工作效率。它是功能豐富的J2EE集成開發(fā)環(huán)境，包括了完備的編碼、調試、測試和發(fā)布功能，完整支持HTML，Struts，JSF，CSS，Javascript，SQL，Hibernate。對于以上每一種功能上的類別，在Eclipse中都有相應的功能部件，并通過一系列的插件來實現它們。MyEclipse結構上的這種模塊化，可以讓在不影響其他模塊的情況下，對任一模塊進行單獨的擴展和升級。簡單而言，MyEclipse是Eclipse的插件，也是一款功能強大的J2EE集成開發(fā)環(huán)境，支持代碼編寫、配置、測試以及除錯。主要開發(fā)語言簡介本系統采用Java語言進行開發(fā)，Java是由SunMicrosystems公司于1995年5月推出的Java程序設計語言和Java平臺（即JavaSE,JavaEE,JavaME）的總稱，它是一種可以撰寫跨平臺應用軟件的面向對象的程序設計語言。Java技術具有諸多優(yōu)點，如卓越的平臺移植性、安全性、高效性、通用性，廣泛應用于移動電話和互聯網、科學超級計算機、游戲控制臺、數據中心、個人PC，它還擁有全球最大的專業(yè)開發(fā)者社群。整體開發(fā)設計簡介系統設計方面，采用二進制0-1編碼。裝入背包的物品用1表示，未裝入的用0表示，一種裝入方法用一個染色體表示，總共產生的染色體個數等于群體規(guī)模。對各個染色體計算其適應度值，淘汰適應度值最低的，復制適應度值最高的，用最高的代替最低的，這樣完成選擇；再隨機產生交叉點及相互交叉的染色體進行交叉。選擇交叉的染色體是使用賭輪盤法或者稱為比例選擇法。兩個父代個體通過單點交叉和均勻交叉兩種方式交叉產生四個子代個體，選擇其中適應度最大的個體作為交叉產生的個體而淘汰其它適應度低的個體；交叉完成后就進行變異，根據變異概率隨機選擇變異的染色體，隨機產生變異點進行變異，若變異后的染色體其適應度小于變異之前的染色體的適應度，則仍然保留變異之前的染色體，否則，將保存變異后的染色體。變異后也需要計算染色體是否符合要求，即是否滿足由該染色體結構計算出來的總體積不大于背包的容量。若不符合則變異失敗，重新進行選擇、交叉、變異，直到符合條件為止。在新一代種群產生之后，判斷新種群中個體的最大適應度是否大于父代種群的個體最大適應度，若是則在未達到最大進化代數的條件下進行下一輪進化，否則就將父代適應度最大的個體的染色體復制到新生代種群適應度最小的個體染色體內，并相應地改變其適應度，更新種群信息。這樣遺傳算法的基本步驟完成，重復以上步驟，直到設計的進化次數才退出?？偨Y起來主要步驟如下：群體的初始化、產生遺傳編碼，構造適應度函數，選擇操作，交叉操作，變異操作。界面設計方面，根據處理數據的方式不同分別顯示運算結果，包括最優(yōu)值，最大體積，染色體結構以及對應的物體收益與體積。對于具體結果顯示詳細的進化曲線以及產生進化的具體數據。對于對遺傳算法效率影響很大的三個參數分別做出了最優(yōu)值關于這三個參數的變化曲線。本章小結本章以系統開發(fā)的相關理論及技術為基礎，介紹系統開發(fā)過程中需要了解和掌握的方法和技術，并簡要的講解了系統開發(fā)的基本內容和研究目標，以及開發(fā)過程中所用到的相關工具和語言，最后闡述了整體的開發(fā)設計方案。第三章遺傳算法的基本原理與實現技術模式定理模式遺傳算法通過對群體中多個個體的迭代搜索來逐步找出問題的最優(yōu)解。這個搜索過程是通過個體之間的優(yōu)勝劣汰、交叉重組和變異等遺傳操作來實現的，那么新一代個體的編碼串組成與其父代個體的編碼串組成結構之間就有一些相似的結構聯系。因此引入了模式的概念。模式表示一些相似的模塊，它描述了在某些位置上具有相似結構特征的個體編碼串的一個子集。以二進制編碼方式為例，模式H=11*1*描述了長度為5，且在位置1、2、4上取值為“1”的所有字符串的集合{11010,11011,11110,11111}。模式的概念使得我們可以簡明的描述具有相似結構特點的個體編碼字符串。遺傳算法的本質是對模式所進行的一系列運算。通過這些遺傳運算，一些較差的模式逐步被淘汰，而一些較好的模式逐步被遺傳和進化，最終就可得到問題的最優(yōu)解。此外為便于定量的估計模式運算，還引入了模式階和模式定義的概念。在模式中具有確定基因值的位置數目稱為該模式的模式階，模式中第一個確定基因值的位置和最后一個確定基因值的位置之間的距離稱為該模式的模式定義長度。模式定理【模式定理】遺傳算法中，在選擇、交叉和變異算子的作用下，具有低階、短的定義長度，并且平均適應度高于群體平均適應度的模式將按照指數級增長[15]。模式定理闡述了遺傳算法的理論基礎，它說明了模式的增加規(guī)律，同時也給遺傳算法的應用提供了指導作用。編碼技術編碼是應用遺傳算法時要解決的首要問題，也是設計遺傳算法時的一個關鍵步驟。在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉換到遺傳算法所能處理的搜索空間的轉換方法就稱為編碼。如何設計一種完美的編碼方案一直是遺傳算法的應用難點之一，也是遺傳算法的一個重要研究方向。DeJong曾提出兩條操作性較強的實用編碼原則[16]：(1)有意義積木塊編碼原則：應使用能易于產生與所求問題相關的且具有低階、短定義長度模式的編碼方案。(2)最小字符集編碼原則：應使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案。由于遺傳算法的廣泛應用，迄今為止人們已經提出了許多種不同的編碼方法?？偟膩碚f，這些編碼方法可以分為三大類[17]：二進制編碼方法、浮點數編碼方法、符號編碼方法。二進制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號集是由二進制符號0和1所組成的二值符號集{0,1}。二進制編碼有諸多優(yōu)點，例如編碼、解碼操作簡單易行，交叉、變異等遺傳操作便于實現，符合最小字符集編碼原則，便于利用模式定理對算法進行理論分析。本論文便采用二進制編碼的方法。浮點數編碼方法適合于一些多維、高精度要求的連續(xù)函數優(yōu)化問題。符號編碼方法是指個體染色體編碼串中的基因值取自一個無數值含義、而只有代碼含義的符號集。群體設定根據問題的具體情況，把握問題的最優(yōu)解的范圍在整個問題空間的分布范圍，然后在這個范圍內設定初始種群。產生初始種群時根據約束條件來選擇，此時不用考慮其適應度。關于隱含并行性的一個重要結論是：遺傳算法所處理的有效模式總數約與群體規(guī)模的立方成正比[13]，所以實際應用中，群體個數的取值范圍一般在幾十到幾百。遺傳操作中的選擇操作對群體規(guī)模大小確定的影響很大。群體規(guī)模越大時，群體的多樣性便也越大，從而算法越不容易陷入局部最優(yōu)解；但群體過大時，計算量增加，在很大程度上影響算法的效率。若群體規(guī)模過小，那么搜索空間的范圍就很小，搜索有可能停止在為成熟階段，導致未成熟收斂。適應度函數遺傳算法使用適應度這個概念來度量群體中各個個體在優(yōu)化計算中與可能達到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。適應度越高遺傳到下一代的概率就越大。度量個體適應度的函數稱為適應度函數。目標函數與適應度函數[18]遺傳算法的一個特點是它僅適用所求問題的目標函數值就可得到下一步的有關搜索信息。而對目標函數值的使用是通過評價個體的適應度來體現的。最優(yōu)化問題可分為兩大類，一類為求目標函數的全局最大值，另一類為求目標函數的全局最小值。對于求最大值問題，其轉換公式如公式（1-3）所示，求最小值問題的轉換公式如公式（1-4）所示。適應度尺度變換遺傳算法中，各個個體遺傳到下一代的概率是由該個體的適應度來決定的。應用實踐中表明，僅僅使用公式（1-3）或公式（1-4）來計算個體適應度時，有些遺傳算法會收斂得很快，也有的會很慢。過快的情況可能會使群體的多樣性降低，容易導致遺傳算法發(fā)生早熟現象，使遺傳算法所求到的解停留在某一局部最優(yōu)解上。這就需要我們可能在遺傳算法運行的不同階段，需要對個體的適應度進行適當的擴大或縮小。這種對個體適應度所做的擴大或縮小變換就稱為適應度尺度變換。目前常用的個體適應度尺度變換方法主要有以下三種[19]：①線性尺度變換公式為：；②乘冪尺度變換公式為：；③指數尺度變換公式為：；遺傳操作選擇算子遺傳算法使用選擇算子來對群體中的個體進行優(yōu)勝劣汰操作：適應度較高的個體被遺傳到下一代群體中的概率較大；適應度較低的個體被遺傳到下一代群體中的概率較小。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計算效率。目前常用的選擇算子有[20]：①比例選擇這是一種回放式隨機采樣的方法，其基本思想是：各個個體被選中的概率與其適應度大小成正比。但是由于隨機操作的原因，這種選擇方法的選擇誤差比較大，有時甚至連適應度較高的個體也選擇不上。②最優(yōu)保存策略隨著群體的進化會產生越來越多的優(yōu)良個體，但由于選擇、交叉、變異等遺傳操作的隨機性，它們也有可能破壞掉當前群體中適應度最好的個體，這樣就會降低群體的平均適應度，并且對遺傳算法的運行效率、收斂性都有不利的影響。罪域保存策略進化模型的思想是：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來替換掉本代群體中經過交叉、變異等遺傳操作后所產生的適應度最低的個體。③排序選擇排序選擇方法的主要著眼點是個體適應度之間的大小關系，對個體適應度是否取正值或負值以及個體適應度之間的數值差異程度并無特別要求。其基本思想是：對群體中的所有個體按其適應度大小進行排序，基于這個排序來分配各個個體被選中的概率。交叉算子交叉算子的設計交叉算子的設計與實現與所研究的問題密切相關，一般要求它既不要太多的破壞個體編碼串中表示優(yōu)良形狀的優(yōu)良模式，又要能夠有效的產生出一些較好的新個體模式。另外，交叉算子的設計要和個體編碼設計統一考慮。交叉算子的設計包括以下兩方面的內容[21]：如何確定交叉點的位置；如何進行部分基因交換。交叉算子的設計簡要介紹幾種適合于二進制編碼個體或者浮點數編碼個體的交叉算子。①單點交叉又稱為簡單交叉，它是指在個體編碼串中只隨機設定一個交叉點，然后在該點相互交換兩個配對個體的部分染色體。其特點是：若鄰接基因座之間的關系能提供較好的個體性狀和較高的個體適應度的話，則這種單點交叉操作破壞這種個體性狀和降低個體適應度的可能性最小。②雙點交叉指在個體編碼串中隨機設置兩個交叉點，然后再進行兩個部分基因交換。③均勻交叉指兩個配對個體的每一個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體。④算術交叉[22]指由兩個個體的線性組合而產生出兩個新的個體。為了能夠進行線性組合運算，算術交叉的操作對象一般是由浮點數編碼所表示的個體。變異算子遺傳算法中的所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其它等位基因來替換，從而形成一個新的個體。遺傳算法中使用變異算子主要有以下兩個目的：一是改善遺傳算法的局部搜索能力，二是維持群體的多樣性，防止出現早熟現象。變異算子的設計包括兩方面的內容：如何確定變異點的位置以及如何進行基因值替換。常用的變異操作有基本位變異、均勻變異、邊界變異、非均勻變異、高斯變異等，關于每種變異的特點及操作過程限于篇幅不再贅述。本章小結本章主要對遺傳算法的基本原理以及實現技術作了比較系統的講解，包括作為遺傳算法基礎的模式定理，所用到的編碼技術，適應度函數的設置，以及選擇、交叉、變異等基本的遺傳操作，為后續(xù)系統設計與實現打下了基礎。第四章背包問題描述與實現以及對簡單遺傳算法的改進背包問題描述關于背包問題已經在第二章第一節(jié)做了比較詳細的描述，在此不再贅述。本系統所處理的數據請參看附錄文件。編碼選擇群體設定根據第三章關于群體規(guī)模設定所介紹的理論方法，在設計遺傳算法解決背包問題的方案中將群體規(guī)模設置為200。適應度函數所求的是在所有物體體積之和不超過背包的容量的情況下使得所有物體的價值之和達到最大，所以適應度函數就是各被裝入物體的價值之和。約束條件處理約束條件有三種方法：一種方法是用罰函數法改造目標函數；第二種方法是結合貪心算法改造染色體的解碼過程，即一種混合遺傳算法；第三種是搜索空間限定法。對于用遺傳算法解決背包問題來說，限制條件就是背包的容量。所以本系統對約束條件的設定就是保證裝入物體的總體積不大于背包的最大容量，用程序來保證直到產生出在解空間中有對應可行解的染色體之前，一直進行交叉運算和變異運算。雖然這個實現方法對編碼方法的要求不高，但它有可能反復地進行交叉運算和變異運算才能產生出一個滿足約束條件的可行解，這樣有可能會降低遺傳算法的運行效率。這即是所謂的搜索空間限定法。選擇算子的設計關于幾種選擇算子前面已經做了比較詳細的描述，針對于本系統的設計來說，綜合考慮各方面因素，選擇用比例選擇方法。交叉算子的設計交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起著關鍵作用，是產生新個體的主要方法。關于幾類常用的交叉算子第三章也已經做了比較詳細的講解。依據本系統設計時所采用的二進制編碼方案以及問題的規(guī)模，采用單點交叉與均勻交叉相結合的方法。變異算子的設計從遺傳運算過程中產生新個體的能力方面來說，變異運算只是產生新個體的輔助方法，但它也是一個必不可少的一個運算步驟，因為它決定了遺傳算法的局部搜索能力。第三章同樣也已經介紹了幾類常用的變異方法，本系統中采用的是基本位變異，但是增加了關于適應度的判斷條件來對其進行改進。對利用遺傳算法解決背包問題的改進參數實驗遺傳算法自身有三個參數，即群體大小，交叉概率及變異概率。下表為設置不同參數的情況下對附錄文件中數據的處理結果：遺傳代數交叉概率變異概率群體大小第一次第二次第三次第四次第五次平均適應度最大適應度第一組8000.80200297029913083305630543030.83083第二組8000.80.2200306730803059308230643070.43082第三組8000.80.5200304630453002301530493031.43049第四組8000.80.8200304829683040300930343019.83048第五組8000.81200304330483049300430533039.43053第六組80000.2200307030803051305330503060.83080第七組8000.20.2200307130503059305130523056.63071第八組8000.50.2200306130473049305830543053.83061第九組80010.2200308530693049305330683064.83085第十組8000.80.240306830233006301730183026.43068第十一組8000.80.2100304330583051307130683058.23071第十二組8000.80.2160304930593072307130553061.23072第十三組8000.80.2240305530863073309530703075.83095表4SEQ表\*ARABIC\s11參數實驗表顯而易見的是進化代數越大肯定會更有可能接近最優(yōu)值。上表中之所以選擇進化代數為800是為了更準確的比較各參數對結果的影響，若都會在設置的進化代數之內達到最大值，那么就將無法比較。比較一、二、三、四、五組，橫軸為變異概率，縱軸為最優(yōu)值。如圖（4-1）圖4SEQ圖\*ARABIC\s11最優(yōu)值-變異概率曲線圖從圖中可以看出最優(yōu)值是關于變異概率變化的，當變異概率在0~0.4之間時能得到比較好的結果。比較六、七、八、二、九組，橫軸為交叉概率，縱軸為最優(yōu)值。如圖（4-2）圖4SEQ圖\*ARABIC\s12最優(yōu)值-交叉概率曲線圖從圖中可以看出，當交叉概率在0.5至1之間時最優(yōu)值比較大，所以交叉概率最好選擇在這個范圍之間的值。比較十、十一、十二、二、十三組，橫軸為群體大小，縱軸為最優(yōu)值。如圖（4-3）圖4SEQ圖\*ARABIC\s13最優(yōu)值-群體大小曲線從圖中可以看出，最優(yōu)值隨著群體規(guī)模的增大呈上升趨勢，超過200后斜率下降，考慮運行和效率的方面，我們一般取群體大小為200左右。改進的交叉算子：單點交叉與均勻交叉結合的算子先來看一下兩種交叉方式的優(yōu)缺點。單點交叉P1與P2是兩個進行交叉的個體：P1=11011|0010P2=10000|0010劃線處為兩個個體進行交叉的位置，交叉之后的子個體為：=110110010=100000010通過上面的例子可以看出，采用單點交叉方式的優(yōu)點是它可以很好地保留父代個體的優(yōu)良性狀，是的種群向著更有利的方向進化；但正是由于此，它降低了種群的多樣性，單點交叉方式也有可能使得種群向著一個局部最優(yōu)解的方向進化。均勻交叉同樣對于上面的兩個父代個體：P1=110110010P2=100000010假設隨機產生的一個屏蔽字為：W=101100110均勻交叉的過程是：若，則在第i個基因座上的基因值繼承P1的對應基因值，在第i個基因座上的基因值繼承P2的對應基因值；若，則在第i個基因座上的基因值繼承P2的對應基因值，在第i個基因座上的基因值繼承P1的對應基因值。所以：=110010010=100100010通過上面的交叉結果可以看出，均勻交叉可以增加種群的多樣性，在某種程度上防止種群進化到一個局部最優(yōu)解；但其缺點也顯而易見，即它對個體的結構破壞的可能性很大，這樣很難有效的保存較好的模式，從而可能影響遺傳算法的性能。如果設計一個算子能夠融合這兩種算子的優(yōu)點來彌補各自的不足，那就會取得有效的改進。本系統的改進方案是，讓上一代個體通過兩種交叉方式產生四個個體，從這四個個體中選出適應度最大的那個個體作為新一代，新一代個體就產生了很明顯的進化，這樣整個種群也就產生了顯著地改進。下面通過改進程序所得到的數據來演示效果。數據請參考附錄文件，參數設定如表（4-2）種群大小交叉概率變異概率進化代數2000.80.2800表4SEQ表\*ARABIC\s12參數表實驗結果統計如表（4-3）第一次第二次第三次第四次第五次第六次第七次第八次第九次第十次平均值最好值最優(yōu)值298529692950298529502958295230013016295429753016最小生成代數46219699816330447046128524523446表4SEQ表\*ARABIC\s13改進的交叉算子所得結果統計表最好結果：代數285，最優(yōu)值3016，如圖（4-4）所示：圖4SEQ圖\*ARABIC\s14改進的交叉算子所得最優(yōu)結果圖進化曲線如圖（4-5）所示圖4SEQ圖\*ARABIC\s15改進的交叉算子所得最優(yōu)值-進化代數曲線圖下表是交叉算子改進之前的數據結果：第一次第二次第三次第四次第五次第六次第七次第八次第九次第十次平均值最好值最優(yōu)值29422961295329932935294629222942297329502951.72993最小生成代數300402563101340933745131352219.313表4SEQ表\*ARABIC\s14未改進的交叉算子所得結果統計表最好結果：代數310，最優(yōu)值2993，如圖（4-6）所示：圖4SEQ圖\*ARABIC\s16未改進的交叉算子所得最優(yōu)結果圖進化曲線如圖（4-7）所示圖4SEQ圖\*ARABIC\s17未改進的交叉算子所得最優(yōu)值-進化代數曲線圖通過以上數據及曲線可以看出，改進的交叉算子在最優(yōu)值方面比改進之前僅適用單點交叉的方式所得結果有明顯的改善。改進的變異算子：不降低適應度的變異方式簡單遺傳算法采用的變異算子是對染色體上每一個基因位以某一概率進行變異，這樣的一個缺點是變異之后的染色體適應度可能會小于變異之前的染色體適應度，結果會導致這一代群體平均適應度的降低，從而影響進化的效率。本文對變異算子的改進之處是：如果染色體變異之后其適應度降低，那么就仍然讓染色體保留變異之前的結構，否則便進行變異。實驗參數如表（4-2）所示，實驗結果統計如表（4-5）所示（本次實驗數據是在交叉算子改進的基礎上進行的）：第一次第二次第三次第四次第五次第六次第七次第八次第九次第十次平均值最好值最優(yōu)值309530973103309530943099310331033098310330993103最小生成代數1414151313121313121413.312表4SEQ表\*ARABIC\s15改進的變異算子所得結果統計表最好結果：代數14，最優(yōu)值3103，如圖（4-8）所示：圖4SEQ圖\*ARABIC\s18改進的變異算子所得最優(yōu)結果圖進化曲線如圖（4-9）所示：圖4SEQ圖\*ARABIC\s19改進的變異算子所得最優(yōu)值-進化代數曲線圖目前對背包問題，比較好的解決方法是混合遺傳算法，它處理附錄文件中的數據能夠達到的最大最優(yōu)值是3103[10]，本改進算法的最優(yōu)值的平均值為3100，基本上已經達到使用混合遺傳算法的準確度，而且本改進算法的進化速度相當快，一般可以在20代以內達到最優(yōu)值。相比于改進之前的表（4-4）中的結果，可以明顯的看出算法的改進效果。本章小結本章首先對待解決的問題進行了詳細的描述，然后闡述了一些常用的編碼技術，包括群體的設定、適應度函數、限定條件、選擇算子的設計、交叉算子的設計和變異算子的設計。最后詳細的分析了本系統對于傳統的遺傳算法在解決背包問題方面的改進之處，并用數據結果證明了改進的效果。第五章帶互動界面的遺傳算法演示系統詳細設計系統功能模塊詳細設計帶互動界面的遺傳算法演示系統的詳細設計包括從文件中讀取數據、從鍵盤輸入數據、關于演示系統、退出演示系統四個模塊的詳細設計。從文件中讀取數據用戶通過輸入已存在的有效文件名或者完整路徑來使系統達到演示效果。流程如圖5-1所示：圖5SEQ圖\*ARABIC\s11處理文件流程(2)從鍵盤輸入數據流程如圖5-2所示：圖5SEQ圖\*ARABIC\s12從鍵盤輸入數據流程參數曲線演示對于遺傳算法的種群大小、交叉概率、變異概率三個主要參數，本模塊分別做出了最優(yōu)值-種群大小曲線，最優(yōu)值-交叉概率曲線，最優(yōu)值-變異概率曲線。關于演示系統本模塊主要介紹了系統的一些基本信息，包括作者姓名，學號，專業(yè)，班級等。退出演示系統用戶通過此模塊退出演示系統。系統性能優(yōu)化設計關于本系統在數據處理方面的改進在第四章已經做了比較詳細的分析與介紹，在此不再贅述。本章小結本章在第三章、第四章的基礎上對系統進行了詳細設計。重點介紹系統功能模塊的詳細設計及其流程，緊接著對性能優(yōu)化等方面進行了設計。第六章帶互動界面的遺傳算法演示系統實現系統界面實現本系統開發(fā)語言使用Java，使用MyEclipse作為開發(fā)工具。該項目的運行環(huán)境為MicrosoftWindows7。本系統在界面設計方面使用的是Java的Swing圖形用戶界面。圖（6-1）為從文件中讀取數據模塊的演示界面：圖6SEQ圖\*ARABIC\s11從文件讀取數據模塊主界面圖6-2為從鍵盤輸入數據模塊的演示界面：圖6SEQ圖\*ARABIC\s12從鍵盤輸入數據模塊界面圖（6-3）為參數曲線演示界面：圖6SEQ圖\*ARABIC\s13參數曲線演示模塊界面圖6SEQ圖\*ARABIC\s14關于演示系統模塊界面系統功能模塊實現以從文件中輸入數據模塊為例。主界面要求用戶輸入文件名稱或者完整的文件路徑，若文件不存在或者文件數據有誤都會發(fā)出警告。如圖所示：圖6SEQ圖\*ARABIC\s15文件不存在時發(fā)出警告圖6SEQ圖\*ARABIC\s16文件數據有誤時發(fā)出警告若輸入的文件名存在并且文件數據無誤則系統顯示處理結果，如圖所示：圖6SEQ圖\*ARABIC\s17顯示處理結果可以顯示詳細的進化曲線，包括平均適應度以及最大適應度曲線，如圖所示：圖6SEQ圖\*ARABIC\s18進化曲線圖可以顯示詳細的進化數據，不過顯示的是真正進化的數據，對于那些沒有進化或者退化的數據不予顯示。如圖所示：圖6SEQ圖\*ARABIC