甘 屹，李 勝

（上海理工大學(xué) 機(jī)械工程學(xué)院，上海 200093）

0 引言

蟻群優(yōu)化(Ant Colony Optimization, ACO)是一種模擬自然界螞蟻尋找食物的行為智能優(yōu)化算法[1]。目前，對ACO 算法的研究已經(jīng)由單一的旅行商問題(Traveling Salesman Problem, TSP)領(lǐng)域擴(kuò)展到了多個應(yīng)用領(lǐng)域。在運用蟻群算法求解問題時，參數(shù)數(shù)值的設(shè)置直接影響算法的收斂性。本文通過正交試驗法獲取小生境蟻群優(yōu)化（Microhabitat ACO，MACO）[2,3]的參數(shù)配置，對小生境蟻群算法性能進(jìn)行優(yōu)化。并用以求解旅行商問題(Traveling Salesman Problem, TSP)[4,5]和車間調(diào)度問題（job shop scheduling Problems，JSSP）問題[6]。

1 小生境蟻群優(yōu)化概述

針對基本蟻群算法存在的問題，MACO從蟻群信息素分布多樣性、更新信息素策略、信息差突變等機(jī)制上，對基本蟻群算法進(jìn)行改進(jìn)，并應(yīng)用于求解動態(tài)聯(lián)盟伙伴選擇問題和車間調(diào)度問題[2]。

MACO對經(jīng)驗信息和啟發(fā)信息的利用是隨著搜索演化進(jìn)程而變化的。在蟻群搜索最優(yōu)解的初期，小生境中可利用的經(jīng)驗信息還不多，這時螞蟻運用初始啟發(fā)信息，以“探索”為主；隨著搜索的演進(jìn)，小生境中經(jīng)驗信息增多，這時螞蟻的搜索則以“利用”經(jīng)驗信息為主，加速解的收斂；而到了搜索的后期，要避免算法早熟、停滯的現(xiàn)象，就要在已有解的基礎(chǔ)上“再探索”，以擴(kuò)大解的搜索空間，使更優(yōu)解得以突現(xiàn)。

MACO算法的螞蟻更新信息素的方式有兩種：局部更新和全局更新。局部更新規(guī)則是螞蟻每移向下一個結(jié)點，就會在該路徑上留下信息素；全局更新則是在每一次搜索周期結(jié)束時（即所有尋優(yōu)群體都搜索結(jié)束時），更新全部路徑的信息素。全局更新考慮了每一批尋優(yōu)群體尋路的結(jié)果，隱含了信息反饋，使得算法更容易趨優(yōu)。本文采用全局更新。

MACO算法還生成小生境信息差（Information Difference），以增加信息的多樣性，擴(kuò)大搜索空間。根據(jù)具體問題的特點，小生境信息差可以有不同的產(chǎn)生方法。對于TSP，本文對每代螞蟻搜索的解采用遺傳操作（遺傳交叉，遺傳變異），產(chǎn)生小生境信息差，擴(kuò)大解的搜索空間，保證更優(yōu)解的突現(xiàn)。 對于JSSP，本文的選擇概率選擇下一可達(dá)結(jié)點時，以隨機(jī)概率產(chǎn)生小生境信息差[3]，以跳出局部最優(yōu)，擴(kuò)展搜索范圍，保持解的多樣性。

MACO算法的參數(shù)包括關(guān)于啟發(fā)信息、經(jīng)驗信息的α0，β0，kα和kβ等，這些參數(shù)體現(xiàn)出蟻群優(yōu)化進(jìn)行尋優(yōu)的同時和真實螞蟻受環(huán)境影響一樣，也受到多種因素的影響。這些參數(shù)的取值直接關(guān)系到算法的尋優(yōu)效能。

2 正交試驗設(shè)計

針對蟻群優(yōu)化多參數(shù)的多種取值，本文運用小生境蟻群優(yōu)化算法求解TSP和JSSP問題，利用正交試驗法分析參數(shù)α0、β0、kα、kβ對算法尋優(yōu)性能的影響。

2.1 正交試驗因素與水平

在小生境蟻群優(yōu)化中，一次螞蟻搜索循環(huán)是指所有螞蟻從初始節(jié)點出發(fā)，找到一條符合條件的路徑的過程。如果最大循環(huán)次數(shù)NC_m過大，會使算法的收斂時間比較長；如果NC_m偏小，會使算法的結(jié)果隨機(jī)性能增加，影響尋優(yōu)性能。通過大量實例計算，一般NC_m=500時，算法性能較穩(wěn)定。同樣，如果螞蟻數(shù)目越大，算法的全局搜索能力越強(qiáng)，但是算法的計算速度將成指數(shù)級遞增。對于TSP，螞蟻數(shù)目一般為城市規(guī)模n的2/3[7]。對于JSSP, 每代的螞蟻數(shù)目取為工件數(shù)目[8]。通過大量實例計算，本文中，對于TSP，信息揮發(fā)率ρ=0.1,對于JSSP，ρ=0.7。

在正交試驗中，選取各參數(shù)的代表性取值。取α0、β0分別以1的步長遞增，lgkα、lgkβ分別取-4.699、-4、-3.699、-3、-2.699。取實驗10次的平均值作為實驗結(jié)果。影響MACO求解的因素與水平如表1所示。由于小生境信息差中的信息是相互關(guān)聯(lián)的[2]，所以考慮α0和β0，kα和kβ，α0和kα以及β0和kβ之間可能存在交互作用，希望通過正交實驗設(shè)計找出好的因素水平搭配。本文測試的仿真編程軟件為MATLAB R2008b，操作系統(tǒng)為Windows XP，CPU為2.0GHz，內(nèi)存為1.99GB。

表1 正交試驗因素和水平

這是個4因素5水平的正交試驗，考慮到的交互交互作用有4個，所以采用L50 (511)正交表進(jìn)行試驗。對應(yīng)的表頭設(shè)計如表2所示。

表2 L50 (511)表頭設(shè)計

2.2 試驗結(jié)果

表3是根據(jù)正交表 L25 (56)表頭測試48個城市的Att48問題[9]的結(jié)果及分析。其中，

Tour_ length =(算法計算所得最短距離-已知最優(yōu)解)/已知最優(yōu)解×100%

Iteration _Time =(算法計算所得最短耗費時間-已知最優(yōu)解)/已知最優(yōu)解×100%

根據(jù)表3計算出每列的極差。極差最大的因素意味著它的不同水平造成的實驗差別比較大，由此確定出各個因素對MACO在求解TSP問題的重要性，如表4所示。

表3 各方案的試驗結(jié)果

設(shè)目標(biāo)函數(shù)f(x)=minL。由表4可知，若L為旅行距離，則各因素指標(biāo)影響的重要性順序為：α0＞β0＞kα＞ kβ＞α0×β0＞β0×kβ＞α0×kα＞kα×kβ；若L為耗費時間，則各因素指標(biāo)影響的重要性順序為：α0＞ kα×kβ＞β0＞kβ＞ kα＞α0×β0＞α0×kα＞β0×kβ。這也說明求解該問題不能同時滿足兩個目標(biāo)函數(shù)最優(yōu)。

由表4可得正交水平與因素的關(guān)系，如圖1所示。圖1中，目標(biāo)函數(shù)為f(x)=minL，若L為旅行距離，各因素的最佳組合為，α0=1，β0=3，kα=0.0002，kβ=0.001；若L為耗費時間，各因素的最佳組合為，α0=1，β0=1，kα=0.002，kβ=0.001。

表4 各方案下實驗指標(biāo)結(jié)果分析

圖1 正交水平與因素的關(guān)系

3 計算和結(jié)果分析

3.1 計算

對于TSP問題，考慮不同的城市規(guī)模，選用4個TSP基準(zhǔn)算例[9]：Bayg29, Att48, Kroc100,A180。目標(biāo)函數(shù)f(x)=minL，L為旅行距離，得到的解如表5所示。

表5 通過正交試驗得到的TSP參數(shù)配置

對于JSSP問題，選用6個JSSP基準(zhǔn)算例[10]：FT06, FT10, FT20, LA06,LA22,LA22。目標(biāo)函數(shù)為單位工時，得到的解如表6所示。

表6 通過正交試驗得到的JSSP參數(shù)配置

3.2 結(jié)果分析

表7給出了目標(biāo)函數(shù)f(x)=minL（L為旅行距離），利用正交試驗優(yōu)化配置參數(shù)，求解以上4個算例的結(jié)果。

表7 參數(shù)配置后的計算結(jié)果

注：N-城市規(guī)模，Opt.-樣例的已知最優(yōu)解，Best-獲得的最好解，Ave. -平均最優(yōu)解，Orig.-優(yōu)化配置以前的結(jié)果（隨機(jī)20次的平均值）。

由表7可以看出，通過優(yōu)化配置參數(shù)的最優(yōu)解與隨機(jī)解相比，更接近已知的最優(yōu)解，說明正交試驗的參數(shù)配置可以在較短的計算時間獲得較好的尋優(yōu)結(jié)果。若目標(biāo)函數(shù)f(x)=minL（L為耗費時間）也得到相似結(jié)論。

對于JSSP問題，利用表6的參數(shù)配置求解對應(yīng)基準(zhǔn)算例[10]的結(jié)果如表8所示。從表8可看出，采用所配置的參數(shù)，在求解問題規(guī)模逐漸增大時，MACO能獲得的較滿意的解。

表8 JSSP基準(zhǔn)測試問題的求解結(jié)果

圖2 優(yōu)化配置前后的MACO進(jìn)化特征曲線

圖2 給出了優(yōu)化配置后的MACO求解FT06和FT10的進(jìn)化特征曲線。從圖2可以看出優(yōu)化配置之后的MACO再求解JSSP問題時用了100次的迭代的收斂速度但是一般都在30到40次收斂，隨著規(guī)模的增加收斂次數(shù)會逐漸增多。

4 結(jié)論

為了提高M(jìn)ACO求解時的尋優(yōu)性能，本文采用正交試驗的方法進(jìn)行MACO的參數(shù)配置。當(dāng)然，采用正交試驗獲得的參數(shù)優(yōu)選值，具有一定的局限性。這些優(yōu)選值是所設(shè)定的試驗所用水平的某種組合，優(yōu)選結(jié)果不會超越所取水平的范圍。本文通過適當(dāng)選取試驗水平，對不同計算規(guī)模的TSP、JSSP基準(zhǔn)算例的求解，所得到結(jié)果證明了MACO算法及通過正交試驗獲得的參數(shù)配置在求解精度和收斂速度上可以獲得最優(yōu)和準(zhǔn)最優(yōu)解。

[1] Macro D.Thomas stutzle.ant colony optimization[J].Cambridge:MIT Press,2003.

[2] 甘屹,李勝,張志偉.小生境蟻群優(yōu)化及其在JSSP中的應(yīng)用研究[J].中國機(jī)械工程,2010,21(10):1173-1178.

[3] 甘屹,齊從謙,杜繼濤.基于蟻群算法的動態(tài)聯(lián)盟伙伴選擇研究[J].系統(tǒng)仿真學(xué)報,2006,18(2):517-520,525.

[4] Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,41(1):53-66.

[5] 鄭向瑜,彭勇.求解旅行Agent 問題的自適應(yīng)蟻群算法[J].計算機(jī)工程與應(yīng)用,2010,46(16):52-54.

[6] 許瑞,陳華平,邵浩,等.極小化總完工時間批調(diào)度問題的兩種蟻群算法[J].計算機(jī)集成制造系統(tǒng),2010,16(6),1255-1264.

[7] 蔣玲艷,張軍,鐘樹鴻.蟻群算法參數(shù)分析[J].計算機(jī)工程與應(yīng)用,2007,43(20),31-36.

[8] 張曉玲,楊健,杜英國.基于正交實驗的蟻群算法在車間調(diào)度問題中的應(yīng)用[J].計算機(jī)系統(tǒng)應(yīng)用,2010,19(4),152-156.

[9] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.[10]http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html.