【正文】 Visual C++環(huán)境 ,采用 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，變異 算 子 采用了常規(guī)的 基本位變異 法 ， 通過 多 組實驗和數(shù)據(jù) 近似的 求解 出了 45 個 城市的最優(yōu)解， 實現(xiàn) 了計算機仿真求解 TSP 問題 。 MUTATION ALGORITHM。雖然它是一個比較古老的問題，最早可以追溯到 Euler 提出的騎士旅行問題，但同時它也是一個新的問題，因為它的計算復雜度 較高， 雖然人們一直在嘗試用新的方法來改進求解該問題的復雜度，但是 這一類問題 距今 都沒有能找到一個有效的算法來解決 。 遺傳算法（ Geic Algorithms,GA） 又叫 基因進化算法或進化算法 ，是 一種通過模擬自然界生物 適者生存 、優(yōu)勝劣 汰的 進化過程而形成的一種自適應、具有全局優(yōu)化能力的隨機搜索算法。 第五 章結(jié)論 。在 遺傳算法中，種群中的 每一個 個體是問題的一個 解 ， 稱為“染色體”， 染色體是 一串 符號，比如二進制的 01 串 。 4）進化（ evolution） 。參數(shù) N 可以根據(jù) 具體的情況 而定 。 主要有 以 下幾點： （ 1） 遺傳 算法的本質(zhì)并行性。對于 這些 非線性、 求 極 值、 多模型或 多目標的 函數(shù) 優(yōu)化 問題，用傳統(tǒng)的優(yōu)化方法很難解決，而用遺傳算法可以 方便地 得到 較好的結(jié)果。 （ 6）人工 生命 人工生命是用計算機、機械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。它有以下一些優(yōu)點： (1）編碼、解碼操作簡單易行 (2)交叉、變異等遺傳操作便于實現(xiàn) (3)符合最小字符集編碼原則 (4)利用模式定理對算法進行理論分析。 算子的設計（ 交叉 、選擇、變異） 交叉 算子 交叉運算，一般 指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。 parent2=RandomInt(0,m_nGroupSize1)。 選擇 算子 選擇操作是建立在對個體適應度進行評價的基礎(chǔ)之上的。i++) { double max=。 if (m_CurGANum == m_GANum 1) { // 繪制圖形 DrawNetwork()。例如： Tx=（ B C A D E J H I F G） （ B C A I E J H D F G） =Tx′ 具體 代碼如下 ： for(i=0。具體代碼如下所示 ： for(int i=0。 表 IDD_CHINA45_DIALOG 的菜單選項 ID 說明文字 功能描述 IDC_EDIT1 城市數(shù)目 顯示城市數(shù)量 IDC_EDIT2 群體規(guī)模 顯示群體規(guī)模 IDC_EDIT3 交叉概率 顯示 交叉概率 IDC_EDIT4 變異概率 顯示 變異概率 IDC_EDIT5 遺傳代數(shù) 顯示 遺傳代數(shù) IDC_EDIT6 進化代數(shù) 顯示 進化代數(shù) IDC_EDIT7 最小費用 顯示最小 費用 IDC_EDIT8 交叉數(shù)目 顯示 交叉數(shù)目 IDC_EDIT9 變異數(shù)目 顯示 變異數(shù)目 IDC_EDIT10 群體適應度 顯示群體 適應度 表 （ ClassView）選項卡，向主對話框添加成員變量 變量類型 變量名 功能描述 int m_GALen 城市 數(shù)量 int m_nGroupSize 群體 規(guī)模大小 double m_GACrossProb 交叉 概率 double m_GAVariProb 變異 概率 int m_GANum 遺傳 代數(shù) int m_CurGANum 進化 代數(shù) double m_MiniCost 最小 費用 int m_CrossNum 交叉 數(shù)目 19 int m_VariNum 變異 數(shù)目 double m_GAFitness 群體 適應度 初始化 參數(shù)設置代碼如下： m_GALen = 45。 DDX_Text(pDX, IDC_EDIT7, m_MiniCost)。 } （ 2） 主窗口 菜單設置： 在 菜單欄中需要做三個 選項 ： 文件 、 設置 和幫助 。 int px=。 經(jīng)過 算法運算之后 ，結(jié)果 如下圖所示 ： 圖 42 23 圖 43 圖 44 24 圖 45 通過對圖 4 4 44 的分析可知，由于本次 試算設置的 群體大小、交叉概率、變異概率、進化代數(shù)這幾個參數(shù) 都在規(guī)定 范圍內(nèi)，通過運行，算法運行到指定的進化代數(shù)之后停止運行，并輸出 了 當前群體中的最小費用路徑 的 大小，即 城市 路徑總長度最短者。 (執(zhí)行數(shù)據(jù)綁定的功能 ,用于顯示關(guān)于作者信息 ) 再 拖入一個按鈕， 在此處可以 對其 添加 函數(shù) 聲明， 該函數(shù)執(zhí)行確定操作 ： void CAuthDlg::OnOK() { // TODO: Add extra validation here 22 CDialog::OnOK()。 =+290。 oldpop=new PopNode[m_nGroupSize]。 DDX_Text(pDX, IDC_EDIT3, m_GACrossProb)。極端情況不可執(zhí)行。個體 的 適應度越大，該個體被遺傳到下一代的概率也越大；反之，個體 的 適應度越小，該個體被遺傳到下一代的概率也越小。基本位變異算子的執(zhí)行過程如下： 15 （ 1）對個體的每一個基因座，依變異概率 Pm 指定其為變異點。 m_GAFitness=。im_nGroupSize。 //交叉完成 ,保存結(jié)果 newpop[m_nGroupSize+2*i].CopyNode(amp。 //父代基因 1 int parent2=0。 對于每個城市用一個整數(shù)來編號，例如有 45 個城市，就用 0 到 45 來標識每一個城市，然后一個路徑就是一條染色體編碼，染色體長度為 45，如： 0,1,2,3,4...44 就是一個染色體，它表達的意思就是旅行者從 0 號城市出發(fā)，依次訪問 1,2,...44 號城市再回到0 號城市；下面 具體 具體 介紹一 下 這一種 編碼方法 。迄今為止人們已經(jīng)提出了許多種不同的編碼方法。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。 （ 4） 遺傳 算法可以直接用于實際應用當中，對于給定的問題，可以產(chǎn)生許多解，最終選擇是根據(jù)用戶自己的需求來選取，通用性 高 ， 實際 應用性強 ， 應用范圍 廣 。 數(shù)值 方法求解這一問題的主要手段是迭代運算。 11）染色體： 是生物細胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的主要載體，由多個遺傳因子 — 基因組成。 下面給出生物學的幾個基本概念知 識，這對于理解遺傳算法很重要： 1）遺傳因子（ gene） :DNA 長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱基因。 5 1991 年編輯出版了《遺傳算法手冊 (Handbook of Geic Algorithms)》書中包括遺傳算法在科學計算、工程技術(shù)和社會經(jīng)濟中的大量應用實例。 第三 章 基于遺傳 算法求解 TSP 問題。毫無疑問，高效、低成本、低能耗成了各個物流企業(yè)追求的目標，更加合理的配送路線能明顯地為物流公司增大利潤 。 應用 遺傳算法求解旅行商問題最關(guān)鍵的 是 編碼方式、交叉、選擇、變異算子的設計， 直接 關(guān)系到算法 能否求出 最優(yōu)解 或 近似最優(yōu)解 。目前求解TSP 問題的主要方法有模擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡算法、啟發(fā)式搜索法、二叉樹描述算法。 IV 目錄 遺傳算法求解 TSP 問題的計算機仿真 .............................................................................. II Abstract...................................................................................................................................... III 1 緒論 ......................................................................................................................................... 1 研究背景 ................................................................................................................................. 1 研究意義 ................................................................................................................................. 2 研究內(nèi)容 ................................................................................................................................. 2 本文的結(jié)構(gòu) ............................................................................................................................. 3 2 遺傳算法理論概述 ............................................................................................................. 4 遺傳算法的產(chǎn)生及發(fā)展 ......................................................................................................... 4 遺傳算法基本原理 ................................................................................................................. 5 遺傳算法基本步驟 ................................................................................................................. 6 遺傳算法算法流程圖 ............................................................................................................. 6 遺傳算法的特點 ..................................................................................................................... 7 遺傳算法的應用 ..................................................................................................................... 7 3 基于遺傳算法求解 TSP 問題 ........................................................................................ 9 旅行商問題的描述與建模 ...................................................................................................... 9 編碼方式 .................................................................................................................................. 9 遺傳算子的設計（交叉、選擇、變異） ............................................................................ 12 交叉算子 ............................................................................