【正文】 束需 求，這樣才能提高算法的搜索性能。 對(duì)于每個(gè)城市用一個(gè)整數(shù)來(lái)編號(hào)，例如有 45 個(gè)城市，就用 0 到 45 來(lái)標(biāo)識(shí)每一個(gè)城市，然后一個(gè)路徑就是一條染色體編碼，染色體長(zhǎng)度為 45，如： 0,1,2,3,4...44 就是一個(gè)染色體，它表達(dá)的意思就是旅行者從 0 號(hào)城市出發(fā)，依次訪(fǎng)問(wèn) 1,2,...44 號(hào)城市再回到0 號(hào)城市；下面 具體 具體 介紹一 下 這一種 編碼方法 。將全部 Gi 順序排列在一起所得到的一個(gè)列表： G=（ G1， G2， G3， …… ， Gn） 這樣就 可以表示一條 巡回 路線(xiàn)，它就是遺傳算法中的一個(gè) 個(gè)體 基因。 算子的設(shè)計(jì)（ 交叉 、選擇、變異） 交叉 算子 交叉運(yùn)算，一般 指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。 求解 旅行商 問(wèn)題的遺傳算法的交叉算法主要有：部分匹配交叉（ PMX） 、 循環(huán)交叉（ CX） 、次序 交叉（ OX） 、線(xiàn)性次序 交叉（ LOX） 、 邊重組交叉（ EX） 等 。 由于 在確定算法的編碼方式的過(guò)程中使用的是 Grefenstette 等提出的 編碼方式，用這種編碼方式表示個(gè)體時(shí)，個(gè)體的 基因型 和表現(xiàn)型之間是一一對(duì)應(yīng)的， 它使 經(jīng)過(guò)運(yùn)算之后得到的每一個(gè)基因型都是一條有 實(shí)際 意義的 巡回 路線(xiàn)。使用 單點(diǎn)交叉，即在個(gè)體的編碼串上隨機(jī)設(shè)置一個(gè)交叉點(diǎn)， 然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。 如下 是具體代碼： for(i=0。i++) { int nPos, temp=0。 //父代基因 1 int parent2=0。 temp=RandomInt(0,m_nGroupSize1)。 parent2=RandomInt(0,m_nGroupSize1)。 if(parent2temp) parent2=temp。 PopNode pop2。oldpop[parent1])。oldpop[parent2])。 (amp。 //交叉完成 ,保存結(jié)果 newpop[m_nGroupSize+2*i].CopyNode(amp。 newpop[m_nGroupSize+2*i+1].CopyNode(amp。 選擇 算子 選擇操作是建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上的。本課題采用最常用的選擇算子 —— 比例選擇算子（又 稱(chēng)輪盤(pán)賭選擇） 。適應(yīng)度越高的個(gè)體被選中的概率也越大；反之，適應(yīng)度越低的個(gè)體被選中的概率也越小。 具體 代碼如下： for(int gen=0。gen++) { // 計(jì)算當(dāng)前一代群體中個(gè)體的適應(yīng)度數(shù)值 F for(int i=0。i++) TotalF+=1/oldpop[i].CalcCost(m_distance)。im_nGroupSize。 // 將當(dāng)前一代群體中的個(gè)體按 F 值從大到小排序 for(i=0。i++) { double max=。 for(int j=i。j++) if(oldpop[j].fitmax) { max=oldpop[j].fit。 14 } if(i!=maxpos) oldpop[i].SwapNode(amp。 } m_CurGANum=gen。 (amp。 m_GAFitness=。 UpdateData(false)。 if (m_CurGANum == m_GANum 1) { // 繪制圖形 DrawNetwork()。im_nGroupSize。oldpop[i])。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。本系統(tǒng)中變異算子采用基本位變異算子。 因?yàn)?使用由 Grefenstette 等所提出的編譯方法來(lái)表示個(gè)體，一個(gè)個(gè) 體經(jīng)過(guò)遺傳運(yùn)算后所得到的任意一個(gè)基因型個(gè)體 與交叉后的情況相同， 都能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線(xiàn) ?；疚蛔儺愃阕拥膱?zhí)行過(guò)程如下： 15 （ 1）對(duì)個(gè)體的每一個(gè)基因座，依變異概率 Pm 指定其為變異點(diǎn)。 針對(duì)旅行商問(wèn)題對(duì)變異算子的設(shè)計(jì)要求，基本位變異即交換變異。例如： 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。i++) { int nPos1,nPos2,parent=0。 （ 取 其中 第三位與 倒數(shù)第三位做 nPos2=RandomInt(3,MAXCHROM3)。 (amp。 (nPos1,nPos2)。pop)。個(gè)體 的 適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體 的 適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。 本 系統(tǒng) 中以每條路徑長(zhǎng)度的倒數(shù)作為適應(yīng)度函數(shù)值，并對(duì)其進(jìn)行 統(tǒng) 一化 的 操作，即按從大到小 進(jìn)行 排序，為下一步選擇操作做準(zhǔn)備。具體代碼如下所示 ： for(int i=0。i++) （ nGroupSize 是 城市 之間 的距離） TotalF+=1/oldpop[i].CalcCost(m_distance)。 算法設(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)目。 圖 41系統(tǒng) 功能模塊圖 系 統(tǒng)詳細(xì)設(shè)計(jì) 由前 文 中介紹的個(gè)體編碼方法 及 各種遺傳算子可以構(gòu)成 許多種 不同的求解旅行商問(wèn)題的遺傳算法，本系統(tǒng) 主要 利用這些遺傳算 子 對(duì)含有 45 座城市的旅行商問(wèn)題進(jìn)行了試算。 ●適應(yīng)度函數(shù) 系統(tǒng)中以每條路徑長(zhǎng)度的倒數(shù)作為適應(yīng)度函數(shù)值。 ●變異算子 使用 基本位 交換變異操作算子 ●運(yùn)行參數(shù) {M， T， Pc， Pm}={0~500， 0~300， ~， ~}，式中 M 為群體大小， T 為終止代數(shù)， Pc 為交叉概率， Pm 為變異概率。極端情況不可執(zhí)行。 演示 模塊 設(shè)計(jì) （ 1） 主窗口 設(shè)計(jì)： 在 VC 工具欄 insent 中插入窗口 IDD_CHINA45_DIALOG， 再在上面設(shè)置 變量 ，并進(jìn)行初始化。 表 IDD_CHINA45_DIALOG 的菜單選項(xiàng) ID 說(shuō)明文字 功能描述 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ì)話(huà)框添加成員變量 變量類(lèi)型 變量名 功能描述 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。 m_GACrossProb = 。 m_GANum = 100。 m_MiniCost = 。 m_VariNum = 0。 變量與 對(duì)話(huà)框進(jìn)行綁定： DDX_Text(pDX, IDC_EDIT1, m_GALen)。 DDX_Text(pDX, IDC_EDIT3, m_GACrossProb)。 DDX_Text(pDX, IDC_EDIT5, m_GANum)。 DDX_Text(pDX, IDC_EDIT7, m_MiniCost)。 DDX_Text(pDX, IDC_EDIT9, m_VariNum)。 打開(kāi)類(lèi)向?qū)В?Class Wizard）對(duì)話(huà)框向主對(duì)話(huà)框類(lèi)添加響應(yīng)函數(shù)，用于 顯示新生成的群體規(guī)模、交叉變異數(shù)目等。 if(()==IDOK) { m_nGroupSize=。 （將 新的交叉概率 賦值 給 對(duì)話(huà)框 ） m_GAVariProb=。 （將 新 的 遺傳代數(shù) 賦值 給 對(duì)話(huà)框 ） UpdateData(false)。 oldpop=new PopNode[m_nGroupSize]。k1。 } （ 2） 主窗口 菜單設(shè)置： 在 菜單欄中需要做三個(gè) 選項(xiàng) ： 文件 、 設(shè)置 和幫助 。 （ 3） 遺傳 算法參數(shù)設(shè)置窗口的 設(shè)計(jì) ： 在菜單 遺傳算法設(shè)置下 插入 一個(gè)窗口IDD_DIALOG_SET,具體 設(shè)置如下表所示： 表 為工程添加 IDD_DIALOG_SET 的菜單選項(xiàng) ID 說(shuō)明文字 功能描述 IDC_EDIT2 群體規(guī)模 接受用戶(hù) 輸入 群體 規(guī)模 IDC_EDIT3 交叉概率 用戶(hù) 輸入 交叉 概率 IDC_EDIT4 變異概率 用戶(hù) 輸入變異概率 IDC_EDIT5 遺傳代數(shù) 用戶(hù) 輸入遺傳代數(shù) 然 后 拖入兩個(gè)按鈕， 分別 為確認(rèn)和取消， 分別 設(shè)置功能名為 OnOK、 OnCancel， 分別可以在如下位置 添加 響應(yīng) 函數(shù) ： void CGASetDlg::OnCancel() { CDialog::OnCancel()。 } (4)設(shè)置 屏幕顯示函數(shù) ， 在主窗 口 上 選出一片 區(qū)域， 作為 地圖，用于存放城市位置。具體 代碼 如下圖所示： 21 void CChina45Dlg::DrawNetwork() { CPen Pen。 CRect RectClient,Workarea。 =+140。 =+290。 pDCRectangle(Workarea)。 int px=。 pDCSetTextColor(0x00F08080)。iMAXCHROM。 =px+m_point[i].x2。（城市 位置 向右 兩個(gè)單位） =pym_point[i].y2。（城市 位置 向下 兩個(gè)單位） pDCEllipse(city)。 (執(zhí)行數(shù)據(jù)綁定的功能 ,用于顯示關(guān)于作者信息 ) 再 拖入一個(gè)按鈕， 在此處可以 對(duì)其 添加 函數(shù) 聲明， 該函數(shù)執(zhí)行確定操作 ： void CAuthDlg::OnOK() { // TODO: Add extra validation here 22 CDialog::OnOK()。 (數(shù)據(jù)綁定 ,顯示關(guān)于軟件的信息 ) 再 拖入一個(gè)按鈕， 在此處可以 對(duì)其添加響應(yīng)函數(shù)： void CAboutDlg::OnOK() { // TODO: Add extra validation here CDialog::OnOK()。 經(jīng)過(guò) 算法運(yùn)算之后 ，結(jié)果 如下圖所示 ： 圖 42 23 圖 43 圖 44 24 圖 45 通過(guò)對(duì)圖 4 4 44 的分析可知，由于本次 試算設(shè)置的 群體大小、交叉概率、變異概率、進(jìn)化代數(shù)這幾個(gè)參數(shù) 都在規(guī)定 范圍內(nèi)，通過(guò)運(yùn)行，算法運(yùn)行到指定的進(jìn)化代數(shù)之后停止運(yùn)行，并輸出 了 當(dāng)前群體中的最小費(fèi)用路徑 的 大小，即 城市 路徑總長(zhǎng)度最短者。如上圖所示，以相同的參數(shù)連續(xù)執(zhí)行三次遺傳算法演示，最小費(fèi)用不同，但相差 并 不是很大 。 測(cè)試二 如圖 4 4 4 48 所示 ，本次測(cè)試的分別設(shè)置了 {M， T， Pc， Pm}={500， 100， }， {M， T， Pc， Pm}={1000， 100， ， }。下 實(shí)驗(yàn)結(jié)果分別如下圖所示 ： 25 圖 46 圖 47 26 圖 48 通過(guò) 對(duì)圖 4 8 可以 看出，算法經(jīng)過(guò)運(yùn)算之后，其求解的結(jié)果有一 定 的更優(yōu)的趨勢(shì)， 但是 通過(guò)運(yùn)算的計(jì)算時(shí)間卻大大的增加了，當(dāng)種群數(shù)量小時(shí)的計(jì)算 時(shí)間短 ，但是當(dāng)增加到 500 后 ，時(shí)間 明顯 感覺(jué)增加 ； 但 增加到 1000 后 ， 時(shí)間