《基于新型的蚁群算法在路径安排的研究》由会员分享，可在线阅读，更多相关《基于新型的蚁群算法在路径安排的研究（3页珍藏版）》请在金锄头文库上搜索。
1、基于新型的蚁群算法在路径安排的研究基于新型的蚁群算法在路径安排的研究是小柯论文网 通过网络搜集，并由木站工作人员整理示发布的，基于新型的蚁群算法在路径安排的研究是 篇质量较高的学术论文，供木站访问者学习和学术交流参考Z用，不可用于其他商业目的, 基于新型的蚁群算法在路径安扌II喲研究的论文版权归原作者所有，因网络整理，有些文章作 者不详，敬请谅解，如需转摘，请注明岀处小柯论文网，如果此论文无法满足您的论文要求, 您可以申请木站帮您代写论文，以下是正文。摘要蚁群优化算法作为一种新型的启发式算法，在解决组合优化问题如旅行商问题, 中可以得到较好的次优解而备受重视，但蚁群算法的运算过程rti于受各种
2、参数设置以及信息 素更新方式的影响，存在着早熟收敛，容易陷入局部最优的现彖。木文在这方面应用蚁群系 统来进行尝试解决，并将其应用到邮递员的路径安排中进行实证检验。关键词蚁群优化算法旅行商问题蚁群系统信息素更新路径安排路径优化问题属于典型的组合优化问题，因为在对其求解的过程中存在肴“组合爆炸” 等NP类难题，蚁群算法具有良好的并行性、鲁棒性以及白组织性，并且可以对其不足之处 不断进行更新改造，容易与其他启发式算法结合等优点，在解决旅行商问题，二次分恥问题 等收到很好的效果。一、TSP模型旅彳亍商问题TSP(Traveling Salesman Problem)： 一个旅行商(推销员)想到n个城市
3、推 销商品，他面临如何选择一条道路使白己走完一遍示冋到起点且所走路径最短的问题。旅行 商问题(TSP)的数学模型：这里，V是一个城市集合，ISI为集合S中所含图G的顶点个数。前面两个约朿(2.3)、 (2.4)意味着对每个顶点而言，仅有一条边进和一条边出，约束(2.5)则保证了没有任何了冋路 解的产生。二、蚁群算法蚂蚁优化算法(Am Colony Optimization. ACO)是一种随机搜索算法。通常以蚂蚁系统 (AS)求解平面上n个城市的TSP问题为例来说明蚁群算法模型。m:中蚂蚁的数量;clij:城市i 和j Z间的距离;：1时刻在i与j连线上残留的信息量。蚁群系统(Ant Colo
4、ny System, ACS)的状态转移规则：一只位于城市i的蚂蚁通过应用 式(3.1)给出的规则选择下一个将要移动到的城市j,蚂蚁选择下一条路径的方法是：(3.1)其中，：城市i到城市j可望稈度，有记录蚂蚁k已经访问过的城市的禁忌表；q为均 匀分布在0,1上的一个随机变量，q()为在0,1上的参数，当时，使用随机选择的方式选择 下一条路径(称为开发exploitation)；当时,选择概率最高的路径(称为探险方式exploration)；仅仅是天才蚂蚁才允许在每次解构造完成后释放信息索，而对于非已知最优路径上的 信息素则也不进行挥发操作，此称为全局信息素更新。其更新方法如下：(3.2)其中为
5、到忖前为止找出的全局最优路径，算法已经发现的最好解称为。除了全局信息 素更新外，算法还在解构造过程中通过弧后立即进行局部的信息素更新，其更新方法如下:(3.3)其中，设置可以产生好的结果，n是TSP问题中城市的个数，是通过最近邻居方法构造 的解的长度。实验表明，局部更新规则可以有效的避免蚂蚁收敛到同一路径。蚁群算法基本实现流程：初始化各参数 For NC=1 to 循环次数 dobeginfor k=l to m dobeginrepeat根据(4.1)式选择下次访问的城市jUntil蚂蚁k完成一条路径，计算其路径长度 并保存下来End根据(4.2)(4.3)式进行信息素更新end三、应用检验
6、假设某一个小镇(i=0)有15个村庄，镇上邮局的一名邮递员负责每天骑车将报纸书信 投递到每个村庄i (i=l,2,.,15),相邻的村庄相互通路(如表1),且邮递员一次可以完成所 有的任务，并且骑车路线寻求最短。在例了中，设置参数。通过蚁群系统的模拟计算，最后 得到邮递员的最优行进路线：总行程为L= 18.1 (km)表1.邮局和各个村庄的坐标参考文献：1李军谢秉磊郭耀煌:非满载车辆调度问题的遗传算法系统工程理论方法应用,2000 3,235-2392J Luca Maria Gambardella and Marco Dorigo:Solving symmetric and asymmetr
7、ic TSPs by antcolonies. IEEE Int. Conf. Evolutionary Computation. IEEE-EC 96, 1996,6226273Desrosiers J, Soumis F, Desrochers M. Routing with time windows by column generation J.Networks, 1984,14, 5455654|华宝玉王雪峰冯英浚:有时间窗约束单车场单车熨非满载车辆调度问题的遗传算法. 哈尔滨商业大学学报(自然科学版),2002,6: 621624其他参考文献Baker, Sheridan. The
8、Practical Stylist. 6lh ed. New York: Harper & Row, 1985.Flesch, Rudolf. The Art of Plain Talk. New York: Harper & Brothers, 1946.Gowers, Ernest. The Complete Plain Words. London: Penguin Books, 1987.Snell-Hornby, Mary. Translation Studies: An Integrated Approach. Amsterdam: JohnBenjamins, 1987.Hu, Z
9、huanglin.湖壮麟,语言学教程M.北京：北京大学出版社,2006.Jespersen, Otto. The Philosophy of Grammar. London: Routledge, 1951.Leech, Geoffrey, and Jan Svartvik. A Communicative Grammar of English. London:Longman, 1974.Li, Qingxue, and Peng Jianwu. 庆学、彭建武,英汉翻译理论与技巧M.北京:北京 航空航天大学出版社,2009.Lian, Shuneng. 淑能,英汉对比研究M.北京：高等教冇出版
10、社，1993.Ma, Huijuan, and Miao Ju.马会姐、苗菊,当代西方翻译理论选读MJ.北京：外语教学 与研究岀版社,2009.Newmark, Peter. Approaches to Translation. London: Pergmon P, 1981.Quirk, Randolph, et al. A Grammar of Contemporary English. London: Longman, 1973.Wang, Li. IT.力,中国语法理论MJ.济南：山东教育出版社,1984.Xu, Jiunping.许建平,英汉互译实践与技巧M.北京：清华大学出版社,2003.Yan, Qigang.严启刚,英语翻译教程M.天津：南开大学出版社,2001.Zandvoort, R. W. A Handbook of English Grammar. London: Longmans, 1957.Zhong, Shukong. 钟述孔,英汉翻译手册M.北京：商务印书馆,1983.Zhou, Zhipei.周志培,汉英对比与翻译中的转换M,上海：华东理工大学出版社, 2003.
