【正文】 這兩種 情況 分別 進行了兩次實驗。 但是從 圖 45 可以 看出此次運算的結(jié)果偏大 許 多， 這 就 體現(xiàn)了 出了 遺傳算法的特點： 是 不斷搜索出適應(yīng)度較高的個體，并在群體中增加其數(shù)量，最終求出問題的最優(yōu)解或近似最優(yōu)解 ，所以其最后 的求解結(jié)果是有 一定的波動的 ?；?本系統(tǒng) 使用的所有算法計算出了最短路徑的城市序列后，依次將兩兩城市之間路徑長度累加 就 得 到 最小費用路徑 ， 也就是城市最短路徑。 } 測試結(jié)果及分析 測試 一 如 下圖所示，本次測試的是默認的參數(shù) {M， T， Pc， Pm}={200， 100， ， }， 所取數(shù)值 都 在系統(tǒng)設(shè)置的參考范圍 之 內(nèi)。 } （ 2） 關(guān)于 軟件： 在 VC 工具欄 insent 中插入窗口 IDD_ABOUTBOX， 對其添加如下操作： enum { IDD = IDD_ABOUTBOX } (指定窗口 ID) protected: virtual void DoDataExchange(CDataExchange* pDX)。（以城市 位置為圓心畫圓） } 幫助 模塊設(shè)計 （ 1） 關(guān)于 作者： 在 VC 工具欄 insent 中插入窗口 ,窗口 ID 為 IDD_AUTH， 并對 其添加如下操作： protected: virtual void DoDataExchange(CDataExchange* pDX)。（城市 位置 向上 兩個單位） =pym_point[i].y+2。（城市 位置 向左 兩個單位） =px+m_point[i].x+2。i++) { CRect city。 for(int i=0。 int py=+20。 pDCSetBkColor(0x00FFFFFF)。 =。 =。 GetClientRect(RectClient)。 CDC* pDC=GetDC()。 為了便于 演示觀察，本系統(tǒng)將城市位置用圓圈表示出來 ，具體操作 是 ： 將 已知 城市的坐標點分別向上下左右移動兩個單位，并 以 城市位置作為圓心畫圓，這 樣 就在主窗口上的地圖區(qū)域確定了城市的位置。 } void CGASetDlg::OnOK() { CDialog::OnOK()。 在 文件下面 繼續(xù)添加菜單 退出 ， 并設(shè)置 ID 為 ID_MENU_EXIT； 文件下邊添加 菜單 遺傳 算法 設(shè)置，設(shè)置 ID 為 ID_MENU_GASET； 幫助 下邊添加 菜單關(guān)于軟件和關(guān)于作者 ， 設(shè)置 ID 分別 為ID_MENU_SOFT、 ID_MENU_WRITE。k++) { ExecGA(k, oldpop)。 for(int k=0。 } 20 } 在 主窗口上拖 一個按鈕進去， 按鈕名 為 OnButtonGa(遺傳算法演示按鈕 )并對其添加 響應(yīng) 函數(shù)聲明 ,該函數(shù)執(zhí)行最短路徑更新的操作 ,即執(zhí)行一次算法 ,顯示一次運算結(jié)果 ： void CChina45Dlg::OnButtonGa() { PopNode *oldpop。 （將 新的 變異 概率 賦值 給 對話框 ） m_GANum=。 （將新的 群體規(guī)模 賦值 給對話框） m_GACrossProb=。具體代碼如下： void CChina45Dlg::OnMenuGaset() { // TODO: Add your mand handler code here CGASetDlg dlg。 DDX_Text(pDX, IDC_EDIT10, m_GAFitness)。 DDX_Text(pDX, IDC_EDIT8, m_CrossNum)。 DDX_Text(pDX, IDC_EDIT6, m_CurGANum)。 DDX_Text(pDX, IDC_EDIT4, m_GAVariProb)。 DDX_Text(pDX, IDC_EDIT2, m_nGroupSize)。 m_GAFitness = 。 m_CrossNum = 0。 m_CurGANum = 0。 m_GAVariProb = 。 m_nGroupSize = 100。 具體 變量 及其窗口 對話框 設(shè)置如下表。 這些在上文中已作過詳細介紹 ,這里就不再重復(fù)。本系統(tǒng)給出各個參數(shù)的參考范圍，在此范圍內(nèi)執(zhí)行搜索 最佳 ，超出范圍也可演示，但這會影響搜索效果，可能得不到最優(yōu)解或近似最優(yōu)解。 ●選擇算子 基于遺傳算法的 TSP 問題仿真軟件設(shè)計 算法 設(shè)計模塊 演示模塊 幫助模塊 群 體 規(guī)模 交叉概率 變異概率 進化代數(shù) 關(guān)于作者 關(guān)于軟件 進化演示 18 采用 適應(yīng)度 比例法 ●交叉算子 采用 常規(guī) 單點交叉操作算子。 本系統(tǒng)中所使用的遺傳算法是 由 以下要素所構(gòu)成的： ●編碼方法 基本遺傳算法使用由 Grefenstette 所提出的編碼方法，詳細設(shè)計見第四章編碼方 式 一節(jié)。下圖是系統(tǒng)的功能模塊圖。（父代 結(jié)點的城市距離的倒數(shù)作為它的適應(yīng)度） 遺傳算法求解 TSP問題的具體流程圖 16 圖 35 遺傳算法 求解旅行商問題的具體流程圖 開始產(chǎn)生城市對城市進行編碼初始化遺傳算法相關(guān)參數(shù)計算個體適應(yīng)度是否符合終止條件 ？輸出正確的T S P 結(jié)果比例選擇算法常規(guī)單點交叉基本位變異算法G E N = G E N + 1是否 17 4 45個城市旅行商問題 的仿真軟件的 設(shè)計 系統(tǒng) 設(shè)計模塊 本系統(tǒng)在 Microsoft Visual C++環(huán)境下完成，根據(jù)需求設(shè)計了三大模塊： 算法 設(shè)計模塊、演示模塊、幫助模塊。im_nGroupSize。 為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應(yīng)度必須為正數(shù)或零，不能是負數(shù)。 因此適應(yīng)度函數(shù)的選擇至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。（ 保存變異結(jié)果 ） } 適應(yīng)度函數(shù) 在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。（ 執(zhí)行結(jié)點操作 ） newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(amp。oldpop[0])。 為變異結(jié)點 ） PopNode pop。 //變異父代基因 parent=RandomInt(0,m_nGroupSize1) （ 定義 變異范圍 ） nPos1=RandomInt(3,MAXCHROM3)。im_VariNum。 變異是單個個體內(nèi)部發(fā)生變化，導(dǎo)致產(chǎn)生新個體， 從而產(chǎn)生出一條新的巡回路線。 （ 2）對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產(chǎn)生出一個新個體。 對于二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為 0，則將其變?yōu)?1；反之，若原有基因值為 1，則將其變?yōu)?0 。 基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。交叉運算可以和變異運算相互配合，共同完成對搜索空間的全局搜索和局部搜索。 變異 算子 變異運算，是指改變個體編碼串中的某些基因值，從而形成新的個體。i++) newpop[i].CopyNode(amp。 } //繼承所有父代基因 for(i=0。 UpdateWindow()。 //AfxMessageBox(顯示數(shù)據(jù) )。oldpop[0])。 // 查找當前一代中的最小費用個 體 m_MiniCost=oldpop[0].cost。oldpop[maxpos])。 maxpos=j。jm_nGroupSize。 int maxpos。im_nGroupSize1。i++) oldpop[i].fit=1/oldpop[i].cost/TotalF*100。 // 歸一化 F 值 for(i=0。im_nGroupSize。genm_GANum。具體 操作如下： 計算出群體中每個個體的適應(yīng)度 f(i=1， 2，?， M)， M 為群體大小； 歸一化 適應(yīng)度 f 的值 將 適應(yīng)度 f 的 值從 大 到小排列， 查找 其中 最小 費 用 的個體 然后 將其作為 下一代 選擇出來。其基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比。選擇操作的目的是為了避免基因缺失、提高全局收斂 性和計算效率。pop2)。pop1)。pop2, nPos)。 13 // 基因序列中用于交叉的基因位 nPos=RandomInt(3,MAXCHROM3)。 (amp。 (amp。 //復(fù)制用于交叉的基因?qū)? PopNode pop1。 temp=RandomInt(0,m_nGroupSize1)。 if(parent1temp) parent1=temp。 //父代基因 2 parent1=RandomInt(0,m_nGroupSize1)。 int parent1=0。im_CrossNum。產(chǎn)生 下一代個體在使用 Grefenstette 等提出的 編碼方式 時 ， 染色體 編碼串 前面 的一 些 基因發(fā)生變化 時 ，會對后面的基因值 產(chǎn)生巨大 的影響 ，產(chǎn)生 的新的個體 與 上一代的性狀變化 就會 十分明顯，有利于整個算法 跳出 局部最優(yōu)解。因此 ， 就可以使用常規(guī)的單點交叉算子 。 本 系統(tǒng)使用的是常規(guī)的 單點 交叉算子 。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。例如 ， 假設(shè)現(xiàn)在有這樣一個城市序列： W=(A,B,C,D,E,F,G,H,I,J) 有 如下兩條 巡回 路線 ： T1=(A,D,B,H,F,I,J,G,E,C) T2=(B,C,A,D,E,J,H,I,F,G) 則按本 系統(tǒng)所用的編碼方法 ， 這兩 條 巡回路線可以編碼為： G1 =(1,3,1,5,3,4,4,3,2,1) 12 G2 =(2,2,1,1,1,5,3,3,1,1) 這種 編碼方式的 優(yōu)點 在于任意的染色體都對應(yīng)一條有實際意義的巡回路線， 因此 可以使用常規(guī)的交叉算子對它 進行 計算，有利于算 法的實現(xiàn)。 對于 給定的旅行商問題 ， 設(shè) 其 城市列表 W， 假定 對 各個 城市的 訪問順序為 T： T=（ T1， T2， T3， ….. ， Tn） 規(guī)定 每訪問完一個 城市， 就 從 城市列表 W 中 將 該城市 除去，則用第 i（ i=1,2,3……n ）個所訪問的城市 Ti 在所有未訪問城市列表 W={T1， T2， T3，? ..， Ti1}中的對應(yīng)位置序號 Gi（ 1≤ Gi≤ ni+1）就可表示具體訪問哪個城市，如此這樣直到處理完 W 中所有的城市。 使用遺傳算法第一件事情就是確定染色編碼方式，它根據(jù)不同的問 題模型使用不同 的編碼方式，本系統(tǒng) 使用的是 Grefenstette 等提出 的 一種新的巡回路線編碼方法， 是 一種 整數(shù)編碼的方式 。 符號編碼的主要優(yōu)點是： （ 1)符合有意義積術(shù)塊編碼原則 （ 2)便于在遺傳算法中利用所求解問題的專門知識 （ 3)便于遺傳算法與相關(guān)近似算法之間的混合使用。在浮點數(shù)編 10 碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)，遺傳算法中所使用的交叉、變異等 11 遺傳算子也必須保證其運算結(jié)果所產(chǎn)生的新個體的基因值也在這個區(qū)間限制范圍內(nèi)。個體長度較知時，可能達不到精度要求，而個體編碼長度較長時，雖然能提高精度，但卻使遺傳算法的搜索空間急劇擴大。 ： 對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，使用二進制編碼來表示個體時將會有一些不利之處。 二進制編碼的缺點是：對于一些連續(xù)函數(shù)的優(yōu)化問題，由于其隨機性使得其局部搜索能力較差，如對 于一些高精度的問題（如上題），當解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會遠離最優(yōu)解，達不到穩(wěn)定。 ： 它由二進制符號 0 和 1 所組成的二值符號集?？偟膩碚f，這些編碼方法可以分為三大類：二進制編碼法、浮點編碼法、符號編碼法。因為編碼方法將會影響到交叉算子、變異算子等遺傳算子的運算方法，很大 的程度上決定了遺傳進化的效率。 可以用如下公式表達 : n1 f(T)= ∑d(ti,ti+1)+d(nt,t1) i=1 本系統(tǒng)是 用遺傳算法求解 45 個 城市的旅行商問題， 并對其 進行計算機仿真，做出一個能在計算機 上 運行的軟件 。 它可以 大致