一种基于精英策略的改进蚁群算法及应用.doc

一种基于精英策略的改进蚁群算法及应用 Improved Ant Colony Algorithm Based on Elitist Strategy and Application 摘 要：针对基本蚁群算法求解速度慢,容易出现早熟和搜索停滞现象，本文基于精英策略并将遗传算法中排序的概念扩展到精英机制当中，提出了一种改进蚁群算法模型。改进算法根据蚂蚁排序，提出一种新的加权方法进行信息素更新。将该算法模型应用于配送优化问题，对30城市配送问题仿真结果表明：改进算法的求解速度和求解精确度都明显优于基本蚁群算法。 关键词：蚁群算法；搜索停滞；精英策略；排序 ABSTRACT： The basic ant colony algorithm converges slowly, is prone to plunge into partial optimum and results in search stagnation. In this paper, improved ant colony algorithm is proposed. Improved algorithm is based on elitist strategy which the optimized compositor is introduced into. According to ant compositor, new weighted coefficient is designed for pheromone updating. New algorithm is applied to the distribution routes optimization.The simulation results show that improved algorithm is much more efficient than the basic ant colony algorithm. KEYWORDS：ant colony algorithm(ACA)；search stagnation；elitist strategy； compositor; 1 引言 蚁群算法（Ant Colony Algorithm，ACA）[1] 又称作蚂蚁算法，是由意大利的Marco Dorigo于1992年在他的博士论文中首先提出，其基本思想是模仿蚂蚁依赖信息素进行通信而显示出的社会行为，在Agent总体的基础上，由一个贪心算法指导下的自催化过程引导每个Agent的行动。该算法模拟了蚂蚁觅食时的行为，按照启发式思想，通过信息素的诱导作用，逐步收敛到问题的最优解。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。目前, 蚁群算法已经广泛应用于旅行商问题、二次分配问题、作业车间调度问题、车辆路径安排问题等问题，成为解决组合优化问题最有效的算法之一。 基本蚁群算法复杂度较高，一般需要较长的搜索时间，而且容易出现搜索停滞现象 AUTHOR 作者 基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No；湛江师范学院 青年基金项目（QW0712）； 作者简介：张家善（1979—），男，四川巴中人，讲师，博士研究生，从事信息管理和物流管理的研究工作，zh_jiashan@163.com；王志宏，教授，博导，研究方向：技术经济；陈应显,讲师,博士。 (Stagnation Behaviour)，即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。围绕该问题，学者们发表了不少文献，如文 献[3]在路径选择时提出了一种不再考虑距离因素，仅考虑信息素强度的方法；文献[4]通过在局部搜索中采用聚类进行二次搜索,取得了较好求解效果；文献[5]?基于蚂蚁分类，提出了一种改进精英策略算法。但是，实例验证表明，上述算法求解结果并不理想。本文基于精英策略并将遗传算法中排序的概念扩展到精英机制当中，对蚁群算法进行改进，试图在较短时间内获得问题的满意最优解。 2. 基本蚁群算法 [1,2,6] 蚂蚁在觅食过程中对所经过路段释放一种被称为信息素的物质，其他经过该路段的蚂蚁通过对残留信息素的数量判断是否重复该路段，从而找到一条巢穴到食物源之间的最短路径。该路段残留信息素越多，所有蚂蚁选择该路段的可能性也就越大。蚁群算法正是模拟真实蚁群觅食行为策略而产生的一种启发式算法。 假设有m只蚂蚁放入到n个随机选择的需求节点中，每一只蚂蚁将根据线路上的信息浓度选择下一个它还没有访问的节点；同时在完成一步(从一个节点到达另外一个节点)或者一个循环(完成对所有n个