馬駿

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

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

中圖分類號： TP301.6 文獻(xiàn)標(biāo)識碼： 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 前言

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

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

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

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

1.1 群體初始化

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

num=size（dmatrix，2）；%個體數(shù)據(jù)數(shù)，即城市數(shù)

for i=1：NP

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

end

1.2 定義適值函數(shù)

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

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； %隨機(jī)生成0～1的隨機(jī)數(shù)

for j=1：NP

if r<=leiji（j）；

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

break；

end

end

end %按累計概率選擇父代

1.4 交叉操作

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

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；%隨機(jī)選擇交叉位置

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%執(zhí)行部分映射交叉操作

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 變異操作

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

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 結(jié)果分析

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

分析發(fā)現(xiàn)，遺傳算法對于規(guī)模較大的問題的求解往往難以做到唯一性，由于遺傳算法帶有隨機(jī)性成分，其分析結(jié)果也有所不同，需要多次分析選取最優(yōu)結(jié)果，上述分析結(jié)果是多次實驗分析后較好的結(jié)果。

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

3 結(jié)論

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

【參考文獻(xiàn)】

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

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

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

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

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

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