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

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