計算機科學與技術畢業(yè)論文-基于遺傳算法的tsp問題研究(編輯修改稿)
2025-07-10 15:07 本頁面
【文章內容簡介】 m，簡稱 GA）是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法，它是由美國 Michigan 大學 教授于 1975 年首先提出來的，并出版了頗有影響的專著《 Adaptation in Natural and Artificial Systems》， GA 這個名稱才逐漸為人所知， 教授所提出的 GA 通常為簡單遺傳算法（ SGA）。遺傳算法是從代表問題可能潛在的解集的一個種群（ population）開始的，而一個種群則由經(jīng)過基因（ gene）編碼的一定數(shù)目的個體 (individual)組成。每個個體實際上是染色體 (chromosome)帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的 外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。這個過程將導致種群像自然進化一樣，后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（ decoding），可以作為問題近似最優(yōu)解 [1]。 （ 2）遺傳算法特點 遺傳算法是一類可用于復雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點： （ 1）遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學中的染色體和基因的概念，可以模仿自然界生物的遺傳和進化機理，也使得我們能夠方便地應用遺傳操作算子。 （ 2）遺傳算法直接以適應度作為搜索信息，無需導數(shù)等其它輔助信息。 二、關于 TSP 問題的簡介 TSP（ Traveling Salesman Problem） [2]問題又稱為貨郎擔問題、旅行商問題，是出現(xiàn)在許多應用中的一個組合優(yōu)化問題。該問題可簡單的描述為：已知 n 個城市各城市間的相對距離，某一旅行商從某個城市出發(fā)訪問每個城市一次且僅一次，最后回到出發(fā)城市，怎樣安排才使其所走路線 最短。 TSP 是一個典型的優(yōu)化組合問題，它需要求出旅行商從某一城市出發(fā)經(jīng)過所有城市所走路程的最短路徑，其可能的路徑數(shù)與城市個數(shù)成指數(shù)關系增長 [3]。用圖論的術語來說，假設有一個圖 G=(V,E)，其中 V 是頂點集， E 是邊集，設 D＝ (dij)是由頂點 i與頂點 j 間的距離所組成的距離矩陣， TSP 就是求出一條通過所有頂點且每個頂點通過一次的最短路徑的哈密爾頓回路 [4]。通常說的 TSP 都指對稱型的 TSP。若對于 n 個城市 V＝｛ V1， V2，?， Vｎ ｝的一個訪問順序為 T＝ (t1， t2，?， tn)，其中 tｉ ∈ V（ i＝ 1， 2，?，n），且記 t n+1＝ t1。則數(shù)學模型可以描述為公式（ ）。 ???? = ????/∑ ????????=1(?? = 1,…,??) （ ） 三、本論文的研究內容 本次設計的研究內容包括： （ 1）用 C++ 寫出基于遺傳算法解決 TSP 問題的核心程序，本系統(tǒng)用的是兩點交叉法和兩點區(qū)間隨機排序的變異法； （ 2）用 C++ 寫出一個界面來調用所寫的遺傳算法程序解決給定的數(shù)據(jù)； 1 遺傳算法的設計思想 以遺傳算法的思想去解決 TSP 問題，即要在眾多的城市路徑中找到一個最短的，我們模擬生物進化的程序，即遺傳的方式，我們先以一定的方式生成一個初始化群
畢業(yè)設計相關推薦
鄂ICP備17016276號-1