遺傳算法TSP的matlab求解分析

馬駿

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

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

中圖分類號(hào)： TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ī)搜索方法，遺傳算法在運(yùn)算過程中直接對(duì)個(gè)體對(duì)象進(jìn)行操作，而不需要任何導(dǎo)數(shù)、梯度等信息[1-2]，因此，遺傳算法對(duì)于存在多峰性、非線性、非連續(xù)、不可微函數(shù)的優(yōu)化問題是個(gè)很好的優(yōu)化手段[3]。

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

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

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

1.1 群體初始化

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

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

for i=1：NP

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

end

1.2 定義適值函數(shù)

一般在求解最優(yōu)解問題時(shí)，目標(biāo)函數(shù)可以是求解最大值，也可以是求解最小值。但是在基本遺傳算法里，適值函數(shù)[5]（目標(biāo)值）越大，其被選擇的概率越大，也就是越容易得到最優(yōu)值。因此如果是求解最小值的優(yōu)化問題時(shí)，需要作相應(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 %概率累計(jì)

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 %按累計(jì)概率選擇父代

1.4 交叉操作

為了避免傳統(tǒng)的單點(diǎn)交叉或者雙點(diǎn)交叉造成的非法子代，本程序采用由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ī)地選擇兩個(gè)位置，并將兩個(gè)位置上的城市相互交換。

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)容加以整合，組成完成的計(jì)算程序。分別以5個(gè)城市、10個(gè)城市、20個(gè)城市的TSP問題進(jìn)行校驗(yàn)計(jì)算。結(jié)果如下圖表所示。

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

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

3 結(jié)論

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

【參考文獻(xiàn)】

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

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

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

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

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

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