基于動態(tài)規(guī)劃法和模擬退火算法求解旅行商問題

王永靜

(河南質(zhì)量工程職業(yè)學(xué)院，河南 平頂山 467000)

?

基于動態(tài)規(guī)劃法和模擬退火算法求解旅行商問題

王永靜

(河南質(zhì)量工程職業(yè)學(xué)院，河南 平頂山 467000)

旅行商問題是一個非常典型、容易描述卻難以處理的NP完全問題，同時也是許多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式.有效解決旅行商問題在計算理論上和實際應(yīng)用上都有很高的價值.文章對幾種常見算法的優(yōu)缺點(diǎn)進(jìn)行總結(jié)，并利用動態(tài)規(guī)劃法和模擬退火算法結(jié)合實例求解旅行商最短路問題.

旅行商問題；動態(tài)規(guī)劃；模擬退火算法

0 引言

1 常見的幾種算法的優(yōu)缺點(diǎn)

賦權(quán)漢密爾頓回路法，總是可以通過枚舉法求出其解的，但由于枚舉法的計算量過大，達(dá)到(n-1)!的數(shù)量級，因而不是可行的方法.回溯法雖然可以得到問題的最優(yōu)解，但復(fù)雜度較高.分支定界法的復(fù)雜度仍舊為O(n!)[2]104-105，貪心算法的復(fù)雜度為O(n2)，此算法能夠快速的搜索，但由于其貪心的特征，得到的解不一定是最優(yōu)解，還有可能是最壞的解.遺傳算法也存在一些缺陷，在理論上，它缺乏深刻而又具有普遍意義的理論指導(dǎo)和數(shù)學(xué)分析模型，因此對遺傳算法的評估都是基于對比實驗.在應(yīng)用上，參數(shù)的設(shè)置是個敏感的問題，而參數(shù)只有憑經(jīng)驗設(shè)置，不同的參數(shù)結(jié)果的差別極大[3]27-31.在網(wǎng)絡(luò)模型法求解中，當(dāng)訪問結(jié)點(diǎn)的數(shù)目增加時，神經(jīng)網(wǎng)絡(luò)路徑算法的有效性降低甚至無法得到合法路徑.

2 動態(tài)規(guī)劃法和模擬退火算法

2.1 動態(tài)規(guī)劃求解

以某位在各個旅游景點(diǎn)銷售旅游產(chǎn)品的商人為例，該商人的銷售路線有成都至九寨溝、成都至峨眉山、成都至青城山、成都至都江堰等，以此為案例，本文首先用動態(tài)規(guī)劃對其求解.表1給出了各個景區(qū)之間的近似距離，為了簡化問題，設(shè)往返距離相等，即dij=dji.

表1 各個景區(qū)之間的距離(單位：km)

在本文的旅行商最佳路徑的研究過程中，建立以下模型：

設(shè)S表示從V1到Vi中間所有可能經(jīng)過的地點(diǎn)集合，狀態(tài)變量(i，S)表示從V1出發(fā)，經(jīng)過S集合中所有點(diǎn)依次到達(dá)最后Vi.

決策：由一個景點(diǎn)到另一個景點(diǎn).Pk(i,S)表示從Vi經(jīng)K個景點(diǎn)的S的集合到Vi景點(diǎn)的最短路線上鄰接Vi的前一個城市.

動態(tài)規(guī)劃的遞推關(guān)系為：

令i，j=1，2，3，4 ，分別表示成都，九寨溝，峨眉山和都江堰.

首先，根據(jù)動態(tài)規(guī)劃的邊界條件及距離矩陣知，從出發(fā)點(diǎn)成都到各個旅游景點(diǎn)的直接距離為：

令K=1，從成都出發(fā)經(jīng)過一個城市到達(dá)城市i的最短距離分別為：

令K=2，從出發(fā)點(diǎn)成都出發(fā)，中間經(jīng)過2個城市再回到成都的最短距離為：

f2(2,{3,4})=min[f1(3,{4})+d32,f1(4,{3})+d42]=min[185+510,290+350]=640

此時，在這里決策組成的集合：

f2(3,{2,4})=min[f1(2,{4})+d23,f1(4,{2})+d43]=min[415+510,780+120]=900

此時，在這里決策組成的集合：

f2(4,{2,3})=min[f1(2,{3})+d24,f1(3,{2})+d34]=min[680+350,940+120]=1030

此時，在這里決策組成的集合：

令K=3，從出發(fā)點(diǎn)成都出發(fā)，中間經(jīng)過3個城市回到成都的最短距離為：

min[640+430,900+120,1030+65]=1070

所以，在這里的決策集合為：

由以上動態(tài)規(guī)劃的遞推關(guān)系知，旅行商最佳的路線是先從成都出發(fā)，然后依次九寨溝，都江堰和峨眉山，最后從峨眉山返回出發(fā)地成都，這是最短的路線，最短路線長度為1 020 km.

2.2 模擬退火算法演算

上文用動態(tài)規(guī)劃求解的案例較為簡單，城市的數(shù)目較少，運(yùn)算步驟不是十分的繁瑣.但是，當(dāng)涉及的城市數(shù)目很多時，發(fā)現(xiàn)上述計算過程開始變得復(fù)雜，求解困難.

利用模擬退火算法，討論旅行商問題：假設(shè)一共有n個城市，如果分別用1,…,n代表.城市i與城市j之間的距離記做d(i，j)， (i,j)=1,…,n．旅行商問題是要找到一條不重復(fù)的通過各個城市的路線，且其要求總長度為最短[4]13-16.

求解的模旅行商問題的模擬退火算法模型可描述如下：

解空間： 解空間S是所有不重復(fù)的通過每個城市的回路，即為{1，…，n}的所有循環(huán)排列所構(gòu)成的集合，S中的成員記為(w1,w2,......wn)，并記wn+1=w1.初始解可選為(1，…，n).

目標(biāo)函數(shù)：不重復(fù)的通過所有城市的最短路線.關(guān)鍵是要求解此目標(biāo)函數(shù)的最小值.

新解的產(chǎn)生：從1到n中隨機(jī)產(chǎn)生的兩個相異數(shù)k和m，若km,則將(w1,w2,…wk,wk+1…wm,wn)變?yōu)椋?wm,wm-1,…w1,wm+1…wk-1,wn,wn-1,.....wk) .

簡單來說上述方法即為“逆轉(zhuǎn)中間或逆轉(zhuǎn)兩端”. 在實際應(yīng)用中，為了達(dá)到更好效果，也可以靈活引用其他的方法.

代價函數(shù)差：設(shè)將(w1,w2,…,wn) 變換 (u1,u2,…,un).通過分析，得到用模擬退火算法求解問題旅行商的偽程序：

Procedure TSPSA:

begin

init-of-T; { T為初始溫度}

S={1，…，n}; {S為初始值}

termination=false;

while termination=false

begin

for i=1 to L do

begin

generate(S′form S); { 由當(dāng)前回路S產(chǎn)生新的回路S′}

Δt:=f(S′))-f(S);{f(S)為路徑總長}

IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])

S=S′;

IF the-halt-condition-is-TRUE THEN

termination=true;

End;

T_lower;

End;

為了體現(xiàn)模擬退火算法的在求解最短路線問題的優(yōu)越性，在這里將訪問的城市數(shù)目增加到原來的10倍即40個，再次運(yùn)用模擬退火算法進(jìn)行求解.為了簡化計算，此時，設(shè)初始溫度T0=30,結(jié)束溫度為0,循環(huán)控制常數(shù)L=10,溫度衰減系數(shù)α=0.97,終止條件q=20.此時的運(yùn)行的結(jié)果是，最短路徑長度為16 842，運(yùn)行的時間約為3秒.

3 結(jié)語

通過計算結(jié)果可以得出：通過的村莊數(shù)目較少時，利用動態(tài)規(guī)劃法可以通過簡單的計算過程求解出最優(yōu)答案；模擬退火算法在求解最短路問題時較為快速，特別是當(dāng)城市數(shù)目較多時，具有比動態(tài)規(guī)劃更明顯的優(yōu)勢.隨著城市數(shù)目的增加，求解時間可能會有所增加，主要原因是可行解空間的指數(shù)增長造成的，但求解時間并不會呈現(xiàn)指數(shù)增長的情況.演算結(jié)果說明模擬退火算法在城市數(shù)目較多情況下，求解過程具有優(yōu)越性.

[1] 吳振奎，劉舒強(qiáng)．運(yùn)籌學(xué)概論[M]．北京：中國經(jīng)濟(jì)出版社，2000．

[2] 管 琳，白艷萍．用分支定界算法求解旅行商問題[J]．中北大學(xué)學(xué)報，2007，28(02)．

[3] 林章美.貨郎擔(dān)問題的若干解法[J]．閩江學(xué)院學(xué)報，2005，26(05)．

[4] 高 尚.求解旅行商問題的模擬退火算法[J]．江蘇科技大學(xué)學(xué)報(自然科學(xué)版)，2003，17(3)．

[責(zé)任編輯 梧桐雨]

2016-03-30

王永靜(1985- )，女，河南平頂山人，河南質(zhì)量工程職業(yè)學(xué)院講師，碩士，主要從事基礎(chǔ)數(shù)學(xué)教育研究。

1671-8127(2016)05-0005-03

O224；U116.2

A