自適應(yīng)動態(tài)鄰域布谷鳥混合算法求解TSP問題

陳 雷，張紅梅，張向利

桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

1 引言

旅行商問題（Traveling Salesman Problem，TSP）是經(jīng)典的NP困難組合優(yōu)化問題[1]，該問題可描述為給定一組城市及城市之間的距離，求只經(jīng)過每座城市一次并返回出發(fā)地的最短路線。TSP問題具有廣泛的應(yīng)用背景，如物流配送、航線設(shè)計(jì)等，是組合優(yōu)化領(lǐng)域研究的熱點(diǎn)。近年來，啟發(fā)式算法已成為解決TSP問題的一種思路，如經(jīng)典的遺傳算法[2-3]、蟻群算法[4]、粒子群算法[5-7]和一些混合算法[8-9]，以及新型群智能優(yōu)化算法如蝙蝠算法[10-11]、帝國競爭算法[12]和布谷鳥搜索算法[13-17]等。這些算法為解決旅行商問題提供了優(yōu)秀的方案。

布谷鳥搜索算法（Cuckoo Search，CS）是Yang于2009年提出的一種群智能優(yōu)化算法[18]，它通過結(jié)合列維飛行機(jī)制與偏好隨機(jī)游走策略，在求解連續(xù)空間優(yōu)化問題方面具有優(yōu)良的性能[19]。同時(shí)也有一些學(xué)者將其改進(jìn)并應(yīng)用于求解組合優(yōu)化問題，如TSP問題，其中Ouaarab等人設(shè)計(jì)了離散布谷鳥算法（Discrete Cuckoo Search Algorithm，DCS）[13]和基于隨機(jī)鍵的布谷鳥算法（Random-Key Cuckoo Search，RKCS）[14]，DCS 算法使用2-opt和雙橋移動方式產(chǎn)生符合列維飛行機(jī)制的鄰域，以此離散化布谷鳥算法，但DCS算法在遍歷鄰域時(shí)未進(jìn)行篩選，且設(shè)置的步長概率是相同的，減緩了收斂速度，同時(shí)產(chǎn)生鄰域的方式太過單一，不利于快速找到最優(yōu)解；而RKCS算法引入了隨機(jī)鍵表示法，利用列維飛行后的鍵值排序產(chǎn)生結(jié)果，但此方案不僅增加了額外的解碼過程，也沒有發(fā)揮列維飛行的特點(diǎn)，全隨機(jī)排序增加了計(jì)算的復(fù)雜程度，降低了收斂效果。……