【文章內(nèi)容簡(jiǎn)介】 { double max=。 int maxpos。 for(int j=i。jm_nGroupSize。j++) if(oldpop[j].fitmax) { max=oldpop[j].fit。 maxpos=j。 } if(i!=maxpos) oldpop[i].SwapNode(amp。oldpop[maxpos])。 } m_CurGANum=gen。 // 查找當(dāng)前一代中的最小費(fèi)用個(gè)體 m_MiniCost=oldpop[0].cost。 (amp。oldpop[0])。 m_GAFitness=。 //AfxMessageBox(顯示數(shù)據(jù))。 UpdateData(false)。 UpdateWindow()。 if (m_CurGANum == m_GANum 1) { // 繪制圖形 DrawNetwork()。 } //繼承所有父代基因 for(i=0。im_nGroupSize。i++) newpop[i].CopyNode(amp。oldpop[i])。 變異算子變異運(yùn)算，是指改變個(gè)體編碼串中的某些基因值，從而形成新的個(gè)體。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。交叉運(yùn)算可以和變異運(yùn)算相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。本系統(tǒng)中變異算子采用基本位變異算子?；疚蛔儺愃阕邮侵笇?duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。因?yàn)槭褂糜蒅refenstette等所提出的編譯方法來(lái)表示個(gè)體，一個(gè)個(gè)體經(jīng)過(guò)遺傳運(yùn)算后所得到的任意一個(gè)基因型個(gè)體與交叉后的情況相同，都能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線。對(duì)于二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則將其變?yōu)?；反之，若原有基因值為1，則將其變?yōu)? ?；疚蛔儺愃阕拥膱?zhí)行過(guò)程如下：（1）對(duì)個(gè)體的每一個(gè)基因座，依變異概率Pm指定其為變異點(diǎn)。（2）對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其他等位基因值來(lái)代替，從而產(chǎn)生出一個(gè)新個(gè)體。針對(duì)旅行商問(wèn)題對(duì)變異算子的設(shè)計(jì)要求，基本位變異即交換變異。變異是單個(gè)個(gè)體內(nèi)部發(fā)生變化，導(dǎo)致產(chǎn)生新個(gè)體，從而產(chǎn)生出一條新的巡回路線。例如：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。im_VariNum。i++) { int nPos1,nPos2,parent=0。 //變異父代基因 parent=RandomInt(0,m_nGroupSize1) （定義變異范圍） nPos1=RandomInt(3,MAXCHROM3)。 （取其中第三位與倒數(shù)第三位做 nPos2=RandomInt(3,MAXCHROM3)。 為變異結(jié)點(diǎn)） PopNode pop。 (amp。oldpop[0])。 (nPos1,nPos2)。（執(zhí)行結(jié)點(diǎn)操作） newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(amp。pop)。（保存變異結(jié)果） } 適應(yīng)度函數(shù)在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群體中的概率。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。因此適應(yīng)度函數(shù)的選擇至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。本系統(tǒng)中以每條路徑長(zhǎng)度的倒數(shù)作為適應(yīng)度函數(shù)值，并對(duì)其進(jìn)行統(tǒng)一化的操作，即按從大到小進(jìn)行排序，為下一步選擇操作做準(zhǔn)備。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。具體代碼如下所示： for(int i=0。im_nGroupSize。i++) （nGroupSize是城市之間的距離） TotalF+=1/oldpop[i].CalcCost(m_distance)。（父代結(jié)點(diǎn)的城市距離的倒數(shù)作為它的適應(yīng)度） 遺傳算法求解TSP問(wèn)題的具體流程圖圖35 遺傳算法求解旅行商問(wèn)題的具體流程圖4 45個(gè)城市旅行商問(wèn)題的仿真軟件的設(shè)計(jì) 系統(tǒng)設(shè)計(jì)模塊本系統(tǒng)在Microsoft Visual C++環(huán)境下完成，根據(jù)需求設(shè)計(jì)了三大模塊：算法設(shè)計(jì)模塊、演示模塊、幫助模塊。算法設(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)目。下圖是系統(tǒng)的功能模塊圖?；谶z傳算法的TSP問(wèn)題仿真軟件設(shè)計(jì)算法設(shè)計(jì)模塊演示模塊幫助模塊群體規(guī)模交叉概率變異概率進(jìn)化代數(shù)進(jìn)化演示關(guān)于作者關(guān)于軟件圖41系統(tǒng)功能模塊圖 系統(tǒng)詳細(xì)設(shè)計(jì)由前文中介紹的個(gè)體編碼方法及各種遺傳算子可以構(gòu)成許多種不同的求解旅行商問(wèn)題的遺傳算法，本系統(tǒng)主要利用這些遺傳算子對(duì)含有45座城市的旅行商問(wèn)題進(jìn)行了試算。本系統(tǒng)中所使用的遺傳算法是由以下要素所構(gòu)成的：●編碼方法基本遺傳算法使用由Grefenstette所提出的編碼方法，詳細(xì)設(shè)計(jì)見(jiàn)第四章編碼方式一節(jié)。●適應(yīng)度函數(shù)系統(tǒng)中以每條路徑長(zhǎng)度的倒數(shù)作為適應(yīng)度函數(shù)值。●選擇算子采用適應(yīng)度比例法●交叉算子采用常規(guī)單點(diǎn)交叉操作算子。●變異算子使用基本位交換變異操作算子●運(yùn)行參數(shù){M，T，Pc，Pm}={0~500，0~300，~，~}，式中M為群體大小，T為終止代數(shù)，Pc為交叉概率，Pm為變異概率。本系統(tǒng)給出各個(gè)參數(shù)的參考范圍，在此范圍內(nèi)執(zhí)行搜索最佳，超出范圍也可演示，但這會(huì)影響搜索效果，可能得不到最優(yōu)解或近似最優(yōu)解。極端情況不可執(zhí)行。這些在上文中已作過(guò)詳細(xì)介紹,這里就不再重復(fù)。（1）主窗口設(shè)計(jì)：在VC工具欄insent中插入窗口IDD_CHINA45_DIALOG，再在上面設(shè)置變量，并進(jìn)行初始化。具體變量及其窗口對(duì)話框設(shè)置如下表。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ì)話框添加成員變量變量類型變量名功能描述intm_GALen城市數(shù)量intm_nGroupSize群體規(guī)模大小doublem_GACrossProb交叉概率doublem_GAVariProb變異概率intm_GANum遺傳代數(shù)intm_CurGANum進(jìn)化代數(shù)doublem_MiniCost最小費(fèi)用intm_CrossNum交叉數(shù)目intm_VariNum變異數(shù)目doublem_GAFitness群體適應(yīng)度初始化參數(shù)設(shè)置代碼如下： m_GALen = 45。 m_nGroupSize = 100。 m_GACrossProb = 。 m_GAVariProb = 。 m_GANum = 100。 m_CurGANum = 0。 m_MiniCost = 。 m_CrossNum = 0。 m_VariNum = 0。 m_GAFitness = 。變量與對(duì)話框進(jìn)行綁定： DDX_Text(pDX, IDC_EDIT1, m_GALen)。 DDX_Text(pDX, IDC_EDIT2, m_nGroupSize)。 DDX_Text(pDX, IDC_EDIT3, m_GACrossProb)。 DDX_Text(pDX, IDC_EDIT4, m_GAVariProb)。 DDX_Text(pDX, IDC_EDIT5, m_GANum)。 DDX_Text(pDX, IDC_EDIT6, m_CurGANum)。 DDX_Text(pDX, IDC_EDIT7, m_MiniCost)。 DDX_Text(pDX, IDC_EDIT8, m_CrossNum)。 DDX_Text(pDX, IDC_EDIT9, m_VariNum)。 DDX_Text(pDX, IDC_EDIT10, m_GAFitness)。打開(kāi)類向?qū)В–lass Wizard）對(duì)話框向主對(duì)話框類添加響應(yīng)函數(shù)，用于顯示新生成的群體規(guī)模、交叉變異數(shù)目等。具體代碼如下：void CChina45Dlg::OnMenuGaset() { // TODO: Add your mand handler code here CGASetDlg dlg。 if(()==IDOK) { m_nGroupSize=。 （將新的群體規(guī)模賦值給對(duì)話框） m_GACrossProb=。 （將新的交叉概率賦值給對(duì)話框） m_GAVariProb=。 （將新的變異概率賦值給對(duì)話框） m_GANum=。 （將新的遺傳代數(shù)賦值給對(duì)話框） UpdateData(false)。 }}在主窗口上拖一個(gè)按鈕進(jìn)去，按鈕名為OnButtonGa(遺傳算法演示按鈕)并對(duì)其添加響應(yīng)函數(shù)聲明,該函數(shù)執(zhí)行最短路徑更新的操作,即執(zhí)行一次算法,顯示一次運(yùn)算結(jié)果：void CChina45Dlg::OnButtonGa() { PopNode *oldpop。 oldpop=new PopNode[m_nGroupSize]。 for(int k=0。k1。k++) { ExecGA(k, oldpop)。 }（2）主窗口菜單設(shè)置：在菜單欄中需要做三個(gè)選項(xiàng)：文件、設(shè)置和幫助。在文件下面繼續(xù)添加菜單退出，并設(shè)置ID為ID_MENU_EXIT；文件下邊添加菜單遺傳算法設(shè)置，設(shè)置ID為ID_MENU_GASET；幫助下邊添加菜單關(guān)于軟件和關(guān)于作者，設(shè)置ID分別為ID_MENU_SOFT、ID_MENU_WRITE。（3）遺傳算法參數(shù)設(shè)置窗口的設(shè)計(jì)：在菜單遺傳算法設(shè)置下插入一個(gè)窗口IDD_DIALOG_SET,具體設(shè)置如下表所示： 為工程添加IDD_DIALOG_SET的菜單選項(xiàng)ID說(shuō)明文字功能描述IDC_EDIT2群體規(guī)模接受用戶輸入群體規(guī)模IDC_EDIT3交叉概率用戶輸入交叉概率IDC_EDIT4變異概率用戶輸入變異概率IDC_EDIT5遺傳代數(shù)用戶輸入遺傳代數(shù)然后拖入兩個(gè)按鈕，分別為確認(rèn)和取消，分別設(shè)置功能名為OnOK、OnCancel，分別可以在如下位置添加響應(yīng)函數(shù)：void CGASetDlg::OnCancel() { CDialog::OnCancel()。}void CGASetDlg::OnOK() { CDialog::OnOK()。}(4)設(shè)置屏幕顯示函數(shù)，在主窗口上選出一片區(qū)域，作為地圖，用于存放城市位置。為了便于演示觀察，本系統(tǒng)將城市位置用圓圈表示出來(lái)，具體操作是：將已知城市的坐標(biāo)點(diǎn)分別向上下左右移動(dòng)兩個(gè)單位，并以城市位置作為圓心畫(huà)圓，這樣就在主窗口上的地圖區(qū)域確定了城市的位置。具體代碼如下圖所示：void CChina45Dlg::DrawNetwork(){ CPen Pen。 CDC* pDC=GetDC()。 CRect RectClient,Workarea。GetClientRect(RectClient)。 =+140。 =。 =+290。 =。pDCRectangle(Workarea)。pDCSetBkColor(0x00FFFFFF)。 int px=。 int py=+20。 pDCSetTextColor(0x00F08080)。 for(int i=0。iMAXCHROM。i++) { CRect city。 =px+m_point[i].x2。（城市位置向左兩個(gè)單位） =px+m_point[i].x+2。（城市位置向右兩個(gè)單位） =pym_point[i].y2。（城市位置向上兩個(gè)單位） =pym_point[i].y+2。（城市位置向下兩個(gè)單位） pDCEllipse(city)。（以城市位置為圓心畫(huà)圓） }（1）關(guān)于作者：在VC工具欄insent中插入窗口,窗口ID為IDD_AUTH，并對(duì)其添加如下操作： protected: virtual void DoDataExchange(CDataExchange* pDX)。 (執(zhí)行數(shù)據(jù)綁定的功能,用于顯示關(guān)于作者信息)再拖入一個(gè)按鈕，在此處可以對(duì)其