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