基于最好最差螞蟻路徑差異的獎懲蟻群算法

(廣東石油化工學院 計算機與電子信息學院,廣東茂名,525000)

1 引言

蟻群算法(Ant Colony Optimal, ACO)是一種基于種群的啟發(fā)式智能搜索算法，是由意大利學者Dorigo M.等人提出的[1]，具有全局優(yōu)化、良好的可擴充性，支持并行分布式計算等特點。作為一種概率搜索算法，蟻群中的螞蟻運動是隨機的，容易陷入局部最優(yōu)而無法找到全局最優(yōu)解。近年來的研究對基本蟻群算法提出了一些改進，如ACS(Ant Colony System )系統(tǒng)，MAX-MIN蟻群系統(tǒng)(MAX-MIN Ant System, MMAS)，至今的實驗研究表明，ACS和MMAS是目前蟻群算法中公認的效果較好的兩種算法[2]，特別是MMAS算法，在采用最優(yōu)螞蟻的路徑信息更新信息素的同時限制信息素的范圍，以防止信息素的過度累積或過小，保證了收斂和探索的平衡,取得了較好的效果且運算速度較快。但信息素的更新沒考慮不同路段的差異性，導致算法存在搜索效率低和解的穩(wěn)定度差等缺點[3]。本文在MMAS算法的基礎上，提出基于最好最差螞蟻路徑差異獎懲的信息素更新策略，通過比較最優(yōu)最差螞蟻的路徑差異，進一步突出不同路段對路徑的差異貢獻，實施區(qū)分獎懲的信息素更新策略，增強信息素釋放的針對性，加快算法的搜索效率和增加最優(yōu)解的穩(wěn)定性。

2 蟻群算法簡介

其中，allowedk表示螞蟻k下一步允許訪問的城市的集合，訪問過的城市，不允許重復訪問。

螞蟻完成一次循環(huán)后，M只螞蟻構(gòu)建了路徑的集合T，按式(2)，對各條路徑上的信息素進行更新。

(2)

其中Ck代表了第k只螞蟻建立的路徑Tk的長度或旅行代價，Q是計算信息素的度量系數(shù)，Q的大小對算法性能影響不大，通常取100[4]。

MMAS算法在AS算法的基礎上做了一些改進：只有最優(yōu)螞蟻(迭代最優(yōu)或至今最優(yōu))才可以釋放信息素，信息素更新策略如式(4)[3]；將信息素大小的取值范圍限制在區(qū)間[τmin,τmax]內(nèi)，且將信息素的初值設定為取值范圍的上界。

3 基于最好最差螞蟻路徑差異獎懲的改進蟻群算法

3.1 基本思想

蟻群算法是通過種群內(nèi)螞蟻個體之間的競爭、協(xié)作實現(xiàn)種群整體的協(xié)同進化達到對最優(yōu)解的搜索。信息素的更新策略是影響算法性能的關(guān)鍵因素，MMAS算法每一次迭代后，只有最優(yōu)螞蟻才可以更新對應路徑上的信息素，強化了對后面螞蟻的引導，通過限制信息素的范圍，擴大了最優(yōu)解區(qū)域的搜索。信息素范圍的限制也使較差解被選中的概率增大了，存在太多無效搜索，影響了進化效率。

一條路徑由多個路段組成，路徑優(yōu)劣差異主要由組成路徑的路段的差異所造成。通常情況下，好的路徑中含有較多的較好路段，差的路徑中含有較多的較差路段。MMAS對最優(yōu)螞蟻進行獎勵的策略利用了好的路徑中含有較多的較好路段這一信息，如果也利用差的路徑中含有較多較差路段的信息，選取較差螞蟻的典型代表迭代最差螞蟻，對其進行懲罰，加速較差路段信息素的蒸發(fā)，減少其出現(xiàn)概率，將加速解的收斂，提高解的穩(wěn)定性?；诖朔N認識，本文通過最優(yōu)最差螞蟻路徑的比對，進一步突出其差異路段在構(gòu)成路徑代價中的不同貢獻，采取區(qū)分性獎懲策略，增強信息素釋放的針對性,提高搜索效率，增加解的穩(wěn)定性。

3.2 最好最差螞蟻路徑差異獎懲規(guī)則

(1) 路徑矩陣的生成

一只螞蟻k在一次求解過程中，所形成路徑為Tk，路徑包含的節(jié)點按順序排列Tk(α1α2,...,αn-1αn)，αi∈{1,2,...,n},1≤i≤n。

路徑中相鄰的兩個節(jié)點之間的路徑構(gòu)成一個路段，最后一個節(jié)點與第一個節(jié)點構(gòu)成一個路段lαnα1，一條路徑Tk有N個路段，構(gòu)成路徑的路段集合。

Tkc={lα1α2,...,lαn-1αn,lαnα1},αi∈{1,...,n}, 1≤i≤n;

(5)

定義一個路徑Tk的路徑矩陣Rk，表示路徑中含有的路段。如果路段 lij∈Tkc，則rij=1；否則rij=0,如式(6)。矩陣數(shù)據(jù)可直接用于相同、相異路段、局部信息素的生成計算，提高算法效率。

(2)信息素獎懲策略

對比一次迭代內(nèi)的M條路徑，選擇迭代最優(yōu)、最差螞蟻路徑Tnbest,Tnworst，生成路徑矩陣Rnbest,Rnworst，比較兩者的相同或相異路段，如式(7)生成相同路段Rsame，最優(yōu)路徑矩陣Rnbest減去相同路段Rsame余下部分稱為獎勵路段Rpremium，這部分路段在最優(yōu)解與最差解的差異中貢獻最大，通常該部分路徑中含有較好的路段(解元素)，需要進行額外獎勵；最差路徑矩陣Rnworst減去相同路段Rsame余下部分稱為懲罰路段Rpenalty，這部分路段是導致路徑整體效果差的主要因素，其中必定含有較差的路段(解元素)，所以要降低這部分路段的信息素，減弱其被選中的概率，降低對無用區(qū)域的搜索概率。

Rsame=Rnbest&Rnworst;

Rpremuim=Rnbest-Rsame;

Rpenalty=Rnworst-Rsame;

(7)

3.3 算法框架

算法流程和MMAS算法基本相同，在step4中，除利用最優(yōu)螞蟻更新信息素外，增加了本文提出的最優(yōu)最差螞蟻相異路徑計算、區(qū)分獎懲的策略。

Step1.初始化，取ρ=0.02，設定τmax,τmin；按τmax初始化信息素矩陣，初始化迭代次數(shù)NC=1，NC_max為設定的最大迭代次數(shù)。

Step2.當NC≤NC_max時，進入Step3，否則進入Step6。

Step3.一次迭代內(nèi)構(gòu)建路徑，m螞蟻隨機放在n個城市，讀取路徑禁忌表，按公式(2)，按照輪賭盤規(guī)則選擇下一步移動城市，構(gòu)建m條路徑。

Step4.對比生成的m條路徑，按3.2.2描述的獎懲規(guī)則，選出最好(或選擇至今最優(yōu))、最差螞蟻路徑。，生成相同路段，獎勵路段Rpremium，懲罰路段Rpenalty， 按式(8)、(9)生成τij。按式(10)[2]更新全局信息素。

Step5.清零局部信息素，迭代次數(shù) NC增加1。

Step6.循環(huán)結(jié)束，輸出結(jié)果。

4 實驗仿真

在Matlab7.0下，實現(xiàn)本文算法(Premium Penalty-MMAS，PP-MMAS)和MMAS算法，實驗中取α=1.0，β=5.0，m=n，ρ=0.02，Pbest=0.05，Q=100。本文算法中，獎懲系數(shù)ε=0.1，每組數(shù)據(jù)實驗20次，對TSP問題測試集中的Eil51，Eil101，D198三組測試數(shù)據(jù)進行了實驗。

圖1為本文算法求得的eil51問題最優(yōu)路線, 路線距離為426等于該問題的已知最優(yōu)解[5]，三組數(shù)據(jù)實驗結(jié)果如表1所示，20次實驗中本文算法找到的最優(yōu)解的最小迭代次數(shù)小于MMAS算法，反映了本文算法的搜索效率較高；本文算法求得的最優(yōu)解的平均值優(yōu)于MMAS算法，方差小于MMAS算法，說明本文算法對最優(yōu)解區(qū)域的搜索引導加強，求解的質(zhì)量、解的穩(wěn)定度都有提高。實驗數(shù)據(jù)圖表均說明了算法改進的有效性。

表1 MMAS和本文算法的仿真數(shù)據(jù)結(jié)果

5 結(jié)束語

本文在MMAS算法的基礎上，提出一種基于最好最差螞蟻路徑差異獎懲的信息素更新策略，通過比較最優(yōu)最差螞蟻的路徑差異，進一步突出不同路段對路徑的差異貢獻，實施信息素區(qū)分性獎懲，增強信息素釋放的針對性，強化對蟻群的搜索引導，提高了算法求解的效率和穩(wěn)定度，通過一些TSP問題數(shù)據(jù)集的測試，驗證了算法策略的有效性。