下载文档原格式
2019，55（3）1引言旅行商问题（Traveling Salesman Problem ，TSP ）是数学领域中一个重要的问题。
假设一个商人从某地出发，要求选择一条最短路径，可以不重复地走完所有城市并回到起点。
TSP 问题是一类NP 完全组合优化问题。
目前，TSP 问题有很多求解算法，主要有贪婪算法、模拟退火[1]、遗传算法、粒子群算法[2]和蚁群算法等。
蚁群算法由于其正反馈和鲁棒性等特点，成为解决TSP 这类组合优化问题最有效的方法之一。
1996年，Marco Dorigo 提出了蚂蚁系统（AS ），该模基于聚度的自适应动态混沌蚁群算法刘明霞1，游晓明1，刘升21.上海工程技术大学电子电气工程学院，上海2016202.上海工程技术大学管理学院，上海201620摘要：针对蚁群算法收敛速度慢，容易陷入局部最优的问题，提出了一种基于聚度的自适应动态混沌蚁群算法（A_ACS ）。
在迭代前期利用聚度来衡量解的多样性，自适应调节局部信息素分布，同时引入混沌算子来增加种群多样性，避免算法陷入局部最优，从而提高解的精度；在迭代后期去掉混沌算子，减少混沌扰动性，来提高算法的收敛速度。
将A_ACS 用于TSP 问题，仿真结果表明，该算法较ACS 和MMAS 算法减少了搜索时间，并且提高了解的质量，其平衡了多样性与收敛性之间的矛盾，整体性能优于其他两种算法。
关键词：蚁群算法；聚度；混沌优化；自适应信息素更新；旅行商问题文献标志码：A中图分类号：TP18doi ：10.3778/j.issn.1002-8331.1809-0316刘明霞，游晓明，刘升.基于聚度的自适应动态混沌蚁群算法.计算机工程与应用，2019，55（3）：15-22.LIU Mingxia,YOU Xiaoming,LIU Sheng.Adaptive dynamic chaotic ant colony algorithm based on degree of puter Engineering and Applications,2019,55（3）：15-22.Adaptive Dynamic Chaotic Ant Colony Algorithm Based on Degree of AggregationLIU Mingxia 1,YOU Xiaoming 1,LIU Sheng 21.College of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China2.College of Management,Shanghai University of Engineering Science,Shanghai 201620,ChinaAbstract ：Aiming at the problem that the ant colony algorithm is slow in convergence and easily falls into a local opti-mum,an adaptive dynamic chaotic ant colony algorithm （A_ACS ）based on the degree of aggregation is proposed.In the early iterations,the degree of aggregation is used to measure the diversity of solutions and self-adaptively adjust the local pheromone distribution,and chaos operators are introduced to increase the diversity of the population to avoid the algo-rithm falling into a local optimum,thereby improving the accuracy of the solution.In the later iterations,the chaotic operator is removed to reduce the chaotic disturbance and increase the convergence speed of the algorithm.The A_ACS is used for the TSP problem.The simulation results show that the proposed algorithm reduces the search time and improves the quality of solution compared with the ACS and MMAS algorithm.It balances the contradiction between diversity and conver-gence,and the overall performance is better than the other two algorithms.Key words ：ant colony algorithm;degree of aggregation;chaotic optimization method;adaptive method of updating pheromone;traveling salesman problem基金项目：国家自然科学基金（No.61673258，No.61075115，No.61403249，No.61603242）。
物联网中的动态路由算法近年来，随着物联网技术的飞速发展，越来越多的智能设备进入我们的生活中。
这些设备之间需要进行通信，而要实现这样的通信，就需要迅速、高效地找到一条合适的通信路径。
在物联网中，动态路由算法被广泛应用，它可以实现网络的自适应、优化和可靠性。
本文将介绍物联网中常用的动态路由算法及其优缺点。
一、物联网中的路由算法在物联网中，路由算法的主要任务是找到一条最佳的路径，让信息尽快地传输到目的地。
传统的路由算法有基于离散事件的模拟技术（DES）、最短路径算法（SPF）和最小成本路由算法等。
但这些传统算法并不适用于物联网。
物联网通常涉及大量的设备和节点，这个网络是分布式的、动态的，并且节点具有不可预测的移动性。
因此，物联网中的路由算法必须是动态的、自适应的、具有负载均衡和容错能力的。
为此，物联网中采用了一些适用于动态环境下的路由算法，常用的有以下几种。
二、基于距离矢量的路由算法基于距离矢量的路由算法（Distance Vector Routing Protocol，DVRP）是一种基于链路状态的路由算法，其主要思想是每个节点维护到其他节点的距离信息，通过比较每个节点距离其它节点的距离，寻找到一条最短路径。
这种算法的优势在于其简单易实现、抗噪声和抗故障能力强。
但它的缺点也很明显，如容易出现环路、收敛速度慢等。
但在小型的物联网中，这种算法仍然是一个不错的选择。
三、基于链路状态的路由算法在物联网中，基于链路状态的路由算法（Link State Routing Protocol，LSRP）也被广泛应用。
该算法要求每个节点通过广播自己的链路状态信息，以构建整个网络图，然后计算每个节点到达其他节点的最短路径。
这种算法的优点在于其收敛速度快、计算准确性高，但缺点也很明显，如通信效率低下、节点存储和计算负载大等。
四、基于蚁群算法的路由算法基于蚁群算法的路由算法是指模拟蚂蚁寻找食物的行为来寻找网络中最短的路径，它具有自组织、分布式、容错、自适应等特点，可以有效地处理动态和复杂的网络环境。
基于蚁群算法的自动化配送路线规划在当今快节奏的商业环境中，高效的配送路线规划对于企业的运营和客户满意度至关重要。
传统的配送路线规划方法往往依赖于人工经验和简单的数学模型，难以应对复杂多变的实际情况。
随着信息技术的不断发展，蚁群算法作为一种新兴的智能优化算法，为自动化配送路线规划提供了一种创新且有效的解决方案。
蚁群算法的灵感来源于自然界中蚂蚁寻找食物的行为。
蚂蚁在寻找食物的过程中，会在经过的路径上释放一种叫做信息素的化学物质。
其他蚂蚁能够感知到这种信息素，并倾向于选择信息素浓度较高的路径。
通过这种正反馈机制，蚂蚁们能够逐渐找到从蚁巢到食物源的最短路径。
将蚁群算法应用于配送路线规划，首先需要对问题进行数学建模。
我们可以将配送中心和各个配送点看作是蚁巢和食物源，将配送路线看作是蚂蚁行走的路径。
每个配送点都有一定的货物需求，车辆有最大的装载量和行驶里程限制。
目标是找到一组最优的配送路线，使得配送成本最低、时间最短、客户满意度最高等。
在算法的实现过程中，需要定义一些关键的参数和操作。
例如，蚂蚁的数量、信息素的初始浓度、信息素的挥发系数、启发式因子等。
蚂蚁在选择下一个配送点时，会综合考虑信息素浓度和启发式因子。
启发式因子通常与配送点之间的距离、货物需求等因素相关，用于引导蚂蚁做出更合理的选择。
蚁群算法具有很强的自适应性和鲁棒性。
它能够在复杂的配送网络中自动搜索最优解，并且对于不同的问题规模和约束条件具有较好的适应性。
与传统的优化算法相比，蚁群算法不需要对问题的性质进行过多的假设，也不需要复杂的数学推导，更适合解决实际中的配送路线规划问题。
然而，蚁群算法也存在一些不足之处。
例如，算法的收敛速度较慢，容易陷入局部最优解。
为了克服这些问题，研究人员提出了许多改进的方法。
例如，采用混合算法，将蚁群算法与其他优化算法（如遗传算法、模拟退火算法等）相结合；或者对算法的参数进行动态调整，以提高算法的性能。
在实际应用中，基于蚁群算法的自动化配送路线规划系统通常包括以下几个模块：数据输入模块、模型构建模块、算法求解模块和结果输出模块。
Ad Hoc 网络中基于改进蚁群算法的QoS 多播路由算法孙明明,邵罕(信阳师范学院计算机与信息技术学院,河南信阳464000)摘要:蚁群算法作为一种新型的随机优化算法,能够较好地适应Ad Hoc 动态网络环境,但存在收敛速度慢和易陷入局部最优等缺点。
本文在改进蚁群算法的基础上,针对蚁群算法应用于Ad Hoc 网络多播路由时普遍产生的拥塞问题,提出了一种多约束Q oS 多播路由算法。
该算法能够对拥塞链路做出较快的反应,进行拥塞回避,从而实现网络业务流负载均衡。
关键词:AdHoc 网络;QoS 多播路由;蚁群算法;拥塞回避中图分类号:TP 301.6文献标识码:AA QoS Multicast Routing Based on Improved Ant Colony Algorithm for Ad HocNetworksSUN M ing-ming ,SHAO Han(Computer and Information T echnolo gy Academy of Xinyang No rmal University ,Henan Xiny ang 464000)Key wor ds:Ad Hoc netw orks;QoS multicast r outing;ant colony algorithm;congestion avoidanc e作者简介:孙明明(1981-),男,河南省洛阳市人,助教,大学本科,主要研究方向计算机科学与技术教育;邵罕(),男,河南省驻马店市人,助教,大学本科,主要研究方向计算机科学与技术教育。
1引言近年来,随着各类多媒体业务及实时业务的普及和推广,要求网络在带宽、时延等方面提供保障,在AdHoc 网络中提供QoS 支持越来越重要。
然而,考虑到Ad Hoc 网络中节点是移动的,网络拓扑结构在不断变化,同时,这些节点的计算能力和存储容量较低、能量受限,因此,如何设计出满足Q oS 约束的多播路由,是一个具有挑战性的课题。
