旅行商問題的混沌混合離散蝙蝠算法

戚遠(yuǎn)航,蔡延光,蔡 顥,湯雅連,呂文祥

(1.廣東工業(yè)大學(xué)自動化學(xué)院,廣東廣州510006;2.奧爾堡大學(xué)健康科學(xué)與技術(shù)系,丹麥奧爾堡9220)

?

旅行商問題的混沌混合離散蝙蝠算法

戚遠(yuǎn)航1,蔡延光1,蔡 顥2,湯雅連1,呂文祥1

(1.廣東工業(yè)大學(xué)自動化學(xué)院,廣東廣州510006;2.奧爾堡大學(xué)健康科學(xué)與技術(shù)系,丹麥奧爾堡9220)

針對現(xiàn)有離散蝙蝠算法在求解旅行商問題時(shí)存在的收斂速度較慢、收斂率不高等問題,提出了混沌混合離散蝙蝠算法.該算法采用混沌初始化策略提高算法的尋優(yōu)能力,引入2-Opt技術(shù)增強(qiáng)算法的局部搜索能力、加快算法的收斂速度.大量的仿真實(shí)驗(yàn)表明:所提出的算法在求解小規(guī)模TSP時(shí)能快速收斂到已知最優(yōu)解;在求解大規(guī)模TSP時(shí)能在較短的時(shí)間內(nèi)收斂到偏差0.4%以內(nèi)的最優(yōu)解.

旅行商問題;混沌初始化;蝙蝠算法;2-Opt

1 引言

旅行商問題(Traveling Salesman Problem,TSP)是組合優(yōu)化中的一個著名難題.其求解算法很多,如遺傳算法、蟻群算法、粒子群算法[1].

蝙蝠算法(Bat Algorithm,BA)是Xin-She YANG在2010年提出的一種元啟發(fā)式算法[2].李枝勇等[3]提出了離散型蝙蝠算法求解最小比率旅行商問題,A Rezaee Jordehi[4]提出了混沌蝙蝠群算法.但是,現(xiàn)有離散蝙蝠算法在求解TSP時(shí)存在著收斂速度較慢、收斂率不高等問題.

本文提出了混沌混合離散蝙蝠算法(Chaotic Hybrid Discrete Bat Algorithm,CHDBA).CHDBA采用混沌初始化策略提高算法的尋優(yōu)能力,引入2-Opt技術(shù)增強(qiáng)算法的局部搜索能力、加快算法的收斂速度.在大量的仿真實(shí)驗(yàn)中:與離散型蝙蝠算法[3](Discrete Bat Algorithm,DBA)、混合粒子群算法[5](Hybrid Particle Swarm Optimization,HPSO)相比,CHDBA在求解小規(guī)模TSP時(shí)能快速收斂到已知最優(yōu)解;與混合遺傳算法[6](Hybrid Genetic Algorithm,HGA)、離散型螢火蟲群優(yōu)化算法[7](Discrete Glowworm Swarm Optimization,DGSO)相比,CHDBA在求解大規(guī)模TSP時(shí)能在較短的時(shí)間內(nèi)收斂到偏差0.4%以內(nèi)的最優(yōu)解.

2 TSP的定義及其數(shù)學(xué)模型

給定n個城市以及各城市之間的距離,要求找到一條遍歷所有城市且每個城市只能被訪問一次的路徑,并使得總路徑長度最短.數(shù)學(xué)模型[8]:對于n個城市,遍歷所有城市且只能被訪問一次的路徑為C=(c1,c2,…,cn),使

(1)

其中,d(ci,ci+1)為城市ci、ci+1之間的距離,i=1,2,…,n-1,d(cn,c1)為cn、c1之間的距離.

3 混沌混合離散蝙蝠算法

3.1 參數(shù)定義與算子設(shè)計(jì)

①蝙蝠位置:第i個蝙蝠的位置定義為xi=(xi1,xi2,…,xin),其中n為城市的個數(shù),i=1,2,…,Q(Q∈N+為種群規(guī)模),(xi1,xi2,…,xin)是(1,2,…,n)的一個置換.xi表示第i個蝙蝠的城市遍歷路徑為xi1→xi2→…→xin→xi1.

②蝙蝠速度:第i個蝙蝠的速度定義為vi={(si1,ti1),(si2,ti2),…,(sin,tin)},其中sim,tim∈{1,2,…,n},m=1,2,…,n.

③蝙蝠頻率:第i個蝙蝠的頻率定義為fi∈[0,1].

(2)

(3)

其中:α、γ均為常數(shù),0<α<1、γ>0;t=1,2,….

⑤置換操作:設(shè)第i個蝙蝠的位置為xi=(xi1,xi2,…,xin),wi=(k1,k2)為置換序列,其中k1,k2=1,2,…,n.xi的基于wi的置換操作是指xi中第k1分量和第k2分量互換位置.

3.2 混沌初始化

3.2.1 Logistic映射

選用Logistic映射來產(chǎn)生混沌序列:

zi+1=μzi(1-zi)

(4)

其中0≤zi≤1且zi≠0.25,0.5,0.75,i=0,1,2,…,μ=4.

3.2.2 混沌量與路徑的對應(yīng)關(guān)系

應(yīng)用全排列構(gòu)造理論[9]建立序號D(D∈{1,…,n!})與路徑(即1,2,…,n的全排列)的對應(yīng)關(guān)系.

以(1,2,3)的全排列為例,序號D、向量V和構(gòu)造C(即路徑)組成了DVC表,如表1所示.

表1 (1,2,3)全排列的DVC表

①D/V轉(zhuǎn)換公式:

(5)

其中i=1,2,…,n-1.

以(1,2,3)的全排列為例,n=3;取序號D=3,根據(jù)式(5)可得V=(v1,v2)=(2,2).

②V/C轉(zhuǎn)換

通過向量V的指針功能來確定構(gòu)造C.

以V=(2,2)為例,轉(zhuǎn)換步驟如表2所示.

表1 V/C轉(zhuǎn)換步驟

從表2可看出,C=(c1,c2,c3)=(2,3,1).

③混沌量可以與向量V的轉(zhuǎn)換公式

由式(4)產(chǎn)生混沌量zi,則D0=n!zi,代入式(5),令d1=nzi,得

(6)

其中i=2,3,…,n-1.

混沌量zi與向量V對應(yīng),再通過V/C轉(zhuǎn)換,混沌量zi便可與構(gòu)造C(即路徑)對應(yīng).

3.2.3 混沌初始化策略

當(dāng)蝙蝠種群初始化時(shí),通過式(4)和式(6)生成一定數(shù)量的可選擇的蝙蝠位置,擇優(yōu)初始化蝙蝠種群,以此加快算法的收斂速度.

3.3 2-Opt算法

2-Opt算法示意圖如圖1所示,其中沒有標(biāo)號的頂點(diǎn)代表兩個或者兩個以上頂點(diǎn)間一系列的邊.如果ab+cd>ac+bd成立,則刪除邊ab和cd,同時(shí)增加邊ac和bd,并把頂點(diǎn)b、c之間的邊反向[10].

3.4 算法步驟

第2步:根據(jù)初始蝙蝠種群中每個蝙蝠的xi計(jì)算函數(shù)適應(yīng)值fitnessi,初始化全局最優(yōu)解x*和fitness*.

第8步:如果Nnow

第9步:輸出全局最優(yōu)解x*.

4 算法測試

4.1 實(shí)驗(yàn)環(huán)境與算法參數(shù)設(shè)置

實(shí)驗(yàn)軟件為VS2008,CPU為Intel Core i7 2.30GHz,內(nèi)存為4GB,Window 7操作系統(tǒng).

在仿真實(shí)驗(yàn)的分析中,收斂率、偏差分別由式(7)、(8)定義,“已知最優(yōu)解”是指TSPLIB標(biāo)準(zhǔn)庫提供的最優(yōu)解,“——”是指所參考的文獻(xiàn)并未提供該相關(guān)數(shù)據(jù).

收斂率 (7) 偏差 (8) 表3 CHDBA在不同TSP算例中種群規(guī)模和最大迭代次數(shù)的取值

4.2 小規(guī)模TSP實(shí)驗(yàn)與分析

小規(guī)模TSP實(shí)驗(yàn)中,將CHDBA和DBA、HPSO進(jìn)行比較,實(shí)驗(yàn)結(jié)果如表4所示.

從表4可以看出,針對小規(guī)模TSP,CHDBA具有較好的尋優(yōu)能力(所有算例均收斂到已知最優(yōu)解),偏差為0,收斂率為100%,較少的時(shí)間耗費(fèi).圖2(a)為CHDBA優(yōu)化Eil51的最優(yōu)解.

表4 小規(guī)模TSP實(shí)驗(yàn)結(jié)果

4.3 大規(guī)模TSP實(shí)驗(yàn)與分析

大規(guī)模TSP實(shí)驗(yàn)中,將CHDBA和HGA、DGSO進(jìn)行比較,實(shí)驗(yàn)結(jié)果如表5所示.

從表5可以看出,針對大規(guī)模TSP,CHDBA能收斂到偏差0.4%以內(nèi)的最優(yōu)解,尋優(yōu)能力比DGSO、HGA更強(qiáng),而相對于HGA,CHDBA耗費(fèi)的時(shí)間更少.尤其在Krob200中,CHDBA雖然也沒有收斂到已知最優(yōu)解,但是收斂結(jié)果為29554.13,偏差僅為0.39%,比DGSO降低了0.18%,比HGA降低了0.02%,耗費(fèi)的時(shí)間卻僅為HGA的1/4.圖2(b)、2(c)、2(d)分別為CHDBA優(yōu)化Ch130、Krob150和Krob200的最優(yōu)解.

表5 大規(guī)模TSP實(shí)驗(yàn)結(jié)果

5 結(jié)語

本文提出的CHDBA采用混沌初始化策略提高算法的尋優(yōu)能力,引入2-Opt技術(shù)增強(qiáng)算法的局部搜索能力、加快算法的收斂速度.大量的仿真實(shí)驗(yàn)表明:CHDBA在求解小規(guī)模TSP時(shí)能快速收斂到已知最優(yōu)解,在求解大規(guī)模TSP時(shí)能在較短的時(shí)間內(nèi)收斂到偏差0.4%以內(nèi)的最優(yōu)解.今后工作仍需進(jìn)行更多的數(shù)值實(shí)驗(yàn)和對算法的參數(shù)取值做進(jìn)一步的研究.

[1]高海昌,馮博琴,朱利.智能優(yōu)化算法求解TSP問題[J].控制與決策,2006,21(3):241-247.

GAO Hai-chang,FENG Bo-qin,ZHU Li.Reviews of the meta-heuristic algorithms for TSP [J].Control and Decision,2006,21(3):241-247.(in Chinese)

[2]Xin-She YANG.A new metaheuristic bat-inspired algorithm [J].Nature Inspired Cooperative Strategies for Optimization,2010,284:65-74.

[3]李枝勇,馬良,張慧珍.求解最小比率旅行商問題的離散蝙蝠算法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(2):356-359.

LI Zhi-yong,MA Liang,ZHANG Hui-zhen.Discretebat algorithm for solving minimum ratio traveling salesman problem [J].Application Research of Computers,2015,32(2):356-359.(in Chinese)

[4]A Rezaee Jordehi.Chaotic bat swarm optimization (CBSO) [J].Applied Soft Computing,2015,26:523-530.

[5]俞靚亮,王萬良,介婧.基于混合粒子群優(yōu)化算法的旅行商問題求解[J].計(jì)算機(jī)工程,2010,36(11):183-184.

YU Liang-liang,WANG Wan-liang,JIE Jing.Solution of travel salesman problem based on hybrid particle swarm optimization algorithm [J].Computer Engineering,2010,36(11):183-184.(in Chinese)

[6]Yong Wang.The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem [J].Computers & Industrial Engineering,2014,70:124-133.

[7]周永權(quán),黃正新,劉洪霞.求解TSP問題的離散型螢火蟲群優(yōu)化算法[J].電子學(xué)報(bào),2012,40(6):1164-1170.

ZHOU Yong-quan,HUANG Zheng-xin,LIU Hong-xia.Discrete glowworm swarm optimization algorithm for TSP problem [J].Acta Electronica Sinica,2012,40(6):1164-1170.(in Chinese)

[8]Marjan Kuchaki Rafsanjani,Sadegh Eskandari,Arsham Borumand Saeid.A similarity-based mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem [J].Neural Computing and Applications,2015,26(1):213-222.

[9]高尚.解旅行商問題的混沌蟻群算法[J].系統(tǒng)工程理論與實(shí)踐,2005,25(9):100-104.

GAO Shang.Solving traveling salesman problem by chaos ant colony optimization algorithm [J].System Engineering Theory and Practice,2005,25(9):100-104.(in Chinese)

[10]姜昌華,戴樹貴,胡幼華.求解車輛路徑問題的混合遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2007,13(10):2047-2052.

JIANG Chang-hua,DAI Shu-gui,HU You-hua.Hybrid genetic algorithm for capacitated vehicle routing problem [J].Computer Integrated Manufacturing Systems,2007,13(10):2047-2052.(in Chinese)

戚遠(yuǎn)航 男,1993年6月出生,廣東湛江人.現(xiàn)為廣東工業(yè)大學(xué)碩博連讀生,從事供應(yīng)鏈物流及智能算法的研究.

E-mail:qiyuanhang77@163.com

蔡延光 男,1963年2月出生,湖北咸寧人.1988年和1996年分別在重慶大學(xué)和浙江大學(xué)獲理學(xué)碩士和工學(xué)博士學(xué)位.現(xiàn)為廣東工業(yè)大學(xué)教授,博士生導(dǎo)師,從事復(fù)雜網(wǎng)絡(luò)系統(tǒng)建模、控制與優(yōu)化、物流控制與優(yōu)化、智能交通系統(tǒng)、組合優(yōu)化、智能優(yōu)化、物聯(lián)網(wǎng)信息處理與優(yōu)化控制等方面的研究.

Chaotic Hybrid Discrete Bat Algorithm for Traveling Salesman Problem

QI Yuan-hang1,CAI Yan-guang1,CAI Hao2,TANG Ya-lian1,Lü Wen-xiang1

(1.SchoolofAutomation,GuangdongUniversityofTechnology,Guangzhou,Guangdong510006,China;2.DepartmentofHealthScience&Technology,AalborgUniversity,Aalborg9220,Denmark)

In view of some problems,like slow convergence speed and low constringency rate,arising during the process of applying discrete bat algorithms to solve travelling salesman problem,a chaotic hybrid discrete bat algorithm is proposed.The proposed algorithm adopts chaotic initialization strategy to improve the capability of optimization,and the 2-Opt to enhance the capability of local search and to speed up the convergence speed.A large amount of simulations show that the algorithm can achieve their solutions rapidly for some small scale traveling salesman problems,and obtain their solutions in a relatively short time with the error less than 0.4% for large ones.

traveling salesman problem;chaotic initialization;bat algorithm;2-Opt

2015-03-24；

2015-06-04；責(zé)任編輯：李勇鋒

國家自然科學(xué)基金(No.61074147)；廣東省自然科學(xué)基金(No.S2011010005059)；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目(No.2012B091000171，No.2011B090400460)；廣東省科技計(jì)劃項(xiàng)目(No.2012B050600028，No.2014B010118004)；廣州市花都區(qū)科技計(jì)劃項(xiàng)目(No.HD14ZD001)

TP301

A

0372-2112 (2016)10-2543-05

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.037