《蚁群优化算法及其应用研究进展》由会员分享，可在线阅读，更多相关《蚁群优化算法及其应用研究进展（4页珍藏版）》请在金锄头文库上搜索。
1、专家论坛计算机测量与控制. 2003. 11 (12) Computer M easurement 蚂蚁系统;组合优化;启发式算法Progresses in Ant Colony Opti m ization Algorithm with ApplicationsL I Shi2yong(Department of Control Science and Engineering, Harbin Institute of Technology, Harbin 150001, China)Abstract: The recent research results of A nt Colony A
2、lgorithm(ACA)and its applications for combinatorial opti m izationare overviewed. A t first ant colonies foraging behavior and their communication system are briefly introduced. Then the basicprinciple and the main characteristics of artificial ant colony algorithm are presented. Thirdly the applica
3、tions of ACA for thecombinatorial opti m ization problem s are described, such as TSP, QA P, JSP, VRP, GCP, SOP and the networks routing prob2lem.Finally the problem s to be solved and the future works are discussed.Key words:ant colony algorithm;ant system;combinatorial opti m ization; meta- heuris
4、tic algorithm1 引言随着科学技术的飞速发展,计算机测量与控制系统 的信息化、数字化及智能化的发展趋势锐不可挡。在自 动化测试与控制系统中,存在着控制策略、规则、结构 以及控制参数的组合优化问题,因此,在计算机自动控制系统中,控制和优化始终是两个重要问题。 实际上,使 用计算机进行控制和优化本质上都表现为对信息的某种 处理。随着研究对象的日益复杂化,其特性表现为非线 性、不确定性等,难以建立精确“数学模型” 。因此,传 统的基于对象精确模型的控制理论与使用确定性的优化算法都遇到了极大的困难。于是人们就从模拟人的智能 控制行为得到启示,将人工智能同自动控制理论相结合, 创立了智能控制
5、理论;人们从生物进化及仿生学中受到 启发,提出许多启发式的智能优化方法。 如禁忌算法、 神 经网络算法、遗传算法、免疫算法及蚁群算法等,它们为解决许多复杂优化问题(N P-困难问题)提供了崭新 的途径。 文章就蚁群优化算法的基本原理及其应用研究进展加以 综述,旨在为进一步推动这一领域的理论与应用研究 。2 蚂蚁的群体行为及信息系统蚂蚁是最古老的社会昆虫之一,它的个体结构和行为 虽简单,但由这些简单个体构成的蚂蚁群体,却表现出高度 结构化的社会组织。蚂蚁王国俨然是一个小小 “社会” 。这 里,有专司产卵的后蚁;有为数众多的从事觅食打猎、兴建 屋穴、 抚育后代的工蚁;有负责守卫门户、 对敌作战的兵
6、蚁; 还有专备后蚁招婿纳赘的雄蚁等等。 蚂蚁是社会性昆虫,组成社会的三要素之一就是社 会成员除有组织、有分工之外,还有相互的通讯和信息 传递。研究表明,蚁群有着奇妙的信息系统。其中包括 视觉信号、声音通讯和更为独特的无声语言,即包括化 学物质不同的组合、触角信号和身体动作在内的多个征 集系统,来策动其它个体。蚂蚁特有的控制自身环境的 能力,是在高级形式的社会性行为及不断进化过程中获 得的1- 2。 觅食行为是蚁群一个重要而有趣的行为。据昆虫学 家的观察和研究,发现蚂蚁有能力在没有任何可见提示 下找出从蚁穴到食物源的最短路径,并且能随环境变化 适应性地搜索新的路径,产生新的选择。虽然单个蚂蚁 的
7、行为极其简单,但由大量的蚂蚁个体组成蚂蚁群体却 表现出极其复杂的行为,能够完成复杂的任务。 生物学家和仿生学家经过大量的细致观察研究发 现,蚂蚁在觅食走过的路径上释放一种蚂蚁特有的分泌 物信息激素(Pheromone)。蚂蚁个体之间正是通过912计算机测量与控制 第11卷这种信息激素进行信息传递,从而能相互协作,完成复 杂任务。在一定范围内蚂蚁能够察觉到这种信息激素并 指导它的行为,当一些路径通过的蚂蚁越多,则留下的 信息激素轨迹(trail)也就越多,招致后来更多的蚂蚁选 择该路径的概率也越高,于是越发增加了该路径的信息素强度。这种选择过程称之为蚂蚁的自催化过程,形成 一种正反馈机制,可理解
8、为增强型学习系统,蚂蚁最终 可以发现最短路径。3 人工蚁群优化算法原理人工蚁群算法是模拟真实蚁群觅食过程寻求最短路径 的原理,由意大利学者M. Dorigo等人首先提出的3, 4。最 初的蚂蚁算法称为蚂蚁系统(A nt System),对于旅行商问 题(TSP)及二次分配问题(QA P)等取得了较好效果,经过改进后称为蚂蚁算法,或称蚁群算法。 蚁群算法吸收了蚂蚁群体行为的典型特征:一是能 察觉小范围区域内状况,并判断出是否有食物或其他同 类的信息素轨迹;二是能释放自己的信息素;三是所遗 留的信息素数量会随时间而逐步减少。蚂蚁算法通过侯选解组织群体的进化过程来寻求最 优解,这一过程包括适应阶段和
9、协作阶段。在适应阶段, 各侯选解根据积累的信息不断调整自身的结构;在协作 阶段各侯选解间通过信息交流,以便产生性能更好的解。 在蚁群算法中,一个有限规模的人工蚁群体,通过相互协作搜索用于解决优化问题的较优解。每只蚂蚁根据问 题依赖的准则,从被选的初始状态出发建立一个可行解 或是解的一个组成部分。 在建立蚂蚁自己的解决方案中, 每只蚂蚁都搜集关于问题拓征和其自身行为的信息,并 且使用这些信息来修改问题的表现形式,正如其它蚂蚁所看到的那样。 蚂蚁既能共同的行动又能独立的工作,显 示出了一种相互协作的行为,它们之间不使用直接通讯, 而使用信息激素指导着蚂蚁间的信息交换。蚂蚁使用一 种结构上的贪婪启发
10、式搜索可行解。根据问题的约束条 件列出了一个解,作为经过问题状态的最小代价(最短路径)。每只蚂蚁都能够找出一个解,但可能是较差解。 蚁群中的个体同时建立了很多不同的解决方案,找出高 质量的解是群体中的所有个体之间全局性的相互协作的 结果。有关蚁群算法的具体实现可参阅有关文献。4 蚁群算法在组合优化中的应用蚁群算法主要用于求解不同的组合优化问题,一类 应用于静态组合优化问题,另一类用于动态组合优化问 题。静态问题指一次性给出问题的特征,在解决问题过 程中,问题的特征不再改变。这类问题的范例就是经典旅行商问题(TSP);动态问题被定义为一些量的函数,这 些量的值由隐含系统动态设置。因此,问题在运行
11、时间 内是变化的,而优化算法须在线适应不断变化的环境。 这 类问题的典型例子是网络路由问题。411 ACA在静态组合优化中的应用 (1)旅行商问题(TSP):蚁群优化算法首先应用于一个测试问题就是旅行商问题。TPS问题是组合优化中 研究最多的N Phard问题之一,该问题就是寻找通过n个城市,各1次且最后回到原出发城市的最短路径。许多研究表明,应用蚁群优化算法求解TSP问题优于模拟 退火法、遗传算法、神经网络算法、禁忌算法等多种优化方法5- 6。(2)二次分配问题(QA P):二次分配问题是指分配n个设备给n个地点,从而使得分配的代价最小,其中代 价是设备被分配到位置上方式的函数。QA P是继
12、TSP之后蚁群算法应用的第一个问题,实际上, QA P是一般化的TSP3, 7。(3)车间任务调度问题(JSP): JSP问题指已知一组M台机器和一组T个任务,任务由一组指定的将在这些 机器上执行的操作序列组成。车间任务调度问题就是给 机器分配操作和时间间隔,从而使所有操作完成的时间最短,并且规定两个工作不能在同一时间在同一台机器 上进行。Colorni, Dorigo等人将蚂蚁算法应用于车间任务调度问题8。混流装配线问题:混流装配线是J IT生产方式的具体应用之一,它可以在不增加产品库存条件下满足用户多样化的需求。 混流装配线有时也特指混合车型组装线,即在一定时间内,在一条生产线上根据顾客需
13、求的变化 生产出各种不同型号的产品,这一类问题同属生产调度问题。文献9研究用蚁群算法解决混流装配线调度问题。(4)车辆路线问题(VRP): VRP问题来源于交通运输。已知M辆车,每辆车的容量为D,目的是找出最佳行车路线在满足某些约束条件下使得运输成本最小。文 献10- 12利用蚁群算法研究VRP结果表明,该方法优于模拟退火和神经网络,稍逊于禁忌算法。(5)图着色问题(GCP):已知一个图G=(N,E),G的一个q个颜色的着色是一个映射C:N1,q使得如果(i,j)E,则C(i)C(j)。GCP就是 找出图G的一种着色从而使得所使用的颜色数量q最小。Costa和Heits提出使用两条外激素轨迹解
14、决图着色问题13。(6)有序排列问题(SOP):给定一个有向图,图上的弧和节点都加了权,服从于节点间先后次序的约束,SOP指在有向图上找出一个最选权值的哈密顿路径。SOP 是N P难题,它以许多工程实际问题为模型,如有着接载和运送乘客约束的单车选路径问题,生产计划以及柔性制造系统中的运输问题等。Gambardella和Dorigo应用扩展的蚂蚁算法解决SOP,结果非常理想14。412 ACA在动态组合优化中的应用在动态组合优化问题中,通讯网络是一个典型例子。 网络优化问题有一些特征,如信息和计算分布,非第12期李士勇:蚁群优化算法及其应用研究进展913 静态随机动态,以及不同时的网络状态更新等
15、。路由是 网络控制中最关键的组件之一,它涉及到建立和使用路由表来指导数据通信量在网络范围内的分配活动。普通路由问题可以理解为是要建立一个路由表使得网络性能的一些量度最大化。(1)有向连接的网络路由:在有向连接的网络中,同一个话路的所有数据包沿着一条共同的路径传输,这条路径由一个初步设置状态选出15。在国际上Schoonder2werd等人首先将ACO算法应用于路由问题。后来,W hite等人将ACO算法用于单对单点和单对多点的有 向连接网络中路由16, Bonabeau等人通过引入一个动态规则机制改善ACO算法17。D icarogy、Dorigo研究将蚁群算法用于高速有向连接网络系统中,达到
16、公平分配效果最好的路由18。在国内张素兵、刘泽民等人提出了基于蚂蚁算法的QoS路由调度方法及分段QoS路由调度方法19, 20。(2)无连接网络系统路由:在无连接或数据包中,同一话路的网络系统数据包,可以沿着不同的路径传输,在沿着信道从源节点到终节点的每一个中间结点上,一个具体决策是由局部路由组件做出。随着Internet规模不断扩大,在网络上导入QoS技术,以确保实时业务的通信质量。QoS组播路由的目的 是在分布的网络中寻找最优路径,要求从源节点出发,历经所有的目的节点,并且在满足所有的约束条件下,达到花费最小或达到特定的服务水平。 在分析路由问题时,为方便可将网络看成无向带权的连通图,顾军华等人用蚂蚁算法研究解决包含带宽、延时、延时抖动、包丢失率和最小花费等约束条件在内的QoS组播路由问题,效果优于模拟退火算法及遗传算法21。413 ACA在其他领域的应用(1)管线敷设问题:电缆敷设问题与TSP问题类似。要求每一根电缆在从电缆连接起点设备开始,通过不同 的通道、竖井至电缆连接终端,连接起来的电
