蚁群算法求解连续空间优化问题的一种方法.pdfVIP

维普资讯 1000．9825／2002／13(12)2317．07 ~2002JournalofSoftware 软 件 学 报 Vo1．13，No．12 蚁群算法求解连续空间优化 问题的一种方法 陈 蛟1,2，沈 洁，秦 玲 (扬州大学 计算机科学与工程系，江苏 扬州 225009)； (南京大学 计算机软件新技术国家重点实验室，江苏 南京 210093) E-mail：yzlchen@pub．yz．jsinfo．net http：／／www．yzu．edu．ca 摘要：针对蚁群算法不太适合求解连续性优化 问题的缺陷，提出用蚁群算法求解连续空间优化 问题的一种方 法．该方法将解空间划分成若干子域，在蚁群算法的每一次迭代 中，首先根据信息量求出解所在的子域，然后在该 子域 内已有的解 中确定解的具体值．以非线性规划 问题为例所进行的计算结果表 明，该方法 比使用模拟退火算 法、遗传算法具有更好 的收敛速度． 关 键 词：蚁群算法；优化；遗传操作；非线性规划问题 中图法分类号：TP18 文献标识码：A 人们从仿生学的机理中受到启发，提 出许 多用于解决复杂优化问题 的新方法，统称为元启发 (metahueristic) 算法，如遗传算法 、进化策略、模拟退火 、蚁群算法、禁忌有哪些信誉好的足球投注网站(tabusearch)算法等，并成功地应用于实际问题． 蚁群算法 (antcolonyalgorithm，简称 ACA)是最近几年才提 出来 的一种新型的模拟进化算法．它是 由意大利学者 Dorigo。Mahiezzo，Colomi等人受到人们对 自然界中真实 的蚁群集体行为的研究成果的启发而首先提 出来的…． 他们充分利用蚁群有哪些信誉好的足球投注网站食物 的过程与旅行商 问题 (TSP)之间的相似性，通过人工模拟蚂蚁搜 索食物 的过程 中个 体之 间的信息交流与相互协作，最终找到从蚁群 到食物源的最短路径的原理从而解决 了 TSP 问题 [2】，取得了很 好 的结果．随后，蚁群算法被用来求解 job．shop调度 问题 [3】、指派 问题 4【_5】、序列求序 (sequentialordering)[61等 NP 完全 问题，显示 出蚁群算法在求解复杂优化 问题 (特别是离散优化 问题)方面的优越性，证明它是一种具有广阔 发展前景的好方法． 生物学的研究表 明，虽然单个蚂蚁的能力非常有 限，但多个蚂蚁构成的群体具有找到蚁穴与食物之 间最短 路径 的能力．这种 能力是靠其在所经过的路径上 留下 的一种挥发性分泌物 (pheromone)来实现 的．蚂蚁在路径上 前进 时会根据前边走过 的蚂蚁所 留下 的分泌物选择其要走 的路径．其选择一条路径 的概率与该路经上分泌物 的强度成正 比．因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走 过的蚂蚁越 多，后面的蚂蚁选择该路径 的可能性就越大．蚂蚁 的个体之间通过这种信息的交流寻求通 向食物 的 最短路径．这种优化过程 的本质在于：(1)选择机制．分泌物越 多的路径，被选择的概率越大．(2)更新机制，路径上 面的分泌物会 随蚂蚁 的经过而增长，而且同时也 随时间的推移逐渐挥发消失．(3)协调机制．蚂蚁之间实际上是 通过分泌物来互相通信、协同工作的．蚁群算法正是充分利用了这样 的优化机制，即通过个体之 间的信息交流 与相互协作最终找到最优解，使它具有很强的发现较优解的能力． 但是，蚁群算法也有一些缺 陷，如 需要较长的搜 索时间．这是因为蚁群中多个个体 的运动是随机的。虽然通 } 收稿 日期 ：2001．09．25；修改 日期 ：2002．04．10 基金项 目：国家 自然科学基金资助项 目；~／家高性能计算基金资助项 目(00219)；~苏省教育厅 自然科学基金项 目 (99KJB520003)：南京大学计算机软件新技术 国家重 点实验室开放基金资助项 目 作者简介：陈峻(1951-)，男 ，江苏宝应人，教授，主要研究领域为并行算法，并行体系结构 ：沈洁 (1954一)，男，江苏姜堰人 ，副教授 ，主 要研究领域为系统优化，软件工程 ：秦玲(1979-)，女，江苏泰兴人，硕士生，主要研究领域为算法设计，并行计算． 维普资讯 2318