遺傳算法研究與應用論文.doc

畢業(yè)設計（論文）畢業(yè)設計（論文） 設計論文題目：設計論文題目： 遺傳算法研究與應用遺傳算法研究與應用 學生姓名： 學生學號： 專業(yè)班級： 學院名稱： 指導老師： 學院院長： 5 月 22 日 畢業(yè)設計 (論文 ) 第 i 頁 遺傳算法研究與應用 摘要 遺傳算法（genetic algorithms, gas）是借鑒生物界自然選擇和重組機制的隨機的搜索 算法。由于它簡單易行、魯棒性強，應用范圍極為廣泛，并且已在眾多領(lǐng)域得到了實際應 用，引起了廣大學者和工程人員的關(guān)注。traveling salesman problem（tsp）問題是一個典 型np難題，是衡量近似算法效率的主要標準，因此設計tsp問題的近似算法具有非常重要 的意義。本文討論遺傳算法及其對于tsp問題的解決方法。 論文首先介紹了遺傳算法的基本概念、原理、意義及發(fā)展現(xiàn)狀。通過對遺傳算法基本 理論的學習和研究，提出了解決tsp問題的算法，并詳細給出了算法中的編碼方案、適應 度函數(shù)、選擇算子、交叉算子、變異算子。最后用c+語言設計并實現(xiàn)了該算法，結(jié)果表 明該算法可以在較短的時間內(nèi)得到tsp問題的近似最優(yōu)解。 關(guān)鍵詞關(guān)鍵詞：遺傳算法；tsp 問題；適應度函數(shù)；交叉；變異 畢業(yè)設計 (論文 ) 第 ii 頁 research and application of genetic algorithms abstract genetic algorithms (gas) are optimization search algorithms based on the mechanics of artificial selection and genetic recombination operators. they are simple, robust and easy to implement. they have been used in many fields. for these reasons now they are the hot research field which has got many scholars attention. traveling salesman problem (tsp) is a classic np problem, which is the main standard of measuring the efficiency of approximative algorithms. so the solution of the problem has has very important significance. the paper discusses the basic genetic algorithms and their application. the essay first introduces the basic concepts, principle, procedure, significance and characteristics of genetic algorithms. by learning the basic theory of genetic algorithms one solution of tsp is given. the detailed coding scheme, fitness function, selection operator, cross operator and mutation operator of the solution are also given. finally using c+ implement the solution. the result of the program show that the algorithm can get optimal solution of the problem quickly. keywords: genetic algorithms(g a); traveling salesman problem( tsp); fitness function; cross operator; mutation operator; 畢業(yè)設計 (論文 ) 第 iii 頁 目目 錄錄 1 1緒論緒論 1 1 1.1課題背景1 1.2課題研究意義2 1.3國內(nèi)外研究現(xiàn)狀3 1.4論文內(nèi)容5 2 2遺傳算法簡介遺傳算法簡介 6 6 2.1遺傳算法基本概念6 2.2遺傳算法基本原理7 2.3遺傳算法的步驟8 3 3遺傳算法基本理論遺傳算法基本理論 1111 3.1模式定理.11 3.2積木塊假設與欺騙問題.12 3.3收斂性分析.13 4 4旅行商問題概述旅行商問題概述 1414 4.1旅行商問題的定義和數(shù)學模型.14 4.1.1定義 .14 4.1.2數(shù)學模型 .14 4.2旅行商問題的計算復雜性.15 4.3研究旅行商問題的意義.16 5 5遺傳算法在巡回旅行商問題中的應用遺傳算法在巡回旅行商問題中的應用 1818 5.1旅行商問題的建模.18 5.1.1編碼 .18 5.1.2適應度函數(shù) .18 畢業(yè)設計 (論文 ) 第 iv 頁 5.2遺傳算法中三個算子的設計.19 5.2.1選擇算子的設計 .20 5.2.2交叉算子的設計 .21 5.2.3變異算子的設計 .25 5.3遺傳算法求解旅行商問題的步驟.27 5.4測試結(jié)果.27 6 6結(jié)束語結(jié)束語 2929 致致 謝謝3030 參考文獻參考文獻: :3131 畢業(yè)設計 (論文 ) 第 1 頁 1緒論 1.1 課題背景 遺傳算法（genetic algorithm，ga），是一類以達爾文的自然進化論與遺傳變異理論 為基礎(chǔ)的求解復雜全局優(yōu)化問題的仿生型算法。它借鑒生物界自然選擇和自然遺傳機制， 以概率論為基礎(chǔ)在解空間中進行隨機化搜索，最終找到問題的最優(yōu)解。 遺傳算法的興起是在80年代末90年代初期，但是它的歷史可以追溯到60年代初期。早 期的研究大多以對自然遺傳系統(tǒng)的計算機模擬為主。早期遺傳算法的研究特點是側(cè)重于對 一些復雜的操作的研究。其中像自動博弈、生物系統(tǒng)模擬、模式識別和函數(shù)優(yōu)化等給人以 深刻的印象，但總的說來，這是一個無明確目標的發(fā)展時期，缺乏帶有指導性的理論和計 算工具的開拓。這種現(xiàn)象直到70年代中期由于holland和dejong的創(chuàng)造性研究成果的發(fā)表 才得到改觀。1967年，bagley在他的論文中首次提出了遺傳算法 1這一術(shù)語，并討論了 遺傳算法在自動博弈中的應用。1970年，cavicchio把遺傳算法應用于模式識別中。第一 個把遺傳算法應用于函數(shù)優(yōu)化的是hollstien，1971年他在論文計算機控制系統(tǒng)中的人 工遺傳自適應方法中闡述了遺傳算法用于數(shù)字反饋控制的方法。1975年在遺傳算法研究 的歷史上是十分重要的一年，holland出版了他的著名專著自然系統(tǒng)和人工系統(tǒng)的適配 ，該書系統(tǒng)的闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法理論研究和發(fā)展極 為重要的模式理論（schemata theory），該理論首次確認了結(jié)構(gòu)重組遺傳操作對于獲得 隱并行性的重要性。j. holland教授和他的研究小組圍繞遺傳算法進行研究的宗旨有兩個： 一是抽取和解釋自然系統(tǒng)的自適應過程，二是設計具有自然系統(tǒng)機理的人工系統(tǒng)。同年， dejong完成了他的重要論文遺傳自適應系統(tǒng)的行為分析，他把holland的模式理論和 他的計算實驗結(jié)合起來，這可以看作遺傳算法發(fā)展過程中的一個里程碑，盡管dejong和 hollstien一樣主要側(cè)重于函數(shù)優(yōu)化的研究，但他將選擇、交叉和變異操作進一步完善和 系統(tǒng)化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術(shù)，為遺傳算法及 其應用打下了堅實的基礎(chǔ)。進入80年代，遺傳算法迎來了興盛發(fā)展時期，理論研究和應用 研究都成了十分熱門的話題。可以認為，dejong的研究工作為遺傳算法及其應用打下了堅 畢業(yè)設計 (論文 ) 第 2 頁 實的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導意義。 1.2 課題研究意義 由于遺傳算法不受搜索空間的限制性假設的約束, 因此不必要求諸如連續(xù)性、導數(shù)存 在和單峰等條件， 同時遺傳算法還具有以下特點： 1、遺傳算法是利用決策變量集的某種編碼進行運算，而不是直接作用在決策變量集上， 通用性強。 2、遺傳算法能同時使用多個搜索點的搜索信息。傳統(tǒng)的優(yōu)化算法往往是從解空間中的 一個初始解開始最優(yōu)解的迭代搜索過程。而遺傳算法從一個解的種群開始搜索，而不是從 單個解開始，就像在解空間撒網(wǎng)一樣，可以對不同區(qū)域采樣，并不斷交換信息。這使得它 減少了陷入局部優(yōu)解的風險，能以較大概率找到全局最優(yōu)解。 3、遺傳算法在尋優(yōu)過程中僅利用解的適應度函數(shù)信息作為尋優(yōu)的依據(jù)。它對目標函 數(shù)幾乎無要求，也不涉及映射空間或函數(shù)的連續(xù)性，僅使用由目標函數(shù)值變換來的適應度 函數(shù)值，就可確定進一步的搜索方向和搜索范圍。而傳統(tǒng)搜索算法不僅要利用目標函數(shù)值， 而且往往需要目標函數(shù)的導數(shù)值等其他一些輔助信息才能確定搜索方向。 4、遺傳算法使用概率搜索技術(shù)，以一種概率的方式來進行搜索，從而增加了其搜索 過程的靈活性。而很多傳統(tǒng)的優(yōu)化算法使用的是確定性的搜索方法，這種確定性往往可能 使得搜索永遠達不到最優(yōu)點，因而也限制了算法的應用范圍。 5、遺傳算法具有本質(zhì)并行性，包括內(nèi)在并行性和隱并行性。內(nèi)在并行性說明遺傳算 法非常適合大規(guī)模并行運算，而隱并行性使得遺傳算法能以較少的計算獲得較大的收益。 遺傳算法的這些特點使得它比傳統(tǒng)搜索方法具有更大的優(yōu)越性，適用范圍更廣并且能 夠應用于一些到目前為止人們知之甚少的困難問題領(lǐng)域。遺傳算法提供了一種求解復雜、 困難優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，不要求目標函數(shù)有明確的解析表 達，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面是遺傳算法的一些主 要應用領(lǐng)域6 7： 函數(shù)優(yōu)化問題。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領(lǐng)域，也是對遺傳算法進行性能評價 畢業(yè)設計 (論文 ) 第 3 頁 的常用算例。很多人構(gòu)造出了各種各樣的復雜形式的測試函數(shù)來評價遺傳算法的性能。而 且對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳 算法卻可以方便地得到較好的結(jié)果。 組合優(yōu)化問題。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在 目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復雜問題，人們已 意識到應把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。 實踐證明，遺傳算法對于求解組合優(yōu)化問題非常有效。遺傳算法已經(jīng)在求解旅行商問題、 圖形劃分問題等方面得到成功的應用。 生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即 使經(jīng)過一些簡化之后可以求解，也會因簡化太多而使求解結(jié)果與實際相差甚遠。由于可以 采用字符編碼，而且不必使用恰好的目標函數(shù)估值，遺傳算法也成為解決復雜調(diào)度問題的 有效工具。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務分配、虛擬企業(yè) 中的伙伴選擇方面遺傳算法都得到了有效的應用。 自動控制。在自動控制領(lǐng)域有很多與優(yōu)化相關(guān)的問題需要求解，而且這些優(yōu)化問題通 常要么是通過積分表達的，要么是寫不出明確而嚴格的解析表達式。遺傳算法在求解這類 自動控制問題方面已顯示出其獨特的優(yōu)點。例如，用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、 用遺傳算法優(yōu)化設計透平機械、設計模糊控制器等，都取得了較好的效果。 機器學習。學習能力是高級自適應系統(tǒng)所應具備的特征之一。基于遺傳算法的機器學 習在很多方面都得到成功應用。例如，遺傳算法被用于學習模糊控制規(guī)則、確定模糊集的 隸屬函數(shù)、改進模糊系統(tǒng)的性能；被用來調(diào)整人工神經(jīng)網(wǎng)絡的連接權(quán)及網(wǎng)絡拓撲優(yōu)化。 此外，遺傳算法還被應用到反問題求解、機器人學習、生物計算、圖像處理、人工生 命以及遺傳編程等領(lǐng)域。 1.3 國內(nèi)外研究現(xiàn)狀 進入 90 年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了 十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍，不但它的應用領(lǐng)域擴大，而 且利用遺傳算法進行優(yōu)化和規(guī)則學習的能力也顯著提高，同時產(chǎn)業(yè)應用方面的研究也在摸 畢業(yè)設計 (論文 ) 第 4 頁 索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳 算法增添了新的活力。遺傳算法的應用研究已從初期的組合優(yōu)化求解擴展到了許多更新、 更工程化的應用方面。 隨著應用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺傳 算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴 展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法。這一新的學習機制對于解決人工智 能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡、 模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓 21 世紀中新的智 能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅 對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結(jié)構(gòu)的研究都是十分重要的。四 是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算 機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的 重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃 （evolution programming ,ep）以及進化策略（evolution strategy ,es）等進化計算理論日 益結(jié)合。ep 和 es 幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是 模擬自然界生物進化機制的只能計算方法，即同遺傳算法具有相同之處，也有各自的特點。 目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點。 1991 年 d.whitey 在他的論文中提出了基于領(lǐng)域交叉的交叉算子（adjacency based crossover） ，這個算子是特別針對用序號表示基因的個體的交叉，并將其應用到了 tsp 問 題中，通過實驗對其進行了驗證。d.h.ackley 等提出了隨即迭代遺傳爬山法（stochastic iterated genetic hill-climbing，sigh）采用了一種復雜的概率選舉機制，此機制中由 m 個 “投票者”來共同決定新個體的值（m 表示群體的大小） 。實驗結(jié)果表明，sigh 與單點交叉、 均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體 來講，sigh 比現(xiàn)存的許多算法在求解速度方面更有競爭力。h.bersini 和 g.seront 將遺傳 算法與單一方法（simplex method）結(jié)合起來，形成了一種叫單一操作的多親交叉算子 （simplex crossover） ，該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個體，事實上他 的交叉結(jié)果與對三個個體用選舉交叉產(chǎn)生的結(jié)果一致。同時，文獻還將三者交叉算子與點 畢業(yè)設計 (論文 ) 第 5 頁 交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個有更好的性能。 國內(nèi)也有不少的專家和學者對遺傳算法的交叉算子進行改進。2002 年，戴曉明等應 用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變 異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經(jīng)典遺傳 算法的收斂到局部最優(yōu)值問題 2004 年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化 問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（building-block coded parallel ga，bcpga） 。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體 中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較 短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。2005 年，江雷等針對并行遺傳算法求解 tsp 問題,探討了使用彈性策略來維持群體的多樣性,使 得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進化。 1.4 論文內(nèi)容 本文內(nèi)容安排如下： 第一章：緒論。介紹本課題的選題背景和研究現(xiàn)狀以及文章結(jié)構(gòu)。 第二章：簡要介紹了遺傳算法的基本概念、原理、實現(xiàn)步驟。 第三章：敘述了遺傳算法的主要理論：模式定理、積木塊假設，以及遺傳算法的收斂 性的簡單說明。 第四章：就在旅行推銷商問題做了簡要介紹，并對旅行推銷商問題的數(shù)學模型，計算 的復雜度和求解該問題的意義進行簡單概要。 第五章：提出了遺傳算法求解旅行商問題的一種方式，并詳細給出了算法中的編碼方 案、適應度函數(shù)、選擇算子、交叉算子、變異算子及部分源碼。 第六章：結(jié)束語。 文章的最后是參考致謝和參考文獻。 畢業(yè)設計 (論文 ) 第 6 頁 2遺傳算法簡介 2.1 遺傳算法基本概念 遺傳算法的基本思想是基于darwin進化論和mendel的遺傳學說的。 darwin進化論最重要的是適者生存原理。它認為每一物種在發(fā)展中越來越適應環(huán)境。 物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。在環(huán)境 變化時，只有那些能適應環(huán)境的個體特征才能保留下來。 mendel遺傳學說最重要的是基因遺傳原理。它認為遺傳以密碼方式存在細胞中，并以 基因形式包含在染色體內(nèi)。每個基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個基因 產(chǎn)生的個體對環(huán)境具有某種適應性?；蛲蛔兒突螂s交可產(chǎn)生更適應于環(huán)境的后代。經(jīng) 過存優(yōu)去劣的自然淘汰，適應性高的基因結(jié)構(gòu)得以保存下來。 由于遺傳算法是由進化論和遺傳學機理產(chǎn)生的直接搜索優(yōu)化方法，所以在這個算法中 要用到各種進化和遺傳學的概念。這些概念如下： 1.串 它是個體的形式，在算法中為二進制串，并且對應于遺傳學中的染色體。 2.種群 個體的集合稱為群體，串是種群中的元素 3.種群大小 在種群中個體的數(shù)量稱為種群的大小。 4.基因 基因是串中的元素，基因用于表示個體的特征。例如有一個串s1011，則其中的 1011這4個元素分別稱為基因。 5.基因位置 一個基因在串中的位置稱為基因位置，有時也簡稱基因位。基因位置在串中由左向右 計算，例如在串s1101中，0的基因位置是3。基因位置對應于遺傳學中的地點。 畢業(yè)設計 (論文 ) 第 7 頁 6.基因特征值 在用串表示整數(shù)時，基因的特征值與二進制數(shù)的權(quán)一致；例如在串s=1011中，基因位 置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。 7.串結(jié)構(gòu)空間 在串中，基因任意組合所構(gòu)成的串的集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進行的。串結(jié)構(gòu) 空間對應于遺傳學中的基因型的集合。 8.參數(shù)空間 s p 這是串空間在物理系統(tǒng)中的映射，它對應于遺傳學中的表現(xiàn)型的集合。 九、適應度 表示某一個體對于環(huán)境的適應程度。 遺傳算法還有一些其它的概念，這些概念在介紹遺傳算法的原理和執(zhí)行過程時，再進 行說明。 2.2 遺傳算法基本原理 遺傳算法ga把問題的解表示成“染色體”，在算法中也就是二進制編碼的串。并且， 在執(zhí)行遺傳算法之前，給出一群“染色體”，也就是假設解。然后，把這些假設解置于問 題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應環(huán)境的“染色體”進行復制， 再通過交叉，變異過程產(chǎn)生更適應環(huán)境的新一代“染色體”群。這樣，一代一代的進化， 最后就會收斂到最適應環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。很明顯，遺傳算 法是一種最優(yōu)化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產(chǎn)生新的 解，最后收斂到一個特定的串bi處，即求出最優(yōu)解。 長度為l的n個二進制串bi(i1，2，n)組成了遺傳算法的初始解群，也稱為初始 群體。在每個串中，每個二進制位就是個體染色體的基因。根據(jù)進化術(shù)語，對群體執(zhí)行的 操作有三種： 1選擇 這是從群體中選擇出較適應環(huán)境的個體。這些選中的個體用于繁殖下一代。故有時也 稱這一操作為再生。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應度來 畢業(yè)設計 (論文 ) 第 8 頁 決定其繁殖量的，故而有時也稱為非均勻再生。 2交叉 這是在選中用于繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換， 從而產(chǎn)生新的個體。交叉算子示意如圖1.1。 圖1.1 交叉算子示意圖 3變異 這是在選中的個體中，對個體中的某些基因按變異概率 p 執(zhí)行異向轉(zhuǎn)化。在串 bi中， 如果某位基因為 1，產(chǎn)生變異時就是把它變成 0；反之亦然。 2.3 遺傳算法的步驟 1初始化 選擇一個群體，即選擇一個串或個體的集合bi，i=1，2，.n。這個初始的群體也就 是問題假設解的集合。一般取n30-160。 通常以隨機方法產(chǎn)生串或個體的集合bi,i1，2，.n。問題的最優(yōu)解將通過這些初 始假設解進化而求出。 畢業(yè)設計 (論文 ) 第 9 頁 2選擇 根據(jù)適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則。適應度準則 體現(xiàn)了適者生存，不適應者淘汰的自然法則。 給出目標函數(shù)f，則f(bi)稱為個體bi的適應度。以公式（1-1） p選中bi (1-1) n )( )( 1 n j bjf bif 為選中bi為下一代個體的次數(shù)。 顯然。從上式可知： (1)適應度較高的個體，繁殖下一代的數(shù)目較多。 (2)適應度較小的個體，繁殖下一代的數(shù)目較少，甚至被淘汰。 這樣，就產(chǎn)生了對環(huán)境適應能力較強的后代。從問題求解角度來講，就是選擇出和最 優(yōu)解較接近的中間解。 3交叉 對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率p。 在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基因組合，也 即產(chǎn)生新的個體。交叉時，可實行單點交叉或多點交叉。 例如有個體 s1=100101 s2=010111 選擇它們的左邊3位進行交叉操作，則有 s1=010101 s2=100111 一般而言，交叉概率p。取值為0.250.75。 4變異 根據(jù)生物遺傳中基因變異的原理，以變異概率pm對某些個體的某些位執(zhí)行變異。在變 畢業(yè)設計 (論文 ) 第 10 頁 異時，對執(zhí)行變異的串的對應位求反，即把1變?yōu)?，把0變?yōu)?。變異概率pm與生物變異極 小的情況一致，所以，pm的取值較小，一般取0.01-0.2。 例如有個體s101011。 對其的第1，4位置的基因進行變異，則有 s=001111 單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進化的單一 群體。因為當所有的個體一樣時，交叉是無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的 個體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。 5全局最優(yōu)收斂 當最優(yōu)個體的適應度達到給定的閥值，或者最優(yōu)個體的適應度和群體適應度不再上升 時，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代 群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。 圖1.2中表示了遺傳算法的執(zhí)行過程 圖1.2 遺傳算法原理 畢業(yè)設計 (論文 ) 第 11 頁 3遺傳算法基本理論 3.1 模式定理 模式定理是由holland 在1971 年提出的，它是ga 的基本定理。它將ga的運算過程 理解為模式運算過程，并從模式運算的角度解釋ga 的性能特點。模式是描述字符串集的 模板，反映字符串集中串的某些位置上存在的相似性。在本節(jié)的敘述中，僅就二進制編碼 的情況進行討論。 【定義2.1】基于三值字符集0,1,*所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1 字符 串集的字符串稱作模式。 例如，模式s = 01*0*描述了所有在位置1 和位置4 上為0，在位置2 上為1的字符串， 該模式描述的字符串集合為01000，01001，01100，01101。 也就是：s = 01*0* = 01000，01001，01100，01101 事實上，模式的概念使得我們可以簡明地描述具有相似結(jié)構(gòu)特點的個體編碼字符串。 在引入模式的概念后，遺傳算法的本質(zhì)就是對模式所進行的一系列運算，遺傳運算過 程中的個體通過模式聯(lián)系起來。通過這些遺傳運算，一些比較差的模式逐漸被淘汰，而一 些較好的模式逐步被遺傳和進化。 在進行遺傳算法的理論分析時，往往需要定量地估計模式運算。因此，有必要引入以 下兩個概念：模式階和模式定義距。 【定義2.2】模式h 中確定位置的個數(shù)稱為模式的模式階(schemata order)，記作o(h)。 模式h 中第一個確定位置和最后一個確定位置之間的距離稱為模式的定義距(schemata defining length)，記作(h)。 根據(jù)定義2.2，o(101*0) = 4，(101*0) = 4；o(0*1*) = 2，(0*1*) = 3。而對于h = *1、h = *0*之類的模式，由于他們只有一個確定位置，所以我們規(guī)定它們的定義 距為0，如(*0*) = 0。 當字符串的長度確定時，模式的階數(shù)越高，與該模式相匹配的樣本數(shù)目就越少，該模 式的確定性也就越高。而模式的定義距越大，則在遺傳運算中，該模式被遺傳運算破壞的 畢業(yè)設計 (論文 ) 第 12 頁 概率越大，生存概率越小。 【定理2.1】模式定理在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以 及平均適應度高于種群平均適應度的模式在子代中將得以指數(shù)級增長。 模式定理可以用數(shù)學形式表示為： （21）)()1/()()/ )(),() 1,( mc pholhpfhfthmthm 其中，h 表示一個模式，m(h,t) 表示在第t 代種群中存在的模式h 中串的個數(shù)。f (h) 表示在第t 代種群中模式h 串的平均適應度，表示第t 代種群的平均適應度，l 表示串f 的長度, p是串之間發(fā)生交叉的概率，p是一個串發(fā)生變異的概率，(h) 表示模式h 的 cm 定義距, o(h) 表示模式h 的階。 模式定理保證了遺傳優(yōu)化過程中較優(yōu)解的樣本呈指數(shù)級增長，在一定意義上可以解釋 基本遺傳算法的優(yōu)化本質(zhì)，同時也給遺傳算法的應用提供了指導作用。 3.2 積木塊假設與欺騙問題 模式定理說明，低階、短定義距、平均適應度高的模式被交叉切斷的可能性低，隨著 世代交替其數(shù)量將增加。這種類型的模式稱為積木塊。 【定義2.3】具有低階、短定義距以及高適應度的模式稱作積木塊。 【假設2.1】積木塊假設積木塊在遺傳算子的作用下相互結(jié)合，能生成高階、長定義距、 高平均適應度的模式，并最終生成全局最優(yōu)解。 模式定理說明了積木塊的樣本數(shù)呈指數(shù)級增長，亦即說明了用遺傳算法尋求最優(yōu)樣本 的可能性；而積木塊假設說明了用遺傳算法求解各種問題的基本思想，即通過積木塊之間 的相互拼接能夠產(chǎn)生出問題更好的解，表明遺傳算法具有全局尋優(yōu)能力，能夠?qū)で蟮阶顑?yōu) 樣本。到目前為止，上述假設并未得到完整而嚴密的數(shù)學證明，但大量的實踐對這一假設 提供了強有力的支持。 如果一個問題的編碼滿足積木塊假設，那么用遺傳算法求解的效率較高，否則用遺傳 算法求解的效率較低。應用實踐表明，存在一類用遺傳算法難以求解的問題，稱為“ga- 難”問題。屬于“ga-難”的問題一般包括有孤立的最優(yōu)點，在搜索過程中，低階積木塊錯誤 地引導搜索過程，不能發(fā)現(xiàn)高階積木塊，通過欺騙遺傳算法，使其進化過程偏離最優(yōu)解， 畢業(yè)設計 (論文 ) 第 13 頁 最終使遺傳算法發(fā)散，這種現(xiàn)象稱為欺騙。實際上，目前尚未沒有解決這類問題的較好的 方法，也無法判斷一個問題包含欺騙的多少與問題相對于遺傳算法的難易程度。不過，現(xiàn) 實中遇到的各種應用問題中，遺傳算法大部分是適用的。 3.3 收斂性分析 模式定理雖然指出了具有優(yōu)良結(jié)構(gòu)的模式在算法的進化過程中的演變趨勢，但是，它 并未回答了遺傳算法最終收斂于最優(yōu)解的概率為多少。積木塊假設雖然指明了遺傳算法能 夠收斂于全局最優(yōu)解，但是僅僅是通過大量的應用數(shù)據(jù)來證明其有效性，還沒有完整而嚴 密的數(shù)學證明。利用馬爾可夫鏈對遺傳算法的分析嚴格論證了遺傳算法收斂性方面的一些 重要性質(zhì)，有力地支撐了遺傳算法的理論基礎(chǔ)。下面是由馬爾可夫鏈推導出來的一些結(jié)論， 具體證明可以參考文獻8。 【定理2.3】基本遺傳算法收斂于最優(yōu)解的概率小于1。 【定理2.4】使用保留最佳個體策略的遺傳算法夠收斂于最優(yōu)解的概率為1。 通過上述定理可以看出，基本遺傳算法收斂于最優(yōu)解的概率小于1，而通過對基本遺 傳算法進行改進，修正它的選擇策略，就能使算法一定收斂于最優(yōu)解。這兩個定理不僅在 理論上是模式定理和積木塊假設的有力補充，更為實際的應用中的算法收斂提供了保證。 畢業(yè)設計 (論文 ) 第 14 頁 4旅行商問題概述 4.1 旅行商問題的定義和數(shù)學模型 4.1.1定義 旅行商問題是組合數(shù)學中一個古老而又困難的問題，它易于描述但至今尚未徹底解決， 現(xiàn)己歸入所謂的 np 完全問題類，經(jīng)典提法為: 有一貨物推銷員要去若干個城市推銷貨物，從城市1出發(fā)，經(jīng)其余各城市一次，然后 回到城市1，問選擇怎樣的行走路線，才能使總行程最短(各城市間距離為己知)。 該問題在圖論的意義下就是所謂的最小hamilton圈問題，由于在許多領(lǐng)域中都有著廣 泛的應用，因而尋找其實際而有效的算法就顯得頗為重要了。遺憾的是，計算復雜性理論 給予我們的結(jié)論卻是，這種可能性尚屬未知。 若設城市數(shù)目為n時，那么組合路徑數(shù)則為(n-1)!。很顯然，當城市數(shù)目不多時要找 到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級數(shù)規(guī)律急 劇增長，以至達到無法計算的地步，這就是所謂的“組合爆炸問題”。假設現(xiàn)在城市的數(shù) 目增為20個，組合路徑數(shù)則為(20-1)!，如此龐大的組合數(shù)目，若計算機以每秒檢索1000 萬條路線的速度計算，也需要花上386年的時間。 盡管現(xiàn)在計算機的計算速度大大提高，而且己有一些指數(shù)級的算法可精確地求解旅行 商問題，但隨著它們在大規(guī)模問題上的組合爆炸，人們退而求其次，轉(zhuǎn)向?qū)ふ医扑惴ɑ?啟發(fā)式算法，經(jīng)過幾十年的努力，取得了一定的進展。 4.1.2數(shù)學模型 設g=(v, e)為賦權(quán)圖，v=l ,2,. n為頂點集，e為邊集，各頂點間距離為c。 ij 已知(c 0, c=,i,j v )，并設 ijij x = （31） ij ，其它 ）在最優(yōu)路線上，邊（ 0 ji1 畢業(yè)設計 (論文 ) 第 15 頁 則旅行商問題的數(shù)學模型可寫成如下的線性規(guī)劃形式： minz ji ij c xij s.ts.t vjix vkkx vjx vix ij sji ij ji ij ij ji ,1 , 0 , 1 , 1 , 1 , 這里，k 為 v 的所有非空子集，為集合 k 中所含圖 g 的頂點個數(shù)。前兩個約束意味k 著對每個頂點而言，僅有一條邊進出，后一約束則保證了沒有任何子回路解的產(chǎn)生。于是， 滿足上述約束的解構(gòu)成了一條 hamilton 回路。除此之外，模型還有其它一些等價的書寫 形式。 4.2 旅行商問題的計算復雜性 一般的，我們定義一個組合優(yōu)化問題: 設，其中s為一個有限集，f為映射函數(shù)，對每個產(chǎn)生唯一的實數(shù)f(x)，rsf:sx 則最大(小)化問題即找一個，使得對于任何其它有。sx sx)()()( xfxf 此組合優(yōu)化問題的一個基本算法是:對于每個，求f(x)的值，挑選，使對于所sx x 有的，。sx )()()( xfxf 這就是窮舉搜索法，它在理論上可以解決任何有限的組合最優(yōu)化問題。 但對于n個城市的tsp，可能的回路數(shù)有條，計算每一條路徑需求n個距離之和， 2 )!1( n 故計算量將正比于。表41顯示了運算速度億次/秒的crayxt3巨型計算機按窮舉搜 2 ! n 5 10 索法計算tsp所需的時間，這里還未考慮算法所需的巨大存貯空間。由此足見tsp時空復雜 度之高。 畢業(yè)設計 (論文 ) 第 16 頁 表 4.1 4.3 研究旅行商問題的意義 旅行商問題是一個np完全問題，目前任何np完全問題都不能用任何已知的多項式算法 求解；若任何一個np完全問題有多項式算法，則一切np完全問題都有多項式算法。 由此，不少人猜測任何np完全問題都沒有多項式算法，但至今無人證明。事實上，人 們普遍認為，不發(fā)展全新的數(shù)學技術(shù)就證明不了這個猜想。這樣一種認識的實際意義就在 于許多人相信，難計算是這樣一類問題的固有性質(zhì)，因此它們不可能用有效算法求解，而 所有能精確求解np完全問題的算法，在最壞情況下都需要指數(shù)級的時間。 另外，旅行商問題是一個理想化的問題，大多數(shù)對于此問題的研究都不是為了直接的 實際應用，但這些研究可以經(jīng)轉(zhuǎn)化后用于許多現(xiàn)實的組合優(yōu)化問題。很自然地可以想到， 旅行商問題的成果可以應用于運輸和物流問題。旅行商問題最早的應用是在上個世紀的四 十年代，應用于校車路線的優(yōu)化。現(xiàn)在，旅行商問題在越來越多的領(lǐng)域得到應用。 1電路板鉆孔進度的安排。在這個應用當中，電路板上的孔代表旅行商問題中的城 市，鉆頭從一個鉆孔移動到另一個鉆孔。尋找最短路徑變成了尋找最省時的鉆頭移動時間。 盡管目前鉆機的工藝技術(shù)發(fā)展很塊，但鉆頭的移動時間仍然是一個令人頭疼的問題。 2基因測序。concorde是一種求解旅行商問題的程序。美國國家衛(wèi)生機構(gòu)的研究人 員利用這一程序來進行基因測序。在這一應用中，局部的基區(qū)圖譜作為城市，城市與城市 的距離代表某張圖譜與其它圖譜相連的可能性。研究人員試圖尋找一種可能性最高的連接 城市數(shù)n 回路數(shù) 2 )!1( n 加法量 2 ! n搜索時間 51260 秒 12 106 10 5 108144 . 1 6 108144. 1秒 7 108144 . 1 20 16 1008 . 6 18 1022 . 1 秒 5 1022 . 1 40 46 1002 . 1 47 1008 . 4 年 27 1032 . 1 100 155 106 . 4 157 106 . 4年 136 1048 . 1 200 371 100 . 5 374 100 . 1年 356 1022 . 3 畢業(yè)設計 (論文 ) 第 17 頁 方式把這些局部的圖譜合成為整張基因圖譜。 3半導體的線路設計。一家半導體生產(chǎn)廠家應用concorde程序來優(yōu)化半導體的線路 設計，這樣可以節(jié)省刻制半導體的時間，也能減少半導體電路消耗的能量。 4光纜的線路設計。貝爾電話公司利用concorde程序來設計光纜的鋪設線路，同樣 的方法也應用于電話和電力線路的鋪設當中。 5在機器人控制等其它方面，旅行商問題也有許多應用。 畢業(yè)設計 (論文 ) 第 18 頁 5遺傳算法在巡回旅行商問題中的應用 5.1 旅行商問題的建模 5.1.1編碼 在遺傳算法中，染色體通常采用簡單的二進制串編碼，但這種簡單的編碼方式不能較 好的適用于tsp和其它組合優(yōu)化問題。tsp常用的編碼表達方式主要有鄰接表達、矩陣表達、 邊表達、隨機鍵表達和序表達等。其中，序表達和隨機鍵表達不僅適用于tsp，也適用于 其它組合優(yōu)化問題。 本文使用序表達形式。序表達是tsp問題的最自然的表達，其中城市是按訪問的順序 排列的。例如，對于9個城市的tsp:325471698可簡單表示為向量3 2 5 4 7 1 6 9 8，表示從城市3出發(fā)依次經(jīng)過城市2，5，4，7，1，6，9，8然后返回城市3的 一條路徑。序表達方式滿足完全無向圖tsp問題的約束條件。保證了每個城市經(jīng)過且只經(jīng) 過一次，并且保證在任何一個城市子集中不形成回路. 5.1.2適應度函數(shù) 適應度是生物學家在研究自然界中生物的遺傳與進化現(xiàn)象時用以度量某個物種對其生 存環(huán)境的適應程度。在遺傳算法中適應度用來度量個體作為全局最優(yōu)解的可接受程度，它 是模擬進化算法評價和選擇個體的度量依據(jù)。適應度的取值與適應度函數(shù)成正比。適應度 函數(shù)的確定通常反映應用者對個體的評價標準和搜索機理。 適應度函數(shù)是遺傳進化操作的基礎(chǔ)，它的構(gòu)造是遺傳算法的關(guān)鍵。合理的適應度函數(shù) 能引導搜索朝最優(yōu)化方向進行。本文構(gòu)造基于序的適應度函數(shù)。它的特點是個體被選擇的 概率與目標函數(shù)的具體值無關(guān)。將種群中的所有個體按其目標函數(shù)值的大小降序排列，設 參數(shù)，定義基于序的適應度函數(shù)) 1 , 0( e i1，2，3，p （32） 1 )1 ()( i ival x size 式中：x種群排序后第i個個體； i 畢業(yè)設計 (論文 ) 第 19 頁 p種群中個體總數(shù)。 size 程序源碼： void createfitnessofpop( ) std:vector:iterator iter_router; double alpha = eval_base; std:vector vecsort; for( iter_router=vecpop.begin();iter_router!=vecpop.end();iter_router+ ) vecsort.push_back( iter_router-m_ftotaldistance ); iter_router-m_ffitness = -100.0; std:sort( vecsort.begin(), vecsort.end() ); std:vector:iterator iter_sort; int nindex = 0; for( iter_sort=vecsort.begin();iter_sort!=vecsort.end();iter_sort+ ) for( iter_router=vecpop.begin(); iter_router!=vecpop.end();iter_router+ ) if( fabs(iter_router-m_ftotaldistance-(*iter_sort) m_ffitness m_ffitness = alpha*pow(1-alpha,(double)nindex); nindex+; 5.2 遺傳算法中三個算子的設計 畢業(yè)設計 (論文 ) 第 20 頁 5.2.1選擇算子的設計 按照某種選擇策略從群體中選擇出若干個體進入交配池。交配池中的個體通過遺傳算 子的作用產(chǎn)生新一代群體。選擇策略應遵守的基本原則是:適應度值越大的個體被選中的 概率應該越大。即選擇策略應遵循自然界“優(yōu)勝劣汰、適者生存”的自然選擇規(guī)律。從群 體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫選擇。選擇算子有時又稱為再生算子。選擇 的目的是把優(yōu)化的個體(或解)直接遺傳到下一代或通過交叉產(chǎn)生新的個體再遺傳到下一代。 選擇操作是建立在群體中個體的適應度評估基礎(chǔ)上的。在遺傳算法中，目前常用的選擇機 制有以下幾種:適應度比例方法、最佳個體保存方法、期望值方法、排序選擇機制、聯(lián)賽 選擇機制。 本文適應度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或 蒙特卡羅(monte carlo)選擇。在該方法中，各個個體的選擇概率和其適應度值成比例。 程序源碼如下： void selectpop()/群體競爭 輪盤賭選擇 std:vector vecroll; std:vector vecselpop; int nrollnumber, nrollrange; int npopsize = vecpop.size(); int i, j; for( i=0;i ncrossoverbegin ) break; else if( ncrossoverend ncrossoverbegin ) std:swap( ncrossoverbegin, ncrossoverend ); 畢業(yè)設計 (論文 ) 第 23 頁 break; for( int i=ncrossoverbegin;i=ncrossoverend;i+ ) sona.push_back( vecpopnfathera.m_cityrouteri ); sonb.push_back( vecpopnfatherb.m_cityrouteri ); std:vector:iterator iter_father, iter_son; bool hascity = false; int naddbegin = 0; for( iter_father=vecpopnfatherb.m_cityrouter.begin(); iter_father!=vecpopnfatherb.m_cityrouter.end(); iter_father+ ) hascity = false; for( iter_son=sona.begin();iter_son!=sona.end();iter_son+ ) if( *iter_son = *iter_father ) hascity = true; break; if( !hascity ) if( naddbegin ncrossoverbegin ) sona.insert( sona.begin()+naddbegin, *iter_father ); naddbegin+; 畢業(yè)設計 (論文 ) 第 24 頁 else sona.push_back( *iter_father ); naddbegin = 0; for( iter_father=vecpopnfathera.m_cityro