遺傳算法畢業(yè)論文.doc

遺遺傳算法畢業(yè)論文【摘要】遺傳算法(GeneticAlgorithm,GA)是近年來迅速發(fā)展起來的一種全新的隨機(jī)搜索與優(yōu)化算法,其基本思想基于Darwin的進(jìn)化論和Mendel的遺傳學(xué)。遺傳算法的廣泛應(yīng)用和發(fā)展?jié)撃苁购芏鄬W(xué)者深入研究遺傳算法，并出版了很多關(guān)于它的書籍。TSP問題是古老的經(jīng)典的問題，有關(guān)的研究有幾百年的時間。TSP旅行商問題是一類典型的NP完全問題，遺傳算法是解決NP問題的一種較理想的方法。論文首先介紹了遺傳算法的基本原理、遺傳算法的特點(diǎn),遺傳算法的發(fā)展方向和它的主要應(yīng)用領(lǐng)域；接著針對TSP問題論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子，交叉算子，變異算子這三種算子）等方面的應(yīng)用情況，簡單討論幾種編碼方法，并改進(jìn)了交叉算子。接著對改進(jìn)的遺傳算法做了實(shí)驗(yàn)，得出結(jié)果并分析了數(shù)據(jù)。最后我做了一個TSP簡單應(yīng)用?！娟P(guān)鍵詞】遺傳算法；TSP；遺傳算子；編碼畢業(yè)論文題目2【Abstract】GeneticAlgorithm(GeneticAlgorithm,GA)isanewrandomsearchandoptimizationalgorithm，developrapidlyinrecentyears,thebasicideaofthetheoryisDarwinandMendelsgenetics.Extensiveuseofgeneticalgorithmsanddevelopmentpotentialmakemanyscholarsin-depthstudyofgeneticalgorithms,andpublishedmanybooksaboutit.TSPproblemistheoldclassicquestionandaboutitsresearchhavehundredsofyearsoftime.TSPTravelingSalesmanProblemisakindofatypicalNP-completeproblem,geneticalgorithmstosolveNPproblemsisamoredesirablemethod.Paperfirstintroducesthecharacteristics,developmentdirectionandmajorapplicationsofbasicgeneticalgorithms,andthendiscussedfortheTSPproblemofgeneticalgorithmsandgeneticcodingthatoperator(includingtheselectionoperator,crossoveroperator,mutationoperatorofthesethreeoperator)andotheraspectsoftheapplication,makeabriefdiscussionaboutseveralcodingmethods,andimprovedcrossoveroperator.Thenuseimprovedgeneticalgorithmtodotheexperiment,gettheoutcomeandanalyzethedata.Finally,IdoasimplesuingaboutTSP.【Keywords】geneticalgorithm；TSP；geneticoperator；coding遺傳算法畢業(yè)論文3目錄第一章遺傳算法理論.41.1遺傳算法的起源.41.2遺傳算法概念.61.3遺傳算法的原理.71.3.1遺傳算法在應(yīng)用中關(guān)鍵的問題.91.3.2遺傳算法基本操作.91.4遺傳算法的特點(diǎn).101.5遺傳算法幾個主要應(yīng)用領(lǐng)域.111.6遺傳算法發(fā)展方向.13第二章遺傳算法的基本原理和實(shí)現(xiàn)技術(shù).152.1模式定理.152.2編碼技術(shù).162.2.1群體設(shè)定.162.2.2適應(yīng)度函數(shù).172.2.3遺傳操作.172.3混合遺傳算法.19第三章TSP問題描述與實(shí)算.203.1旅行商問題描述.203.2編碼選擇.213.2.1群體設(shè)定.213.2.2適應(yīng)函數(shù)度.213.2.3選擇算子的設(shè)計.213.2.4交叉算子的設(shè)計.223.2.5變異算子的設(shè)計.243.3對TSP遺傳算法的改進(jìn)：.253.3.1TSP遺傳算法參數(shù)實(shí)驗(yàn).253.3.2改進(jìn)的交叉算子：產(chǎn)生多個個體的部分映射與順序交叉結(jié)合的算子.293.4TSP算法實(shí)例.383.5附錄（求51個城市最短距離算法）.42總結(jié).54參考文獻(xiàn).55致謝.56畢業(yè)論文題目4第一章遺傳算法理論1.1遺傳算法的起源當(dāng)前科學(xué)技術(shù)正進(jìn)入多學(xué)科互相交叉、互相滲透、互相影響的時代，生命科學(xué)與工程科學(xué)的交叉、滲透和相互促進(jìn)是其中一個典型例子，也是近代科學(xué)技術(shù)發(fā)展的一個顯著特點(diǎn)。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點(diǎn)和趨勢。1967年，Holland的學(xué)生在博士論文中首次提出“遺傳算法”（GeneticAlgorithms）一詞。此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1971年，R.B.Hollstien在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。1975年Holland出版了他的著名專著自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)（AdaptationinNaturalandArtificialSystems），這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把1975年作為遺傳算法的誕生年。Holland在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論（schematheory）。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得并行性的重要性。同年，K.A.DeJong完成了他的博士論文一類遺傳自適應(yīng)系統(tǒng)的行為分析（AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem）。該論文所做的研究工作，可看作是遺傳算法發(fā)展進(jìn)程中的一個里程碑，這是因?yàn)?，他把Holland的模式理論與他的計算實(shí)驗(yàn)結(jié)合起來。盡管DeJong和Hollstien一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時又提出了諸如代溝（generationgap）等新的遺傳操作技術(shù)?？梢哉J(rèn)為，DeJong的研究工作為遺傳算法及其應(yīng)用打下了堅實(shí)的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。進(jìn)入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。1985年，在美國召開了第一屆遺傳算法國際會議（InternationalConferenceonGeneticAlgorithms，ICGA），并且成立國際遺傳算法學(xué)會（InternationalSocietyofGeneticAlgorithms，ISGA），以后每兩年舉行一次。1989年，Holland的學(xué)生D.E.Goldberg出版了專著搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法（GeneticAlgorithmsinSearch,Optimization,andMachineLearning）。該書總結(jié)了遺傳算法研究的主要成果，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。同年，美國斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計(geneticprogramming,GP)方法，成遺傳算法畢業(yè)論文5功地解決了許多問題。在歐洲，從1990年開始每隔一年舉辦一次ParallelProblemSolvingfromNature學(xué)術(shù)會議，其中遺傳算法是會議主要內(nèi)容之一。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會議還有FoundationsofGeneticAlgorithms，該會也是從1990年開始隔年召開一次。這些國際會議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動向。1991年，L.Davis編輯出版了遺傳算法手冊（HandbookofGeneticAlgorithms），其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實(shí)例。1992年，Koza發(fā)表了他的專著遺傳程序設(shè)計:基于自然選擇法則的計算機(jī)程序設(shè)計”。1994年，他又出版了遺傳程序設(shè)計，第二冊:可重用程序的自動發(fā)現(xiàn)深化了遺傳程序設(shè)計的研究，使程序設(shè)計自動化展現(xiàn)了新局面。有關(guān)遺傳算法的學(xué)術(shù)論文也不斷在ArtificialIntelligence、MachineLearning、Informationscience、ParallelComputing、GeneticProgrammingandEvoluableMachines、IEEETransactionsonNeuralNetworks、IEEETransactionsonSignalProcessing等雜志上發(fā)表。1993年，MIT出版社創(chuàng)刊了新雜志EvolutionaryComputation。1997年，IEEE又創(chuàng)刊了TransactionsonEvolutionaryComputation。AdvancedComputationalIntelligence雜志即將發(fā)刊，由模糊集合創(chuàng)始人L.A.Zadeh教授為名譽(yù)主編。目前，關(guān)于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中。遺傳算法(GeneticAlgorithm,GA)是近三十年來迅速發(fā)展起來的一種全新的隨機(jī)搜索與優(yōu)化算法,其基本思想是基于Darwin的進(jìn)化論和Mendel的遺傳學(xué)說。該算法由密執(zhí)安大學(xué)教授Holland及其學(xué)生于1975年創(chuàng)建。此后，遺傳算法的研究引起了國內(nèi)外學(xué)者的關(guān)注。自1985年以來.國際上已召開了多次遺傳算法的學(xué)術(shù)會議和研討會.國際遺傳算法學(xué)會組織召開的ICGA(InternationalConferenceonGeneticAlgorithms)會議和FOGA(WorkshoponFoundationofGeneticAlgorithms)會議。為研究和應(yīng)用遺傳算法提供了國際交流的機(jī)會。作為一種通用的問題求解方法，遺傳算法采用簡單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)并通過對一組編碼表示進(jìn)行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導(dǎo)學(xué)習(xí)和確定搜索的方向。遺傳程序設(shè)計是借鑒生物界的自然選擇和遺傳機(jī)制，在遺傳算法的基礎(chǔ)上發(fā)展起來的搜索算法，它已成為進(jìn)化計算的一個新分支。在標(biāo)準(zhǔn)的遺傳算法中，由定長字符串(問題的可行解)組成的群體借助于復(fù)制、交叉、變異等遺傳操作不斷進(jìn)化找到問題的最優(yōu)解或次優(yōu)解。遺傳程序設(shè)計運(yùn)用遺傳算法的思想，常采用樹的結(jié)構(gòu)來表示計算機(jī)程序，從而解決問題。對于許多問題，包括人工智能和機(jī)器學(xué)習(xí)上的問題都可看作是需要發(fā)現(xiàn)一個計算機(jī)程序，即對特定輸入產(chǎn)生特定輸出的程序，形式化為程序歸納，那么遺傳程序設(shè)計提供了實(shí)現(xiàn)程序歸納的方法。畢業(yè)論文題目6把遺傳算法和計算機(jī)程序結(jié)合起來的思想出現(xiàn)在遺傳算法中，Holland把產(chǎn)生式語言和遺傳算法結(jié)合起來實(shí)現(xiàn)分類系統(tǒng)，還有一些遺傳算法應(yīng)用領(lǐng)域的研究者將類似于遺傳算法的遺傳操作施加于樹結(jié)構(gòu)的程序上。近年來，遺傳程序設(shè)計運(yùn)用遺傳算法的思想自動生成計算機(jī)程序解決了許多問題，如預(yù)測、分類、符號回歸和圖像處理等，作為一種新技術(shù)，它已經(jīng)與遺傳算法并駕齊驅(qū)。1996年，舉行了第1次遺傳程序設(shè)計國際會議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣?，F(xiàn)在的基因表達(dá)式算法應(yīng)該算是遺傳算法的繼承者1.2遺傳算法概念遺傳算法和字面意思一樣，原理是關(guān)于遺傳的算法。遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的。生物的進(jìn)化是一個奇妙的優(yōu)化過程，它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由BagleyJ.D在1967年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975年，這一開創(chuàng)性工作是由Michigan大學(xué)的J.H.Holland所實(shí)行。當(dāng)時，其主要目的不是對遺傳算法系統(tǒng)研究而是說明自然和人工系統(tǒng)的自適應(yīng)過程。遺傳算法簡稱GA(GeneticAlgorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。遺傳算法在模式識別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會科學(xué)等方面都得到應(yīng)用。在人工智能研究中，現(xiàn)在人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動機(jī)、混沌理論與人工智能一樣，都是對今后十年的計算技術(shù)有重大影響的關(guān)鍵技術(shù)”。遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的。Darwin進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境。物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。在環(huán)境變化時，只有那些能適應(yīng)環(huán)境的個體特征方能保留下來。Mendel遺傳學(xué)說最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個基因產(chǎn)生的個體對環(huán)境具有某種適應(yīng)性。基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個算法中要用到各種進(jìn)化和遺傳學(xué)的概念。19遺傳算法畢業(yè)論文7這些概念如下：(1)串(String)它是個體(Individual)的形式，在算法中為二進(jìn)制串，并且對應(yīng)于遺傳學(xué)中的染色體(Chromosome)。(2)群體(Population)個體的集合稱為群體，“串”是群體的元素（3）群體大小(PopulationSize)在群體中個體的數(shù)量稱為群體的大小。（4）基因(Gen