【正文】 e the search direction of the objective function and the corresponding fitness function, and so provides a generic framework for solving plicated system problem, so the geic algorithm is widely used in mathematical problem, binatorial optimization, mechanical design, artificial intelligence, etc Geic algorithm (based Algorithms, the GA) is mimic natural biological natural selection and evolution mechanism and developed a kind of highly parallel, adaptive random search algorithm. Particularly suitable for solving the traditional search algorithm is not good to deal with plex optimal solution of problem. Traveling Salesman Problem (39。 MUTATION ALGORITHM。 附錄一程序 ................................................................................................................................ 33 附錄二外文翻譯 ......................................................................................... 錯誤 !未定義書簽。遺傳算法固有的并行性和 并行 計算的能力 ，使 在搜索過程中不容易陷入局部最優(yōu) 。 采用 自然進(jìn)化機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠 快速 可靠地解決求解非常困難的問題 ， 非常 適 用于本課題 涉及 的 TSP 問題的求解與 研究。 TSP 問題其實(shí)是“ 哈密頓回路問題 ”中的“哈密頓最短 回路問題 ”。 因?yàn)?遺傳算法本 身 是模擬生物自然選擇 和遺傳的 過程的， 所以 用遺傳算法求解 TSP 最先要 確定 的 是問題的建模 ， 即如何用 遺傳學(xué)的 算子來表示旅行商問題中的變量 。 應(yīng)用 遺傳算法求解旅行商問題最關(guān)鍵的 是 編碼方式、交叉、選擇、變異算子的設(shè)計， 直接 關(guān)系到算法 能否求出 最優(yōu)解 或 近似最優(yōu)解 。 本章 主要 論述 本文所研究的主要內(nèi)容，并對論文 的 章節(jié)結(jié)構(gòu)進(jìn)行規(guī)劃。雖然它是一個比較古老的問題，最早可以追溯到 Euler 提出的騎士旅行問題，但同時它也是一個新的問題，因?yàn)樗挠嬎銖?fù)雜度 較高， 雖然人們一直在嘗試用新的方法來改進(jìn)求解該問題的復(fù)雜度，但是 這一類問題 距今 都沒有能找到一個有效的算法來解決 。 旅行商 問題就是要解決 一個 最小回路問題，回路中所有頂點(diǎn)有且僅經(jīng)過一次 。所以 當(dāng) 輸入越大，則 耗費(fèi)的 時間就是個天文數(shù)字了，因此 旅行商問題至今都沒有 能 找到 一種 有效的求解方法。 盡管 旅行商問題 至今 仍然沒有找 到 最優(yōu)解， 但 求解它 的算法已經(jīng)在不斷的改進(jìn)。 1980Crowder和 Padberg 求解 了 318 個 城市的 TSP 問題； 1987 年 Padberg 和 Rinaldi 成功 將城市數(shù)量增加到了 2392 個 ； 最大的 成功求解的旅行商問題 已經(jīng) 增加 到 24798 個 城市。 其次 ， 隨著旅游業(yè)的快速發(fā)展，大量的旅客在旅途中浪費(fèi)了不必要的時間和金錢， 而這些不必要的浪費(fèi)完全可以通過對旅行路線的合理規(guī)劃來避免。毫無疑問，高效、低成本、低能耗成了各個物流企業(yè)追求的目標(biāo)，更加合理的配送路線能明顯地為物流公司增大利潤 。由于 旅行商 問題在計算機(jī)網(wǎng)絡(luò)、物流、旅游業(yè)、交通運(yùn)輸?shù)仍S多領(lǐng)域都有著十分廣泛的應(yīng)用 ，因此尋找一個 求解這類問題的求解方法 有 很 高的 應(yīng)用價值 因此 ，對旅行商問題有效算法的研究不僅 具有重要的理論意義，而且具有重大的實(shí)際應(yīng)用價值 。 遺傳算法（ Geic Algorithms,GA） 又叫 基因進(jìn)化算法或進(jìn)化算法 ，是 一種通過模擬自然界生物 適者生存 、優(yōu)勝劣 汰的 進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機(jī)搜索算法。 本文 采用的 是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，其 可以在一定程度上克服 常規(guī)巡回路線編碼方法 在 交 異操作時易 產(chǎn)生 不滿足問題約束條件或無實(shí)際意義的巡回路線 的 缺點(diǎn) 。 變異 算法采用的是基本位變異法 ， 即 只是 根據(jù) 變異概率隨機(jī)改變?nèi)旧w中的某一 段 染色體， 具體會在后 文 中做詳細(xì)說明 。本課題中以每條路徑長度的倒數(shù)作為適應(yīng)度函 數(shù)值 。 本文 的結(jié)構(gòu) 本文 一共分為 5 章 ， 結(jié)構(gòu) 如下： 第一章緒論 。 第二章遺傳算法理論 概述 。 第三 章 基于遺傳 算法求解 TSP 問題。 第四 章 45 個城市旅行商 問題 的仿真軟件的 設(shè)計。 第五 章結(jié)論 。 4 2 遺傳算法 理論 概述 遺傳 算法的 產(chǎn)生 及發(fā)展 最早由美國 Michigan(密執(zhí)安大學(xué) )的 Hollang 教授提出，起源于 60 年代對自然和人工自適應(yīng)系統(tǒng)的研究。 70 年代 De Jong 基于遺傳算法的思想在計算機(jī)上進(jìn)行了大量純數(shù)值函數(shù)優(yōu)化計算實(shí)驗(yàn) ， 建立 了著名的 五 函數(shù)測試平臺。進(jìn)入90 年代 ，遺傳算法進(jìn)入了興盛期，無論是理論研究 還 是實(shí)際應(yīng)用都成了十分熱門的課題。 下面 是一些在遺傳算法發(fā)展 進(jìn)程 中做出 杰出 貢獻(xiàn)的 人物 ： 1 60 年代提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時 ,可以借鑒生物遺傳的機(jī)制； 70 年代初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)； 80 年代實(shí)現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)系統(tǒng)－分類器系統(tǒng) (Classifier Systems),開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。 3 Jong 1975 年在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計算實(shí)驗(yàn)，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標(biāo)和離線指標(biāo)。 5 1991 年編輯出版了《遺 傳算法手冊 (Handbook of Geic Algorithms)》書中包括遺傳算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟(jì)中的大量應(yīng)用實(shí)例。 5 遺傳 算法基本原理 遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機(jī)搜索算法。在 遺傳算法中，種群中的 每一個 個體是問題的一個 解 ， 稱為“染色體”， 染色體是 一串 符號，比如二進(jìn)制的 01 串 。在 每一代 中應(yīng)用適應(yīng)度（ fitness） 來 測量染色體的優(yōu)越性 ， 適應(yīng)度 高的 更容易在自然的選擇中 存活 下來。 后代通常是前一代染色體通過交叉（ crossover） 或者 變異 （ mutation ） 形成 。 遺傳算法中每一條染色體，對應(yīng)著遺傳算法的一個解決方案，一般我們用適應(yīng)性函數(shù)（ fitness function）來衡量這個解決方案的優(yōu)劣。在這個多維曲面里面也有數(shù)不清的 “山峰 ”，而這些最優(yōu)解所對應(yīng)的就 是 這些山峰 ， 這些山峰就是局部最優(yōu)解 。而遺傳 算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。 下面給出生物學(xué)的幾個基本概念知識，這對于理解遺傳算法很重要： 1）遺傳因子（ gene） :DNA 長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱基因。 2）個體（ individual） :指染色體帶有特征的實(shí)體。 4）進(jìn)化（ evolution） 。生物的進(jìn)化是以種群的形式進(jìn)行的。 6）選擇（ selection） :指以一定的概率從種群中選擇若干個體的操作。 8）編碼（ coding） :DNA 中遺傳信息在一個長鏈上按一定的模式排列，也即進(jìn)行了遺傳編碼。 9）串（ String） :它是 個體的 形式 ，在算法 中 為二進(jìn)制串，并且對應(yīng)于遺傳學(xué) 中 的染色體。 基因 操作是在 結(jié)構(gòu) 空間中進(jìn)行的。 11）染色體：是生物細(xì)胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的主要載體，由多個遺傳因子 — 基因組成。 步驟二 ： 初始化 ：隨機(jī)生成有 N 個 個體的初始群體 ， 這些個 體一起組成了一個種群 。參數(shù) N 可以根據(jù) 具體的情況 而定 。 所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。 步驟四 ： 適應(yīng)度： 確定個體適應(yīng)度的量化評價方法， 適應(yīng)度 用于 衡 量種群中個體的優(yōu)劣性， 是確定 種群中個體留存的關(guān)鍵 。選擇 操作 是建立在適應(yīng)度之上的，適應(yīng)度高的被選 中的幾率就大，選擇操作體現(xiàn)出了 生物 適者生存的原 則 。 變異 操作可以保證 算法 過程中不會產(chǎn)生無法進(jìn)化的單一群體， 避免 算法 早熟 出現(xiàn) 局部最優(yōu)。給定最大的遺傳代數(shù)，算法在計算到最大的遺傳代數(shù)時，終止計算。 數(shù)值 方法求解這一問題的主要手段是迭代運(yùn)算。遺傳算法 很好 地克服了這個缺點(diǎn)，是一種全局優(yōu)化算法。 主要有 以 下幾點(diǎn)： （ 1） 遺傳 算法的本質(zhì)并行性。這是 遺傳算法與 傳統(tǒng)優(yōu)化算法的 最 大區(qū)別。遺傳算法 從 串集開始搜索，覆蓋面大，有利于全局最優(yōu)。 （ 2） 遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序 .僅 用 適應(yīng)度函數(shù)值來評估個體 ，在 此基礎(chǔ)上進(jìn)行遺傳操作。 （ 3） 遺傳算法 不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo) 它 的搜索方向 ，具有 自組織 、自適應(yīng)和自學(xué)習(xí)性。 這種 通過自然選擇與進(jìn)化的機(jī)制消除了算法設(shè)計過程中的一個最大障礙，即需要事先描述問題的 全部 特點(diǎn)， 并 要 說明 針對 所求 問題的不同 特點(diǎn)， 我們設(shè)計的算法應(yīng)該采用的具體 措施 。 （ 4） 遺傳 算法可以直接用于實(shí)際應(yīng)用當(dāng)中，對于給定的問題，可以產(chǎn)生許多解，最終選擇是根據(jù)用戶自己的需求來選取，通用性 高 ， 實(shí)際 應(yīng)用性強(qiáng) ， 應(yīng)用范圍 廣 。 （ 1） 函數(shù) 優(yōu)化 函數(shù) 優(yōu)化是遺傳算法經(jīng)典的應(yīng)用領(lǐng)域 ，也是 使用最頻繁的 領(lǐng)域 。對于 這些 非線性、 求 極 值、 多模型或 多目標(biāo)的 函數(shù) 優(yōu)化 問題，用傳統(tǒng)的優(yōu)化方法很難解決，而用遺傳算法可以 方便地 得到 較好的結(jié)果。對于 這一類 復(fù)雜的 問題 ， 遺傳 算法 已經(jīng) 被證實(shí)是十分有效的求解方式 。 (3)生產(chǎn)調(diào)度問題 生產(chǎn)調(diào)度問題在很多情況下建立起來的傳統(tǒng)數(shù)學(xué)模難以精確求解，雖然經(jīng)過一些簡化之后可以進(jìn)行求解 .也會因簡化得太多而使得求解結(jié)果與實(shí)際相差太大?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效措施。 （ 4）機(jī)器人 學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。例如，遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動軌跡規(guī)劃、機(jī)器人逆運(yùn)動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。 許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。 （ 6）人工 生命 人工生命是用計算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。人工生命與遺傳算法有著密切的關(guān)系。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。 9 3 基于 遺傳 算法求解 TSP問題 旅行商問題， 即 TSP 問題 又譯為旅行推銷員問題， 屬于 NP 完全問題，是 數(shù)學(xué)領(lǐng)域中著 名的 問題之一。要求得的路徑路程為所有可能路徑之中的最小值， 即 最優(yōu)值問題 。 方式 編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計遺傳算法時的一個關(guān)鍵步驟。迄今為止人們已經(jīng)提出了許多種不同的編碼方法。下面我們從具體實(shí)現(xiàn)角度出發(fā)介紹其中的幾種主要編碼方法。它有以下一些優(yōu)點(diǎn)： (1）編碼、解碼操作簡單易行 (2)交叉、變異等遺傳操作便于實(shí)現(xiàn) (3)符合最小字符集編碼原則 (4)利用模式定理對算法進(jìn)行理論分析。而格雷碼能有效地防止這類現(xiàn)象。 二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時的映射誤差。 所謂浮點(diǎn)法，是指個體的每個基因值用某一范圍內(nèi)的一個浮點(diǎn)數(shù)來表示 。 浮點(diǎn)數(shù)編碼方法有下面幾個優(yōu)點(diǎn)： （ 1)適用于在遺傳算法中表示范圍較大的數(shù) （ 2)適用于精度要求較高的遺傳算法 （ 3)便于較大空間的遺傳搜索 （ 4)改善了遺傳算法的計算復(fù)雜性，提高了運(yùn)算交率 （ 5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用 （ 6)便于設(shè)計針對問題的專門知識的知識型遺傳算子 （ 7)便于處理復(fù)雜的決策變量約束條件 ： 符號 編碼法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集如｛ A,B,C?｝。 但對于使用符號編碼方法的遺傳算法，一般需要 認(rèn)真設(shè)計交叉、變異等遺傳運(yùn)算