Computer Engineering a nd Applications 计算机工程与应用2010,46(30)
1 引言
近些年随着近代仿生学的发展,仿生算法也越来越受到
学者们的关注,1991 年意大利学者 M.Dor-igo
[1]
等人首先根据
蚂蚁的觅食行为提出了蚁群优化(Ant Col ony Optimization)
算法并成功地应用于很多离散域的组合优化问题,例如求解
TSP
[2]
,QAP-(Quadratic Assignment Problem)等
[3]
。ACO 的离
散性本质非常适合于求解组合优化问题,却不能直接用于连
续域优化。目前连续蚁群优化算法及相关收敛性的研究成果
都相对较少。
为了探索把 ACO 算法用于函数优化,有不少学者提出了
很多方案,具有代表性的方案有三类,一类是把连续域离散
化,再用蚁群算法来求解。例如基于图的蚁群算法
[4]
、网格优
化算法
[5]
等等。第二类是把基本的蚁群算法进行改进,使其可
以用于连续域优化的问题,例如:Bilchev 和 Parmee 首先提出
了 CA CO
[6]
(Continuous Ant Optimization)算法,该方法采用
遗传算法对解空间进行全局搜索,再由蚁群算法对解进行局
部优化。最后一类是直接模拟蚂蚁行为提出的新算法,例如在
文献[7]中,N.Mo nma-rche 等人提出了一种 API(after Pachy-
con dyla API-calis)算法,这种算法模仿一种墨西哥的蚂蚁的
觅食行为,利用可见标志而不用信息素的优化算法。后来,
Dreo和Siarry提出了CIAC
[8]
(Continuous Interacting Ant Colo-
ny)算法,该算法主要提出了利用两个通道进行融合的技术,
用于连续域寻优的分组蚁群算法
李秋云,朱庆保,马 卫
LI Q iu-yun,ZHU Qing-bao,MA Wei
南京师范大学 数学与计算机科学学院,南京 210097
Col lege of Mathematics and Computer Science,Nanjing Normal University,Na njing 210097,Chi na
E-mail:lqy81@163.com
LI Qiu-yun,ZH U Qing-bao,MA Wei.Grouped ant colony algorithm for solvi ng continuous optimization problems.Com-
puter Engineering and Applications,2010,46(30):46-49.
Abstract:Ant colony alg orithm is easy to fall into local optimum when it solve s multi-optimum function optimi zation p rob-
lem,which impacts the accuracy and convergence sp eed.Therefore this paper prese nts grouped ant colony algorithm for solv-
ing con tinuous optimization problems.The algorithm divides the definitio n domain int o several sub-regions,and gives each
sub -region a set of an ts.Ants of each region search in their domain,and in the search proce ss the algorithm uses the“elite
stra tegy”to update the location information of ordinary ants,the strategy can speed up converge nce speed.At the same time,
when the elite is far fro m the o rdinary ants the a lgorithm uses big move search to accelerate the search speed,on the con-
trary,use s small move search to improve the lev el of the fine.The m ethod narrows the search space multiply and it can ef-
fectively improve the situat ion of a local optimum,th us convergence speed and accuracy can be significantly improved.The
results of computer simu lation confirm this co nclusion.
Key words:ant colony algorithm;continuous optimization;gr oupe d
摘 要:用蚁群算法进行多模函数优化时,容易陷入局部最优,从而影响了寻优精度和收敛速度。因此提出了一种用于求解连续
空间优化问题的分组蚁群算法。该算法将连续空间优化问题的定义域划分成若干个子区域,并给每个子区域分配一组蚂蚁。每
组蚂蚁在各自的区域里进行搜索,且在搜索过程采用“精英策略”并利用精英蚂蚁更新普通蚂蚁的位置信息,以加快算法的收敛
速度。同时,当普通蚂蚁离精英蚂蚁之间的距离较长时,使用大步长搜索,以加快搜索速度,反之,采用小步长搜索,可提高搜索
过程的精细程度。该方法使每组蚂蚁的搜索空间成倍地缩小并能有效地改善陷入局部最优的情况,从而能使收敛速度和精度大
幅提高。计算机的仿真实验结果证实了这一结论。
关键词:蚁群算法;连续域寻优;分组
DOI:10.3778/ j.issn.100 2-8331.2010.30.014 文章编号:1002-8331(2010)30-0046-04 文献标识码:A 中图分类号:TP301.6
基金项目:国家自然科学基金(the National Na tural Science Foundation of China under Grant No.60673102);江苏省自然科学基金(the Natu -
ral Science Foundation of Jiangsu Province of Chin a under Grant No.BK2006218)。
作者简介:李秋云(1984-),女,硕士生,主要研究方向:智能优化与人工智能;朱庆保(1955-),男,教授,博导,硕导,主要研究方向:智能优化与人
工智能;马卫(1983-),男,硕士生,主要研究方向:智能优化与人工智能。
收稿日期:2009-04-07 修回日期:2009-08-14
46