何錦福 符強(qiáng) 王豪東

摘? 要： 模擬退火算法是一種結(jié)構(gòu)簡單，魯棒性強(qiáng)的群智能方法，在旅行商問題（Traveling Salesman Problem TSP）中得到了較好的應(yīng)用。但是該算法在獲取高性能解的過程中需要放慢降溫過程，因此收斂速度較慢。為了解決該問題，本文對求解TSP問題的模擬退火算法進(jìn)行了降溫方式的改進(jìn)，針對溫度設(shè)置能量值，并根據(jù)能量值的高低狀態(tài)判斷是否進(jìn)行跳躍式降溫，從而在保證精度的同時(shí)，加快了算法的收斂速度。用TSPLIB標(biāo)準(zhǔn)庫數(shù)據(jù)測試的結(jié)果表明，與改進(jìn)前的模擬退火算法相比，改進(jìn)的算法具有更加高效的尋優(yōu)能力。

關(guān)鍵詞： TSP問題; 模擬退火算法; 跳躍式降溫; 二重退火

中圖分類號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）07-47-04

Abstract： Simulated annealing is a simple and robust swarm optimization method， which has been well applied in solving Traveling Salesman Problem （TSP）. However， the algorithm needs to slow down the cooling process in the process of obtaining high-performance solutions， so the convergence speed is slow. In order to solve this problem， this paper improves the simulated annealing algorithm for solving TSP， sets the energy value for the temperature， and judges whether the jumping cooling is carried out according to the state of the energy value， thus speeds up the convergence speed of the algorithm while ensuring the accuracy. The performance of the algorithm is verified by the test on standard TSPLIB data， the results show that the improved algorithm has a more efficient optimization.

Key words： TSP; Simulated annealing algorithm; jumping cooling; twice annealing

0 引言

TSP問題又被稱之為旅行商問題，該問題為一名旅行商人要去多個(gè)城市旅游，其中每個(gè)城市僅去一次，且最終回到原點(diǎn)，求所走路徑最短的方案。隨著TSP問題中的城市數(shù)目增加，問題的復(fù)雜度呈指數(shù)上升，此類問題的大型實(shí)例無法用窮舉法這類常規(guī)算法求解，需尋找有效的近似方法計(jì)算。目前人們已經(jīng)提出了多種人工智能算法來求解該類問題：蟻群優(yōu)化算法[4]，遺傳算法[5]，神經(jīng)網(wǎng)絡(luò)算法[6]，改進(jìn)的遺傳混合蟻群算法[1]等。其中模擬退火算法使用靈活、描述問題簡單直觀，能擴(kuò)大全局搜索能力，有效解決算法結(jié)果陷入局部最優(yōu)的問題。因此在TSP問題的求解中具有更佳的性能。

模擬退火算法借鑒了固體退火的機(jī)制。當(dāng)固體處于高溫狀態(tài)時(shí)，內(nèi)部的粒子無序并且活躍，而在其慢慢冷卻的過程中，隨著溫度逐漸下降，內(nèi)部粒子將隨之變得漸漸有序。1983年，S. Kirkpatrick等人成功將模擬退火思想引入到組合優(yōu)化問題上。目前已經(jīng)廣泛應(yīng)用于VLSI設(shè)計(jì)、一維下料問題研究[2]和神經(jīng)網(wǎng)計(jì)算機(jī)的研究。在解決TSP問題時(shí)，模擬退火算法為得到精確的結(jié)果，耗費(fèi)時(shí)間成本較大，本文由此改進(jìn)了模擬退火算法的退火策略以達(dá)到保證結(jié)果精度的同時(shí)縮減時(shí)間的目的。

1 模擬退火算法

1.1 模擬退火算法簡介

給算法一個(gè)初始值作為當(dāng)前解，這個(gè)解包含的部分元素通過變換產(chǎn)生大量新解，算法選擇其中的最優(yōu)解作為當(dāng)前新解。每一次都以最優(yōu)解作為當(dāng)前新解會(huì)讓算法結(jié)果陷入局部最優(yōu)，因此模擬退火算法有著概率突跳特性。即會(huì)以一定的概率去接受比最優(yōu)解要差的解作為當(dāng)前新解，那么下一次選擇當(dāng)前新解時(shí)就會(huì)在該差解的鄰域空間中去尋找，這就為尋找全局最優(yōu)解提供了新的方向，使算法跳出局部最優(yōu)具有更大的可能性。模擬退火算法突跳性的概率會(huì)隨著溫度的降低而降低，在溫度降低的同時(shí)算法重復(fù)著“產(chǎn)生新解→比較兩個(gè)解的優(yōu)劣→是否接受”的過程。當(dāng)達(dá)到終止條件，算法所得的解即為全局最優(yōu)解。

1.2 算法流程

Step1 初始化：設(shè)定初始溫度T0，每個(gè)溫度下的迭代次數(shù)L，給定初始解M。

Step2 每個(gè)溫度下的L次迭代重復(fù)Step3-Step5。

Step3 產(chǎn)生新解MC。

Step4 計(jì)算增量ΔT=C（MC）-C（M），其中C（M）為評(píng)價(jià)函數(shù)。

Step5 若ΔT<0則接受MC成為新解，否則以exp（-ΔT/T）的概率接受MC作為新的當(dāng)前解。

Step6 當(dāng)算法滿足要求或者達(dá)到終止溫度時(shí)，程序結(jié)束。

2 基于改進(jìn)模擬退火算法的TSP問題求解方案

在求解tsp問題時(shí)，模擬退火算法在初始溫度、降溫系數(shù)、終止溫度、每個(gè)溫度的迭代次數(shù)L共同作用下，算法進(jìn)行大規(guī)模的數(shù)據(jù)迭代以及更新，搜尋比當(dāng)前解更好的解，當(dāng)達(dá)到終止溫度后，算法運(yùn)行結(jié)束得到的最新解就是最優(yōu)解。模擬退火算法因?yàn)槠浯罅康牡螖?shù)以及概率突跳特性，擁有強(qiáng)大的全局搜索能力。但同時(shí)也需要大量的時(shí)間來完成算法的搜索過程。為了提升算法的效率，目前對模擬退火算法的改進(jìn)方案大多是通過增加算子或與其他人工智能算法相結(jié)合等途徑，來達(dá)到提高算法最優(yōu)解精度的目的，而對于時(shí)間效率的考慮較少。本文對模擬退火算法的過程進(jìn)行了探索，針對提高收斂速度的要求，提出了以下改進(jìn)措施。

2.1 跳躍式降溫

針對退火策略提出跳躍式降溫，每一個(gè)溫度都有能量值P。在某溫度下的L次迭代中，迭代成功的次數(shù)越多，則該溫度的能量值P越大。給定一個(gè)能量標(biāo)準(zhǔn)值N，把此溫度的P值與N值相比較，如果P值超過設(shè)定的N值，那么該溫度被稱為跳躍溫度J。跳躍溫度是指該溫度在臨近的溫度當(dāng)中，進(jìn)行迭代的成功次數(shù)很多。可以進(jìn)行一次跳躍式降溫，把該溫度臨近的溫度所需要進(jìn)行的降溫環(huán)節(jié)省略，進(jìn)行一次幅度比較大的降溫。在算法使用跳躍式降溫后，相比沒有使用跳躍式降溫的算法，數(shù)據(jù)迭代處理的次數(shù)大大減少。

2.2 二重退火

跳躍溫度分為基準(zhǔn)跳躍溫度JR和超級(jí)跳躍溫度JS。JR代表P值略大于或等于N值。JS代表P值遠(yuǎn)遠(yuǎn)大于N值。在JS 中能搜尋到的最優(yōu)解質(zhì)量是遠(yuǎn)高于JR中得到的解。在判定某個(gè)溫度為JR后進(jìn)行了跳躍，如果該溫度的臨近溫度中出現(xiàn)了JS，那么JS就會(huì)被跳過。這種情況下就遺漏了這附近所有溫度中所能得到的最優(yōu)解。為了盡量消除這種情況帶來的影響，算法還使用了二重退火。利用第一次退火產(chǎn)生一個(gè)較優(yōu)的解，然后把溫度初始化。開始進(jìn)行第二次退火，產(chǎn)生一個(gè)最終解。進(jìn)行第二次退火等價(jià)于讓第一次退火中產(chǎn)生的較優(yōu)解重新回到高溫狀態(tài)下去迭代。第二次退火中，初始解的精確度已經(jīng)較高了，因此退火過程中整體的迭代成功率下降。原來的JR退化成了普通溫度，而JS相較之下則更可能被保存下來仍然被判定為跳躍溫度，進(jìn)行跳躍式降溫。這樣就更容易搜尋到最優(yōu)解，解決了JR與JS出現(xiàn)位置相近帶來的問題。算法使用跳躍式降溫與二重退火的改進(jìn)后，相比其他文獻(xiàn)，在保證了結(jié)果的精確性的基礎(chǔ)上又減少了數(shù)據(jù)迭代處理次數(shù)。

2.3 路徑的變異方式

路徑變異方式的多樣性影響到全局解是否會(huì)陷入到局部最優(yōu)。在產(chǎn)生新路徑的時(shí)候，如果只用一種路徑的變異方式，那么新的路徑產(chǎn)生就只朝著該變異方式的方向進(jìn)行下去，即使模擬退火算法以一定概率接受較差解來跳出局部最優(yōu)解，所能達(dá)到的也只是該種路徑變異方式下的全局最優(yōu)解。多增加幾種路徑的變異方式，新路徑的產(chǎn)生就能從多個(gè)方向去進(jìn)行，此時(shí)就會(huì)有更大的可能去逼近標(biāo)準(zhǔn)的解。本文采用了交換、移位、倒置的路徑變異方式。

路徑交換是指隨機(jī)選擇若干個(gè)城市進(jìn)行交換位置。如果是兩個(gè)城市之間的交換看成是點(diǎn)與點(diǎn)的交換。若干個(gè)城市點(diǎn)之間的交換，可以看成是城市點(diǎn)連成的城市段之間形成的交換。以此來形成新的路徑。路徑移位是指隨機(jī)在路徑中選出兩個(gè)城市，把這兩個(gè)城市以及它們中間的若干個(gè)城市，統(tǒng)一向左或者向右移動(dòng)若干個(gè)位置，得到了新的路徑。路徑倒置是指隨機(jī)在路徑中選出兩個(gè)城市，將這兩個(gè)城市之間的城市順序完全倒置得出新的路徑。

2.4 改進(jìn)后的算法流程

Step1 初始化：設(shè)定初始溫度T0，溫度下降系數(shù)A，終止溫度Tf，每個(gè)溫度下的迭代次數(shù)L，給定一條初始路徑以及初始解。

Step2 每個(gè)溫度下的L次迭代重復(fù)Step3-Step5。

Step3 用交換、移位、倒置的方式產(chǎn)生新的路徑。

Step4 把新路徑長度與原來的路徑相比較，若新路徑更短則直接替代原來的路徑。如果新路徑長則以“exp（-（Ln+1-Ln）/T）”的概率來接受新路徑。（Ln+1為最新路徑長度，Ln為原來長度，T為當(dāng)前溫度）

Step5 根據(jù)P值與N值得關(guān)系判斷溫度是否為跳躍溫度。

Step6 降溫。

Step7 達(dá)到終止溫度Tf。算法運(yùn)行結(jié)束得到結(jié)果。

3 仿真實(shí)驗(yàn)分析

為了驗(yàn)證改進(jìn)后的算法相比較于模擬退火算法在解決TSP問題時(shí)，在提高了收斂速度的同時(shí)還保證了解的精準(zhǔn)度。該算法在TSPLIB標(biāo)準(zhǔn)庫中隨機(jī)選擇不同規(guī)模的城市進(jìn)行測試。為了保證實(shí)驗(yàn)不出現(xiàn)偶然性，針對每一個(gè)城市規(guī)模的TSP問題都進(jìn)行十次仿真實(shí)驗(yàn)并采集數(shù)據(jù)。記錄下最優(yōu)解、計(jì)算出平均解，并以其他文獻(xiàn)中的優(yōu)秀解或官方解做參考。實(shí)驗(yàn)分別記錄了每一個(gè)TSP問題的前五次算法平均運(yùn)行時(shí)間和后五次的算法平均運(yùn)行時(shí)間。每個(gè)問題的10次實(shí)驗(yàn)中前五次是沒有改進(jìn)降溫機(jī)制的，后五次是使用了改進(jìn)的降溫機(jī)制。為節(jié)省篇幅，實(shí)驗(yàn)數(shù)據(jù)采用整數(shù)。

算法測試在Window 10系統(tǒng)core i7的環(huán)境下進(jìn)行，測試的程序?yàn)镸ATLAB R2017b。每個(gè)TSP問題的實(shí)驗(yàn)初始溫度為97?目標(biāo)溫度為3?迭代次數(shù)L為5000。eil51問題，st70問題，eil76問題，pr107問題，lin105的降溫系數(shù)A為0.999，dantzig42問題、berlin52問題、kroA100問題、kroa150問題為0.99。從表中的平均值可看出本文算法的結(jié)果比較穩(wěn)定，這是因?yàn)槎赝嘶饳C(jī)制可以增強(qiáng)算法魯棒性。實(shí)驗(yàn)數(shù)據(jù)中得到的最優(yōu)解與參考解精度相近，從個(gè)別TSP問題中的到的最優(yōu)解已經(jīng)超越了參考解。從前五組與后五組的平均時(shí)間對比中可以得出在使用改進(jìn)的降溫方式以后，退火所需時(shí)間基本減少，加快了收斂速度。在針對城市數(shù)越多分布越復(fù)雜，降溫越慢的情況上，效果更加明顯。

為了更好地展現(xiàn)改進(jìn)后的模擬退火算法比改進(jìn)前收斂速度的加快情況，本文記錄并繪制了在不同城市規(guī)模下，各tsp測試結(jié)果的收斂曲線圖。因篇幅的長度限制，這里僅顯示st70在算法改進(jìn)前降溫系數(shù)為0.999（圖1），以及改進(jìn)后降溫系數(shù)為0.999（圖2）數(shù)據(jù)處理次數(shù)的測試結(jié)果。

在圖1和圖2兩幅圖中，曲線呈快速下降的趨勢說明是高溫狀態(tài)。而趨于平緩則是已經(jīng)到了低溫期。從圖中曲線的下降趨勢可以看出，算法在改進(jìn)前處理st70問題時(shí)，當(dāng)數(shù)據(jù)處理1×107次時(shí)路徑長度為1000～1500還處于快速縮短的過程。而算法改進(jìn)后當(dāng)數(shù)據(jù)處理1×107次時(shí)路徑長度為500～1000已經(jīng)處于平緩狀態(tài)。圖1的數(shù)據(jù)處理次數(shù)為52132245次，圖2的數(shù)據(jù)處理次數(shù)為26949830次，減少了近一半的處理次數(shù)，因此花費(fèi)時(shí)間也相應(yīng)的縮短了一半，所得到路徑長度是相近的。綜上所述，本文改進(jìn)后的模擬退火算法能夠提高時(shí)間效率，節(jié)省時(shí)間。

4 結(jié)論

本文提出了一種改進(jìn)的模擬退火算法，通過結(jié)合多種路徑變異方式保證了解的精準(zhǔn)度。創(chuàng)造了跳躍式降溫的降溫方式減少了運(yùn)算時(shí)間。在保證算法尋找全局最優(yōu)解能力的前提下，加快了從高溫到低溫的降溫過程。使模擬退火算法的概率跳變特性更具有自適應(yīng)性，利于算法尋優(yōu)，并將改進(jìn)的思想在程序中實(shí)現(xiàn)，通過對TSP不同實(shí)例的優(yōu)化實(shí)驗(yàn)結(jié)果及對比分析表明，本文設(shè)計(jì)的算法具有可行性，可以為想要在模擬退火算法解的質(zhì)量上做改進(jìn)的同行，提供縮短算法運(yùn)行時(shí)間的方法。該方法提高了針對TSP問題的優(yōu)化效率，但是目前只對能量值做出一個(gè)定性的判定，下一步將對能量值做出一個(gè)定量的分析，使跳躍溫度的判定更加準(zhǔn)確。

參考文獻(xiàn)（References）：

[1] 徐德明.改進(jìn)的遺傳混合蟻群算法在TSP問題中的應(yīng)用[J].計(jì)算機(jī)時(shí)代，2012（11）：31-32+36.

[2] 張夢，陳仕軍，李嘉賓，劉朝陽.基于模擬退火算法的一維下料研究[J].計(jì)算機(jī)時(shí)代，2017.12：1-4

[3] 杜鵬楨，唐振民，孫研.一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解[J].控制與決策，2014.29（10）：1729-1736

[4] 易正俊，李勇霞，易校石.自適應(yīng)蟻群算法求解最短路徑和TSP問題[J].計(jì)算機(jī)技術(shù)與發(fā)展，2016.26（12）：1-5

[5] 姚明海，王娜，趙連朋.改進(jìn)的模擬退火和遺傳算法求解TSP問題[J].計(jì)算機(jī)工程與應(yīng)用，2013.49（14）：60-65

[6] 郭中華，金靈，鄭彩英.人工神經(jīng)網(wǎng)絡(luò)求解TSP問題的改進(jìn)算法研究[J].計(jì)算機(jī)仿真，2014.31（4）：355-358

[7] 張家善，王志宏.基于信息素的改進(jìn)蟻群算法及其在TSP中的應(yīng)用[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013.43（22）：157-161

[8] 于宏濤，高立群，田衛(wèi)華.求解TSP的離散人工蜂群算法[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2015.36（8）：1074-1079

[9] 程博，楊育，劉愛軍等.基于遺傳模擬退火算法的大件公路運(yùn)輸路徑選擇優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2013.19（4）：879-887