【正文】 如上圖所示，以相同的參數(shù)連續(xù)執(zhí)行三次遺傳算法演示，最小費(fèi)用不同，但相差 并 不是很大 。（城市 位置 向下 兩個單位） pDCEllipse(city)。 pDCSetTextColor(0x00F08080)。 =+140。 （ 3） 遺傳 算法參數(shù)設(shè)置窗口的 設(shè)計 ： 在菜單 遺傳算法設(shè)置下 插入 一個窗口IDD_DIALOG_SET,具體 設(shè)置如下表所示： 表 為工程添加 IDD_DIALOG_SET 的菜單選項(xiàng) ID 說明文字 功能描述 IDC_EDIT2 群體規(guī)模 接受用戶 輸入 群體 規(guī)模 IDC_EDIT3 交叉概率 用戶 輸入 交叉 概率 IDC_EDIT4 變異概率 用戶 輸入變異概率 IDC_EDIT5 遺傳代數(shù) 用戶 輸入遺傳代數(shù) 然 后 拖入兩個按鈕， 分別 為確認(rèn)和取消， 分別 設(shè)置功能名為 OnOK、 OnCancel， 分別可以在如下位置 添加 響應(yīng) 函數(shù) ： void CGASetDlg::OnCancel() { CDialog::OnCancel()。 （將 新 的 遺傳代數(shù) 賦值 給 對話框 ） UpdateData(false)。 DDX_Text(pDX, IDC_EDIT9, m_VariNum)。 變量與 對話框進(jìn)行綁定： DDX_Text(pDX, IDC_EDIT1, m_GALen)。 m_GACrossProb = 。 ●變異算子 使用 基本位 交換變異操作算子 ●運(yùn)行參數(shù) {M， T， Pc， Pm}={0~500， 0~300， ~， ~}，式中 M 為群體大小， T 為終止代數(shù)， Pc 為交叉概率， Pm 為變異概率。i++) （ nGroupSize 是 城市 之間 的距離） TotalF+=1/oldpop[i].CalcCost(m_distance)。pop)。i++) { int nPos1,nPos2,parent=0。 因?yàn)?使用由 Grefenstette 等所提出的編譯方法來表示個體，一個個 體經(jīng)過遺傳運(yùn)算后所得到的任意一個基因型個體 與交叉后的情況相同， 都能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線 。im_nGroupSize。 (amp。 for(int j=i。i++) TotalF+=1/oldpop[i].CalcCost(m_distance)。本課題采用最常用的選擇算子 —— 比例選擇算子（又 稱輪盤賭選擇） 。 (amp。 if(parent2temp) parent2=temp。i++) { int nPos, temp=0。 求解 旅行商 問題的遺傳算法的交叉算法主要有：部分匹配交叉（ PMX） 、 循環(huán)交叉（ CX） 、次序 交叉（ OX） 、線性次序 交叉（ LOX） 、 邊重組交叉（ EX） 等 。 但對于使用符號編碼方法的遺傳算法，一般需要 認(rèn)真設(shè)計交叉、變異等遺傳運(yùn)算的操作方法，以滿足問題的各種約束需 求，這樣才能提高算法的搜索性能。而格雷碼能有效地防止這類現(xiàn)象。 方式 編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計遺傳算法時的一個關(guān)鍵步驟。人工生命與遺傳算法有著密切的關(guān)系。例如，遺傳算法已經(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)用。對于 這一類 復(fù)雜的 問題 ， 遺傳 算法 已經(jīng) 被證實(shí)是十分有效的求解方式 。 這種 通過自然選擇與進(jìn)化的機(jī)制消除了算法設(shè)計過程中的一個最大 障礙，即需要事先描述問題的 全部 特點(diǎn)， 并 要 說明 針對 所求 問題的不同 特點(diǎn)， 我們設(shè)計的算法應(yīng)該采用的具體 措施 。這是 遺傳算法與 傳統(tǒng)優(yōu)化算法的 最 大區(qū)別。給定最大的遺傳代數(shù)，算法在計算到最大的遺傳代數(shù)時，終止計算。 所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。 基因 操作是在 結(jié)構(gòu) 空間中進(jìn)行的。生物的進(jìn)化是以種群的形式進(jìn)行的。而遺傳算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。在 每一代 中應(yīng)用適應(yīng)度（ fitness） 來 測量染色體的優(yōu)越性 ， 適應(yīng)度 高的 更容易在自然的選擇中 存活 下來。 3 Jong 1975 年在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計算實(shí)驗(yàn)，樹立了遺傳算法的工作框架，定義了評價遺傳算法性能的在線指標(biāo)和離線指標(biāo)。 4 2 遺傳算法 理論 概述 遺傳 算法的 產(chǎn)生 及發(fā)展 最早由美國 Michigan(密執(zhí)安大學(xué) )的 Hollang 教授提出，起源于 60 年代對自然和人工自適應(yīng)系統(tǒng)的研究。 第二章遺傳算法理論 概述 。 本文 采用的 是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，其 可以在一定程度上克服 常規(guī)巡回路線編碼方法 在 交 異操作時易 產(chǎn)生 不滿足問題約束條件或無實(shí)際意義的巡回路線 的 缺點(diǎn) 。 其次 ， 隨著旅游業(yè)的快速發(fā)展，大量的旅客在旅途中浪費(fèi)了不必要的時間和金錢，而這些不必要的浪費(fèi)完全可以通過對旅行路線的合理規(guī)劃來避免。 旅行商 問題就是要解決 一個 最小回路問題，回路中所有頂點(diǎn)有且僅經(jīng)過一次 。 因?yàn)?遺傳算法本 身 是模擬生物自然選擇 和遺傳的 過程的， 所以 用遺傳算法求解 TSP 最先要 確定 的 是問題的建模 ， 即如何用 遺傳學(xué)的 算子來表示旅行商問題中的變量 。 附錄一程序 ................................................................................................................................ 33 附錄二外文翻譯 ......................................................................................... 錯誤 !未定義書簽。旅行商 問題（ Traveling Salesman Problem） 就是 要決定一條經(jīng)過 路線中 所 有城市當(dāng) 且僅當(dāng)一次且距離最短的路線，即距離最短的 Hamilton 回路 。旅行商 問題是一個具有十分廣泛的 實(shí)用 背景 和 重要理論 價值 的組合優(yōu)化問題 。 1 1 緒論 自 20 世紀(jì) 60 年代以來 ,一種模擬生物自然遺傳與進(jìn)化過程并將生物進(jìn)化原理、最優(yōu)化技術(shù)和 計算機(jī)技術(shù)結(jié)合起來的優(yōu)化方法 —遺傳算法 （ Geic Algorithm,簡稱 GA） 被 提出并得到 廣泛 研究， 該 算法 特別適 用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性 問題 ，可以廣泛 應(yīng) 用于人工智能、 機(jī)械 設(shè)計 、自適應(yīng)控制等領(lǐng)域。必 需要 非常的了解 ，并 熟悉 每一個 遺傳學(xué) 中的 術(shù)語 在遺傳學(xué)中的具體作用， 然后 應(yīng)用 到 求解具體問題當(dāng)中來。對于 具有一個城市的旅行商問題，其可能的路徑 數(shù)目 為（ n1） ！ /2， 5 個 城市 的問題 模型就對應(yīng) 120/10=12 條 路線， 10 個 城市的問題模型對應(yīng) 3628800/20=181440 條 路線。而在互聯(lián)網(wǎng)繼續(xù)擴(kuò)大普及的時代，電子商務(wù)也迎來了期待已久的春天，同時物流產(chǎn)業(yè)也隨之水漲船高。交叉算法 采用的是常規(guī)的單點(diǎn)交叉， 之所以 可以用這一常規(guī)的交叉法，是因?yàn)樵诰幋a方式上使用的是 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，它 可以最大化交叉后后代 與 其 父 代的性狀 差異 ，有利于算法的全局性。 這一章 主要 論述遺傳算法的 起源 發(fā) 展 及其實(shí)際應(yīng)用 ，重點(diǎn)介紹了遺傳算法的 算法原理 及 步驟 。 1967 年 ，他的學(xué)生 Bagley 提出 “遺傳 算法 ”一詞 ，并發(fā)展了復(fù)制、交叉 、 變異、顯性、倒位 等 遺傳算子。 4 1989 年出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法 (Geic Algorithms in Search，Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。生存 下來的 染色體被稱為后代 （ offspring） 。（另外，值得注意的是遺傳算法不一定要找 “最高的山峰 ”，如果問題的適應(yīng)度評價越小越好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對應(yīng)的，遺傳算法所要找的就是 “最深的谷底 ”） 。 5）適應(yīng)度（ fitness） :度量某個物種對于生存環(huán)境的適應(yīng)程度。 串 結(jié)構(gòu)空間 對 應(yīng)用 于遺傳學(xué) 中的基因 型 的 集合 。遺傳算法中起核心作用的就是交叉算子。 遺傳 算法 算法 流程圖 開始編碼初始化染色體種群計算每個染色體的適應(yīng)度滿足終止條件根據(jù)適應(yīng)度選擇交叉變異輸出最優(yōu)解是否 7 圖 24 遺傳 算法算法流程圖 遺傳 算法的特點(diǎn) 遺傳算法 屬于進(jìn)化算法 （ Evolutionary Algorithms） 的 一種，它通過模仿自然界的選擇與 遺傳的原理來求出最優(yōu)解，遺傳算法 有 三個 最 基本的算子：選擇、交叉、變異。傳統(tǒng) 優(yōu)化 算法從單個初始值迭代求最優(yōu)解，容易 早熟 陷入局部最優(yōu)解。 所以 ， 遺傳算法有很高的容錯能力 ，我 們 可以 利用 遺傳算法 解決復(fù)雜的 非 結(jié)構(gòu)化問題。 遺傳 算法 已經(jīng)在求解 TSP 問題、 01 背包 問題、 圖形 劃分問題等方面得到了成功的應(yīng)用。 （ 5）數(shù)據(jù) 挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則?；谶z傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。因?yàn)榫幋a方法將會影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法，很大 的程度上決定了遺傳進(jìn)化的效率。 ： 對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，使用二進(jìn)制編碼來表示個體時將會有一些不利之處。 使用遺傳算法第一件事情就是確定染色編碼方式，它根據(jù)不同的問 題模型使用不同 的編碼方式，本系統(tǒng) 使用的是 Grefenstette 等提出 的 一種新的巡回路線編碼方法， 是 一種 整數(shù)編碼的方式 。 本 系統(tǒng)使用的是常規(guī)的 單點(diǎn) 交叉算子 。 int parent1=0。 //復(fù)制用于交叉的基因?qū)? PopNode pop1。pop2, nPos)。其基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比。 // 歸一化 F 值 for(i=0。jm_nGroupSize。oldpop[0])。i++) newpop[i].CopyNode(amp。 對于二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為 0，則將其變?yōu)?1；反之，若原有基因值為 1，則將其變?yōu)?0 。 //變異父代基因 parent=RandomInt(0,m_nGroupSize1) （ 定義 變異范圍 ） nPos1=RandomInt(3,MAXCHROM3)。（ 保存變異結(jié)果 ） } 適應(yīng)度函數(shù) 在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。（父代 結(jié)點(diǎn)的城市距離的倒數(shù)作為它的適應(yīng)度） 遺傳算法求解 TSP問題的具體流程圖 16 圖 35 遺傳算法 求解旅行商問題的具體流程圖 開始產(chǎn)生城市對城市進(jìn)行編碼初始化遺傳算法相關(guān)參數(shù)計算個體適應(yīng)度是否符合終止條件 ？輸出正確的T S P 結(jié)果比例選擇算法常規(guī)單點(diǎn)交叉基本位變異算法G E N = G E N + 1是否 17 4 45個城市旅行商問題 的仿真軟件的 設(shè)計 系統(tǒng) 設(shè)計模塊 本系統(tǒng)在 Microsoft Visual C++環(huán)境下完成，根據(jù)需求設(shè)計了三大模塊： 算法 設(shè)計模塊、演示模塊、幫助模塊。本系統(tǒng)給出各個參數(shù)的參考范圍，在此范圍內(nèi)執(zhí)行搜索 最佳 ，超出范圍也可演示，但這會影響搜索效果，可能得不到最優(yōu)解或近似最優(yōu)解。 m_GAVariProb = 。 DDX_Text(pDX, IDC_EDIT2, m_nGroupSize)。 DDX_Text(pDX, IDC_EDIT10, m_GAFitness)。 } 20 } 在 主窗口上拖 一個按鈕進(jìn)去， 按鈕名 為 OnButtonGa(遺傳算法演示按鈕 )并對其添加 響應(yīng) 函數(shù)聲明 ,該函數(shù)執(zhí)行最短路徑更新的操作 ,即執(zhí)行一次算法 ,顯示一次運(yùn)算結(jié)果 ： void CChina45Dlg::OnButtonGa() { PopNode *oldpop。 } void CGASetDlg::OnOK() { CDial