求解TSP問題的改進(jìn)融合遺傳灰狼優(yōu)化算法

劉海龍,雷 斌,王菀瑩,柴 獲

(1. 蘭州交通大學(xué)機(jī)電技術(shù)研究所,甘肅 蘭州 730070;2. 蘭州交通大學(xué)交通運(yùn)輸學(xué)院,甘肅 蘭州 730070)

1 引言

旅行商問題(Travelling Salesman Problem,TSP)是組合優(yōu)化問題的典型代表之一,在現(xiàn)實(shí)工程問題中,許多優(yōu)化問題可建立TSP模型,其中包括交通工程、電子信息、物流工程等領(lǐng)域,因此TSP問題長(zhǎng)期以來是研究的熱點(diǎn)之一。

目前求解TSP問題的算法主要分為兩大類:精確算法和啟發(fā)式算法。由于在現(xiàn)實(shí)工程問題存在維度參差不齊、實(shí)時(shí)性要求強(qiáng)等因素,對(duì)算法的穩(wěn)定性、效率、準(zhǔn)確性等方面均有要求,因此相較于求解效率低的精確算法,啟發(fā)式算法能在較短時(shí)間內(nèi)得到符合需要的可行解,更適用于現(xiàn)實(shí)工程問題。

多年來各國研究人員根據(jù)TSP問題的特性對(duì)不同啟發(fā)式算法進(jìn)行了改進(jìn)與應(yīng)用,Yanlan Deng[1]等人提出了模擬退火混合細(xì)胞遺傳算法進(jìn)行求解,Absalom El-Shamir Ezugwu[2]等人提出了融合模擬退火的共生生物搜索優(yōu)化算法,余麗[3]等人提出了遺傳禁忌搜索算法,陳科勝[4]等人提出了自適應(yīng)升溫模擬退火算法進(jìn)行求解。

求解效率與求解精度是啟發(fā)式算法在求解TSP問題上存在的主要矛盾之一[5],控制精度與效率的平衡是目前TSP問題算法設(shè)計(jì)的核心之一。鑒于此,本文利用遺傳算法優(yōu)秀的全局尋優(yōu)能力和改進(jìn)后灰狼算法較強(qiáng)的局部搜索能力來對(duì)TSP問題進(jìn)行求解,并通過TSPLIB數(shù)據(jù)庫的標(biāo)準(zhǔn)算例,從穩(wěn)定性、精度、收斂速度、效率等幾個(gè)方面對(duì)比了幾種現(xiàn)有的的TSP求解算法進(jìn)行了驗(yàn)證分析,以期獲得更好的TSP問題求解方案。

2 灰狼優(yōu)化算法

灰狼算法(Grey Wolf Optimizer,GWO),在2014年首次由澳大利亞學(xué)者 Seyedali Mirjalili等人提出[6]?；依莾?yōu)化算法因其前期收斂速度快、參數(shù)少、易實(shí)現(xiàn)等特點(diǎn),提出的初期被廣泛應(yīng)用求解連續(xù)優(yōu)化問題[7],近些年,經(jīng)過許多研究者的探究與改進(jìn),GWO在多目標(biāo)優(yōu)化[8]、參數(shù)優(yōu)化[9]、復(fù)雜函數(shù)優(yōu)化[10]以及其它多種領(lǐng)域問題中的使用也越來越廣泛。

灰狼群體捕食過程中會(huì)嚴(yán)格遵循一種等級(jí)制度,等級(jí)從高到低分別為α、β、δ和ω,狼群在α、β狼的帶領(lǐng)下經(jīng)過跟蹤、包圍、攻擊三個(gè)步驟,最終達(dá)到捕獲獵物的目的。

灰狼算法則通過模擬這種等級(jí)制度,將每次迭代產(chǎn)生的候選解劃分為對(duì)應(yīng)等級(jí),其中當(dāng)前種群最優(yōu)解為α狼,次優(yōu)解是β狼,第三優(yōu)解為δ,其余均為ω狼,而獵物則代表全局最優(yōu)解。

在狩獵過程中,α、β、δ狼對(duì)狼群下達(dá)指令,ω狼會(huì)根據(jù)α、β、δ狼發(fā)出的指令來調(diào)整自身的位置,以此達(dá)到跟蹤的目的。

在GWO中,將灰狼包圍獵物的行為定義如下

(1)

(2)

(3)

(4)

(5)

灰狼攻擊獵物的行為定義如下

(6)

(7)

(8)

3 灰狼優(yōu)化算法的改進(jìn)與應(yīng)用

3.1 改進(jìn)的灰狼優(yōu)化算法的

3.2 改進(jìn)的融合遺傳灰狼優(yōu)化算法(GA-IGWO)

在將GWO用于求解TSP問題時(shí)發(fā)現(xiàn),原始灰狼優(yōu)化算法前期收斂速度快,但其全局搜索能力差,后期容易陷入局部最優(yōu)或迭代停滯的現(xiàn)象。另一方面,根據(jù)式(8)可知,獵物的位置根據(jù)α、β、δ的指令確定,而灰狼種群位置則會(huì)根據(jù)指令判斷獵物的位置進(jìn)行更新,導(dǎo)致原始灰狼優(yōu)化算法在后期開發(fā)過程中容易陷入局部最優(yōu)、穩(wěn)定性差等問題,因此初始解種群的優(yōu)劣對(duì)于后續(xù)種群的更新也有著相當(dāng)大的影響,選擇合適的初始種群對(duì)于GWO的求解精度也是關(guān)鍵因素之一。

首先利用遺傳算法(Genetic Algorithm,GA)全局搜索能力強(qiáng)的特點(diǎn)[16],對(duì)初步篩選優(yōu)秀個(gè)體生成初始灰狼種群,然后利用距離啟發(fā)因子將α、β、δ的指令劃分權(quán)重,對(duì)原始GWO的更新策略進(jìn)行改進(jìn)。

(9)

(10)

(11)

(12)

(13)

3.3 GA-IGWO算法流程

GA-IGWO算法流程見圖1。

圖1 改進(jìn)融合遺傳灰狼優(yōu)化算法流程圖

4 仿真分析

本實(shí)驗(yàn)統(tǒng)一在MATLAB仿真軟件內(nèi)進(jìn)行,軟件版本為2017b,計(jì)算機(jī)配置Intel(R) Core(TM) i7-9750H CPU @ 2.59 GHz,內(nèi)存8.00GB,從TSPLIB數(shù)據(jù)庫中隨機(jī)抽取8組算例進(jìn)行測(cè)試,結(jié)果將每種算法連續(xù)執(zhí)行30次后所得最優(yōu)解、平均值、標(biāo)準(zhǔn)差以及平均所用時(shí)間進(jìn)行對(duì)比,結(jié)果保留之小數(shù)點(diǎn)后四位。

為驗(yàn)證算法的有效性,將GA-IGWO與原始GWO以及文獻(xiàn)[11]提出的mGWO、文獻(xiàn)[8]提出的IGWO、文獻(xiàn)[13]提出的wdGWO、文獻(xiàn)[14]提出I-GWO進(jìn)行仿真對(duì)比,初始種群均為100,迭代次數(shù)均為100,仿真結(jié)果見表1。

表1 GA-IGWO與其它改進(jìn)GWO的實(shí)驗(yàn)數(shù)據(jù)

從表1的仿真結(jié)果分析,mGWO和IGWO是基于自適應(yīng)函數(shù)a的取值方式進(jìn)行改進(jìn),但與wdGWO和I-GWO基于搜索策略的改進(jìn)方式相比較,顯然基于搜索策略的改進(jìn)方式更有利于求解TSP問題,而本文提出GA-IGWO算法與列舉出來的四種改進(jìn)的灰狼優(yōu)化算法對(duì)比,在精度和穩(wěn)定性方面都優(yōu)于其它改進(jìn)算法。

為進(jìn)一步說明本文GA-IGWO算法的先進(jìn)性,將其與目前在TSP問題中應(yīng)用較廣泛的遺傳算法(GA)、模擬退火算法(SA)、禁忌搜索算法(TS)進(jìn)行仿真對(duì)比。為確保算法能收斂至合適的可行解,各算法設(shè)置參數(shù)不同。其中GA和TS設(shè)置初始種群均為100,最大迭代次數(shù)均為1600;SA初始溫度為目標(biāo)節(jié)點(diǎn)數(shù)的100倍,馬爾科夫鏈長(zhǎng)度100,溫度衰減參數(shù)0.99。仿真結(jié)果見表2。

表2 GA-IGWO與其它智能算法的實(shí)驗(yàn)數(shù)據(jù)

從表2的仿真結(jié)果分析,在求解TSP問題時(shí),相較于SA、TS和GA,GA-IGWO除了在求解時(shí)間上稍慢于GA,但在求解精度、穩(wěn)定性方面均占一定優(yōu)勢(shì)。從以上分析中可以得知,本文提出的算法在求解TSP問題中表現(xiàn)良好,在收斂精度和穩(wěn)定性方面均具有一定優(yōu)越性。

5 結(jié)束語

本文從種群初始化和搜索策略兩個(gè)角度對(duì)灰狼優(yōu)化算法進(jìn)行了改進(jìn),在利用遺傳算法進(jìn)行初始化種群篩選的同時(shí)將距離啟發(fā)因子引入到灰狼優(yōu)化算法的搜索策略中,提出了GA-IGWO算法,避免了GWO算法在求解TSP問題時(shí),由于前三個(gè)可行解之間的差距過大而導(dǎo)致整個(gè)種群產(chǎn)生巨大誤差的問題,同時(shí)提高了GWO算法的求解精度、收斂速度以及穩(wěn)定性。

仿真結(jié)果表明,改進(jìn)融合遺傳灰狼優(yōu)化算法在求解TSP問題時(shí),保留了遺傳算法的全局搜索能力和灰狼算法的局部搜索能力,并能利用較少的求解空間和時(shí)間得出最優(yōu)解。但是仍然存在易陷入局部最優(yōu)問題,所以下一步將在此基礎(chǔ)上對(duì)如何提高灰狼優(yōu)化算法在求解TSP問題時(shí)的精度進(jìn)行進(jìn)一步研究。