遺傳算法研究與應(yīng)用論文.doc

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