（计算机应用技术专业论文）用于连续域寻优的蚂蚁算法研究.pdf

摘要 摘要 用蚁群算法进行多模函数优化时，容易陷入局部最优，从而影响了寻优精度 和收敛速度。当函数维数较高时，蚁群算法运行速度会明显下降。为了解决这些 问题，本文提出了两种改进算法。 提出的第一种算法是用于求解连续空间优化问题的分组蚁群算法。该算法将 连续空间优化问题的定义域划分成若干个子区域，并给每个子区域分配一组蚂 蚁。每组蚂蚁在各自的区域里进行搜索，当一组蚂蚁陷入局部最优时，其他组可 以j 下常工作，组之间相互不受影响。且在搜索过程采用“精英策略”并利用精英 蚂蚁更新普通蚂蚁的位置信息，以加快算法的收敛速度。同时，当普通蚂蚁离精 英蚂蚁之间的距离较长时，使用大步长搜索，以加快搜索速度，反之，采用小步 长搜索，可提高搜索过程的精细程度。该方法使每组蚂蚁的搜索空间成倍地缩小 并能有效地改善陷入局部最优的情况，从而能使收敛速度和精度大幅提高。 提出的第二种算法是遗传算法与网格蚂蚁算法相结合的混合算法。在进行函 数优化时，遗传算法具有很大的灵活性且全局搜索能力强，但其存在早熟收敛和 后期收敛速度慢及局部搜索能力弱的问题；网格蚂蚁算法具有局部搜索能力强、 优化精度高等特点，但其全局收敛速度较慢。因此提出了用于连续优化的遗传网 格蚂蚁融合算法。该算法将遗传算法和网格蚂蚁算法相结合，用遗传算法进行大 范围全局搜索，用网格蚂蚁算法进行局部迭代寻优，经过若干次循环迭代产生最 终结果。为了使得初始遗传算法中的基因具有更好的多样性，本文采用了具有很 好遍历性的混沌算法对基因进行初始化，以改善算法全局收敛的可靠性。 对上述两类算法进行了大量的计算机仿真实验，并且与其它同类算法进行了 实验比较与分析。仿真实验结果表明，这两个算法在解决复杂函数优化问题时全 局收敛性能好、速度快，尤其在解决高维多峰函数优化问题时效果更显著。 关键词：蚁群算法，连续空间优化，分组蚁群算法，网格蚂蚁算法 a b s t r a c t a b s t r a c t a n tc o l o n ya l g o r i t h mi s e a s i l yf a l l i n gi n t o l o c a l o p t i m u mw h e nh a n d l i n g m u l t i e x t r e m ef u n c t i o no p t i m i z a t i o n ，t h e r e b yi ta f f e c t st h ea c c u r a c ya n dc o n v e r g e n c e s p e e do fo p t i m i z a t i o n w h e nt h ed i m e n s i o ni sh i g h ，t h ea l g o r i t h mw i l ls l o w d o w nf a s t i no r d e rt os o l v et h ep r o b l e m ，t h i sa r t i c l ep r e s e n t st w oa l g o r i t h m st oi m p r o v et h e s i t u a t i o n t h ef i r s ta l g o r i t h mi sg r o u p e da n tc o l o n ya l g o r i t h mf o rs o l v i n gt h ec o n t i n u o u s s p a c eo p t i m i z a t i o np r o b l e m s t h ec o n t i n u o u ss p a c eo p t i m i z a t i o np r o b l e md o m a i ni s d i v i d e di n t os e v e r a ls u b r e g i o n s ，a n dd i s t r i b u t e sag r o u po fa n t st oe a c hs u b - r e g i o n a l e a c ha n ts e a r c h e si nt h e i rr e s p e c t i v er e g i o n i nt h em e t h o dw h e no n eg r o u po fa n t s s i n ki n t ol o c a lo p t i m u m o t h e rg r o u p so fa n tc a nw o r kn o r m a l l y , o n eg r o u pd o e s n t i n f l u e n c et h eo t h e r a n di nt h es e a r c hp r o c e s si tu s e s ”e l i t es t r a t e g y ”a n du p d a t e st h e l o c a t i o ni n f o r m a t i o no fg e n e r a la n tb yt h eu s eo fe l i t ea n t si no r d e rt os p e e du pt h e a l g o r i t h mc o n v e r g e n c es p e e d a tt h es a m et i m e ，w h e nt h eo r d i n a r ya n t si sa w a yf r o m t h ee l i t ea n t s ，i tu s e sl o n gs t r i d es e a r c h ，i no r d e rt os p e e du pt h es e a r c hs p e e d ，o nt h e o t h e rh a n du s i n gs h o r ts t r i d es e a r c h ，w h i c hc a ni n c r e a s et h ef i n el e v e l t h i sa p p r o a c h a l l o w se a c hg r o u po fa n t st on a r r o wt h es e a r c hs p a c ee x p o n e n t i a l l y , a n dc a n e f f e c t i v e l yi m p r o v et h e s i t u a t i o n f a l l i n g i n t oal o c a l o p t i m u m ，a l l o w i n gt h e c o n v e r g e n c es p e e da n da c c u r a c yg r e a t l yi m p r o v e d t h ec o m p u t e rs i m u l a t i o nr e s u l t s c o n f i r mt h i sc o n c l u s i o n t h es e c o n da l g o r i t h mi sg e n e t i ca n d 鲥db a s e da n tc o l o n ya l g o r i t h mf o rs o l v i n g c o n t i n u o u so p t i m i z a t i o np r o b l e m s w h e nc a r r y i n go u tf u n c t i o no p t i m i z a t i o n ，g e n e t i c a l g o r i t h mh a st h ec h a r a c t e r i s t i c so ff l e x i b i l i t y , s oi ti sg o o da tg l o b a ls e a r c h ，b u ti th a s s h o r t e s to fp r e m a t u r ec o n v e r g e n c ea n dp o s ts l o wc o n v e r g e n c ea n dw e a kc a p a c i t yo f l o c a ls e a r c h ；g r i da n ta l g o r i t h mh a sag o o da b i l i t yi nl o c a ls e a r c h ，a n do p t i m i z e sw i t h h i g h - p r e c i s i o nf e a t u r e ，b u ti t sg l o b a lc o n v e r g e n c ei s s l o w t h e r e f o r et h ep a p e r p r o p o s e st h eg e n e t i ca n dg r i db a s e da n ta l g o r i t h mf o rc o n t i n u o u so p t i m i z a t i o n t h e a l g o r i t h mc o m b i n eg e n e t i ca l g o r i t h ma n d a n ta l g o r i t h mf o rm e s hg l o b a ls e a r c h ，w h e r e g e n e t i ca l g o r i t h mi sf o rg l o b a ls e a r c ha n d 鲥db a s e da n ta l g o r i t h mi su s e df o rl o c a l i t e r a t i v eo p t i m i z a t i o n t h ef i n a lr e s u l tw i l lb eg e ta f t e ran u m b e ro fl o o pi t e r a t i o n s i n o r d e rt ol e tt h eg e n eo fi n i t i a lg e n e t i ca l g o r i t h mk e e pd i v e r s i t y , t h ea l g o r i t h mu s e c h a o sa l g o r i t h m ，w h i c hh a sg o o de r g o d i cp r o p e r t y , d oi n i t i a l i z a t i o no fg e n e ，t o i l t m p r o v er e l i a b i l i t yo fg l o b a lc o n v e r g e n c e 1h ep a p e rd o e sm a n ys i m u l a t i o n s ，a n dc o m p a r e sw i t ho t h e rs i m i l a ra l g o r i t h m s t h es i m u l a t i o n sr e s u l t ss h o wt h a tt h e a l g o r i t h mh a sag o o dg l o b a lc o n 矾鄱善e n c e p e n o m l a n c ei ns o l v i n gac o m p l e xf u n c t i o no p t i m i z a t i o n ，e s p e c i a l l yi n s o l v i n gt h e h i g hd i m e n s i o nm u l t ip e a kf u n c t i o no p t i m i z a t i o np r o b l e m s k e y w o r d s ：a n tc o l o n ya l g o r i t h m ，c o n t i n u o u so p t i m i z a t i o np r o b l e m s ，g r o u p e da n t c o l o n ya l g o r i t h m ，g e n e t i ca n dg r i db a s e da n tc o l o n ya l g o r i t h m i i i 第1 章绪论 1 1 选题背景 第1 章绪论 蚁群算法 1 】是由意大利学者d o f i g o ，m a n i e z z o 等人在2 0 世纪9 0 年代初受 自然界中真实蚂蚁群体集体行为的启发而提出的一种基于种群个体协作的仿生 算法，属于智能优化仿生搜索算法。它是继模拟退火算法 2 】、遗传算法【3 】、禁 忌搜索算法【4 】、人工神经网络算法【4 】等启发式搜索算法以后又一种应用于组合 优化问题的启发式搜索算法。众多研究可以证明蚁群算法具有较强的发现最优解 的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可以加速进化过 程，而且本质是一种并行的算法，不同个体之间不断进行信息交流和传递，从而 能够相互协作，有利于发现较好的解。蚁群算法通过模拟人工蚂蚁搜索食物的过 程成功地用来求解t s p 问题【5 】、q a p ( q u a d r a t i ca s s i g n m e n tp r o b l e m ) 6 7 问题、 j o b s h o p 8 调度问题、分配类型【9 】等离散性问题，都取得了较好的实验结果。 然而现实生活中我们碰到的很多实用的问题都是连续性问题，因此将优化性 能良好的蚁群算法用于连续性空间优化问题具有很重要的现实意义，这是一个解 决函数优化问题的很好的途径。由于蚁群算法起源于离散优化问题( 如t s p 问 题) ，且离散问题的求解过程和蚁群从蚁穴到食物源最短路径的搜索过程具有内 在的联系和本质的相似性。因此将蚁群算法应用到连续空间优化问题( 函数优化) 时，不能直接套用蚁群算法模型，只能利用算法的原理和人们对连续优化问题取 得的有关先验知识来构造相应的算法模型。有许多学者进行了这方面的研究，这 些方法成功地实现了将蚁群算法应用到连续优化问题( 函数优化) 的转变，它们在 求解低维函数优化时表现出各自突出的优点。但是它们也存在一定的局限性和缺 陷，这些方法遇到高维或复杂多峰函数时求解性能大大下降。所以仍需更进一步 对蚁群算法进行拓展和改进，提出具有更优性能的算法，以更好地适应复杂的连 续优化问题。 1 2 选题目的及意义 连续对象求解最大最小值的问题是生产、生活中普遍存在的一类问题，它们 大多数都可归结为函数优化问题，以往解决函数优化问题的算法对函数本身要求 很严格，往往函数要求满足一定的条件，如可导或可微等，但是如今随着军事、 工业的发展，很多行业都需要解决很复杂的函数优化问题，这些函数没有定的 规律性，主要表现为多变量、多约束、非线性、非凸、不可微、多极值等特性， 第i 章绪论 这些问题就是通常所说的n p 问题，不能用一般的函数优化方法达到求解目的。 到目前为止上述问题没有一个很好很快速的求解方法，因此解决诸如上述连续域 寻优的难题具有非常实际的意义。由于蚂蚁算法本质上是一个复杂的智能系统， 可以用于n p 问题的解决，而且它本身具有一定的随机性，启发性，很强的分 工协作能力，具有较强的鲁棒性，优良的分布式计算机制，易于与其它算法结合 等优点，因此把它用于上述问题的求解具有很广泛的现实意义，但是蚂蚁算法的 特征使其适合解决离散域优化问题，对连续域优化不能直接适用蚂蚁算法的框 架，需要提出适合高效的蚂蚁算法，如何更高效的使用蚂蚁算法来解决这些问题 值得我们去深入探索，近年来已经成为众多学者研究的热点问题。 仿生算法是人工智能研究领域中的一个重要的分支，其中包括模拟生物界中 的自然选择和遗传机制的遗传算法，模拟蚂蚁觅食行为的蚂蚁算法以及模拟鸟类 群体捕食行为的微粒群算法，这些算法都各有优点。随着仿生学的发展，仿生算 法也越来越受到学者们的关注，蚂蚁算法作为仿生算法的一种，受到了很多学者 的青睐。1 9 9 1 年意大利学者m d o r i g o 等人首次根据蚂蚁的觅食行为提出了蚁群 优化( a n tc o l o n yo p t i m i z a t i o n ) 算法并成功地应用于很多离散域的组合优化问题， 例如求解t s p ，q a p ( q u a d r a t i ca s s i g n m e n tp r o b l e m ) 等。而且蚂蚁算法还易于和 其他的仿生算法相结合，利用各种算法的优点来很好的解决问题。例如遗传算法 有很强的全局搜索能力，而蚂蚁算法具有很强的局部搜索能力，我们可以把这两 种算法结合，使算法的搜索效率更高。以上对蚂蚁算法已有的应用展示了蚂蚁算 法的优良性能和巨大的发展潜力。 a c o 的离散性本质非常适合于求解组合优化问题，却不能直接用于连续域 优化问题的求解。利用蚂蚁算法进行连续域的寻优的研究还相对较少，而且还不 够深入，有待进一步完善，要求我们探索出更高效更准确的蚂蚁算法用于解决连 续域寻优问题。尽管蚂蚁算法的严格理论基础尚未奠定，国内外的相关研究还处 于实验探索阶段和初步的应用阶段，但是由于蚂蚁算法具有很多优点，人们对蚂 蚁算法的研究已经由解决一维静态优化问题拓展到解决多维动态组合优化问题， 由离散范围内的研究逐渐拓展到连续范围内的研究。本文提出了两种解决函数优 化问题的新的蚂蚁算法，该方法是在前人研究的基础上提出的性能更高、针对性 更强的解决优化问题的方法。因此，本课题中新蚂蚁算法及其融合算法的提出及 将其应用于函数优化问题，具有很好的理论与现实意义。同时，也为函数优化的 进一步发展提供一种新的仿生算法，促进相关学科的技术进步和发展。 1 3 国内外研究现状分析 从上面章节可以看出由于蚁群算法具有很好的通用性、鲁棒性，同时具有很 2 第1 章绪论 好的分布式协作能力，对蚁群算法的研究已经从单一的t s p 问题扩展到离散域 很多实用的问题的研究，目前已经从离散域问题扩展到连续域问题的寻优。下面 仅对本文研究课题相关的用于连续域函数优化的蚁群算法的国内外研究现状进 行详细的分析。 1 3 1 直接模拟蚂蚁的生物习性 有不少学者从真实的蚂蚁出发，模拟自然界中蚂蚁的生活习性，构建适合求 解连续域优化问题的连续域a c o 模型，提出了用于求解连续空间优化问题的蚁 群算法。 b i l c h e v 和p a r m e e 在19 9 5 年提出了c a c o 10 ( c o n t i n u o u sa n tc o l o n y o p t i m i z a t i o n ) 算法，该算法采用遗传算法对解空间进行全局搜索，再由蚁群算法 对解进行局部优化，其中蚁群搜索是把蚂蚁所在区域视为t s p 问题中的城市， 从而寻找下一个区域。该算法实现了蚁群算法解决连续域寻优问题的突破。随后 在文献 1 1 】中，m o n m a r c h e 等人提出了一种a p i 11 ( a f t e rp a c h y c o n d y l aa p i c a l i s ) 算法，这种算法通过模仿一种墨西哥的蚂蚁的觅食行为，只利用可见标志而不用 信息素实现优化算法。后来，d r e o 和s i a r r y 提出了c i a c 1 2 1 3 ( c o n t i n u o u s i n t e r a c t i n ga n tc o l o n y ) 算法，该算法主要提出了利用两个通道进行融合的技术， 一个通道通过信息素来交流，另一个通道蚂蚁之间可以直接交流。另外，m m a t h u r 等人对c a c o 进行了改进，提出了改进的( m o i d f i e dc a c o ，m c a c o ) 1 4 算法。 2 0 0 6 年，s o c h a 和d o r i g o 提出了a c o r ( a c of o rc o n t i n u o u sd o m a i n ) 15 17 】 算法，该方法可以用于连续域或者离散域的优化，在连续域中该算法用高斯分布 函数来求解。 2 0 0 8 年马卫等提出了求解函数优化问题的快速连续蚁群算法n f c a c o ( n e w f a s tc o n t i n u o u sa n tc o l o n yo p t i m i z a t i o na l g o r i t h m ) 1 8 ，该算法模拟蚂蚁的生活习 性，把蚂蚁分成勘察蚁和觅食蚁，通过勘察蚁进行大视域的全局搜索，觅食蚁在 本代最优解周围空间进行小步长搜索，并且勘察蚁每迭代完一代都及时对解进行 评价，以便觅食蚁更高效的搜索，同时配以混沌序列方法确定蚂蚁的初始位置， 增加了算法全局可靠性。该算法寻优效率高，收敛速度快。 以上这些方法在连续域寻优中取得了一定的成果，但是，如何提高全局收敛 速度和寻优效率仍然是一个有待解决的问题。例如a p i 算法没有利用信息素来 指导蚂蚁搜索，c i a c 算法更多的是强调两种通道的融合，没有产生很好的效果。 c a c o 算法只是去利用t s p 问题的框架，性能受到了很大的限制。 1 3 2 连续域离散化 蚁群算法起始于离散域问题的解决，有许多学者提出了先将连续空间离散 第l 章绪论 化，再用蚁群算法求解的方案。 李艳军等提出了a a c a 1 9 2 1 】( a d a p t i v e a n tc o l o n y a l g o r i t h m ) 算法，该算法 采用新的基于目标函数值的启发式的信息分配策略，并借鉴了g a ( 遗传算法) 求 解连续域问题的编码方法和精英策略以及混合算法中的区域搜索思想。 汪镭、吴启迪 2 2 2 7 等人提出了将a s ( a n ts y s t e m ) 算法拓展为连续的求解函 数优化问题的c a s 算法。将离散域蚁群算法中的“信息量留存”过程拓展为连 续域中的“信息量分布函数”，定义了应用于连续函数寻优问题的改进蚁群算法。 b a s ( b i n a r ya n ts y s t e m ) 2 8 算法利用对h c f ( h y p e r - c u b ef r a m e w o r k ) 的改进 作用于a c o 算法用来处理无约束的函数优化问题。 h i r o y a s u 等人提出了t a c o 2 9 ( t o u r i n ga n tc o l o n yo p t i m i z a t i o n ) 算法，该算 法是一种与普通的蚁群优化比较接近的求解连续空间优化问题的蚁群算法。利用 二进制位的0 、l 来模拟蚂蚁是否选择该路径。t a c o 算法是与普通的a c o 最接 近的一种求解连续空间的优化算法，由于该算法采取的是单纯的基于方向选择策 略的信息素，同时，仅有2 个可供选择的路径( 0 一o ，0 _ 1 ) 。所以，其不可避 免的带来一些缺点，一旦蚂蚁发现一个好的解，所有蚂蚁都会快速的走其所选路 径，导致发现更短路径的能力下降。所以不难看出，t a c o 面临早熟的问题。 m t a c o 3 0 ( m o d i f i e dt o u r i n ga n tc o l o n yo p t i m i z a t i o n ) 算法是k a r a b o g a 等人 对t a c o 的改进，其引进了有记忆特性的禁忌搜索( t s ) 算法，修改了转移概率， 将二进制拓展为十进制，增加了搜索的多样性，但还只是t a c o 的框架的改进。 陈烨 3 1 】于2 0 0 7 年提出了变尺度混沌蚁群优化算法，蚁群算法在每次迭代 结束时，使用混沌搜索算子在当前全局最优解附近搜索更好的解，这样混沌算子 在蚁群搜索初期防止其陷入局部最优，后期起到了提高搜索精度的作用，对上面 的t a c o 算法是一种改进。 段海滨等提出了一种基于网格划分策略的自适应连续域蚁群算法 3 2 3 3 ，在 变量区域里打网格，在网格点上求目标函数的值，每迭代一次在求出的点附近将 点打密，重复上述过程，直到网格点的距离小于给定的精度。高尚 3 4 】等提出了 一种基于网格划分策略的连续域蚁群算法，该算法与网格划分法的不同之处在于 前者利用了每一点的信息，而后者只利用了最小值的信息。后来段海滨【3 5 】等人 又对其进行了改进，在构造网格同时，构造一个与蚁群转移概率相关的评价函数， 同时借助相遇搜索策略对蚁群算法改进，并加入对残留信息素最值的限制，提高 了算法的收敛速度和精度。于干【3 6 】等在2 0 0 7 年提出了一种基于网格的函数优 化方法，在该算法中把网格算法用于遗传算法操作以后，这是一种基于节点的网 格生成策略。尤其对于高维问题，有一个快速随机生成算法，解决了种群规模的 爆炸问题。 4 第1 章绪论 陈烨 3 7 黜- - 种用于连续函数优化的蚁群算法。该算法将函数优化问题中 生成解的过程转化为蚁群每前进一步就选择一个十进制数字并以此来生成一个 十进制串的过程，并且在选择数字过程中将信息记录在选择的路径上，通过信息 素来改变下一次蚁群选择各个数字的概率。 2 0 0 8 年刘利强，于飞等人提出了一种用于求解约束优化问题的连续域蚁群 算法 3 8 。其将搜索区域的任意一点当成食物源，使用多组蚂蚁寻优，每组蚂蚁 代表一个解，每迭代一次选择一组种子蚁群，在该蚁群的信息素密度分布函数下 进行采样，生成子代蚁群，从而得到问题的最优解。该方法具有较快的搜索能力， 但是收敛精度有待提高。 杨勇【3 9 等人提出了一种用于求解连续域优化问题的嵌入确定性搜索蚁群 算法，在全局搜索过程中，该算法利用信息素强度和启发式函数确定蚂蚁移动方 向，在局部搜索过程中嵌入了确定性搜索，加快了收敛速度，改善了算法性能。 李向丽 4 0 等人在上述算法基础上提出了基于退火的蚁群算法，对上述算法进行 了改进，在局部搜索过程中加入了模拟退火的思想，提高了算法跳出局部最优解 的可能，从而提高了算法的可靠性。 周晓静 4 1 1 等人于2 0 0 9 年4 月提出了基于全局单位化的连续域优化的改进 蚁群算法，通过将单位整个搜索空间映射到单位空间，然后在在各变量的每个位 数上进行随机选择，从而实现连续空间的离散化，以此来模拟蚂蚁的觅食过程， 在该算法中还对状态转移规则和信息素更新规则做了相应的改进。 原思聪 4 2 】等人在2 0 0 8 年提出了基于多维有约束问题通过惩罚因子方式转 换为统一的多变量目标函数形式的方法，通过将独立变量分成若干等份区域，进 而利用蚂蚁算法进行全局搜索，遗传算法进行局部搜索，在搜索过程中蚂蚁每到 一个区域将访问的所有变量作为一个可行解，这样将多维变量的函数优化问题转 换成类似组合优化的问题来进行求解。 以上这些方法通过各种途径来将连续空间离散化，但是由于受原蚁群算法框 架的影响，有时候并不能产生理想的效果，另外若是将连续域离散化遇到高维问 题时会很麻烦，处理数据量会很大，算法实现较难，占用过多的存储空问，算法 速度和精度都会受到一定的限制；并且不容易与其他算法结合。 1 3 3 根据概率选择进行采样 高斯分布，也称正态分布，高斯分布的函数图象是一条位于x 轴上方呈钟形 的曲线，称为高斯分布曲线，简称高斯曲线。对于随机变量墨其概率密度函数 分布为高斯分布或正态分布，记为( ，a 2 ) ，其中i t , g 2 为分布的参数，分别为高 斯分布的期望和方差。当这两个参数有确定值时，p 俐也就确定了。通过蚁群算 法和高斯分布函数相结合来指导蚂蚁寻优是一个好的思路，一些学者进行了这方 第1 章绪论 面的研究。 2 0 0 6 年，s o c h a 和d o r i g o 提出了a c o r ( a c of o rc o n t i n u o u sd o m a i n ) 算法， 该方法将启发式的组合优化算法a c o 拓展到a c o * ( a c o r ) ，拓展了其应用限制， 可以用于连续域或者离散域的优化，在优化过程中该算法采用高斯分布函数来进 行信息素的选择，并取得了一定成果。 p o u r t a k d o u s t 等提出了一种仅依赖信息素的连续域蚁群算法 c a c s ( c o n t i n u o u sa n tc o l o n ys y s t e m ) 4 3 ，算法侧重从信息素的角度来研究问 题，采取自适应的信息素更新策略，扩展已有的a c s 算法到c a c s 算法来解决 连续域优化问题。它的优点是结构简单，控制参数少，并且引入了赌轮盘算法增 强了算法全局收敛的可靠性，但其仅仅对a c s 算法扩展和改进，所以更多的受 a c s 算法的限制和制约。 t s u t s u i 4 4 于2 0 0 4 年提出a p s ( a g g r e g a t i o np h e r o m o n es y s t e m ) 算法，该算法 将a c o 算法由离散域扩展到连续域，利用群体行为的聚合信息素解决连续域的 优化问题。 k o n g 等提出了d a c o 4 5 4 6 ( d i r e c ta p p l i c a t i o no f a c o ) 算法，其可用于连续 域和离散域的寻优，该算法是受a c o * 的启发发展的，利用了正态分布函数，并 且其中信息素直接关联于变量j 下态分布的平均值和偏差值。d a c o 提出一个直接 应用a c o 于连续域的函数优化问题的模型：由人工蚂蚁构建解，根据正态分布 模拟信息素在连续空间的密度分布，按此分布函数进行随机抽样，构成蚁群的状 态转移规则，并随着蚂蚁的移动调整分布函数，实施信息素的更新。 程志刚 4 7 】于2 0 0 6 年提出了l 种混合连续蚁群系统( h y b r i dc o n t i n u o u sa n t c o l o n ys y s t e m ，h c a c s ) ，该系统是基于连续分布的信息素，扩展a c s ，从而构 建一种新的蚁群算法，用于求解连续问题，同时又结合优进策略和变异策略。 1 3 4 杂交混合 一般来说每个算法有每个算法的特点，适用于不同的场合，仿生算法也不例 外。这就给我们提供了把若干个算法结合起来发挥更大优势的机会，1 + 1 2 。很 多人都进行了这方面的研究，把蚂蚁算法和其他算法相结合，提出了很多融合算 法。 p s a c o 【4 8 ( p a r t i c l es w a r ma n da n tc o l o n yo p t i m i z a t i o na l g o r i t h m ) 算法是对 p s o ( p a r t i c l es w a r mo p t i m i z a t i o n ) 算法的改进，将粒子群算法和蚁群算法相结合， 把基于高斯分布的蚂蚁算法嵌入到粒子群算法的局部搜索环节，利用蚂蚁信息素 的更新来指引微粒群寻优。宋雪梅 4 9 】等人进行了改进，引入了针对蚂蚁信息量 的变异，避免算法早熟收敛。 高玮 5 0 1 提出了一种免疫连续蚁群算法，把进化算法和免疫算法的原理同蚁 6 第1 章绪论 群算法相融合，蚂蚁进行基于浓度的选择和自适应变异，增强了算法的搜索能力， 适用于复杂连续优化问题。 伍爱华【5 l 】等人提出了多目标蚁群遗传算法，定义了利用信息量指导遗传的 搜索策略和信息更新方法，通过优秀决策引入，决策集更新，改变算法中止条件 等方法，加速了算法收敛速度，同时还提出了多目标遗传算法的终止条件。 w e n 【5 2 等提出了一种结合遗传优化的动态窗口蚁群算法，该算法具有优良 的求解性能，尤其适用于多变量强非线性的大规模复杂多阶段决策问题。 陈岐 5 3 5 6 等提出了一种基于遗传算法里的交叉变异操作的连续域蚁群优 化算法，该算法将所求解问题解的每一分量的可能值组成一个动态的候选组，并 记录候选组中每个可能值的信息量，进而对候选组实施交叉变异操作。 杨勇 5 7 等人提出了一种用于求解连续域优化问题的嵌入确定性搜索蚁群 算法，在全局搜索过程中，该算法利用信息素强度和启发式函数确定蚂蚁移动方 向，在局部搜索过程中嵌入了确定性搜索，加快了收敛速度，改善了算法性能。 m o s c a t o 5 8 等在1 9 9 2 年提出了文化基因算法( m e m e t i ca l g o r i t r m a ) ，1 9 9 4 年 r a d c l i f f e 5 9 等详细说明了m e m e t i c 算法的优化机制，m e m e t i c 算法实际上将基 于种群的全局搜索和基于个体的局部启发式搜索结合。2 0 0 9 年马卫 6 0 】等提出了 基于文化的连续蚂蚁优化算法，把蚂蚁算法融入文化框架，组成基于蚂蚁算法的 主群体和信念的两大空间，并且使用双重进化机制支持问题的求解和知识的提 取。取得了较好的效果。 黄景文 6 1 】等提出了基于量子计算理论及蚁群算法的寻优策略，采用实数编 码量子，避免了二进制编码所带来的资源大量消耗和精度受编码位数影响等问 题，设计了智能量子蚂蚁，利用量子态纠缠和相干机理，通过遗传算法进行前期 的搜索，然后通过智能量子蚂蚁算法进行局部搜索，提高了算法的搜索能力。 段海滨 6 2 】等人与2 0 0 5 年提出了基于云模型理论的蚁群算法，将蚁群算法 的分布式并行计算特性很好地应用来和云模型相结合。改进的蚁群算法采用半正 态云规则进行控制，以语言值为基础构成关联规则，从而实现定性知识的表达。 改进策略直观，大大减少了计算量。该方法对蚁群算法的全局优化性能起到了改 善作用。有效地克服了基本蚁群算法收敛速度慢、易限于局部最优解的缺陷。 1 3 5 其它策略 当然除了蚁群算法，还有很多其他算法也被用于解决函数优化问题，下面给 出这些算法。 张著洪 6 3 】等人提出了一种新的免疫算法在多模态函数优化中的应用。该算 法借鉴小生境共享实现思想方法建立了有助于增强多样性和保留优良抗体的记 忆细胞获取算子，利用亲和成熟机理设计抗体突变算子，并且从理论上证明了算 第1 章绪论 法的收敛性。尤勇 6 4 等提出了一种新的混沌优化方法，利用了类在有限区域 内折叠次数无限的一维迭代混沌自映射算法，提高了混沌算法的性能。 基于随机均匀搜索的改进蚁群算法 6 5 ( r a c o ) i 主1 ：f 君等人提出，该算法采 用赌轮盘选择代替了通过启发式函数和信息素选择路径，并且对蚂蚁信息素的更 新方式做了改善，使其更适合求解带有约束条件的连续函数优化问题。该算法中 采用的是罚函数法，将多约束优化问题转换成了无约束问题，使得蚂蚁能够在可 行解的范围内寻找到较优的解。 李太勇6 6 等提出了基于差分进化基因表达式编程函数优化方法，对遗传算 法进行了改进，通过提高基因表达式编程和引入差分进化设计了新的基因编码方 法，提高了算法收敛的精度。 谢庆华 6 7 】等通过模拟人类竞选活动中对高支持率的追求动机，提出了启发 式竞选优化算法，并将其用于不等高多峰函数优化问题，能跟踪多个次优解，提 高了算法的性能。 2 0 0 7 年赵宝江【6 8 】等人通过对模拟离散域蚁群算法中的分散度自适应节点 选择和白适应信息素挥发因子的信息素更新，提出了一种自适应的蚁群优化算法 a a c a ( a d a p t i v ea n tc o l o n ya l g o r i t h m ) ，该方法通过对各个变量的子域( 路径) 连接 数量的衡量，通过搜索过程解的分布动态调节蚂蚁的路径选择策略和信息素更新 策略，平衡了加速收敛和早熟停滞之间的矛盾，取得了较好的效果。 刘泓 6 9 1 等人提出基于构造图拆分的并行蚁群算法，通过并行计算技术将解 的构造图分成若干块，每块的计算任务放在不同的机器上执行，相互合作完成整 个任务，该方法避免了应用蚁群算法求解大规模多阶段决策问题时计算量成指数 级增长的缺点。 2 0 0 0 年唐巍【7 0 等人提出了混沌遗传算法结合的思想，该方法根据混沌运动 的随机性、遍历性、对初始条件的敏感性等特性，利用混沌算法进行群体的初始 化和最优个体的混沌变尺度载波寻优。将混沌算法嵌入到遗传算法中，但是本算 法中遗传算法采用的二进制编码，这是一个缺陷。 以上这些研究取得了一定的成果，为蚂蚁算法扩展到求解连续域问题起到了 显著的推动作用。但这些方法普遍存在容易陷入早熟，跳出局部最优解能力不强， 收敛精度不高等缺点，如何提高寻优率，提高收敛精度和速度? 这是一个看似矛 盾的问题，解决不好，容易顾此失彼。 1 4 本文的主要研究内容与创新之处 1 4 1 本文的主要研究内容 本文主要针对蚂蚁算法在解决函数优化问题中容易存在的缺陷，如容易陷入 第1 章绪论 局部最优解，高维问题求解性能大大下降等问题，拟研究分组蚂蚁算法和遗传网 格蚂蚁融合算法。 ( 1 ) 分析已有算法容易陷入局部最优的一个重要原因是：当寻优过程到达一 个局部的谷底或峰顶时，如果算法缺少足够强的跳出局部最优解的机制，算法就 会陷入局部最优。如果采用分区分组优化，当某一组陷入局部最优时，另外的组 可j 下常工作，而且，分区分组搜索大大缩小了搜索空间，使每组的优化过程不易 陷入局部最优解。基于上述分析，本文研究用分组蚂蚁算法来解决函数优化问题。 由于蚂蚁算法是一种本质并行的算法，蚂蚁除了依靠自身的适应能力，主要通过 蚂蚁之间的分工协作来完成搜索任务，蚂蚁个数，蚂蚁搜索范围，信息素残留因 子，信息素强度等对算法性能起到了很大的作用，因此本文将通过大量的仿真实 验，研究如何使算法的性能达到最优，及如何最有利于蚂蚁快速找到问题解。本 文实施将蚂蚁分组和不分组进行对比分析，对蚂蚁分组和不分组情况下将采用一 致的参数，包括蚂蚁个数选取，信息素更新规则，蚂蚁位置信息初始化，算法停 止条件等，来展现分组蚂蚁算法的有效性。除了上面的实验，分组蚂蚁算法还将 与其他相关的算法进行对照分析，力争使得分组蚂蚁算法性能上不差于更要优于 其他的算法。 ( 2 ) 参考相关文献，遗传算法在优化过程中模拟自然界生物的遗传和进化过 程，它是基于个体适应度进行概率选择的，另外交叉算子和变异技术使得算法在 产生新个体时变化性很大，从而使搜索过程具有很大的灵活性，遗传算法的这些 特性使得遗传算法具备了很好的全局收敛可靠性，研究将遗传算法用于大范围的 搜索，使解快速定位到全局最优解所在区域。但是也正是遗传算法的灵活性，使 得该算法在需要进行细致搜索时，无法达到理想的效果，而蚁群算法由于受到蚂 蚁信息素的作用，产生了一种正反馈效应，随着搜索次数的增加，蚂蚁会收敛到 局部区域中的最优点。在网格蚂蚁算法中随着迭代的进行，蚂蚁搜索的精度不断 提高，因此利用网格蚂蚁算法进行局部寻优是明智的选择。本文研究怎样将遗传 算法和蚂蚁算法相结合，研究如何使遗传网格蚂蚁算法发挥遗传算法和蚂蚁算法 各自的优点，以提高算法的性能。考虑到混沌算法具有伪随机性、遍历性和对初 始条件的敏感性等特征，本文拟研究采用常用的混沌模型“虫e 1 模型( 一维 l o g i s t i c ) 对遗传算法中的基因进行初始化。在遗传网格蚂蚁算法实验部分中，将 分别用该算法和其他两个算法进行实验比较，争取比对照实验中的性能有所增 强。另外研究遗传网格蚂蚁算法的初衷是为了解决蚁群算法在解决高维函数优化 问题时，算法收敛的速度大大降低，精度不够高的问题，本算法主要选用高维函 数作为测试函数。 9 第l 章绪论 1 4 2 本文的创新之处 目前，利用蚁群算法解决连续域寻优问题时存在收敛速度慢的问题，尤其遇 到高维函数优化时性能大大下降，另外算法容易陷入局部最优解也是常见的缺 点。针对这些缺点，本文提出了一种分组蚁群算法来解决多模函数优化问题；另 外鉴于蚁群算法具有很好的融合性，扬长避短，发挥遗传算法和蚂蚁算法各自的 优点，本文提出了遗传蚁群融合算法，把该算法用于解决高维函数的优化，使得 这些算法在性能上有所提高，使提出的算法具有一定的应用价值和理论意义。 ( 1 ) 本文提出了分组蚁群优化算法，该算法首先把定义域均匀地划分成若干 个子区域，然后给每个区域分配相同个数的蚂蚁，每个组的蚂蚁只在各自的区域 进行搜索。在搜索过程采用“精英策略即把每代中的最优个体定义为精英蚂蚁 并保留到下一代，利用精英蚂蚁更新其它蚂蚁的位置信息，以加快算法的收敛速 度。同时，将搜索过程分为大步长搜索和小步长搜索两种，当普通蚂蚁离精英蚂 蚁之间的距离较长时，使用大步长搜索，以加快搜索速度；当普通蚂蚁离精英蚂 蚁之间的距离较短时，采用小步长搜索，可提高搜索过程的精细程度，从而搜索 到更优的函数值。这样寻优的速度和精度就得到了保证。此外，蚂蚁的搜索算法 主要由每只蚂蚁留下的信息素，信息素浓度越强，对蚂蚁的吸引力就越强。当蚂 蚁完成一步搜索后，对蚂蚁新位置的信息素进行更新通过不断地重复上述过程， 使算法能找到问题的最优解或较好解。 ( 2 ) 本文提出了一种新的遗传网格蚂蚁融合算法，以避免蚁群算法陷入局部 最优解、收敛速度慢等问题，并使算法能够有效地解决高维函数优化问题。遗传 算法搜索由于具有非确定性和灵活性，使算法具有较好的全局收敛性，因此本文 所提出的遗传蚁群融合算法利用遗传算法对全局进行搜索，并采用了混沌方法对 遗传算法中的基因初始化，混沌初始化具有伪随机性，可以产生足够的个体多样 性来保证遗传算法全局收敛的可靠性；该基因采用了十进制的编码方式。十进制 编码方式具有简单可操作性，因而省去编码和解码的时间，提高算法效率。在整 个种群中随机配对的交叉操作虽然有利于提高全局收敛的可靠性，但降低了搜索 的收敛速度，为了能快速收敛到全局最优解附近，在交叉和变异时采用指定起始 位交叉和指定位变异的方法，迅速找到全局最优解所在区域。当每次遗传算法结 束时，选出具有最佳适应值的个体作为网格蚂蚁算法搜索区域的中心，得到网格 蚂蚁