遺傳算法求解tsp問題的計算機仿真畢業論文(存儲版)

　　

【正文】 結果偏大許多，這就體現了出了遺傳算法的特點：是不斷搜索出適應度較高的個體，并在群體中增加其數量，最終求出問題的最優解或近似最優解，所以其最后的求解結果是有一定的波動的。測試表明，變異概率取值太小則變異操作將不能產生新個體或很少生成新個體，將會導致結果出現早熟現象，即求出的解離最優解有一定距離，嚴重影響搜索結果；變異概率太大雖能夠產生出較多的新個體，但也有很大的可能破壞系統的穩定性，可能會破壞較好基因，同樣嚴重影響系統搜索性能。可以看出選擇算子是隨機操作，誤差較大，只有選擇算子起作用對于實驗結果沒有實際意義。要發展遺傳算法也要以這幾個方面作為突破口。BOOL CChina45App::InitInstance(){ AfxEnableControlContainer()。}// : implementation file//include include include include include include include include include ifdef _DEBUGdefine new DEBUG_NEWundef THIS_FILEstatic char THIS_FILE[] = __FILE__。 int nResponse = ()。[19] Sushil Algorithm for TSP[OL ]. :/ /. unr .edu/～sushil/ papers/ conference/ newpapers/ 99/ gecco99/ iga/ GECCO/ gecco/ 附錄一程序程序代碼：include include include ifdef _DEBUGdefine new DEBUG_NEWundef THIS_FILEstatic char THIS_FILE[] = __FILE__。（2）針對具體問題，設計各個模塊，仿真實現遺傳算法。仿真結果見圖416。仿真結果見圖411，412：圖 49圖 410圖 411圖 412如上圖所示，本次測試只改變參數變異概率，其它參數保持不變。基于本系統使用的所有算法計算出了最短路徑的城市序列后，依次將兩兩城市之間路徑長度累加就得到最小費用路徑，也就是城市最短路徑。（城市位置向上兩個單位） =pym_point[i].y+2。 int py=+20。GetClientRect(RectClient)。在文件下面繼續添加菜單退出，并設置ID為ID_MENU_EXIT；文件下邊添加菜單遺傳算法設置，設置ID為ID_MENU_GASET；幫助下邊添加菜單關于軟件和關于作者，設置ID分別為ID_MENU_SOFT、ID_MENU_WRITE。 （將新的變異概率賦值給對話框） m_GANum=。 DDX_Text(pDX, IDC_EDIT8, m_CrossNum)。 m_GAFitness = 。 m_nGroupSize = 100。●選擇算子采用適應度比例法●交叉算子采用常規單點交叉操作算子。im_nGroupSize。（執行結點操作） newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(amp。im_VariNum。基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。 } //繼承所有父代基因 for(i=0。 // 查找當前一代中的最小費用個體 m_MiniCost=oldpop[0].cost。 int maxpos。im_nGroupSize。選擇操作的目的是為了避免基因缺失、提高全局收斂性和計算效率。 // 基因序列中用于交叉的基因位 nPos=RandomInt(3,MAXCHROM3)。temp=RandomInt(0,m_nGroupSize1)。im_CrossNum。交叉運算是遺傳算法區別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用，是產生新個體的主要方法。符號編碼的主要優點是：（1)符合有意義積術塊編碼原則（2)便于在遺傳算法中利用所求解問題的專門知識（3)便于遺傳算法與相關近似算法之間的混合使用。二進制編碼的缺點是：對于一些連續函數的優化問題，由于其隨機性使得其局部搜索能力較差，如對于一些高精度的問題（如上題），當解迫近于最優解后，由于其變異后表現型變化很大，不連續，所以會遠離最優解，達不到穩定。可以用如下公式表達:n1f(T)= ∑d(ti,ti+1)+d(nt,t1)i=1本系統是用遺傳算法求解45個城市的旅行商問題，并對其進行計算機仿真，做出一個能在計算機上運行的軟件。自組織能力和自學習能力是人工生命的兩大主要特征。所以，機器人學理所當然地成為遺傳算法的一個重要應用領域。（2）組合優化隨著變量n的不斷增大，問題的規模增大，組合優化問題的求解空間也急劇增大，應用傳統的枚舉法等就很難求出最優解。遺傳算法利用進化過程獲得信息自行組織搜索時，適應度高的個體具有較高的生存率，并獲得更加適應環境的染色體。首先，遺傳算法并行的方式是從問題解的串集開始搜索，而不是從單個解開始。步驟七：終止。步驟三：交叉算子：這是遺傳算法最重要的操作。10）串結構空間（ss）：在串中，基因任意組合所構成的串集合。生物在其延續生命的過程中，逐漸適應其生存環境使得其品質不斷得到改良，這種生命現象稱為進化。而其中也會有一個“山峰”的海拔最高的，那么這個就是全局最優解。這些染色體在后續的迭代中不斷的進化，稱為遺傳。2 1967年在其博士論文中首次提出了：“遺傳算法”一詞，發展了復制、交叉、變異、顯性、倒位等遺傳算子，創立了自適應遺傳算法的概念。對本文的內容進行總結。這一章主要論述旅行商問題的基本概念，以及本課題主要的研究方法及其研究意義，并對論文的章節結構加以論述。應用遺傳算法求解旅行商問題，最難得地方在于問題建模，如城市編碼方式以及交叉、變異、選擇算子的確定等。首先旅行商問題是用于求解N個城市存在（N1）條閉合路徑的排列方案，對于這一類問題很難用全局搜索法精確地求出最優解，這一問題已經困擾眾多學者許多年，因此研究相應的算法尋找其最優或近似最優解是非常必要的。TSP問題可以形式化描述為：設G=（V,A,D）是一個圖，其中V是n個頂點的集合，A是弧線或邊集,D=（dij）是與A關聯的距離或費用矩陣。在本系統就是要應用遺傳算法求解45個城市的TSP問題。遺傳算法固有的并行性和并行計算的能力，使在搜索過程中不容易陷入局部最優。應用遺傳算法求解旅行商問題最關鍵的是編碼方式、交叉、選擇、變異算子的設計，直接關系到算法能否求出最優解或近似最優解。所以當輸入越大，則耗費的時間就是個天文數字了，因此旅行商問題至今都沒有能找到一種有效的求解方法。毫無疑問，高效、低成本、低能耗成了各個物流企業追求的目標，更加合理的配送路線能明顯地為物流公司增大利潤。變異算法采用的是基本位變異法，即只是根據變異概率隨機改變染色體中的某一段染色體，具體會在后文中做詳細說明。第三章基于遺傳算法求解TSP問題。70年代De Jong基于遺傳算法的思想在計算機上進行了大量純數值函數優化計算實驗。5 1991年編輯出版了《遺傳算法手冊 (Handbook of Genetic Algorithms)》書中包括遺傳算法在科學計算、工程技術和社會經濟中的大量應用實例。后代通常是前一代染色體通過交叉（crossover）或者變異（mutation ）形成。下面給出生物學的幾個基本概念知識，這對于理解遺傳算法很重要：1）遺傳因子（gene）:DNA長鏈結構中占有一定位置的基本遺傳單位，也稱基因。6）選擇（selection）:指以一定的概率從種群中選擇若干個體的操作。11）染色體：是生物細胞中含有的一種微小的絲狀化合物，是遺傳物質的主要載體，由多個遺傳因子—基因組成。步驟四：適應度：確定個體適應度的量化評價方法，適應度用于衡量種群中個體的優劣性，是確定種群中個體留存的關鍵。數值方法求解這一問題的主要手段是迭代運算。遺傳算法從串集開始搜索，覆蓋面大，有利于全局最優。（4）遺傳算法可以直接用于實際應用當中，對于給定的問題，可以產生許多解，最終選擇是根據用戶自己的需求來選取，通用性高，實際應用性強，應用范圍廣。(3)生產調度問題生產調度問題在很多情況下建立起來的傳統數學模難以精確求解。許多數據挖掘問題可看成是搜索問題，數據庫看作是搜索空間，挖掘算法看作是搜索策略。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將得到更為深入的應用和發展。迄今為止人們已經提出了許多種不同的編碼方法。二進制編碼存在著連續函數離散化時的映射誤差。對于每個城市用一個整數來編號，例如有45個城市，就用0到45來標識每一個城市，然后一個路徑就是一條染色體編碼，染色體長度為45，如：0,1,2,3,4...44就是一個染色體，它表達的意思就是旅行者從0號城市出發，依次訪問1,2,...44號城市再回到0號城市；下面具體具體介紹一下這一種編碼方法。由于在確定算法的編碼方式的過程中使用的是Grefenstette等提出的編碼方式，用這種編碼方式表示個體時，個體的基因型和表現型之間是一一對應的，它使經過運算之后得到的每一個基因型都是一條有實際意義的巡回路線。 //父代基因1 int parent2=0。 PopNode pop2。 //交叉完成,保存結果 newpop[m_nGroupSize+2*i].CopyNode(amp。適應度越高的個體被選中的概率也越大；反之，適應度越低的個體被選中的概率也越小。im_nGroupSize。j++) if(oldpop[j].fitmax) { max=oldpop[j].fit。 m_GAFitness=。oldpop[i])。基本位變異算子的執行過程如下：（1）對個體的每一個基因座，依變異概率Pm指定其為變異點。 （取其中第三位與倒數第三位做 nPos2=RandomInt(3,MAXCHROM3)。個體的適應度越大，該個體被遺傳到下一代的概率也越大；反之，個體的適應度越小，該個體被遺傳到下一代的概率也越小。算法設計模塊完成群體規模M、交叉概率Pc、變異概率Pm和進化代數T的設置；具體的參數已經設置在了演示平臺上，可以根據需要更改參數大小，但是盡量在設定的范圍之內，這樣可以保證算法的精確性；幫助模塊則設置了關于軟件和制作作者等查看項目。極端情況不可執行。 m_GANum = 100。 DDX_Text(pDX, IDC_EDIT3, m_GACrossProb)。打開類向導（Class Wizard）對話框向主對話框類添加響應函數，用于顯示新生成的群體規模、交叉變異數目等。 oldpop=new PopNode[m_nGroupSize]。}(4)設置屏幕顯示函數，在主窗口上選出一片區域，作為地圖，用于存放城市位置。 =+290。iMAXCHROM。 (執行數據綁定的功能,用于顯示關于作者信息)再拖入一個按鈕，在此處可以對其添加函數聲明，該函數執行確定操作：void CAuthDlg::OnOK() { // TODO: Add extra validation here CDialog::OnOK()。 測試二如圖44448所示，本次測試的分別設置了{M，T，Pc，Pm}={500，100，}，{M，T，Pc，Pm}={1000，100，}。 測試四如圖413所示，本次測試分別設置{M，T，Pc，Pm}={200，100，0，}，交叉概率為0，其他參數不變，即交叉個體數目為0。5 結論本課題主要對遺傳算法的基本原理進行研究，并針對實例實現基于遺傳算法的具體搜索過程。各種求解TSP問題的算法里面都包含啟發式的信息或者是在編碼過程中包含有邊的信息(如矩陣表示和矩陣交叉等)，我認為這是一種趨勢。ifdef _AFXDLL Enable3dControls()。endif//自定義全局變量//用于繪制連線的顏色COLORREF COLOR[16]={0x008080F0,0x0000D080,0x00800080,0x008080E0, 0x0080E000,0x00E08000,0x0000E080,0x003020D0, 0x0080F080,0x00F08080,0x008080F0,0x00F0F080, 0x0080F020,0x00208080,0x008020F0,0x00A02080,}。dlg。參考文獻[1]王小平，曹立明編著，遺傳算法——理論、應用與軟件實現，西安：西安交通大學出版社，[2]周明，孫樹編著，遺傳算法原理及應用，北京：國防工業出版社，[3]謝政，李建平編著，網絡算法與復雜性理論，長沙：國防科技大學出版社，1995[4]陳國良等，遺傳算法及其應用，北京：人民郵電出版社，1995[5]劉勇等，非數值并行算法（二）——遺傳算法，北京：科學出版社，1995[6]劉值義等，遺傳學，北京：人民教育出版社，1982[7] 謝勝利等“求解TSP問題的一種改進的遺傳算法[J ]”，計算機工程與應用,2002 (8)：58～245[8] 王俊海, “TSP問題的一種高效Memetic算法[J ]”，交通與計算機, 2002 ,20 (