計算機科學與技術畢業(yè)論文-基于遺傳算法的tsp問題研究-文庫吧資料
2025-06-12 15:07本頁面
【正文】 ，因此在遺傳算法中的編碼方式一般為符號編碼。遺傳算法是模擬生物在自然界中的遺傳和進化過程而形成的一種自適應全局概率搜索算法，具有良好的全局尋優(yōu)能力，成 為解決 TSP 問題的有效方法之一。 ???? = ????/∑ ????????=1(?? = 1,…,??) （ ） 三、本論文的研究內容 本次設計的研究內容包括： （ 1）用 C++ 寫出基于遺傳算法解決 TSP 問題的核心程序，本系統(tǒng)用的是兩點交叉法和兩點區(qū)間隨機排序的變異法； （ 2）用 C++ 寫出一個界面來調用所寫的遺傳算法程序解決給定的數據； 1 遺傳算法的設計思想 以遺傳算法的思想去解決 TSP 問題，即要在眾多的城市路徑中找到一個最短的，我們模擬生物進化的程序，即遺傳的方式，我們先以一定的方式生成一個初始化群體，為每個染色體計算評價函數，然后群體競爭選擇，種群交叉種群變異，如此迭代下去直到迭代代數達到要求找到最短的路徑。若對于 n 個城市 V＝｛ V1， V2，?， Vｎ ｝的一個訪問順序為 T＝ (t1， t2，?， tn)，其中 tｉ ∈ V（ i＝ 1， 2，?，n），且記 t n+1＝ t1。用圖論的術語來說，假設有一個圖 G=(V,E)，其中 V 是頂點集， E 是邊集，設 D＝ (dij)是由頂點 i與頂點 j 間的距離所組成的距離矩陣， TSP 就是求出一條通過所有頂點且每個頂點通過一次的最短路徑的哈密爾頓回路 [4]。該問題可簡單的描述為：已知 n 個城市各城市間的相對距離，某一旅行商從某個城市出發(fā)訪問每個城市一次且僅一次，最后回到出發(fā)城市，怎樣安排才使其所走路線 最短。 （ 2）遺傳算法直接以適應度作為搜索信息，無需導數等其它輔助信息。 （ 2）遺傳算法特點 遺傳算法是一類可用于復雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點： （ 1）遺傳算法以決策變量的編碼作為運算對象。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的 外部表現，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。遺傳算法是從代表問題可能潛在的解集的一個種群（ population）開始的，而一個種群則由經過基因（ gene）編碼的一定數目的個體 (individual)組成。 Geic Algorithm 。 關鍵詞 ：組合優(yōu)化 ； TSP 問題 ；遺傳算法 ；最短路徑 Abstract TSP problem is also known as the traveling salesman problem. TSP is a typical portfolio optimization problem and needs to calculate the shortest path that a traveling salesman goes through all cities. The number of the possible paths may grow with index of the number of cities. It is of great significance to find out an effective approximate algorithm. It is u
畢業(yè)設計相關推薦
鄂ICP備17016276號-1