【正文】 { CDialog::OnOK()。 =。 for(int i=0。（以城市 位置為圓心畫圓） } 幫助 模塊設(shè)計 （ 1） 關(guān)于 作者： 在 VC 工具欄 insent 中插入窗口 ,窗口 ID 為 IDD_AUTH， 并對 其添加如下操作： protected: virtual void DoDataExchange(CDataExchange* pDX)。 但是從 圖 45 可以 看出此次運算的結(jié)果偏大 許 多， 這 就 體現(xiàn)了 出了 遺傳算法的特點： 是 不斷搜索出適應(yīng)度較高的個體，并在群體中增加其數(shù)量，最終求出問題的最優(yōu)解或近似最優(yōu)解 ，所以其最后 的求解結(jié)果是有一定的波動的 ?；?本系統(tǒng) 使用的所有算法計算出了最短路徑的城市序列后，依次將兩兩城市之間路徑長度累加 就 得 到 最小費用路徑 ， 也就是城市最短路徑 。（城市 位置 向上 兩個單位） =pym_point[i].y+2。 int py=+20。 GetClientRect(RectClient)。 在 文件下面 繼續(xù)添加菜單 退出 ， 并設(shè)置 ID 為 ID_MENU_EXIT； 文件下邊添加 菜單 遺傳 算法 設(shè)置，設(shè)置 ID 為 ID_MENU_GASET； 幫助 下邊添加 菜單關(guān)于軟件和關(guān)于作者 ， 設(shè)置 ID 分別 為ID_MENU_SOFT、 ID_MENU_WRITE。 （將 新的 變異 概率 賦值 給 對話框 ） m_GANum=。 DDX_Text(pDX, IDC_EDIT8, m_CrossNum)。 m_GAFitness = 。 m_nGroupSize = 100。 ●選擇算子 基于遺傳算法的 TSP 問題仿真軟件設(shè)計 算法 設(shè)計模塊 演示模塊 幫助模塊 群 體 規(guī)模 交叉概率 變異概率 進化代數(shù) 關(guān)于作者 關(guān)于軟件 進化演示 18 采用 適應(yīng)度 比例法 ●交叉算子 采用 常規(guī) 單點交叉操作算子。im_nGroupSize。（ 執(zhí)行結(jié)點操作 ） newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(amp。im_VariNum。 基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。 } //繼承所有父代基因 for(i=0。 // 查找當前一代中的最小費用個體 m_MiniCost=oldpop[0].cost。 int maxpos。im_nGroupSize。選擇操作的目的是為了避免基因缺失、提高全局收斂性和計算效率。 13 // 基因序列中用于交叉的基因位 nPos=RandomInt(3,MAXCHROM3)。 temp=RandomInt(0,m_nGroupSize1)。im_CrossNum。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 符號編碼的主要優(yōu)點是： （ 1)符合有意義積術(shù)塊編碼原則 （ 2)便于在遺傳算法中利用所求解問題的專門知識 （ 3)便于遺傳算法與相關(guān)近似算法之間的混合使用。 二進制編碼的缺點是：對于一些連續(xù)函數(shù)的優(yōu)化問題，由 于其隨機性使得其局部搜索能力較差，如對于一些高精度的問題（如上題），當解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會遠離最優(yōu)解，達不到穩(wěn)定。 可以用如下公式表達 : n1 f(T)= ∑d(ti,ti+1)+d(nt,t1) i=1 本系統(tǒng)是 用遺傳算法求解 45 個 城市的旅行商問題， 并對其 進行計算機仿真，做出一個能在計算機 上 運行的軟件 。自組織能力和自學習能力是人工生命的兩大主要特 征。所以，機器人學理所當然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。 （ 2） 組合優(yōu)化 隨著 變量 n 的 不斷增大，問題的規(guī)模增大，組合優(yōu)化問題的求解空間也急劇增大， 應(yīng) 8 用 傳統(tǒng)的枚舉法等就很難求出最優(yōu)解。遺傳算法 利用 進化過程獲得信息自行組織搜索時，適應(yīng)度高的個體具有較高的生存率，并獲得更加適應(yīng)環(huán)境的 染色體 。 首先 ，遺傳算法并行的方式 是 從問題 解 的串 集 開始搜索，而不是從單個解開始。 步驟七 ： 終止 。 步驟三： 交叉算子：這是遺傳算法最重要的操作。 10）串 結(jié)構(gòu) 空間 （ ss） ： 在串中，基因任意組合所構(gòu)成的串集合。生物在其延續(xù)生命的過程中，逐漸適應(yīng)其生存環(huán)境使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進化。而其中也會有一個 “山峰 ”的海拔最高的，那么這個就是全局最優(yōu)解。這些 染色體 在后續(xù)的迭代中不斷的進化，稱為遺傳。 2 1967 年在其博士論文中首次提出了：“遺傳算法”一詞，發(fā)展了復制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應(yīng)遺傳算法的概念。對本文的內(nèi)容進行總結(jié)。這一章主要論述旅行商問題的基本概念，以及 本課題 主要的研究方法 及其 研究意義，并對論文的章節(jié)結(jié)構(gòu) 加以 論述。應(yīng)用 遺傳算法 求解 旅行商問題，最難得地方在于問題 建 模 ， 如 城市 編碼方式以及 交叉 、 變異 、 選擇算子的確定等。 意義 首先旅行商 問題是 用于 求解 N 個 城市 存在（ N1） 條 閉合路徑的排列方案， 對于 這一類 問題 很難用全局搜索法精確地求出最優(yōu)解， 這一問題 已經(jīng)困擾眾多 學者 許多年，因此研究相應(yīng)的算法尋找其最優(yōu)或近似最優(yōu)解是非常必要的。 2 TSP 問題可以形式化描述為：設(shè) G=（ V,A,D）是一個圖，其中 V 是 n 個頂點的集合，A 是弧線或邊集 ,D=（ ）是 與 A 關(guān)聯(lián) 的距離或費用矩陣。在 本系統(tǒng)就是要 應(yīng)用遺傳算法求解 45 個 城市的 TSP 問題 。 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 遺傳算法的應(yīng)用 ..................................................................................................................... 7 3 基于遺傳算法求解 TSP 問題 ........................................................................................ 9 旅行商問題的描述與建模 ...................................................................................................... 9 編碼方式 .................................................................................................................................. 9 遺傳算子的設(shè)計（交叉、選擇、變異） ............................................................................ 12 交叉算子 ............................................................................................................................. 12 選擇算子 ............................................................................................................................. 13 變異算子 ............................................................................................................................. 14 適應(yīng)度函數(shù) ........................................................................................................................... 15 遺傳算法求解 TSP 問題的具體流程圖 ............................................................................... 15 4 45 個城市旅行商問題的仿真軟件的設(shè)計 ............................................................... 17 系統(tǒng)設(shè)計模塊 ....................................................................................................................... 17 V 系統(tǒng)詳細設(shè)計 ........................