蚁群系统

摘要： 社交网络的影响力最大化是网络分析领域的关键问题,在广告宣传、舆情控制等场景有着诸多应用。该问题指在一个社交图中选取一组源节点,使得所选取的节点集合能够在某种传播模型中形成最大的影响力。由于节点选取问题是典型的NP-hard问题,在大型网络中会遭遇组合爆炸。近些年来,国内外学者一般采用启发式算法求得问题的近似解。然而,现有工作鲜有考虑到节点选取的成本,所得到的解无法满足实际应用中的预算条件。针对此问题,首先考虑节点选取的成本约束,并对成本受限条件下的社交网络影响最大化问题进行数学建模;其次为节约源节点的冗余覆盖成本,使用快速贪婪模块度最大化算法对网络进行社区聚类;然后根据社区聚类结果在蚂蚁游走过程中引入跨社区游走因子,以增强蚂蚁在网络上的全局游走能力;最后,在蚁群系统中设计了新的启发式信息和信息素形式,并将评估函数设计为罚函数的形式以控制节点的选取成本,提出了基于社区发现的蚁群系统算法(Community Detection-based Ant Colony System,CDACS)。在真实数据集上的实验结果表明,CDACS算法比未加入跨社区因子的蚁群算法取得的覆盖率平均提高了15%左右,运行时间平均减少了约20%。在覆盖效果上相比其他现有的影响力最大化算法都取得了显著的改进。此外,CDACS在不同数据集上所产生的解均满足不同的成本限制,体现了CDACS算法在成本控制上的可靠性。

摘要： 现有动态交通分配模型大多使用数值算法求解,无法保证分配结果的准确性.蚁群算法作为一种分布并行计算的启发式算法,能够高效求解网络分配问题,但是,现有算法虽然保证了局部搜索效率,却忽略了全局搜索能力和对出行状况变化的动态反馈.本文在算法中插入阻抗计算步骤,将每步蚂蚁择路结果通过计算生成决策因子,并据此自适应调整算法参数,模拟实际出行者易于得到实时路况信息而有趋向性的择路行为,在保证局部搜索效率的前提下,增加算法求解质量和全局搜索能力.最后,分别使用改进前后的算法求解模型进行对比.结果表明,改进算法的分配结果更优,且路网流量分配更均衡,离散程度小,路网利用率高.改进算法求解模型具有理论结合实际的优势.

摘要： 虚拟化技术是云数据中心的核心技术之一,良好的资源管理及调度方法有利于云数据中心的虚拟资源管理从而提供快速、安全和可靠的服务.本文主要研究了工作流联合调度问题,以最小化费用开销为目的,在保证工作流完成的前提下,提出了一种二阶段的工作流联合调度算法,分别优化了工作流到虚拟机的映射和虚拟机到物理机的部署问题.该算法基于蚁群系统的核心思想,设计了相关的启发函数和信息素更新规则,形成了工作流到虚拟机的映射集合,在减少了工作流的完成时间的同时避免了陷入局部最优解;然后,针对虚拟机-物理机的部署问题,考虑了多类型虚拟机的特点,采用了贪心算法的思想,在保证工作流的完成时间的情况下达到了最小化费用开销目的.最后,通过Cloudsim仿真平台进行实验,分别采用四个工作流数据集:CyberShake,Montage,LIGO,SIPHT,将提出的算法,与代表性的PSO算法、FCFS算法、IPSO算法进行对比,结果表明提出的算法在费用和执行效率明显优于其他算法.

摘要： 本文提出一种新的诊断策略-蚁群系统(Ant Colony System,简称ACS)在比较模型下的快速精确诊断算法,即在系统中通过模拟蚁群获取食物的过程,并对其最短路径进行分析,结合ACS环诊断策略,得到关于序列的重要性质,基于这些性质,从而提出一种快速精确诊断算法,此算法的时间复杂度为O(N),其中N为蚁群中蚂蚁的数量.

摘要： 针对蚁群系统(Ant Colony System,ACS)容易陷入局部最优和收敛速度较慢的不足,提出了自适应模糊蚁群系统(AF-ACS)用于旅行商问题(TSP).该算法的核心是引入模糊隶属度和信息熵的概念,AF-ACS将以信息熵为概率,自适应地对ACS引入模糊隶属度,以平衡算法的种群多样性与收敛速度之间的关系.算法早期引入模糊隶属度的概率较小,保证算法的多样性;算法后期引入模糊隶属度的概率较大,提高算法的收敛速度.通过与ACS和ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm)进行14种不同规模的TSP测试集实验对比,AF-ACS以较少的迭代次数取得最优解或较优解.从而证明了AF-ACS的可行性与高效性.%Because the Ant Colony System(ACS)is easy to fall into the local optimization and slow convergence, an Adaptive Fuzzy Ant Colony System(AF-ACS)is proposed for Traveling Salesman Problem(TSP). The core of the algorithm is to introduce the concept of fuzzy membership and information entropy. AF-ACS will adaptively introduce fuzzy membership to ACS with information entropy as the probability. This balances the relationship between the population diversity of the algorithm and the rate of convergence. The probability of introducing fuzzy membership degree early in the algorithm is small, which ensures the diversity of the algorithm. The probability of introducing fuzzy membership degree in the later stage of the algorithm is large, which improves the convergence speed of the algorithm. By comparing 14 different scale TSP test sets with ACS and ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm), AF-ACS obtains the optimal solution or better solution with fewer iterations. This proves the feasibility and efficiency of AF-ACS.

摘要： Low-voltage power line carrier communication channel often shows strong noise interference,signal attenuation,time-varying strong,which directly affects the power line carrier communication range,and reduces the reliability of power line carrier communication.In this paper,a power line carrier communication method based on Q learning and improved ant colony system fusion is proposed by analyzing the topology of low voltage power line network.Firstly,the Q search algorithm is used to search the power line network globally to obtain the initial value of the pheromone on each path.Then,the ant colony algorithm is used to obtain the optimal path of the positive feedback mechanism and the improved adaptive adjustment search strategy.In this paper,we can compare the algorithm with two ant system algorithms.The results show that the proposed algorithm can quickly and effectively establish the routing of the master node to each slave node in the network and can be based on changes in the communication channel dynamic maintenance routing,and it has a strong resistance to destruction and self-healing,and improve the reliability of lowvoltage power line carrier communication.%低压电力线载波通信信道常常表现出噪声干扰强、信号衰减大、时变性强,直接影响电力线载波通信的范围,降低电力线载波通信的可靠性.文中通过分析低压电力线网络拓扑结构,提出了一种基于Q学习和改进蚁群系统融合的电力线载波通信路由方法.首先采用Q学习算法对电力线网络进行全局搜索得到各路径上信息素初始值;然后利用蚁群算法正反馈收敛机制以及改进后自适应调整搜索策略得到最优路由.将文中算法与两种蚂蚁系统算法进行仿真对比,结果表明,文中算法能更快地建立起网络中主节点到各从节点的路由,并能根据通信信道的变化动态的维护路由,具有很强的抗毁性和自愈性,提高了低压电力线载波通信的可靠性.

摘要： 针对蚁群系统(ACS)解决机器人路径规划问题时种群多样性与收敛速度的不足,对蚁群系统引入动态混沌算子,从而平衡种群多样性和收敛速度之间的关系.动态混沌蚁群系统的核心是在传统蚁群系统引入Logistic混沌算子来增加种群多样性,从而提高解的质量.在迭代前期加入混沌算子,以调整路径中的全局信息素值,增加算法的种群多样性,从而避免算法陷入局域优化解;在后期则转为蚁群系统,来确保动态混沌蚁群系统的收敛速度.仿真结果表明,对于机器人路径规划问题,与蚁群系统相比,动态混沌蚁群系统具有更好的种群多样性、更高的解的质量和更快的收敛速度;与精英蚁群系统(EAS)和基于排序的蚂蚁系统(ASrank)相比,动态混沌蚁群系统能够平衡解的质量与收敛速度之间的关系,即使在复杂障碍物的环境下,动态混沌蚁群系统也能较好地找到最优解.动态混沌蚁群系统能够提升移动机器人路径规划中的效率.%To solve problems of population diversity and convergence speed when an Ant Colony System (ACS) is used to robot path planning,a dynamic chaos operator was introduced in the ACS.The dynamic chaotic ACS can balance population diversity and convergence speed.The core of dynamic chaotic ACS is that a Logistic chaotic operator was added to the traditional ACS to increase population diversity and improve the quality of the solutions.First,the chaotic operator was added to the pre-iteration to adjust the global pheromone value in the path to increase the population diversity of the algorithm,so as to avoid the algorithm to fall into the local optimal solution.Then,in the later stage,the ACS was used to ensure convergence speed of the dynamic chaotic ACS.The experimental results show that the dynamic chaotic ACS has better population diversity compared with the ACS for the robot path planning problem.The solution quality is higher and the convergence speed is faster.Compared with the Elitist Ant colony System (EAS) and the rank-based Ant System (ASrank),the dynamic chaotic ACS can balance the relationship between the quality of the solutions and the convergence speed.The dynamic chaotic ACS can find better optimal solutions even in the complex obstacle environment.The dynamic chaotic ACS can improve the efficiency of mobile robot path planning.

摘要： 为了解决遗传算法中存在的早熟收敛、收敛速度慢等不足，本文结合遗传算法和蚁群算法，提出了一种基于启发式遗传信息的蚁群遗传算法。ACGA算法由基本遗传算法和蚁群系统两部分组成，ACGA算法将蚁群系统产生的所有个体保留至下一代。在遗传算法中加入了蚁群系统，提高了遗传算法的种群的多样性，同时减小了搜索域。实验结果表明，ACGA算法在收敛速度和收敛精度上均优于ACS算法和SGA算法。

摘要： 车辆路径问题(VRP)是一个NP难题,蚁群算法是求解诸如车辆路径安排问题等组合优化问题的有效工具。在了解VRP问题及蚁群算法的基础上,分析了蚁群算法在VRP中的应用,针对蚁群系统(ACS)的不足之处,借鉴MMAS思想,引入动态负反馈机制及适当增大能见度机制对蚁群算法进行改进优化,结合节约函数求解VRP问题。仿真结果表明,本文提出的算法无论是在最优值还是在收敛速度上都优于基本蚁群算法,实用性强,能较好的解决VRP问题。

摘要： 本文将量子群进化算法(QEA)与蚁群系统(ACS)进行融合,提出一种新的量子蚁群算法(QACA).该算法的核心是在蚁群系统(ACS)中引入量子算法中的量子的态矢量和量子旋转门来分别表示和更新信息素,使算法具有更好的种群多样性和全局寻优能力.结合TSP问题,对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法具有较强的问题求解能力.

摘要： 基于联盟的数据汇聚是无线传感器网络中一种新型的数据汇聚机制，其协同数据传输方式具有优良的节能效果，而该数据汇聚机制的路由策略是亟待解决的问题。论文结合了地理位置已知的路由和能量感知的路由协议，提出了一种适用于联盟数据汇聚的路由策略，将联盟质心到下一个联盟头的距离作为路由选择的一个重要决策因子，同时采用蚁群系统的反馈机制引导路由。仿真实验结果表明该策略在保证良好的路由方向性的前提下，能够将路由的能量消耗平均到多个节点上，从而延长网络存活时间。

摘要： 在无线传感器网络(WSN)中,节点间的协同是具有挑战性的问题,多智能体理论的动态联盟是WSN协同的重要方法.由于WSN的能量资源受限,因此设计一种能量有效的动态联盟形成算法是关键。基于蚁群系统的运行机制提出了一种具有"负反馈"特性的动态联盟形成算法,可以在保证一定联盟质量的前提下,将能量消耗平均到多个传感器节点上,从而充分利用多个传感器节点的能量以延长网络存活时间,解决更多、更复杂的问题。仿真结果说明了算法在目标跟踪应用中的有效性.

摘要： 对近年来引起广泛兴趣的蚁群算法的研究现状进行考察,简要介绍了几种修正的蚁群算法,如蚁群系统(ACS)、具有变异特征的蚁群算法、与遗传算法相结合的蚁群算法等.并以蚁群算法的电力系统中以及在事务流程重建(BPR)中的应用为例,考察了该算法与实际应用问题相结合的一些情况.

摘要： 对蚁群算法的进展情况作了简要综述。蚁群算法是一种新型的模拟进化算法，该方法的主要特点是：正反馈、分布式计算、与某种启发式算法相结合。研究表明该方法是 其于种群的鲁棒性较强的算法。

摘要： 对蚁群算法的进展情况作了简要综述。蚁群算法是一种新型的模拟进化算法，该方法的主要特点是：正反馈、分布式计算、与某种启发式算法相结合。研究表明该方法是 其于种群的鲁棒性较强的算法。

摘要： 对蚁群算法的进展情况作了简要综述。蚁群算法是一种新型的模拟进化算法，该方法的主要特点是：正反馈、分布式计算、与某种启发式算法相结合。研究表明该方法是 其于种群的鲁棒性较强的算法。

摘要： 本发明提供了一种基于蚁群系统的多细胞多参数（位置、速度、轮廓等）的联合估计与精确跟踪系统，属于细胞跟踪领域。通过对每一幅灰度图像，定义相应的局部区域灰度方差来生成蚁群初始位置分布；在此基础上，构建两个平行工作且相互独立的信息素场，即位置场和轮廓场，分别在细胞位置估计模块和细胞轮廓估计模块构建有界蚁群决策系统；最终精确估计出细胞的位置、速度与轮廓等重要参数，从而实现对多细胞的精确跟踪。通过有界启发式蚁群系统相互合作，无需细胞检测模块、无需大量的细胞训练样本，解决了在低对比度细胞图像序列下多细胞动力学参数及多细胞轮廓联合估计与跟踪的难题。

摘要： 本发明公开了一种基于极限学习机和蚁群系统的虚拟机整合方法。本发明的目的在于通过虚拟机整合技术减少大规模数据中心的能耗，迁移次数和服务级别协议违反次数。该方法首先使用极限学习机预测输入主机列表中的各个主机的状态，根据这些不同状态的主机确定虚拟机整合过程的源主机和目的主机。然后从源主机上获得要迁移的虚拟机，根据多种群蚁群系统算法将这些虚拟机迁移到合适的目的主机。各个种群得到各自的迁移方案后，将利用局部搜索策略进行优化，然后各个种群之间通过信息素交换规则进行信息素的更新。最后达到指定迭代次数后，输出最佳的虚拟机整合方案。

摘要： 本发明公开了一种基于多蚁群系统的多目标供应链配置方法，包括：将用于存放帕累托解的集合PS和存放帕累托前沿的集合PF置为空集合；对多目标供应链配置问题中的数据进行预处理，并初始化信息素τ0；设置集合newPS0和newPS1分别用于存放当前迭代中两个蚁群系统新生成的帕累托解，并把这两个集合置空；按照节点优先级顺序，针对每个解，贪心的计算启发式信息η并构造解xc,k，局部更新信息素τ，并更新集合PS和PF；检查解xc,k是否是帕累托解；针对每个蚁群，判断是否未构造完popsize个个体；判断两个蚁群是否已未构造完成；全局更新信息素τ；采用局部搜索策略改进PS中的解；判断程序终止条件是否满足。

摘要： 本发明提供了一种基于蚁群系统的多细胞多参数（位置、速度、轮廓等）的联合估计与精确跟踪系统，属于细胞跟踪领域。通过对每一幅灰度图像，定义相应的局部区域灰度方差来生成蚁群初始位置分布；在此基础上，构建两个平行工作且相互独立的信息素场，即位置场和轮廓场，分别在细胞位置估计模块和细胞轮廓估计模块构建有界蚁群决策系统；最终精确估计出细胞的位置、速度与轮廓等重要参数，从而实现对多细胞的精确跟踪。通过有界启发式蚁群系统相互合作，无需细胞检测模块、无需大量的细胞训练样本，解决了在低对比度细胞图像序列下多细胞动力学参数及多细胞轮廓联合估计与跟踪的难题。

摘要： 本发明公开了一种运用蚁群系统优化校园公交线路规划的方法，包括以下步骤：(1)初始化参数，对于不同的路网情况，确定信息素的初始值τ0；(2)初始化蚁群，在每一次循环开始时，每只蚂蚁都会随机赋予一个始发站点，始发站点集合O中选出，每只蚂蚁被随机赋予始发站点后，会根据路网的启发式信息和信息素信息开始构造调度解；(3)基于伪随机比例规则为每只蚂蚁选择下一个访问站点；(4)信息素局部更新；(5)蚂蚁完成单次路径构建，对每个调度解进行评价；(6)信息素全局更新；(7)迭代重复步骤(2)‑步骤(6)的过程，直至达到最大迭代次数；(8)输出公交路线规划集合。

摘要： 本发明公开了一种基于极限学习机和蚁群系统的虚拟机整合方法。本发明的目的在于通过虚拟机整合技术减少大规模数据中心的能耗，迁移次数和服务级别协议违反次数。该方法首先使用极限学习机预测输入主机列表中的各个主机的状态，根据这些不同状态的主机确定虚拟机整合过程的源主机和目的主机。然后从源主机上获得要迁移的虚拟机，根据多种群蚁群系统算法将这些虚拟机迁移到合适的目的主机。各个种群得到各自的迁移方案后，将利用局部搜索策略进行优化，然后各个种群之间通过信息素交换规则进行信息素的更新。最后达到指定迭代次数后，输出最佳的虚拟机整合方案。

摘要： 本发明公开了一种基于多蚁群系统的多目标供应链配置方法，包括：将用于存放帕累托解的集合PS和存放帕累托前沿的集合PF置为空集合；对多目标供应链配置问题中的数据进行预处理，并初始化信息素τ0；设置集合newPS0和newPS1分别用于存放当前迭代中两个蚁群系统新生成的帕累托解，并把这两个集合置空；按照节点优先级顺序，针对每个解，贪心的计算启发式信息η并构造解xc,k，局部更新信息素τ，并更新集合PS和PF；检查解xc,k是否是帕累托解；针对每个蚁群，判断是否未构造完popsize个个体；判断两个蚁群是否已未构造完成；全局更新信息素τ；采用局部搜索策略改进PS中的解；判断程序终止条件是否满足。

摘要： 本发明属于智能算法和生产管理领域，涉及基于多启发信息蚁群系统的柔性作业车间调度方法，包括：建立析取图模型；初始化；构造FJSP的解集；信息素更新；启发式信息档案更新；终止条件检查。本发明在蚁群系统中引入六种启发式信息，使算法在不同问题实例中均能取得理想性能，避免陷入局部最优，并且使用一种能够根据待解问题实例和当前搜索状态来自动选择启发式信息及其引导力控制参数的自适应策略，使整个蚁群的启发式信息设计向能产生优质解的当前最优设计收敛，提高收剑速度，提高算法优化效率，提高柔性作业车间调度效率。

摘要： 本文针对截止期限约束下的租赁费用问题，提出了基于混沌蚁群系统并结合任务概率向上权值的费用优化调度算法R‑CACS。在截止期限约束下，算法考虑关键任务对于科学工作流完成时间的影响，使用传统的概率向上权值对任务优先级进行排序，然后使用混沌蚁群系统对科学工作流中的任务以最小化租赁费用为目标进行虚拟机选择。本发明提出的方法可以有效降低租赁虚拟机而花费的总费用。

摘要： 本发明属于云雾计算领域，具体是一种在物联网场景下关联任务调度策略，目标在不破坏任务间优先约束关系的前提下，考虑了综合任务截止期限和任务处理的总能耗方面。主要分为两个步骤：A.基于松弛度的优先级算法得到优先级序列；B.基于蚁群系统的约束优化算法实现任务分配。本发明针对云雾计算领域提出的LBP‑ACS调度算法在解决具有混合截止期限的关联任务调度问题上，可以在提高任务调度成功率的同时，有效的降低能量消耗。