帶互動界面的遺傳算法演示系統(tǒng)

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