基于螢火蟲算法的最大值最小化著色旅行商問題的求解

王東明, 代 星, 孟祥虎, 徐向平, 李 俊

(東南大學復雜工程系統(tǒng)測量與控制教育部重點實驗室, 南京 210096)

0 引言

多旅行商問題(multiple traveling salesman problem, MTSP)是一種典型的組合優(yōu)化問題, 近年來, MTSP已被成功應用于各類優(yōu)化調度問題．著色旅行商問題(colored traveling salesman problem, CTSP)通過引入顏色來區(qū)分城市對旅行商多樣的可訪問性, 解決了MTSP難以描述城市可訪問性差別的難題[1]．本課題組提出的CTSP[2-4]及相關的應用研究[5-6]均以各旅行商的路徑總和最小化為目標, 而未考慮各旅行商間旅行結果路徑的差異,導致整個系統(tǒng)的效率下降．最大值最小化著色旅行商問題(min-max colored traveling salesman problem, MM-CTSP)采用最大旅行商路徑最小化的目標代替總路徑最小化的目標,有望一定程度地均衡各旅行商之間的旅行結果路徑差異,從而提高系統(tǒng)的運行效率[7]．遺傳算法(genetic algorithm, GA)能成功求解著色旅行商問題, 但當城市規(guī)模增加時,該算法的耗時急劇增加且解質量變差[7]．王艷[8]提出改進的離散化螢火蟲算法(firefly algorithm, FA)求解旅行商問題,并證明了FA的收斂速度優(yōu)于GA．Sayadi等[9]將FA算法應用到車間作業(yè)調度中,驗證了FA算法的求解結果優(yōu)于蟻群算法．于宏濤等[10]提出一種結合變鄰域搜索算法思想的離散人工螢火蟲算法求解旅行商問題, 并驗證了該算法的有效性．本文擬采用FA來求解MM-CTSP, 以均衡各旅行商間的行程, 并通過仿真實驗檢驗該方案的性能．

1 MM-CTSP模型

假設有m個商人和n個城市,m

MM-CTSP的目標是將最大旅行商的花費最小化, 其目標函數(shù)為

(1)

1) 所有商人的起始城市和終止城市是商人各自的起始城市:

∑ixdkik=1, ∑ixidkk=1, ?i∈Ik{dk}, ?k∈Z;

(2)

2) 商人k不能訪問不含顏色ck的城市:

∑i∑jxijk=0, ∑i∑jxjik=0, ?i∈V,?j∈VIk,?k∈Z;

(3)

3) 所有城市被訪問的次數(shù)為1:

∑i∑kxijk=1, ∑i∑kxjik=1,j≠i,?i,j∈Ik,?k∈Z;

(4)

4) 所有城市只能被一個商人訪問一次,即城市i被商人k訪問:

∑jxjik=∑lxilk,i≠j≠l,?j,i,l∈V;

(5)

5) 去除無效的子環(huán):

uik-ujk+nxijk≤n-1,j≠i, ?i,j∈Ik{dk}, ?k∈Z,

(6)

其中uik表示商人k的路徑中從起始城市dk到城市i的城市個數(shù)．

目標函數(shù)(1)及約束方程(2)～(6)構成MM-CTSP模型．由于通用CTSP已被證明是NP-hard問題[4],而在此基礎上提出的MM-CTSP依然是NP-hard問題,其精確求解很困難,故本文采用智能算法求解MM-CTSP．

2 螢火蟲算法

2.1 編碼設計

圖1 雙染色體編碼Fig.1 Dual-chromosome coding

采用雙染色體編碼[1]對CTSP進行編碼, 城市染色體描述城市編號序列,商人染色體描述訪問對應城市編號的商人編號．圖1給出了CTSP雙染色體編碼的2個示例, 其中城市染色體中前面3個節(jié)點是每個商人所對應的起始城市, 在每個商人路徑后須加入對應的起始城市．由圖1可見, 示例1,2中商人1的路徑為1-9-7-1, 商人2的路徑為2-6-8-2, 商人3的路徑為3-5-4-3．雙染色體編碼對不同的基因鏈解碼后得到的路徑可能相同,并且在執(zhí)行兩條基因編碼的交叉和變異操作后須重新確認城市編碼基因與旅行商編碼基因間對應關系的正確性, 故編碼方案耗時長,效率較低[2]．

直接路徑編碼中所有商人都有一個城市訪問序列, 如圖2所示,在每個商人的城市訪問序列后加上商人各自的起始城市即得到商人1的路徑為1-9-7-1, 商人2的路徑為2-6-8-2, 商人3的路徑為3-5-4-3．由于直接路徑的編碼與解碼一一對應, 故本文采用直接路徑編碼．

2.2 亮度與距離

適應度函數(shù)F=1/(1+fmax),fmax=max(f1,f2,…,fm), 其中fmax表示最大的旅行商路徑值,fi表示商人i的路徑值,i∈Z． 適應度值F越大表明解質量越好, 同時F也代表了螢火蟲的亮度．

螢火蟲之間的距離r=10d/n, 其中d為2個螢火蟲路徑存在差異邊的數(shù)目,n為城市的數(shù)目．

2.3 吸引力與螢火蟲更新

距離為r的2個螢火蟲之間的吸引力β(r)=β0e-γr2,β0是其中較亮的螢火蟲的亮度值,γ為光強吸收系數(shù)．

當螢火蟲i的亮度值小于螢火蟲j對螢火蟲i的吸引力值時, 螢火蟲i通過定點翻轉變異更新, 否則采取隨機翻轉變異．

圖3 翻轉變異Fig.3 Inversion mutation

翻轉螢火蟲i路徑中點x,y之間的路徑生成新的引火蟲i′, 如圖3所示．定點翻轉變異是通過存在的不同邊找到定點x,y并翻轉變異更新．隨機翻轉變異則隨機選取不相等的x,y進行翻轉變異更新．比較螢火蟲i和螢火蟲i′的亮度, 保留亮度大的螢火蟲．

圖4 FA算法流程示意圖Fig.4 Flow chart of FA

FA的算法流程如圖4所示．首先隨機初始化第一代螢火蟲種群,將當代種群中最亮的螢火蟲保留到下一代種群,然后對當代種群的所有螢火蟲進行翻轉變異更新,并將更新后的螢火蟲插入到下一代種群,直至達終止條件時最后一代種群中最亮螢火蟲的最大商人路徑即算法所得解．

3 實驗結果與分析

為了驗證螢火蟲算法求解MM-CTSP的性能, 設計10個案例分別從解質量、耗時和收斂速度等3個方面對FA與GA進行分析．

本文案例中所有數(shù)據的坐標來自TSPLIB問題庫．實驗平臺是安裝有32位Windows7操作系統(tǒng)的Dell Optiolex3020, CPU為Inter Core i3, 主頻3.4 GHz, 4 GB內存．算法程序采用C++實現(xiàn), 運行平臺為VS2013．所有案例中的城市坐標和城市顏色分配文件來源于https://pan.baidu.com/s/10hV2u5cdGLqTiFGh0Gd0fQ．

每個算法的種群個體設置為20, 各算法在達到105次函數(shù)評價時停止迭代更新, FA的光強吸收系數(shù)γ取0.06．所有案例運行算法10次, 取運行結果得到最大商人路徑的最優(yōu)解、最差解和平均值, 結果如表1及圖5所示．由表1和圖5可知,在案例1～3中, GA和FA的解質量相近, FA的耗時遠小于GA; 在案例4～10中, FA的解質量和耗時都優(yōu)于GA, 且隨著城市規(guī)模的增大, FA的解質量和耗時的優(yōu)勢更明顯．

表1 GA與FA求解MM-CTSP的實驗結果

圖5 平均解質量(a)及耗時(b)隨城市數(shù)目變化的關系曲線 Fig.5 Average solution quality and time consuming

圖6 案例6的進化曲線Fig.6 Evolutionary curve of case 6

圖6給出了2種算法在案例6中每代種群中最好個體的進化曲線．由圖7可知, 在105次函數(shù)評價下, FA的迭代次數(shù)僅為500代, GA的迭代次數(shù)為5 000代, 但是當FA迭代到約100代時即已收斂且解質量優(yōu)于GA．

綜上所述, 當求解MM-CTSP的城市規(guī)模小于76個時, GA與FA的解質量接近, 但FA的耗時較少;當城市規(guī)模大于76個時, FA的解質量優(yōu)于GA, 且耗時少, 收斂速度快,隨著城市規(guī)模的進一步增加,FA在解質量和耗時上的優(yōu)勢更明顯．