基于新型的蚁群算法在路径安排的研究

来源:用户上传      作者: 宁　博

　　[摘要] 蚁群优化算法作为一种新型的启发式算法，在解决组合优化问题如旅行商问题,中可以得到较好的次优解而备受重视，但蚁群算法的运算过程由于受各种参数设置以及信息素更新方式的影响，存在着早熟收敛，容易陷入局部最优的现象。本文在这方面应用蚁群系统来进行尝试解决，并将其应用到邮递员的路径安排中进行实证检验。
　　[关键词] 蚁群优化算法 旅行商问题 蚁群系统 信息素更新 路径安排
　　
　　路径优化问题属于典型的组合优化问题，因为在对其求解的过程中存在着“组合爆炸”等NP类难题，蚁群算法具有良好的并行性、鲁棒性以及自组织性，并且可以对其不足之处不断进行更新改造，容易与其他启发式算法结合等优点，在解决旅行商问题，二次分配问题等收到很好的效果。
　　一、TSP模型
　　旅行商问题TSP(Traveling Salesman Problem)：一个旅行商（推销员）想到n个城市推销商品，他面临如何选择一条道路使自己走完一遍后回到起点且所走路径最短的问题。旅行商问题(TSP)的数学模型:
　　这里，V是一个城市集合，|S|为集合S中所含图G的顶点个数。前面两个约束(2.3)、(2.4)意味着对每个顶点而言，仅有一条边进和一条边出，约束(2.5)则保证了没有任何子回路解的产生。
　　二、蚁群算法
　　蚂蚁优化算法(Ant Colony Optimization. ACO)是一种随机搜索算法。通常以蚂蚁系统(AS)求解平面上n个城市的TSP问题为例来说明蚁群算法模型。m:中蚂蚁的数量;dij:城市i和j之间的距离;:t时刻在i与j连线上残留的信息量。
　　蚁群系统(Ant Colony System, ACS)的状态转移规则：一只位于城市i的蚂蚁通过应用式(3.1)给出的规则选择下一个将要移动到的城市j，蚂蚁选择下一条路径的方法是：
　　 (3.1)
　　其中，:城市i到城市j可望程度，有记录蚂蚁k已经访问过的城市的禁忌表；q为均匀分布在[0,1]上的一个随机变量，q0为在[0,1]上的参数，当时，使用随机选择的方式选择下一条路径（称为开发exploitation）；当时，选择概率最高的路径（称为探险方式exploration）；
　　仅仅是天才蚂蚁才允许在每次解构造完成后释放信息素，而对于非已知最优路径上的信息素则也不进行挥发操作，此称为全局信息素更新。其更新方法如下：
　　(3.2)
　　其中为到目前为止找出的全局最优路径，算法已经发现的最好解称为。除了全局信息素更新外，算法还在解构造过程中通过弧后立即进行局部的信息素更新，其更新方法如下:
　　(3.3)
　　其中,设置可以产生好的结果，n是TSP问题中城市的个数，是通过最近邻居方法构造的解的长度。实验表明，局部更新规则可以有效的避免蚂蚁收敛到同一路径。
　　蚁群算法基本实现流程：
　　初始化各参数 For NC=1 to 循环次数 do begin for k=1 to m do begin
　　repeat 根据(4.1)式选择下次访问的城市j Until蚂蚁k完成一条路径，计算其路径长度并保存下来 End 根据(4.2)(4.3)式进行信息素更新 end
　　三、应用检验
　　假设某一个小镇 (i=0)有15个村庄，镇上邮局的一名邮递员负责每天骑车将报纸书信投递到每个村庄i (i=1,2,…,15)，相邻的村庄相互通路（如表1），且邮递员一次可以完成所有的任务，并且骑车路线寻求最短。在例子中，设置参数。通过蚁群系统的模拟计算，最后得到邮递员的最优行进路线:
　　
　　总行程为L=18.1(km)
　　表1.邮局和各个村庄的坐标
　　
　　参考文献:
　　[1]李军谢秉磊郭耀煌:非满载车辆调度问题的遗传算法.系统工程理论方法应用,2000 3,235～239
　　[2] Luca Maria Gambardella and Marco Dorigo:Solving symmetric and asymmetric TSP's by antcolonies. IEEE Int. Conf. Evolutionary Computation. IEEE-EC 96，1996,622～627
　　[3]Desrosiers J, Soumis F, Desrochers M. Routing with time windows by column generation [J].Networks，1984,14，545～565
　　[4]华宝玉王雪峰冯英浚:有时间窗约束单车场单车型非满载车辆调度问题的遗传算法.哈尔滨商业大学学报(自然科学版),2002,6: 621～624

转载注明来源:https://www.xzbu.com/3/view-1491161.htm