求解TSP問題的改進融合遺傳灰狼優化算法

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

(1. 蘭州交通大學機電技術研究所,甘肅 蘭州 730070;2. 蘭州交通大學交通運輸學院,甘肅 蘭州 730070)

1 引言

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

目前求解TSP問題的算法主要分為兩大類:精確算法和啟發式算法。由于在現實工程問題存在維度參差不齊、實時性要求強等因素,對算法的穩定性、效率、準確性等方面均有要求,因此相較于求解效率低的精確算法,啟發式算法能在較短時間內得到符合需要的可行解,更適用于現實工程問題。

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

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

2 灰狼優化算法

灰狼算法(Grey Wolf Optimizer,GWO),在2014年首次由澳大利亞學者 Seyedali Mirjalili等人提出[6]。灰狼優化算法因其前期收斂速度快、參數少、易實現等特點,提出的初期被廣泛應用求解連續優化問題[7],近些年,經過許多研究者的探究與改進,GWO在多目標優化[8]、參數優化[9]、復雜函數優化[10]以及其它多種領域問題中的使用也越來越廣泛。

灰狼群體捕食過程中會嚴格遵循一種等級制度,等級從高到低分別為α、β、δ和ω,狼群在α、β狼的帶領下經過跟蹤、包圍、攻擊三個步驟,最終達到捕獲獵物的目的。

灰狼算法則通過模擬這種等級制度,將每次迭代產生的候選解劃分為對應等級,其中當前種群最優解為α狼,次優解是β狼,第三優解為δ,其余均為ω狼,而獵物則代表全局最優解。

在狩獵過程中,α、β、δ狼對狼群下達指令,ω狼會根據α、β、δ狼發出的指令來調整自身的位置,以此達到跟蹤的目的。

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

(1)

(2)

(3)

(4)

(5)

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

(6)

(7)

(8)

3 灰狼優化算法的改進與應用

3.1 改進的灰狼優化算法的

3.2 改進的融合遺傳灰狼優化算法(GA-IGWO)

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

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

(9)

(10)

(11)

(12)

(13)

3.3 GA-IGWO算法流程

GA-IGWO算法流程見圖1。

圖1 改進融合遺傳灰狼優化算法流程圖

4 仿真分析

本實驗統一在MATLAB仿真軟件內進行,軟件版本為2017b,計算機配置Intel(R) Core(TM) i7-9750H CPU @ 2.59 GHz,內存8.00GB,從TSPLIB數據庫中隨機抽取8組算例進行測試,結果將每種算法連續執行30次后所得最優解、平均值、標準差以及平均所用時間進行對比,結果保留之小數點后四位。

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

表1 GA-IGWO與其它改進GWO的實驗數據

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

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

表2 GA-IGWO與其它智能算法的實驗數據

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

5 結束語

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

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