王永靜

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

?

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

王永靜

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

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

旅行商問(wèn)題；動(dòng)態(tài)規(guī)劃；模擬退火算法

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

此時(shí)，在這里決策組成的集合：

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

此時(shí)，在這里決策組成的集合：

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

此時(shí)，在這里決策組成的集合：

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

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

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

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

2.2 模擬退火算法演算

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

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

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

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

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

新解的產(chǎn)生：從1到n中隨機(jī)產(chǎn)生的兩個(gè)相異數(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) .

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

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

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)為路徑總長(zhǎng)}

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

3 結(jié)語(yǔ)

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

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

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

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

[4] 高 尚.求解旅行商問(wèn)題的模擬退火算法[J]．江蘇科技大學(xué)學(xué)報(bào)(自然科學(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