遺傳算法TSP的matlab求解分析

馬駿

【摘 要】TSP（旅行商問題）是一個經典的組合優化問題，是一個非連續的參數變化問題，其不能用傳統的牛頓法去計算分析。遺傳算法是一種可以用于解決含有離散變量的優化求解問題。本文通過遺傳算法，針對TSP，借助matlab編寫運行程序，詳細論述程序的編碼與實現，并進行案例結果分析驗證。分析結果表明本文利用遺傳算法原理所編寫的程序非常好的得到了優化結果，表明了算法程序的正確性與可行性及遺傳算法對旅行商問題的有效性。

【關鍵詞】遺傳算法；旅行商問題；matlab程序；編碼；交叉

中圖分類號： TP301.6 文獻標識碼： A 文章編號： 2095-2457（2018）16-0037-002

DOI：10.19694/j.cnki.issn2095-2457.2018.16.016

【Abstract】TSP（Traveling Salesman Problem） is classic optimization problem， and its parameters are discontinuous，so it cannot be solved by traditional Newton method.This article use Genetic Algorithm to edit a encodeprocedure based on matlabfor TSP（Traveling Salesman Problem），The encode procedure was expounded.The analysis shows that the code can get very good optimization results which means the correctness and practicability of the code and the effectiveness of the GA to TSP.

【Key words】Genetic algorithm；Traveling salesman problem；Matlab code；Encode；Crossover

0 前言

遺傳算法是一種通過模擬生物界進化規律演化而來的隨機搜索方法，遺傳算法在運算過程中直接對個體對象進行操作，而不需要任何導數、梯度等信息[1-2]，因此，遺傳算法對于存在多峰性、非線性、非連續、不可微函數的優化問題是個很好的優化手段[3]。

TSP問題就是一個非連續的，不存在導數或者梯度信息的優化問題。TSP問題可以簡單地描述為：有n個城市，一個人從某個城市出發依次訪問這些城市，最后又回到出發城市，如何選定訪問路線使得路程最短[4]。對于TSP問題重難點在于如何巡回編碼，以及通過什么樣的方式進行交叉運算以避免非法子代。

本文通過遺傳算法，借用Matlab編輯算法程序，對TSP問題機型分析計算。

1 基于旅行商問題的遺傳算法matlab程序

1.1 群體初始化

編碼采用城市的遍歷次序，如6個城市的TSP：3-4-5-1-2-6可以編碼為[3 4 5 1 2 6]。程序首先對各城市之間的間距矩陣dmatrix、迭代次數NG、交叉概率Pc、變異概率Pm進行賦值。

num=size（dmatrix，2）；%個體數據數，即城市數

for i=1：NP

popm（i，：）=randperm（num）； %種群初始化

end

1.2 定義適值函數

一般在求解最優解問題時，目標函數可以是求解最大值，也可以是求解最小值。但是在基本遺傳算法里，適值函數[5]（目標值）越大，其被選擇的概率越大，也就是越容易得到最優值。因此如果是求解最小值的優化問題時，需要作相應改變，將目標函數的最小值問題轉換為適值函數的最大值問題，這里取總路程的倒數作為適值函數。

function L=shizhi（r，dmatrix，num）

Lmax=0；

for i=1：num-1

Lmax=Lmax+dmatrix（r（i），r（i+1））；

end

Lmax=Lmax+dmatrix（r（1），r（num））；

L=1/Lmax；

1.3 選擇操作

使用模擬賭盤操作，用來確定交叉雙親。

Lall=sum（L）；

gailv=L/Lall； %選取概率

leiji（1）=gailv（1）；

for i=2：NP

leiji（i）=leiji（i-1）+gailv（i）；

end %概率累計

for i=1：NP

r=rand； %隨機生成0～1的隨機數

for j=1：NP

if r<=leiji（j）；

father（i，：）=popm（j，：）；

break；

end

end

end %按累計概率選擇父代

1.4 交叉操作

為了避免傳統的單點交叉或者雙點交叉造成的非法子代，本程序采用由Goldberg和Lingle提出的部分交叉映射PMX[6]的方法進行交叉操作，

for i=1：2：NP

crossover=rand；

a=round（rand*（NP-1））+1；

b=round（rand*（NP-1））+1；

while a==b%防止a與b相等

b=round（rand*（NP-1））+1；

end

if crossover<=Pc；%選擇雙親

father1=father（a，：）；

father2=father（b，：）；

k=round（rand*（num-1））+1；%隨機選擇交叉位置

m=round（rand*（num-2））+1；

while k==m

m=round（rand*（num-1））+1；

end

minshu=min（k，m）；

maxshu=max（k，m）；

s1=father1（minshu：maxshu）；

s2=father2（minshu：maxshu）；

f1=father1；

f2=father2；

for j=minshu：maxshu%執行部分映射交叉操作

for h=1：num

if father1（h）==f2（j）

father1（h）=father1（j）；

end

if father2（h）==f1（j）

father2（h）=father2（j）；

end

end

end

father1（minshu：maxshu）=s2；

father2（minshu：maxshu）=s1；

son（i，：）=father1；

son（i+1，：）=father2；

else

son（i，：）=father（a，：）；

son（i+1，：）=father（b，：）；

end

end

1.6 變異操作

變異操作位于交叉操作之后，變異的方法有很多，這里采用互換變異的方法，即隨機地選擇兩個位置，并將兩個位置上的城市相互交換。

for i=1：num

mutation=rand；

if mutation<=Pm；

c=round（rand*（num-1））+1；

g=round（rand*（num-1））+1；

h=round（rand*（num-1））+1；

while g==h

h=round（rand*（num-1））+1；

end

mid=son（c，g）；

son（c，g）=son（c，h）；

son（c，h）=mid；

end

end

2 結果分析

將上述遺傳算法的主要程序內容加以整合，組成完成的計算程序。分別以5個城市、10個城市、20個城市的TSP問題進行校驗計算。結果如下圖表所示。

分析發現，遺傳算法對于規模較大的問題的求解往往難以做到唯一性，由于遺傳算法帶有隨機性成分，其分析結果也有所不同，需要多次分析選取最優結果，上述分析結果是多次實驗分析后較好的結果。

從上圖表可以看出，遺傳算法對于求解TSP有很好的適用性，TSP中，個體數越少，遺傳算法循環次數則越少，個體數越多，則需要更多次的循環迭代才能達到收斂。

3 結論

所編寫的程序成功的計算了上述TSP問題，并且結果符合性很好。通過計算分析，可以發現初始種群數NP、迭代代數NG、交叉概率Pc、變異概率Pm對于TSP問題的結果有影響，對于城市數目（下轉第122頁）（上接第38頁）較小的優化，可以取較小的NP和NG，而對于城市數目較大的優化，則需要較大的NG和NP才能達到收斂。在一般遺傳算法中Pc取值0.6～1.0左右和Pm取值0.05～0.10左右，但是對于該TSP問題，則需要取較小Pc（0.4）和較大的Pm（0.2）才能更容易得到最優解和更快得到最優解。因此，在實際計算分析時，需要根據相應問題，來選擇合適的優化參數。

【參考文獻】

[1]高媛.非支配排序遺傳算法（NSGA）的研究與應用[D].浙江：浙江大學信息科學與工程學院.

[2]賴宇陽.isight參數優化理論與實力詳解[M].北京：北京航空航天大學出版社，2012：138-142.

[3]龔純，王正林.精通MATLAB最優化計算[M].北京：電子工業出版社，2009：313.

[4]玄光南，程潤偉.遺傳算法與工程設計[M].北京：科學出版社，2000：82-83.

[5]李飛，白艷萍.用遺傳算法求解旅行商問題[M].中北大學學報，2007，28（1）：49-52.

[6]Goldberg，D.&R.Lingle.Alleles;，loci and the traveling salesman problem in Grefenstette.154-159.