【正文】 測(cè)試二 如圖 4 4 4 48 所示 ，本次測(cè)試的分別設(shè)置了 {M， T， Pc， Pm}={500， 100， }， {M， T， Pc， Pm}={1000， 100， ， }。 經(jīng)過 算法運(yùn)算之后 ，結(jié)果 如下圖所示 ： 圖 42 23 圖 43 圖 44 24 圖 45 通過對(duì)圖 4 4 44 的分析可知，由于本次 試算設(shè)置的 群體大小、交叉概率、變異概率、進(jìn)化代數(shù)這幾個(gè)參數(shù) 都在規(guī)定 范圍內(nèi)，通過運(yùn)行，算法運(yùn)行到指定的進(jìn)化代數(shù)之后停止運(yùn)行，并輸出 了 當(dāng)前群體中的最小費(fèi)用路徑 的 大小，即 城市 路徑總長(zhǎng)度最短者。 (執(zhí)行數(shù)據(jù)綁定的功能 ,用于顯示關(guān)于作者信息 ) 再 拖入一個(gè)按鈕， 在此處可以 對(duì)其 添加 函數(shù) 聲明， 該函數(shù)執(zhí)行確定操作 ： void CAuthDlg::OnOK() { // TODO: Add extra validation here 22 CDialog::OnOK()。（城市 位置 向右 兩個(gè)單位） =pym_point[i].y2。iMAXCHROM。 int px=。 =+290。 CRect RectClient,Workarea。 } (4)設(shè)置 屏幕顯示函數(shù) ， 在主窗 口 上 選出一片 區(qū)域， 作為 地圖，用于存放城市位置。 } （ 2） 主窗口 菜單設(shè)置： 在 菜單欄中需要做三個(gè) 選項(xiàng) ： 文件 、 設(shè)置 和幫助 。 oldpop=new PopNode[m_nGroupSize]。 （將 新的交叉概率 賦值 給 對(duì)話框 ） m_GAVariProb=。 打開類向?qū)В?Class Wizard）對(duì)話框向主對(duì)話框類添加響應(yīng)函數(shù)，用于 顯示新生成的群體規(guī)模、交叉變異數(shù)目等。 DDX_Text(pDX, IDC_EDIT7, m_MiniCost)。 DDX_Text(pDX, IDC_EDIT3, m_GACrossProb)。 m_VariNum = 0。 m_GANum = 100。 表 IDD_CHINA45_DIALOG 的菜單選項(xiàng) ID 說明文字 功能描述 IDC_EDIT1 城市數(shù)目 顯示城市數(shù)量 IDC_EDIT2 群體規(guī)模 顯示群體規(guī)模 IDC_EDIT3 交叉概率 顯示 交叉概率 IDC_EDIT4 變異概率 顯示 變異概率 IDC_EDIT5 遺傳代數(shù) 顯示 遺傳代數(shù) IDC_EDIT6 進(jìn)化代數(shù) 顯示 進(jìn)化代數(shù) IDC_EDIT7 最小費(fèi)用 顯示最小 費(fèi)用 IDC_EDIT8 交叉數(shù)目 顯示 交叉數(shù)目 IDC_EDIT9 變異數(shù)目 顯示 變異數(shù)目 IDC_EDIT10 群體適應(yīng)度 顯示群體 適應(yīng)度 表 （ ClassView）選項(xiàng)卡，向主對(duì)話框添加成員變量 變量類型 變量名 功能描述 int m_GALen 城市 數(shù)量 int m_nGroupSize 群體 規(guī)模大小 double m_GACrossProb 交叉 概率 double m_GAVariProb 變異 概率 int m_GANum 遺傳 代數(shù) int m_CurGANum 進(jìn)化 代數(shù) double m_MiniCost 最小 費(fèi)用 int m_CrossNum 交叉 數(shù)目 19 int m_VariNum 變異 數(shù)目 double m_GAFitness 群體 適應(yīng)度 初始化 參數(shù)設(shè)置代碼如下： m_GALen = 45。極端情況不可執(zhí)行。 ●適應(yīng)度函數(shù) 系統(tǒng)中以每條路徑長(zhǎng)度的倒數(shù)作為適應(yīng)度函數(shù)值。 算法設(shè)計(jì) 模塊完成群體規(guī)模 M、交叉概率 Pc、變異概率 Pm 和進(jìn)化代數(shù) T 的設(shè)置； 具體的 參數(shù)已經(jīng)設(shè)置在了演示平臺(tái)上，可以 根據(jù) 需要更改參數(shù)大小，但是盡量 在設(shè)定的范圍之內(nèi) ， 這樣可以保證算法的 精確性 ；幫助模塊 則 設(shè)置了關(guān)于軟件和制作作者等查看項(xiàng)目。具體代碼如下所示 ： for(int i=0。個(gè)體 的 適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體 的 適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。 (nPos1,nPos2)。 （ 取 其中 第三位與 倒數(shù)第三位做 nPos2=RandomInt(3,MAXCHROM3)。例如： 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。基本位變異算子的執(zhí)行過程如下： 15 （ 1）對(duì)個(gè)體的每一個(gè)基因座，依變異概率 Pm 指定其為變異點(diǎn)。本系統(tǒng)中變異算子采用基本位變異算子。oldpop[i])。 if (m_CurGANum == m_GANum 1) { // 繪制圖形 DrawNetwork()。 m_GAFitness=。 } m_CurGANum=gen。j++) if(oldpop[j].fitmax) { max=oldpop[j].fit。i++) { double max=。im_nGroupSize。gen++) { // 計(jì)算當(dāng)前一代群體中個(gè)體的適應(yīng)度數(shù)值 F for(int i=0。適應(yīng)度越高的個(gè)體被選中的概率也越大；反之，適應(yīng)度越低的個(gè)體被選中的概率也越小。 選擇 算子 選擇操作是建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上的。 //交叉完成 ,保存結(jié)果 newpop[m_nGroupSize+2*i].CopyNode(amp。oldpop[parent2])。 PopNode pop2。 parent2=RandomInt(0,m_nGroupSize1)。 //父代基因 1 int parent2=0。 如下 是具體代碼： for(i=0。 由于 在確定算法的編碼方式的過程中使用的是 Grefenstette 等提出的 編碼方式，用這種編碼方式表示個(gè)體時(shí)，個(gè)體的 基因型 和表現(xiàn)型之間是一一對(duì)應(yīng)的， 它使 經(jīng)過運(yùn)算之后得到的每一個(gè)基因型都是一條有 實(shí)際 意義的 巡回 路線。 算子的設(shè)計(jì)（ 交叉 、選擇、變異） 交叉 算子 交叉運(yùn)算，一般 指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。 對(duì)于每個(gè)城市用一個(gè)整數(shù)來編號(hào)，例如有 45 個(gè)城市，就用 0 到 45 來標(biāo)識(shí)每一個(gè)城市，然后一個(gè)路徑就是一條染色體編碼，染色體長(zhǎng)度為 45，如： 0,1,2,3,4...44 就是一個(gè)染色體，它表達(dá)的意思就是旅行者從 0 號(hào)城市出發(fā)，依次訪問 1,2,...44 號(hào)城市再回到0 號(hào)城市；下面 具體 具體 介紹一 下 這一種 編碼方法 。 浮點(diǎn)數(shù)編碼方法有下面幾個(gè)優(yōu)點(diǎn)： （ 1)適用于在遺傳算法中表示范圍較大的數(shù) （ 2)適用于精度要求較高的遺傳算法 （ 3)便于較大空間的遺傳搜索 （ 4)改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算交率 （ 5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用 （ 6)便于設(shè)計(jì)針對(duì)問題的專門知識(shí)的知識(shí)型遺傳算子 （ 7)便于處理復(fù)雜的決策變量約束條件 ： 符號(hào)編碼法是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義、而只有代碼含義的符號(hào)集如｛ A,B,C?｝。 二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。它有以下一些優(yōu)點(diǎn)： (1）編碼、解碼操作簡(jiǎn)單易行 (2)交叉、變異等遺傳操作便于實(shí)現(xiàn) (3)符合最小字符集編碼原則 (4)利用模式定理對(duì)算法進(jìn)行理論分析。迄今為止人們已經(jīng)提出了許多種不同的編碼方法。要求得的路徑路程為所有可能路徑之中的最小值， 即 最優(yōu)值問題 。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模 型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。 （ 6）人工 生命 人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。 （ 4）機(jī)器人 學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)， 而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。 (3)生產(chǎn)調(diào)度問題 生產(chǎn)調(diào)度問題在很多情況下建立起來的傳統(tǒng)數(shù)學(xué)模難以精確求解，雖然經(jīng)過一些簡(jiǎn)化之后可以進(jìn)行求解 .也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差太大。對(duì)于 這些 非線性、 求 極 值、 多模型或 多目標(biāo)的 函數(shù) 優(yōu)化 問題，用傳統(tǒng)的優(yōu)化方法很難解決，而用遺傳算法可以 方便地 得到 較好的結(jié)果。 （ 4） 遺傳 算法可以直接用于實(shí)際應(yīng)用當(dāng)中，對(duì)于給定的問題，可以產(chǎn)生許多解，最終選擇是根據(jù)用戶自己的需求來選取，通用性 高 ， 實(shí)際 應(yīng)用性強(qiáng) ， 應(yīng)用范圍 廣 。 （ 3） 遺傳算法 不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo) 它 的搜索方向 ，具有 自組織 、自適應(yīng)和自學(xué)習(xí)性。遺傳算法 從 串集開始搜索，覆蓋面大，有利于全局最優(yōu)。 主要有 以 下幾點(diǎn)： （ 1） 遺傳 算法的本質(zhì)并行性。 數(shù)值 方法求解這一問題的主要手段是迭代運(yùn)算。 變異 操作可以保證 算法 過程中不會(huì)產(chǎn)生無法進(jìn)化的單一群體， 避免 算法 早熟 出現(xiàn) 局部最優(yōu)。 步驟四 ： 適應(yīng)度： 確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法， 適應(yīng)度 用于 衡 量種群中個(gè)體的優(yōu)劣性， 是確定 種群中個(gè)體留存的關(guān)鍵 。參數(shù) N 可以根據(jù) 具體的情況 而定 。 11）染色體： 是生物細(xì)胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的主要載體，由多個(gè)遺傳因子 — 基因組成。 9）串（ String） :它是 個(gè)體的 形式 ，在算法 中 為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué) 中 的染色體。 6）選擇（ selection） :指以一定的概率從種群中選擇若干個(gè)體的操作。 4）進(jìn)化（ evolution） 。 下面給出生物學(xué)的幾個(gè)基本概念知 識(shí)，這對(duì)于理解遺傳算法很重要： 1）遺傳因子（ gene） :DNA 長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱基因。在這個(gè)多維曲面里面也有數(shù)不清的 “山峰 ”，而這些最優(yōu)解所對(duì)應(yīng)的就 是 這些山峰 ， 這些山峰就是局部最優(yōu)解 。 后代通常是前一代染色體通過交叉（ crossover） 或者 變異（ mutation ） 形成 。在 遺傳算法中，種群中的 每一個(gè) 個(gè)體是問題的一個(gè) 解 ， 稱為“染色體”， 染色體是 一串 符號(hào)，比如二進(jìn)制的 01 串 。 5 1991 年編輯出版了《遺傳算法手冊(cè) (Handbook of Geic Algorithms)》書中包括遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量應(yīng)用實(shí)例。 下面 是一些在遺傳算法發(fā)展 進(jìn)程 中做出 杰出 貢獻(xiàn)的 人物 ： 1 60 年代提出在研究和設(shè)計(jì)人工自適應(yīng)系統(tǒng)時(shí) ,可以借鑒生物遺傳的機(jī)制； 70 年代初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)； 80 年代實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)系統(tǒng)－分類器系統(tǒng) (Classifier Systems),開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念 。 70 年代 De Jong 基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn) ， 建立了著名的 五 函數(shù)測(cè)試平臺(tái)。 第五 章結(jié)論 。 第三 章 基于遺傳 算法求解 TSP 問題。 本文 的結(jié)構(gòu) 本文 一共分為 5 章 ， 結(jié)構(gòu) 如下： 第一章緒論 。 變異 算法采用的是基本位變異 3 法 ， 即 只是 根據(jù) 變異概率隨機(jī)改變?nèi)旧w中的某一 段 染色體， 具體會(huì)在后 文 中做詳細(xì)說明 。 遺傳算法（ Geic Algorithms,GA） 又叫 基因進(jìn)化算法或進(jìn)化算法 ，是 一種通過模擬自然界生物 適者生存 、優(yōu)勝劣 汰的 進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機(jī)搜索算法。毫無疑問，高效、低成本、低能耗成了各個(gè)物流企業(yè)追求的目標(biāo)，更加合理的配送路線能明顯地為物流公司增大利潤(rùn) 。 1980Crowder和 Padberg 求解 了 318 個(gè) 城市的 TSP 問題； 1987 年 Padberg 和 Rinaldi 成功 將城市數(shù)量增加到了 2392 個(gè) ； 最大的 成功求解的旅行 商問題 已經(jīng) 增加 到 24798 個(gè) 城市。所以 當(dāng) 輸入越大，則 耗費(fèi)的 時(shí)間就是個(gè)天文數(shù)字了，因此 旅行商問題至今都沒有 能 找到 一種 有效的求解方法。雖然它是一個(gè)比較古老的問題，最早可以追溯到 Euler 提出的騎士旅行問題，但同時(shí)它也是一個(gè)新的問題，因?yàn)樗挠?jì)算復(fù)雜度 較高， 雖然人們一直在嘗試用新的方法來改進(jìn)求解該問題的復(fù)雜度，但是 這一類問題 距今 都沒有能找到一個(gè)有效的算法來解決 。 應(yīng)用 遺傳算法求解旅行商問題最關(guān)鍵的 是 編碼方式、交叉、選擇、變異算子的設(shè)計(jì)， 直接 關(guān)系到算法 能否求出 最優(yōu)解 或 近似最優(yōu)解 。 TSP 問題其實(shí)是“ 哈密頓回路問題 ”中的“哈密頓最短 回路問