【正文】 ............................................................................................ 17 演示模塊設(shè)計 ...................................................................................................................... 18 幫助模塊設(shè)計 ...................................................................................................................... 21 測試結(jié)果及分析 ................................................................................................................. 22 測試一 ................................................................................................................................. 22 測試二 ................................................................................................................................. 24 測試三 ................................................................................................................................. 26 測試四 ................................................................................................................................. 28 測試五 ................................................................................................................................. 29 5 結(jié)論 ....................................................................................................................................... 31 參考文獻 .................................................................................................................................... 32 謝 辭 ............................................................................................................ 錯誤 !未定義書簽。特別 適合 于求解傳統(tǒng)的搜索算法不好 處理 的 復(fù)雜的 最優(yōu)解問題 。目前求解TSP 問題的主要方法有模擬退火算法、遺傳算法、 Hopfield 神經(jīng)網(wǎng)絡(luò)算法、啟發(fā)式搜索法、二叉樹描述算法。遺傳算法固有的并行性和 并行 計算的能力 ，使 在搜索過程中不容易陷入局部最優(yōu) 。 應(yīng)用 遺傳算法求解旅行商問題最關(guān)鍵的 是 編碼方式、交叉、選擇、變異算子的設(shè)計， 直接 關(guān)系到算法 能否求出 最優(yōu)解 或 近似最優(yōu)解 。所以 當(dāng) 輸入越大，則 耗費的 時間就是個天文數(shù)字了，因此 旅行商問題至今都沒有 能 找到 一種 有效的求解方法。毫無疑問，高效、低成本、低能耗成了各個物流企業(yè)追求的目標(biāo)，更加合理的配送路線能明顯地為物流公司增大利潤 。 變異 算法采用的是基本位變異 3 法 ， 即 只是 根據(jù) 變異概率隨機改變?nèi)旧w中的某一 段 染色體， 具體會在后 文 中做詳細說明 。 第三 章 基于遺傳 算法求解 TSP 問題。 70 年代 De Jong 基于遺傳算法的思想在計算機上進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗 ， 建立了著名的 五 函數(shù)測試平臺。 5 1991 年編輯出版了《遺傳算法手冊 (Handbook of Geic Algorithms)》書中包括遺傳算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟中的大量應(yīng)用實例。 后代通常是前一代染色體通過交叉（ crossover） 或者 變異（ mutation ） 形成 。 下面給出生物學(xué)的幾個基本概念知 識，這對于理解遺傳算法很重要： 1）遺傳因子（ gene） :DNA 長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱基因。 6）選擇（ selection） :指以一定的概率從種群中選擇若干個體的操作。 11）染色體： 是生物細胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的主要載體，由多個遺傳因子 — 基因組成。 步驟四 ： 適應(yīng)度： 確定個體適應(yīng)度的量化評價方法， 適應(yīng)度 用于 衡 量種群中個體的優(yōu)劣性， 是確定 種群中個體留存的關(guān)鍵 。 數(shù)值 方法求解這一問題的主要手段是迭代運算。遺傳算法 從 串集開始搜索，覆蓋面大，有利于全局最優(yōu)。 （ 4） 遺傳 算法可以直接用于實際應(yīng)用當(dāng)中，對于給定的問題，可以產(chǎn)生許多解，最終選擇是根據(jù)用戶自己的需求來選取，通用性 高 ， 實際 應(yīng)用性強 ， 應(yīng)用范圍 廣 。 (3)生產(chǎn)調(diào)度問題 生產(chǎn)調(diào)度問題在很多情況下建立起來的傳統(tǒng)數(shù)學(xué)模難以精確求解，雖然經(jīng)過一些簡化之后可以進行求解 .也會因簡化得太多而使得求解結(jié)果與實際相差太大。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模 型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。迄今為止人們已經(jīng)提出了許多種不同的編碼方法。 二進制編碼存在著連續(xù)函數(shù)離散化時的映射誤差。 對于每個城市用一個整數(shù)來編號，例如有 45 個城市，就用 0 到 45 來標(biāo)識每一個城市，然后一個路徑就是一條染色體編碼，染色體長度為 45，如： 0,1,2,3,4...44 就是一個染色體，它表達的意思就是旅行者從 0 號城市出發(fā)，依次訪問 1,2,...44 號城市再回到0 號城市；下面 具體 具體 介紹一 下 這一種 編碼方法 。 由于 在確定算法的編碼方式的過程中使用的是 Grefenstette 等提出的 編碼方式，用這種編碼方式表示個體時，個體的 基因型 和表現(xiàn)型之間是一一對應(yīng)的， 它使 經(jīng)過運算之后得到的每一個基因型都是一條有 實際 意義的 巡回 路線。 //父代基因 1 int parent2=0。 PopNode pop2。 //交叉完成 ,保存結(jié)果 newpop[m_nGroupSize+2*i].CopyNode(amp。適應(yīng)度越高的個體被選中的概率也越大；反之，適應(yīng)度越低的個體被選中的概率也越小。im_nGroupSize。j++) if(oldpop[j].fitmax) { max=oldpop[j].fit。 m_GAFitness=。oldpop[i])?；疚蛔儺愃阕拥膱?zhí)行過程如下： 15 （ 1）對個體的每一個基因座，依變異概率 Pm 指定其為變異點。 （ 取 其中 第三位與 倒數(shù)第三位做 nPos2=RandomInt(3,MAXCHROM3)。個體 的 適應(yīng)度越大，該個體被遺傳到下一代的概率也越大；反之，個體 的 適應(yīng)度越小，該個體被遺傳到下一代的概率也越小。 算法設(shè)計 模塊完成群體規(guī)模 M、交叉概率 Pc、變異概率 Pm 和進化代數(shù) T 的設(shè)置； 具體的 參數(shù)已經(jīng)設(shè)置在了演示平臺上，可以 根據(jù) 需要更改參數(shù)大小，但是盡量 在設(shè)定的范圍之內(nèi) ， 這樣可以保證算法的 精確性 ；幫助模塊 則 設(shè)置了關(guān)于軟件和制作作者等查看項目。極端情況不可執(zhí)行。 m_GANum = 100。 DDX_Text(pDX, IDC_EDIT3, m_GACrossProb)。 打開類向?qū)В?Class Wizard）對話框向主對話框類添加響應(yīng)函數(shù)，用于 顯示新生成的群體規(guī)模、交叉變異數(shù)目等。 oldpop=new PopNode[m_nGroupSize]。 } (4)設(shè)置 屏幕顯示函數(shù) ， 在主窗 口 上 選出一片 區(qū)域， 作為 地圖，用于存放城市位置。 =+290。iMAXCHROM。 (執(zhí)行數(shù)據(jù)綁定的功能 ,用于顯示關(guān)于作者信息 ) 再 拖入一個按鈕， 在此處可以 對其 添加 函數(shù) 聲明， 該函數(shù)執(zhí)行確定操作 ： void CAuthDlg::OnOK() { // TODO: Add extra validation here 22 CDialog::OnOK()。 測試二 如圖 4 4 4 48 所示 ，本次測試的分別設(shè)置了 {M， T， Pc， Pm}={500， 100， }， {M， T， Pc， Pm}={1000， 100， ， }。 經(jīng)過 算法運算之后 ，結(jié)果 如下圖所示 ： 圖 42 23 圖 43 圖 44 24 圖 45 通過對圖 4 4 44 的分析可知，由于本次 試算設(shè)置的 群體大小、交叉概率、變異概率、進化代數(shù)這幾個參數(shù) 都在規(guī)定 范圍內(nèi)，通過運行，算法運行到指定的進化代數(shù)之后停止運行，并輸出 了 當(dāng)前群體中的最小費用路徑 的 大小，即 城市 路徑總長度最短者。（城市 位置 向右 兩個單位） =pym_point[i].y2。 int px=。 CRect RectClient,Workarea。 } （ 2） 主窗口 菜單設(shè)置： 在 菜單欄中需要做三個 選項 ： 文件 、 設(shè)置 和幫助 。 （將 新的交叉概率 賦值 給 對話框 ） m_GAVariProb=。 DDX_Text(pDX, IDC_EDIT7, m_MiniCost)。 m_VariNum = 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 群體適應(yīng)度 顯示群體 適應(yīng)度 表 （ 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 群體 適應(yīng)度 初始化 參數(shù)設(shè)置代碼如下： m_GALen = 45。 ●適應(yīng)度函數(shù) 系統(tǒng)中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值。具體代碼如下所示 ： for(int i=0。 (nPos1,nPos2)。例如： 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。本系統(tǒng)中變異算子采用基本位變異算子。 if (m_CurGANum == m_GANum 1) { // 繪制圖形 DrawNetwork()。 } m_CurGANum=gen。i++) { double max=。gen++) { // 計算當(dāng)前一代群體中個體的適應(yīng)度數(shù)值 F for(int i=0。 選擇 算子 選擇操作是建立在對個體適應(yīng)度進行評價的基礎(chǔ)之上的。oldpop[parent2])。 parent2=RandomInt(0,m_nG