【正文】 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。 附錄一程序 ................................................................................................................................ 33 附錄二外文翻譯 ......................................................................................... 錯誤 !未定義書簽。 采用 自然進化機制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠 快速 可靠地解決求解非常困難的問題 ， 非常 適 用于本課題 涉及 的 TSP 問題的求解與 研究。 因為 遺傳算法本 身 是模擬生物自然選擇 和遺傳的 過程的， 所以 用遺傳算法求解 TSP 最先要 確定 的 是問題的建模 ， 即如何用 遺傳學的 算子來表示旅行商問題中的變量 。 本章 主要 論述 本文所研究的主要內(nèi)容，并對論文 的 章節(jié)結(jié)構(gòu)進行規(guī)劃。 旅行商 問題就是要解決 一個 最小回路問題，回路中所有頂點有且僅經(jīng)過一次 。 盡管 旅行商問題 至今 仍然沒有找 到 最優(yōu)解， 但 求解它 的算法已經(jīng)在不斷的改進。 其次 ， 隨著旅游業(yè)的快速發(fā)展，大量的旅客在旅途中浪費了不必要的時間和金錢，而這些不必要的浪費完全可以通過對旅行路線的合理規(guī)劃來避免。由于 旅行商 問題在計算機網(wǎng)絡(luò)、物流、旅游業(yè)、交通運輸?shù)仍S多領(lǐng)域都有著十分廣泛的應(yīng)用 ，因此尋找一個 求解這類問 題的求解方法 有 很 高的 應(yīng)用價值 因此 ，對旅行商問題有效算法的研究不僅具有重要的理論意義，而且具有重大的實際應(yīng)用價值 。 本文 采用的 是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，其 可以在一定程度上克服 常規(guī)巡回路線編碼方法 在 交 異操作時易 產(chǎn)生 不滿足問題約束條件或無實際意義的巡回路線 的 缺點 。本課題中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值 。 第二章遺傳算法理論 概述 。 第四 章 45 個城市旅行商問題 的仿真軟件的 設(shè)計。 4 2 遺傳算法 理論 概述 遺傳 算法的 產(chǎn)生 及發(fā)展 最早由美國 Michigan(密執(zhí)安大學 )的 Hollang 教授提出，起源于 60 年代對自然和人工自適應(yīng)系統(tǒng)的研究。進入90 年代 ，遺傳算法進入了興盛期，無論是理論研究 還 是實際應(yīng)用都成了十分熱門的課題。 3 Jong 1975 年在其博士論文中結(jié)合模式定理進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標和離線指標。 5 遺傳 算法基本原理 遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機搜索算法。在 每一代 中應(yīng)用適應(yīng)度（ fitness） 來 測量染色體的優(yōu)越性 ， 適應(yīng)度 高的 更容易在自然的選擇中 存活 下來。 遺傳算法中每一條染色體，對應(yīng)著遺傳算法的一個解決方案，一般我們用適應(yīng)性函數(shù)（ fitness function）來衡量這個解決方案的優(yōu)劣。而遺傳算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。 2）個體（ individual） :指染色體帶有特征的實體。生物的進化是以種群的形式進行的。 8）編碼（ coding） :DNA 中遺傳信息在一個長鏈上按一定的模式排列，也即進行了遺傳編碼。 基因 操作是在 結(jié)構(gòu) 空間中進行的。 步驟二 ： 初始化 ：隨機生成有 N 個 個體的初始群體 ， 這些個體一起組成了一個種群 。 所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。選擇 操作 是建立在適應(yīng)度之上的，適應(yīng)度高的被選中的幾率就大，選擇操作體現(xiàn)出了 生物 適者生存的原 則 。給定最大的遺傳代數(shù)，算法在計算到最大的遺傳代數(shù)時，終止計算。遺傳算法 很好 地克服了這個缺點，是一種全局優(yōu)化算法。這是 遺傳算法與 傳統(tǒng)優(yōu)化算法的 最 大區(qū)別。 （ 2） 遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序 .僅 用 適應(yīng)度函數(shù)值來評估個體 ，在 此基礎(chǔ)上進行遺傳操作。 這種 通過自然選擇與進化的機制消除了算法設(shè)計過程中的一個最大 障礙，即需要事先描述問題的 全部 特點， 并 要 說明 針對 所求 問題的不同 特點， 我們設(shè)計的算法應(yīng)該采用的具體 措施 。 （ 1） 函數(shù) 優(yōu)化 函數(shù) 優(yōu)化是遺傳算法經(jīng)典的應(yīng)用領(lǐng)域 ，也是 使用最頻繁的 領(lǐng)域 。對于 這一類 復(fù)雜的 問題 ， 遺傳 算法 已經(jīng) 被證實是十分有效的求解方式 。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效措施。例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。人工生命與遺傳算法有著密切的關(guān)系。 9 3 基于 遺傳 算法求解 TSP問題 旅行商問題， 即 TSP 問題 又譯為旅行推銷員問題， 屬于 NP 完全問題，是 數(shù)學領(lǐng)域中著名的 問題之一。 方式 編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計遺傳算法時的一個關(guān)鍵步驟。下面我們從具體實現(xiàn)角度出發(fā)介紹其中的幾種主要編碼方法。而格雷碼能有效地防止這類現(xiàn)象。 所謂浮點法，是指個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示。 但對于使用符號編碼方法的遺傳算法，一般需要 認真設(shè)計交叉、變異等遺傳運算的操作方法，以滿足問題的各種約束需 求，這樣才能提高算法的搜索性能。將全部 Gi 順序排列在一起所得到的一個列表： G=（ G1， G2， G3， …… ， Gn） 這樣就 可以表示一條 巡回 路線，它就是遺傳算法中的一個 個體 基因。 求解 旅行商 問題的遺傳算法的交叉算法主要有：部分匹配交叉（ PMX） 、 循環(huán)交叉（ CX） 、次序 交叉（ OX） 、線性次序 交叉（ LOX） 、 邊重組交叉（ EX） 等 。使用 單點交叉，即在個體的編碼串上隨機設(shè)置一個交叉點， 然后在該點相互交換兩個配對個體的部分染色體。i++) { int nPos, temp=0。 temp=RandomInt(0,m_nGroupSize1)。 if(parent2temp) parent2=temp。oldpop[parent1])。 (amp。 newpop[m_nGroupSize+2*i+1].CopyNode(amp。本課題采用最常用的選擇算子 —— 比例選擇算子（又 稱輪盤賭選擇） 。 具體 代碼如下： for(int gen=0。i++) TotalF+=1/oldpop[i].CalcCost(m_distance)。 // 將當前一代群體中的個體按 F 值從大到小排序 for(i=0。 for(int j=i。 14 } if(i!=maxpos) oldpop[i].SwapNode(amp。 (amp。 UpdateData(false)。im_nGroupSize。變異運算是產(chǎn)生新個體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。 因為 使用由 Grefenstette 等所提出的編譯方法來表示個體，一個個 體經(jīng)過遺傳運算后所得到的任意一個基因型個體 與交叉后的情況相同， 都能夠?qū)?yīng)于一條具有實際意義的巡回路線 。 針對旅行商問題對變異算子的設(shè)計要求，基本位變異即交換變異。i++) { int nPos1,nPos2,parent=0。 (amp。pop)。 本 系統(tǒng) 中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值，并對其進行 統(tǒng) 一化 的 操作，即按從大到小 進行 排序，為下一步選擇操作做準備。i++) （ nGroupSize 是 城市 之間 的距離） TotalF+=1/oldpop[i].CalcCost(m_distance)。 圖 41系統(tǒng) 功能模塊圖 系 統(tǒng)詳細設(shè)計 由前 文 中介紹的個體編碼方法 及 各種遺傳算子可以構(gòu)成 許多種 不同的求解旅行商問題的遺傳算法，本系統(tǒng) 主要 利用這些遺傳算 子 對含有 45 座城市的旅行商問題進行了試算。 ●變異算子 使用 基本位 交換變異操作算子 ●運行參數(shù) {M， T， Pc， Pm}={0~500， 0~300， ~， ~}，式中 M 為群體大小， T 為終止代數(shù)， Pc 為交叉概率， Pm 為變異概率。 演示 模塊 設(shè)計 （ 1） 主窗口 設(shè)計： 在 VC 工具欄 insent 中插入窗口 IDD_CHINA45_DIALOG， 再在上面設(shè)置 變量 ，并進行初始化。 m_GACrossProb = 。 m_MiniCost = 。 變量與 對話框進行綁定： DDX_Text(pDX, IDC_EDIT1, m_GALen)。 DDX_Text(pDX, IDC_EDIT5, m_GANum)。 DDX_Text(pDX, IDC_EDIT9, m_VariNum)。 if(()==IDOK) { m_nGroupSize=。 （將 新 的 遺傳代數(shù) 賦值 給 對話框 ） UpdateData(false)。k1。 （ 3） 遺傳 算法參數(shù)設(shè)置窗口的 設(shè)計 ： 在菜單 遺傳算法設(shè)置下 插入 一個窗口IDD_DIALOG_SET,具體 設(shè)置如下表所示： 表 為工程添加 IDD_DIALOG_SET 的菜單選項 ID 說明文字 功能描述 IDC_EDIT2 群體規(guī)模 接受用戶 輸入 群體 規(guī)模 IDC_EDIT3 交叉概率 用戶 輸入 交叉 概率 IDC_EDIT4 變異概率 用戶 輸入變異概率 IDC_EDIT5 遺傳代數(shù) 用戶 輸入遺傳代數(shù) 然 后 拖入兩個按鈕， 分別 為確認和取消， 分別 設(shè)置功能名為 OnOK、 OnCancel， 分別可以在如下位置 添加 響應(yīng) 函數(shù) ： void CGASetDlg::OnCancel() { CDialog::OnCancel()。具體 代碼 如下圖所示： 21 void CChina45Dlg::DrawNetwork() { CPen Pen。 =+140。 pDCRectangle(Workarea)。 pDCSetTextColor(0x00F08080)。 =px+m_point[i].x2。（城市 位置 向下 兩個單位） pDCEllipse(city)。 (數(shù)據(jù)綁定 ,顯示關(guān)于軟件的信息 ) 再 拖入一個按鈕， 在此處可以 對其添加響應(yīng)函數(shù)： void CAboutDlg::OnOK() { // TODO: Add extra validation here CDialog::OnOK()。如上圖所示，以相同的參數(shù)連續(xù)執(zhí)行三次遺傳算法演示，最小費用不同，但相差 并 不是很大 。下 實驗結(jié)果分別如下圖所示 ： 25 圖 46 圖 47 26 圖 48 通過 對圖 4 8 可以 看出，算法經(jīng)過運算之后，其求解的結(jié)果有一 定 的更優(yōu)的趨勢， 但是 通過運算的計算時間卻大大的增加了，當種群數(shù)量小時的計算 時間短 ，但是當增加到 500 后 ，時間 明顯 感覺增加 ； 但 增加到 1000 后 ， 時間