【正文】 (數據綁定 ,顯示關于軟件的信息 ) 再 拖入一個按鈕， 在此處可以 對其添加響應函數： void CAboutDlg::OnOK() { // TODO: Add extra validation here CDialog::OnOK()。 pDCRectangle(Workarea)。k1。 DDX_Text(pDX, IDC_EDIT5, m_GANum)。 演示 模塊 設計 （ 1） 主窗口 設計： 在 VC 工具欄 insent 中插入窗口 IDD_CHINA45_DIALOG， 再在上面設置 變量 ，并進行初始化。 本 系統(tǒng) 中以每條路徑長度的倒數作為適應度函數值，并對其進行 統(tǒng) 一化 的 操作，即按從大到小 進行 排序，為下一步選擇操作做準備。 針對旅行商問題對變異算子的設計要求，基本位變異即交換變異。 UpdateData(false)。 // 將當前一代群體中的個體按 F 值從大到小排序 for(i=0。 newpop[m_nGroupSize+2*i+1].CopyNode(amp。 temp=RandomInt(0,m_nGroupSize1)。將全部 Gi 順序排列在一起所得到的一個列表： G=（ G1， G2， G3， …… ， Gn） 這樣就 可以表示一條 巡回 路線，它就是遺傳算法中的一個 個體 基因。下面我們從具體實現角度出發(fā)介紹其中的幾種主要編碼方法。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數據挖掘下具。 （ 1） 函數 優(yōu)化 函數 優(yōu)化是遺傳算法經典的應用領域 ，也是 使用最頻繁的 領域 。遺傳算法 很好 地克服了這個缺點，是一種全局優(yōu)化算法。 步驟二 ： 初始化 ：隨機生成有 N 個 個體的初始群體 ， 這些個體一起組成了一個種群 。 2）個體（ individual） :指染色體帶有特征的實體。 5 遺傳 算法基本原理 遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應、具有全局優(yōu)化能力的隨機搜索算法。 第四 章 45 個城市旅行商問題 的仿真軟件的 設計。由于 旅行商 問題在計算機網絡、物流、旅游業(yè)、交通運輸等許多領域都有著十分廣泛的應用 ，因此尋找一個 求解這類問 題的求解方法 有 很 高的 應用價值 因此 ，對旅行商問題有效算法的研究不僅具有重要的理論意義，而且具有重大的實際應用價值 。 本章 主要 論述 本文所研究的主要內容，并對論文 的 章節(jié)結構進行規(guī)劃。 關鍵字：旅行商 問題 ； 遺傳算法 ； 變異 算法；編碼 方式 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。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。 研究 背景 旅行商問題（ Traveling Salesman Problem, TSP） ,也稱旅行推銷員 問題 ，具體的數學模型可以這樣理解：現在 給定 以下 幾個城市的位置 ，旅行商從 其中 的 某一個城市出發(fā)，不重復地訪問其余的每一個城市，最后又返回到原出發(fā)點城市，要求找出 這樣 一條路線，使旅行所付出的代價最小。 內容 本文 采用遺傳算法求解 45 個 城市的旅行商問題，并對其實現計算機仿真。 本章 主要 對系統(tǒng)模塊 進行 了介紹，而且 對 應用 系統(tǒng)進行了多組試算，最后得出結論。 遺傳算法的思路是通過從給定一個初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進化的三種原則，逐步改進種群，越來越逼近最優(yōu)解，以達到求解最優(yōu)化問題的目的。 3）種群（ population） :染色體帶有特征的個體的集合。遺傳算法 就是 以這個初始群體為起點開始迭代。 遺傳 算法 與 傳統(tǒng)的 優(yōu)化 方法（ 枚舉 ，啟發(fā) 式 等） 相 比較，以生物進化為原型 ， 具有很多的 優(yōu)點 。 尤其是 在數學領域，科學家 構造出了 許許多多復雜 的測試函數： 連續(xù) 函數、離散函數、凸函數、凹函數 、 單峰函數、多峰函數等等。利用該工具對兩個飛機失事的真實數據庫進行了數據挖掘實驗，結果表明遺傳算法是進行數據挖掘的有效方法之一。 ： 它由二進制符號 0 和 1 所組成的二值符號集。例如 ， 假設現在有這樣一個城市序列： W=(A,B,C,D,E,F,G,H,I,J) 有 如下兩條 巡回 路線 ： T1=(A,D,B,H,F,I,J,G,E,C) T2=(B,C,A,D,E,J,H,I,F,G) 則按本 系統(tǒng)所用的編碼方法 ， 這兩 條 巡回路線可以編碼為： G1 =(1,3,1,5,3,4,4,3,2,1) 12 G2 =(2,2,1,1,1,5,3,3,1,1) 這種 編碼方式的 優(yōu)點 在于任意的染色體都對應一條有實際意義的巡回路線， 因此 可以使用常規(guī)的交叉算子對它 進行 計算，有利于算 法的實現。 if(parent1temp) parent1=temp。pop2)。im_nGroupSize1。 UpdateWindow()。 變異是單個個體內部發(fā)生變化，導致產生新個體， 從而產生出一條新的巡回路線。 為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應度必須為正數或零，不能是負數。 具體 變量 及其窗口 對話框 設置如下表。 DDX_Text(pDX, IDC_EDIT6, m_CurGANum)。k++) { ExecGA(k, oldpop)。 pDCSetBkColor(0x00FFFFFF)。 } 測試結果及分析 測試 一 如 下圖所示，本次測試的是默認的參數 {M， T， Pc， Pm}={200， 100， ， }， 所取數值 都 在系統(tǒng)設置的參考范圍 之 內。 } （ 2） 關于 軟件： 在 VC 工具欄 insent 中插入窗口 IDD_ABOUTBOX， 對其添加如下操作： enum { IDD = IDD_ABOUTBOX } (指定窗口 ID) protected: virtual void DoDataExchange(CDataExchange* pDX)。 =。 for(int k=0。 DDX_Text(pDX, IDC_EDIT4, m_GAVariProb)。 這些在上文中已作過詳細介紹 ,這里就不再重復。 因此適應度函數的選擇至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。 （ 2）對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產生出一個新個體。 //AfxMessageBox(顯示數據 )。i++) oldpop[i].fit=1/oldpop[i].cost/TotalF*100。pop1)。 //父代基因 2 parent1=RandomInt(0,m_nGroupSize1)。 對于 給定的旅行商問題 ， 設 其 城市列表 W， 假定 對 各個 城市的 訪問順序為 T： T=（ T1， T2， T3， ….. ， Tn） 規(guī)定 每訪問完一個 城市， 就 從 城市列表 W 中 將 該城市 除去，則用第 i（ i=1,2,3……n ）個所訪問的城市 Ti 在所有未訪問城市列表 W={T1， T2， T3，? ..， Ti1}中的對應位置序號 Gi（ 1≤ Gi≤ ni+1）就可表示具體訪問哪個城市，如此這樣直到處理完 W 中所有的城市?？偟膩碚f，這些編碼方法可以分為三大類：二進制編碼法、浮點編碼法、符號編碼法。因此，應用遺傳算法在數據庫中進行搜索，對隨機產生的一組規(guī)則進行進化 .直 到數據庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數據庫中的規(guī)則。 遺傳 算法的應用 遺傳 算法為求解復雜 系統(tǒng)問題 提供了一種通用的算法框架，它不取決于問題的 具體 領域，有很強的魯棒性 ， 因而被廣泛的 使用 于 組合 優(yōu)化 、 機械設計、人工智能、數學建模、軟件工程等領域 。一般的 迭代 方法容易陷入局部極小的陷阱而出現“ 死循環(huán) ” 現象 ， 使迭代無法進行。 6 遺傳 算法基本步驟 步驟一 ： 編碼 ： 把 所需要選擇的群體進行編號，每一個個體就是 一條 染色體 ，一個 解就是一串基因的組合 。生物的基因根據物種的不同而多少不一。 1992 年將遺傳算法應用于計算機程序的優(yōu)化設計及自動生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應用于人工智能、機器學習符號處理等方面。 本章 主要介紹了 本系統(tǒng) 具體使用什么方式實現求解過程， 包括 編碼方式、選擇、交叉、變異算子的具體選取 。再比如 在裝配線 的 流程中，對每個工件為完成裝配過程節(jié)約的少許時間意味著一天的產量的相應增加。 所以 要在 編碼方式的確定上做好足夠的 功夫 ， 以 確定 程序 求解的精確度。 本文 選 用遺傳算法 求解 45個 城市 的 TSP問題，基于 Microsoft