胡振宇 吳曉玲

摘要：蟻群算法是意大利學(xué)者Dorigo于1991年提出的一種模擬進(jìn)化算法，通過模擬螞蟻在協(xié)作搜索食物時的搜索行為來尋求最優(yōu)解。蟻群算法提出后卻在組合優(yōu)化中獲得廣泛的應(yīng)用,如調(diào)度、二次分配和網(wǎng)絡(luò)路由等。同時大量的實驗結(jié)果表明蟻群優(yōu)化結(jié)果優(yōu)于遺傳算法、進(jìn)化算法和模擬退火算法，因此如何將蟻群算法應(yīng)用到連續(xù)問題優(yōu)化并獲得其在離散優(yōu)化問題上同樣優(yōu)異的性能，成為目前的一個研究熱點，也是該文的主要研究內(nèi)容。

關(guān)鍵詞：蟻群算法;連續(xù)優(yōu)化;指導(dǎo)變異

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)18-4407-03

Guided-mutation Ant Colony Algorithm

HU Zhen-yu1,2, WU Xiao-ling3

(1.Zengcheng Radio and Television University, Guangzhou 511300, China; 2.Zengcheng Oriental Occupation Technical School, Guang? zhou 511300, China;3.Zhixin High School, Guangzhou 510080, China)

Abstract: Ant algorithm(AS) is a simulated evolutionary algorithm,proposed by a Italian scholar Dorigo in 1991, and find the optimal solu? tion by simulating the searching mechanism of ant while collaboratively finding food. Since AS was proposed, it has gradually been applied to combinatorial optimization problems,such as scheduling、QAP、and network routing.Because a large of experimental results shows that the results obtained by AS are better than that of genetic algorithm、evolutionary algorithm and simulated annealing algorithm,so how to ap? ply AS to continuous optimization problems and get the performance as that in discrete optimization problems become a research focus, and it is the main research work of this paper.

Key words: ant algorithm optimization; continuous optimization; guided-mutation

智能優(yōu)化算法作為一種新興的演化計算技術(shù)己成為越來越多研究者的關(guān)注焦點。蟻群算法是一種新興的智能優(yōu)化算法,主要特點就是:通過正反饋、分布式協(xié)作來尋找最優(yōu)路徑。蟻群算法自提出以后在組合優(yōu)化方面取得了較好的效果,產(chǎn)生了大量的改進(jìn)算法,如ACS、MMAS、GAAA、CACS帶雜交因子的蟻群算法和自適應(yīng)蟻群算法等[1-4]。該文主要討論將蟻群算法應(yīng)用到連續(xù)優(yōu)化問題.

該文詳細(xì)介紹了蟻群算法在連續(xù)空間優(yōu)化上的一些關(guān)鍵問題如連續(xù)空間的離散化,以及在離散化了的連續(xù)空間上的狀態(tài)轉(zhuǎn)移方式。同時也詳細(xì)闡述了該文提出的新型高精度蟻群算法的幾個關(guān)鍵方面,并用實驗對該文提出的算法進(jìn)行測試,結(jié)果表明與遺傳算法、連續(xù)蟻群優(yōu)化算法、模擬退火算法相比，該文提出的算法計算復(fù)雜性大大減少。

構(gòu)造了visible矩陣中,就可以用來指導(dǎo)螞蟻變異,若螞蟻在構(gòu)建候選解的過程中已經(jīng)選擇了某一節(jié)點,且該節(jié)點要進(jìn)行變異,只須比較visible矩陣中選擇的節(jié)點所在列中與選擇的節(jié)點直接相鄰的兩個節(jié)點上的值的大小,選擇值較小的節(jié)點為變異后的值。1.6局部搜索--步長加速法

在蟻群算法中,為獲得期望的精度而使迭代次數(shù)大大增加,為了減少運(yùn)算量,該文利用蟻群算法在較少的迭代次數(shù)少收斂到優(yōu)化問題最優(yōu)解的較小的鄰域內(nèi)某點,再從蟻群算法的搜索到的最優(yōu)點用步長加速法來搜索最優(yōu)解,這樣可以大大減少運(yùn)算量。其算法流程見文獻(xiàn)[5]。

本節(jié)介紹新蟻群算法的主要流程,主要過程如下:

1）蟻群算法初始化,包括螞蟻數(shù)目ant_num、迭代次數(shù)iteration、信息素?fù)]發(fā)系數(shù)volaolittion (2-14)tile、信息素相對重要程度系數(shù)Alpha、偽隨機(jī)比例因子Q0等。