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

畢業(yè)設(shè)計(jì)（論文） 5 月 22 日設(shè)計(jì)論文題目： 遺傳算法研究與應(yīng)用 學(xué)生姓名： 學(xué)生學(xué)號(hào)： 專業(yè)班級(jí)： 學(xué)院名稱： 指導(dǎo)老師： 學(xué)院院長(zhǎng)： 畢業(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)鍵詞 ： 遺傳 算法 ； 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.2 課題研究意義 . 2 1.3 國(guó)內(nèi)外研究現(xiàn)狀 . 3 1.4 論文內(nèi)容 . 5 2 遺傳算法簡(jiǎn)介 . 6 2.1 遺傳算法基本概念 . 6 2.2 遺傳算法基本原理 . 7 2.3 遺傳算法的步驟 . 8 3 遺傳算法基本理論 . 11 3.1 模式定理 . 11 3.2 積木塊假設(shè)與欺騙問(wèn)題 . 12 3.3 收斂性分析 . 13 4 旅行商問(wèn)題概述 . 14 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 遺傳算法在巡回旅行商問(wèn)題中的應(yīng)用 . 18 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 結(jié)束語(yǔ) . 29 致 謝 . 30 參考文獻(xiàn) : . 31 畢業(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) 的 適配 ， 該 書 系統(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)用研究 都 成了 十 分熱門 的 話題 。 可以認(rèn)為， DeJong的研究工作為遺傳算法及其應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)，他所 畢業(yè)設(shè)計(jì) (論文 ) 第 2 頁(yè) 得出的許多結(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á)的， 要么是寫不出明確而嚴(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è) 串 S 1011， 則 其中的 1011這 4個(gè) 元素 分別 稱 為基 因 。 5.基 因 位 置 一個(gè)基 因 在 串 中的位 置稱 為基 因 位 置 ，有時(shí)也簡(jiǎn) 稱 基 因 位。基 因 位 置 在 串 中 由 左向右計(jì)算， 例如 在 串 S 1101中， 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ù)空 間 sp這 是 串 空 間在 物 理 系統(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(i 1， 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中，如 果 某 位基 因 為 1，產(chǎn)生 變異 時(shí) 就 是 把 它 變 成 0； 反之亦然 。 2.3 遺傳算法的步驟 1 初 始 化 選擇 一個(gè) 群體 ，即 選擇 一個(gè) 串 或個(gè) 體 的 集 合 bi， i=1， 2， .n。 這 個(gè) 初 始 的 群體 也 就 是問(wèn)題 假 設(shè) 解的 集 合。一 般 取 n 30-160。 通 常 以 隨 機(jī) 方 法產(chǎn)生 串 或個(gè) 體 的 集 合 bi,i 1， 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選 中 bin)()(1njbjfbif (1-1) 為 選 中 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.25 0.75。 4 變異 根據(jù) 生 物 遺傳中基 因 變異 的原理，以 變異 概 率 Pm對(duì) 某 些 個(gè) 體 的 某 些 位 執(zhí) 行 變異 。在 變 畢業(yè)設(shè)計(jì) (論文 ) 第 10 頁(yè) 異 時(shí)，對(duì) 執(zhí) 行 變異 的 串 的對(duì)應(yīng)位 求反 ，即 把 1變 為 0， 把 0變 為 1。 變異 概 率 Pm與生 物變異極小 的 情況 一致，所以， Pm的取 值較小 ，一 般 取 0.01-0.2。 例如 有個(gè) 體 S 101011。 對(duì)其的第 1， 4位 置 的基 因 進(jìn)行 變異 ， 則 有 S=001111 單 靠 變異 不 能 在 求 解中得 到好 處。 但 是，它 能 保證算法過(guò) 程 不 會(huì) 產(chǎn)生 無(wú) 法進(jì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é)形式表示為： )()1/()()/)(),()1,( mc pHolHpfHftHmtHm （ 2 1） 其中， H 表示一個(gè)模式， m(H,t) 表示在第 t 代種群中存在的模式 H 中串的個(gè)數(shù)。 f (H) 表示在第 t 代種群中模式 H 串的平均適應(yīng)度， f 表示第 t 代種群的平均適應(yīng)度， l 表示串的長(zhǎng)度 , pc是串之間發(fā)生交叉的概率， pm是一個(gè)串發(fā)生變異的概率， (H) 表示模式 H 的定義距 , 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ū)ふ医扑惴ɑ騿l(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)間距離為 cij。 已知 (cij 0, cij= ,i,j V )，并設(shè) xij=，其它）在最優(yōu)路線上，邊（0ji1 （ 3 1） 畢業(yè)設(shè)計(jì) (論文 ) 第 15 頁(yè) 則旅行商問(wèn)題的數(shù)學(xué)模型可寫成如下的線性規(guī)劃形式： MinZ ji ijc xijs.t VjixVKKxVjxVixijSjiijjiijijji,1,0,1,1,1,這里， K 為 V 的所有非空子集， K 為集合 K 中所含圖 G 的頂點(diǎn)個(gè)數(shù)。前兩個(gè)約束意味著對(duì)每個(gè)頂點(diǎn)而言，僅有一條邊進(jìn)出，后一約束則保證了沒(méi)有任何子回路解的產(chǎn)生。于是，滿足上述約束的解構(gòu)成了一條 Hamilton 回路。除此之外，模型還有其它一些等價(jià)的書寫形式 。 4.2 旅行商問(wèn)題的計(jì)算復(fù)雜性 一般的，我們定義一個(gè)組合優(yōu)化問(wèn)題 : 設(shè) RSf : ，其中 S為一個(gè)有限集， f為映射函數(shù)，對(duì)每個(gè) Sx 產(chǎn)生唯一的實(shí)數(shù) f(x)，則最大 (小 )化問(wèn)題即找一個(gè) Sx ，使得對(duì)于任何其它 Sx 有 )()()( xfxf 。 此組合優(yōu)化問(wèn)題的一個(gè)基本算法是 :對(duì)于每個(gè) Sx ，求 f(x)的值，挑選 x ，使對(duì)于所有的 Sx ， )()()( xfxf 。 這就是窮舉搜索法，它在理論上可以解決任何有限的組合最優(yōu)化問(wèn)題。 但對(duì)于 n個(gè)城市的 TSP，可能的回路數(shù)有2 )!1( n條，計(jì)算每一條路徑需求 n個(gè)距離之和，故計(jì)算量將正比于2!n。表 4 1顯示了運(yùn)算速度 510 億次 /秒的 CrayXT3巨型計(jì)算機(jī)按窮舉搜索法計(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í)間 5 12 60 12106 秒 10 5108144.1 6108144.1 7108144.1 秒 20 161008.6 181022.1 51022.1 秒 40 461002.1 471008.4 271032.1 年 100 155106.4 157106.4 1361048.1 年 200 371100.5 374100.1 3561022.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:3 2 5 4 7 1 6 9 8可簡(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ù) )1,0( ， 定義基于序的適應(yīng)度函數(shù) e 1)1()( iiv a l x i 1， 2， 3， psize（ 3 2） 式中： xi 種群排序后第 i個(gè)個(gè)體； 畢業(yè)設(shè)計(jì) (論文 ) 第 19 頁(yè) psize 種群中個(gè)體總數(shù)。 程序源碼： 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；inPopSize；i+ ) double fsumfitness = 0.0； for( int j=0；j=i；j+ ) fsumfitness += vecPopj.m_fFitness*10000； vecRoll.push_back( fsumfitness )； nRollRange = (int)fsumfitness； 畢業(yè)設(shè)計(jì) (論文 ) 第 21 頁(yè) for( i=0；inPopSize；i+ ) nRollNumber = rand()%nRollRange； for( j=0；jnPopSize；j+ ) if( nRollNumber ncrossoverbegin ) break； else if( ncrossoverend ncrossoverbegin ) std:swap( ncrossoverbegin, ncrossoverend )； 畢業(yè)設(shè)計(jì) (論文 ) 第 23 頁(yè) break； for( int i=ncrossoverbegin；i:iterator iter_father, iter_son； bool hasCity = false； int naddbegin = 0； for( iter_father=vecPopnFatherB.m_CityRout