利用遺傳算法解決tsp問題

利用遺傳算法解決tsp問題利用遺傳算法解決tsp問題第1頁TSP問題，又稱旅行商問題,旅行推銷員問題,是指對于給定

n個城市,旅行商從某一城市出發(fā)不重復(fù)訪問其余城市

后回到出發(fā)城市,要求找出一條旅行路線,是總旅行旅程最短.

遺傳算法（GeneticAlgorithms，GA）是一個基于自然群體遺傳演化機制算法,它模擬自然界生物進(jìn)化過程,采取人工進(jìn)化方式對目標(biāo)空間進(jìn)行隨機化搜索。它將問題域中可能解看作是群體個體,并將個體編碼成符號串形式(即染色體),模擬生物進(jìn)化過程,對群體重復(fù)進(jìn)行雜交等操作,依據(jù)預(yù)定適應(yīng)度函數(shù)對每個個體進(jìn)行評價,依據(jù)優(yōu)勝劣汰進(jìn)化規(guī)則,不停得到更優(yōu)群體,同時搜索優(yōu)化群體中最優(yōu)個體,求得滿足要求最優(yōu)解。利用遺傳算法解決tsp問題第2頁編碼方式

給每個城市一個固定基因編號，比如10個城市為0123456789，隨機地組成一個染色體（以下全部情況都以10個城市為例說明）。

約定這10個城市之間行走路線為：

0123456789

(其余基因序列路線一樣道理)利用遺傳算法解決tsp問題第3頁兩個城市間距離（用r[i][j]表示）

012345678901234567890,1,4,6,8,1,3,7,2,9,1,0,7,5,3,8,3,4,2,4,4,7,0,3,8,3,7,9,1,2,6,5,3,0,3,1,5,2,9,1,8,3,8,3,0,2,3,1,4,6,1,8,3,1,2,0,3,3,9,5,3,3,7,5,3,3,0,7,5,9,7,4,9,2,1,3,7,0,1,3,2,2,1,9,4,9,5,1,0,1,9,4,2,1,6,5,9,3,1,0利用遺傳算法解決tsp問題第4頁基因序列初始化1將這10個基因存放在一個暫時數(shù)組matrix[0]～matrix[9]。2隨機產(chǎn)生兩個0～9數(shù)，比如產(chǎn)生了x1=2,x2=7,交換matrix[2]和matrix[7]內(nèi)容（利用voidswap(int*,int*)實現(xiàn)。）3重復(fù)過程2屢次，得到一個基因序列，作為一個個體染色體。4產(chǎn)生基因序列賦值給一個個體gene[0]～gene[9].利用遺傳算法解決tsp問題第5頁一個完整路線長度比如基因序列為：0829756413，存放在gene[0]～gene[9]中。表示行旅行路線為：0829756413總旅程為：

r[gene[0]][gene[1]]+r[gene[1]][gene[2]]~

+r[gene[9]gene[0]]利用遺傳算法解決tsp問題第6頁輪盤選擇for(mem=0;mem<PopSize;mem++) sum+=population[mem].fitness; for(mem=0;mem<PopSize;mem++)//使小選中可能性大

x[mem]=sum-population[mem].fitness; sum=0.0; for(mem=0;mem<PopSize;mem++) sum+=x[mem]; /*Calculaterelativefitness*/ for(mem=0;mem<PopSize;mem++) population[mem].rfitness=x[mem]/sum;利用遺傳算法解決tsp問題第7頁交叉

比如一個基因序列為：

0256981347

產(chǎn)生兩個0～9int型隨機數(shù)，如得到2和6，將gene[2]和gene[6]之間基因反序，得到：

0218965347利用遺傳算法解決tsp問題第8頁變異比如一個基因序列為：

0256981347產(chǎn)生兩個0～9int型隨機數(shù)，如得到2和6，將gene[2]和gene[6]基因交換，得到：

0216