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