【正文】 具對兩個飛機(jī)失事的真實數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。 尤其是 在數(shù)學(xué)領(lǐng)域，科學(xué)家 構(gòu)造出了 許許多多復(fù)雜 的測試函數(shù)： 連續(xù) 函數(shù)、離散函數(shù)、凸函數(shù)、凹函數(shù) 、 單峰函數(shù)、多峰函數(shù)等等。適應(yīng)度 函數(shù) 不僅不受連續(xù)可微的約束，而且其定義域可以任意的設(shè)定 ， 故幾乎可處理任何問題 。 遺傳 算法 與 傳統(tǒng)的 優(yōu)化 方法（ 枚舉 ，啟發(fā) 式 等） 相 比較，以生物進(jìn)化為原型 ， 具有很多的 優(yōu)點 。 步驟六 ： 變異 算子：變異 是根據(jù) 生物 遺傳 中基因突變的原理， 以 變異概率 對 群體中的某一些個體 的 某些 “位 ”執(zhí)行 變異。遺傳算法 就是 以這個初始群體為起點開始迭代。遺傳編碼可以看成是從表現(xiàn)型到遺傳子型的映射。 3）種群（ population） :染色體帶有特征的個體的集合。所以也可以把遺傳算法的過程看作是一個在多元函數(shù)里面求最優(yōu)解的過程。 遺傳算法的思路是通過從給定一個初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進(jìn)化的三種原則，逐步改進(jìn)種群，越來越逼近最優(yōu)解，以達(dá)到求解最優(yōu)化問題的目的。如今 遺傳 算法已經(jīng)被廣泛的應(yīng)用于 計算機(jī)科學(xué) 、 人工智能、機(jī)械設(shè)計、圖像處理等各個領(lǐng)域，不僅如此，利用遺傳算法進(jìn)行理論研究的優(yōu)化和最優(yōu)解問題的解決能力也顯著提高。 本章 主要 對系統(tǒng)模塊 進(jìn)行 了介紹，而且 對 應(yīng)用 系統(tǒng)進(jìn)行了多組試算，最后得出結(jié)論。 在 求出 之后 將其按照 從大 到小的順序排列，以便于 后面找出 路徑 之 和最小的城市序列 。 內(nèi)容 本文 采用遺傳算法求解 45 個 城市的旅行商問題，并對其實現(xiàn)計算機(jī)仿真。 目前，求解 TSP問題常用的算法主要有遺傳算法和蟻群 算法，另外 還 有 爬山 法、模擬 退火 算法 、 神經(jīng)網(wǎng)絡(luò)方法、貪婪算法、禁忌搜索算法等。 研究 背景 旅行商問題（ Traveling Salesman Problem, TSP） ,也稱旅行推銷員 問題 ，具體的數(shù)學(xué)模型可以這樣理解：現(xiàn)在 給定 以下 幾個城市的位置 ，旅行商從 其中 的 某一個城市出發(fā)，不重復(fù)地訪問其余的每一個城市，最后又返回到原出發(fā)點城市，要求找出 這樣 一條路線，使旅行所付出的代價最小。 旅行商 問題 （ Traveling Salesman Problem ,TSP） 是一個 非常經(jīng)典的組合優(yōu)化問題的 NP難題 ， 長期 以來 都沒有 一個十分有效的算法來解決它，但 TSP 本身 在許多領(lǐng)域有著重要的應(yīng)用，如 連鎖店 的貨物配送路線、計算機(jī)網(wǎng)絡(luò)路由器遍歷、印刷電路板的鉆孔路線等問題都可以 建模為旅行商問題。ll Salesman Problem) is to determine a through route if and only if all cities in time and distance is the shortest route, the shortest distance of Hamilton loop. Traveling salesman problem is a very wide range of practical background and important theoretical value of the binatorial optimization problem. At present the main method of solving TSP problem with simulated annealing algorithm, geic algorithm and Hopfield neural work algorithm, the heuristic search method, the binary tree described algorithm. This article chooses 45 cities geic algorithm to solve the TSP problem, based on Microsoft Visual c + + environment, use the proposed a new tour routes such as Grefenstette coding method, mutation operator adopted conventional basic variation method, through multiple sets of experimental data and the approximate solution of the 45 cities the optimal solution, has realized the puter simulation to solve the TSP problem. KEY WORDS: TRAVELING SALESMAN PROBLEM. GENETIC ALGORITHM。 I 題目： 遺傳算法求解旅行商問題的計算機(jī)仿真 II 遺傳 算法求解 TSP 問題 的計算機(jī)仿真 摘要 由于 遺傳算法在整體搜索策略和優(yōu)化搜索方法 上 不依賴梯度信息或其他輔助 知識 ， 只需要 影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)， 所以提供了一種 求解復(fù)雜系統(tǒng) 問題的通用框架 ，因此 遺傳算法廣泛應(yīng)用于數(shù)學(xué)問題、組合優(yōu)化、機(jī)械設(shè)計、 人工 智能等領(lǐng)域。 關(guān)鍵字：旅行商 問題 ； 遺傳算法 ； 變異 算法；編碼 方式 III The puter simulation of geic algorithm to solve TSP problem Abstract Due to geic algorithm on the overall search strategy and optimization search method does not depend on the gradient information or other auxiliary knowledge, only need to influence 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。 采用 自然進(jìn)化機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠 快速 可靠地解決求解非常困難的問題 ， 非常 適 用于本課題 涉及 的 TSP 問題的求解與 研究。 本章 主要 論述 本文所研究的主要內(nèi)容，并對論文 的 章節(jié)結(jié)構(gòu)進(jìn)行規(guī)劃。 盡管 旅行商問題 至今 仍然沒有找 到 最優(yōu)解， 但 求解它 的算法已經(jīng)在不斷的改進(jìn)。由于 旅行商 問題在計算機(jī)網(wǎng)絡(luò)、物流、旅游業(yè)、交通運(yùn)輸?shù)仍S多領(lǐng)域都有著十分廣泛的應(yīng)用 ，因此尋找一個 求解這類問 題的求解方法 有 很 高的 應(yīng)用價值 因此 ，對旅行商問題有效算法的研究不僅具有重要的理論意義，而且具有重大的實際應(yīng)用價值 。本課題中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值 。 第四 章 45 個城市旅行商問題 的仿真軟件的 設(shè)計。進(jìn)入90 年代 ，遺傳算法進(jìn)入了興盛期，無論是理論研究 還 是實際應(yīng)用都成了十分熱門的課題。 5 遺傳 算法基本原理 遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機(jī)搜索算法。 遺傳算法中每一條染色體，對應(yīng)著遺傳算法的一個解決方案，一般我們用適應(yīng)性函數(shù)（ fitness function）來衡量這個解決方案的優(yōu)劣。 2）個體（ individual） :指染色體帶有特征的實體。 8）編碼（ coding） :DNA 中遺傳信息在一個長鏈上按一定的模式排列，也即進(jìn)行了遺傳編碼。 步驟二 ： 初始化 ：隨機(jī)生成有 N 個 個體的初始群體 ， 這些個體一起組成了一個種群 。選擇 操作 是建立在適應(yīng)度之上的，適應(yīng)度高的被選中的幾率就大，選擇操作體現(xiàn)出了 生物 適者生存的原 則 。遺傳算法 很好 地克服了這個缺點，是一種全局優(yōu)化算法。 （ 2） 遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序 .僅 用 適應(yīng)度函數(shù)值來評估個體 ，在 此基礎(chǔ)上進(jìn)行遺傳操作。 （ 1） 函數(shù) 優(yōu)化 函數(shù) 優(yōu)化是遺傳算法經(jīng)典的應(yīng)用領(lǐng)域 ，也是 使用最頻繁的 領(lǐng)域 ?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效措施。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。 9 3 基于 遺傳 算法求解 TSP問題 旅行商問題， 即 TSP 問題 又譯為旅行推銷員問題， 屬于 NP 完全問題，是 數(shù)學(xué)領(lǐng)域中著名的 問題之一。下面我們從具體實現(xiàn)角度出發(fā)介紹其中的幾種主要編碼方法。 所謂浮點法，是指個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示。將全部 Gi 順序排列在一起所得到的一個列表： G=（ G1， G2， G3， …… ， Gn） 這樣就 可以表示一條 巡回 路線，它就是遺傳算法中的一個 個體 基因。使用 單點交叉，即在個體的編碼串上隨機(jī)設(shè)置一個交叉點， 然后在該點相互交換兩個配對個體的部分染色體。 temp=RandomInt(0,m_nGroupSize1)。oldpop[parent1])。 newpop[m_nGroupSize+2*i+1].CopyNode(amp。 具體 代碼如下： for(int gen=0。 // 將當(dāng)前一代群體中的個體按 F 值從大到小排序 for(i=0。 14 } if(i!=maxpos) oldpop[i].SwapNode(amp。 UpdateData(false)。變異運(yùn)算是產(chǎn)生新個體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。 針對旅行商問題對變異算子的設(shè)計要求，基本位變異即交換變異。 (amp。 本 系統(tǒng) 中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值，并對其進(jìn)行 統(tǒng) 一化 的 操作，即按從大到小 進(jìn)行 排序，為下一步選擇操作做準(zhǔn)備。 圖 41系統(tǒng) 功能模塊圖 系 統(tǒng)詳細(xì)設(shè)計 由前 文 中介紹的個體編碼方法 及 各種遺傳算子可以構(gòu)成 許多種 不同的求解旅行商問題的遺傳算法，本系統(tǒng) 主要 利用這些遺傳算 子 對含有 45 座城市的旅行商問題進(jìn)行了試算。 演示 模塊 設(shè)計 （ 1） 主窗口 設(shè)計： 在 VC 工具欄 insent 中插入窗口 IDD_CHINA45_DIALOG， 再在上面設(shè)置 變量 ，并進(jìn)行初始化。 m_MiniCost = 。 DDX_Text(pDX, IDC_EDIT5, m_GANum)。 if(()==IDOK) { m_nGroupSize=。k1。具體 代碼 如下圖所示： 21 void CChina45Dlg::DrawNetwork() { CPen Pen。 pDCRectangle(Workarea)。 =px+m_point[i].x2。 (數(shù)據(jù)綁定 ,顯示關(guān)于軟件的信息 ) 再 拖入一個按鈕， 在此處可以 對其添加響應(yīng)函數(shù)： void CAboutDlg::OnOK() { // TODO: Add extra validation here CDialog::OnOK()。下 實驗結(jié)果分別如下圖所示 ： 25 圖 46 圖 47 26 圖 48 通過 對圖 4 8 可以 看出，算法經(jīng)過運(yùn)算之后，其求解的結(jié)果有一 定 的更優(yōu)的趨勢， 但是 通過運(yùn)算的計算時間卻大大的增加了，當(dāng)種群數(shù)量小時的計算 時間短 ，但是當(dāng)增加到 500 后 ，時間 明顯 感覺增加 ； 但 增加到 1000 后 ， 時間