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