基于模拟并行蚁群算法的无线传感器网络异常节点自适应定位方法

由于无线传感器网络自身节点数量庞大,导致在异常节点自适应定位过程中,定位到的异常节点个数较少的问题.针对上述问题,提出基于模拟并行蚁群算法的无线传感器网络异常节点自适应定位方法.从网络中提取出异常节点的原始数据,并对异常节点数据属性进行详细的解析,根据解析后的数据属性,利用蚁群算法的优化搜索特性,结合并行计算的思想,建立并行蚁群算法模型,模拟蚂蚁在寻找食物过程中的协作和寻优行为,运行并行蚁群算法,获取异常节点的估计坐标值,实现节点的自适应定位.实验结果表明,该方法在面对复杂网络环境和多种异常类型时能够定位到多个异常节点,增强了定位方法的鲁棒性和自适应性.

基于多种类多种群并行蚁群算法的火力通道分配

针对舰艇编队超视距网络化反导体系构建问题,首先分析了反导体系构建流程,确定了反导作战的任务,分析了火力通道分配与网络化反导体系构建之间的关系。建立了基于综合火力杀伤效能的舰艇编队反导作战火力通道分配模型,并基于多种类多种群并行蚁群算法对所建立的模型进行了优化计算。仿真算例表明:构建的火力通道分配模型以及设计的优化计算方法能够保证舰艇编队成功遂行超视距网络化反导作战任务,有效地提高了舰艇编队反导作战效能。

基于蚁群算法的立式行星齿轮传动装置并行装配序列规划研究

装配体中零部件的增加导致装配流程与工艺趋向于复杂化,装配序列的规划需要更加严谨,计算机辅助装配序列规划成为虚拟装配的重要方向。以复杂立式人字齿行星齿轮传动装置为例,通过子装配体和聚族零固件的识别,采用装配连接无向关系图确定装配连接关系,将装配关联矩阵转化成数学信息,采用蚁群算法进行了装配路线规划。结果表明,立式行星齿轮传动装置的装配时间减少了约20%,人力资源节省1/3。

基于多级并行蚁群算法的智能医疗建筑综合布线系统设计

最小生成树算法(Minimum Spanning Tree,MST)是一种用于在加权连通图中找到最小生成树的算法。其目标是选择连接所有顶点并且边权重之和最小的边的子集。改进的A算法通过动态评估优先级来进行搜索。这种评估方式能够通过启发信息的引导。由于智能医疗建筑综合布线系统架构复杂,导致最小树算法、改进A*算法在安全方面较差,因此,提出基于多级并行蚁群算法的智能医疗建筑综合布线系统设计。在系统的硬件设计上,设计配线架,之后进入嵌入式处理器,最后到达随机存取存储器。在系统的软件设计上,构建医疗建筑综合布线路径的目标函数,根据目标函数,建立布线规划约束条件,完成基于多级并行蚁群算法的最优建筑预埋布线方案求解。对该系统进行性能测试,结果表明,该系统在耗时方面表现较为稳定,满足实际应用需求。

改进蚁群算法的送餐机器人路径规划

蚁群算法拥有良好的全局性、自组织性、鲁棒性,但传统蚁群算法存在许多不足之处。为此,针对算法在路径规划问题中的缺陷,在传统蚁群算法的状态转移公式中,引入目标点距离因素和引导素,加快算法收敛性和改善局部最优缺陷。在带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)上,融合蚁群算法和遗传算法,并将顾客时间窗宽度以及机器人等待时间加入蚁群算法状态转移公式中,以及将蚁群算法的解作为遗传算法的初始种群,提高遗传算法的初始解质量,然后进行编码,设置违反时间窗约束和载重量的惩罚函数和适应度函数,在传统遗传算法的交叉、变异操作后加入了破坏-修复基因的操作来优化每一代新解的质量,在Solomon Benchmark算例上进行仿真,对比算法改进前后的最优解,验证算法可行性。最后在餐厅送餐问题中把带有障碍物的仿真环境路径规划问题和VRPTW问题结合,使用改进后的算法解决餐厅环境下送餐机器人对顾客服务配送问题。

基于双种群蚁群算法的AGV路径规划研究

针对蚁群算法存在的收敛速度慢、易陷入局部最优和容易死锁等问题,提出了一种用于自动引导车(AGV,automated guided vehicle)路径规划的双种群蚁群算法;该算法引入差异化信息素初始值,修改启发函数并在信息素更新时对最优及最差路径进行奖惩;以改进策略为基础,引入自适应步长搜索策略,通过具有差异化步长的两个种群相互协作加强算法寻优能力和搜索效率;针对死锁问题,提出了将符合条件的单元格视为障碍物的“填充陷阱”策略;分别进行仿真实验和车间现场实验,结果表明,该算法可以为AGV规划出一条安全且综合性能较好的路径,为AGV路径规划提供了一种可行的方案。

改进并行蚁群算法在配电网网架优化中的应用

针对蚁群算法收敛速度慢、易陷入局部极小的不足,在并行蚁群算法的基础上,改进组间蚂蚁沟通交流方式,并提出一种自适应分组策略,在算法运行过程中,每过一定迭代次数,将蚂蚁的组数减半,每组蚂蚁的数量倍增,直至为一组蚂蚁。每次蚂蚁组数减半时,采用一种组间信息素融合规则更新留存组蚂蚁路径信息素。通过一个配电网网架优化问题的实例进行实验,仿真结果表明改进算法在收敛速度和寻优方面都有所提升。

多阶段输电网络最优规划的并行蚁群算法

多阶段输电网络最优规划是一个复杂的非线性组合优化问题,难以采用传统的数学优化方法求解。蚁群算法是近年来出现的用于解决组合优化问题的一种高效的内启发式搜索技术,但存在着未成熟收敛问题。文中给出了多阶段输电网络最优规划的数学模型及其解的向量形式;详细分析了传统蚁群算法的未成熟收敛现象及其原因;提出一种并行蚁群算法并用于求解多阶段输电网络最优规划问题。并行蚁群算法无需初始可行解,能很好地协调局部搜索与全局搜索,在加快计算速度的同时有效地避免了因参数设置、种群规模等不同而引起的未成熟收敛。对实际算例的计算结果表明,该方法具有很高的计算效率和良好的全局收敛性。

求解TSP问题的模式学习并行蚁群算法

针对大规模旅行商问题(TSP)会遇到计算时间过长以及计算效率降低的问题,将并行计算和模式学习引入蚁群算法,通过各个节点机提取模式,在各节点间筛选和交流优良模式,以改变计算粒度,达到缩短计算时间、提高计算效率的目的.实验结果表明该算法取得了较好的效果.

基于两阶段蚁群算法的带非等效并行机的作业车间调度

针对带非等效并行机的作业车间生产调度问题,以制造系统的生产成本、准时交货率等为目标,构建生产调度多目标模型。利用蚁群算法在求解复杂优化问题方面的优越性,建立调度问题与蚁群并行搜索的映射关系,将调度过程分成任务分派和任务排序两个阶段,每个阶段分别设计蚁群优化算法,并将两阶段寻优蚂蚁有机结合,构建一种具有继承关系的两阶段蚁群并行搜索算法,可以大大提高获得较优解的概率,并且压缩求解空间,快速获得较优解。通过均匀试验和统计分析确定算法的关键参数组合,将两阶段蚁群算法应用不同规模的8组算例。结果表明,无论是优化结果还是计算效率,两阶蚁群算法均优于改进的遗传算法。将所提出两阶段蚁群算法应用于实际车间的生产调度,减少了生产过程中工序间等待时间和缩短了产品交付周期。

求解平衡约束圆形Packing问题的快速启发式并行蚁群算法

带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.

基于蚁群算法的并行测试任务调度

并行测试的任务优化调度是并行测试技术的核心问题。提出了一种用于解决并行测试任务调度问题的改进蚁群算法,通过该算法可以获得测试时间最短的任务调度序列。给出了并行测试任务调度问题的数学模型,设计了启发式函数和状态转移概率的计算公式。采用动态标注方法在搜索过程中加大可行解间的信息素差别,避免算法早熟。给出了应用实例,实际应用表明该算法是有效的,能很好地解决此类多维动态组合优化问题。

并行蚁群算法及其在区位选址中的应用

提出基于多叉树并行蚁群算法的区位选址优化方法。算法依据蚁群算法具有的并行特性,采用GPU(graphicprocessing unit,图形处理器)并行运算技术,对地理空间进行多叉树划分,收集蚂蚁在多叉树层间旅行时逐步留下的信息素信息,进行路径选优获得理想的候选解,从而为解决平面空间资源优化配置问题提供新的思路。实验结果表明,与普通蚁群算法相比,采用基于多叉树搜索的并行蚁群算法,能够发挥蚁群算法的并行特征,在短时间内求得较为理想的解,适合计算大区域的空间资源配置问题。

一种改进的粗粒度并行蚁群算法

蚁群算法是一种模拟进化算法,具有很强的全局搜索能力。提出了一种基于粗粒度模型的并行蚁群算法,该算法采用了一个新的信息素更新策略———Ant-proportion,这种新的更新策略是综合考虑全局和局部信息,依据蚂蚁在搜索过程中所得到的路径的优劣程度和路径中各路段对其贡献的大小来分配信息素增量;另一方面,该算法采用的粗粒度模型充分利用了蚁群算法内在的并行性,使得算法具有更快的收敛速度和更好的优化质量。最后,选用了CHN144问题对该算法进行了检验,算法求得的最优路径优于已知的最优结果。

基于异类蚁群的双种群蚁群算法

提出一种基于异类蚁群的双种群蚁群(Dual Population Ant Colony Algorithm Basedon Heterogeneous Ant Colonies,DPACBH)算法,算法将两种信息素更新机制不同的蚁群分别独立进行进化求解,并定期交换优良解和信息来改善解的多样性,增强跳出局部最优的能力,使算法更容易收敛到全局最优解。以TSP(Travel Salesman Problem)问题为例所进行的计算表明,该算法比基本双种群蚁群算法具有更好的收敛速度和准确性。

基于并行蚁群算法的常规导弹作战任务分配

作战任务分配是常规导弹作战研究的关键问题之一。结合常规导弹作战实际情况和任务分配特点,综合考虑作战意图、任务协同等约束条件,采用并行蚁群算法,建立了作战任务分配模型。在多子群蚁群算法的基础上,设计了基于任务能力评估的子群协调沟通策略和基于任务代价的状态转移规则,提出了并行求解任务分配问题的蚁群算法思想。通过仿真验证了模型的正确性,仿真结果表明该方法能够有效解决常规导弹作战任务分配问题。

基于模式记忆并行蚁群算法的输电网规划

该文讨论了目前大规模输电网规划求解中常见的无法完成对解空间的充分搜索,从而难于求得全局最优解的问题;给出了泛函形式的输电网规划模型,并重点分析了输电网规划解的模式。在分析了传统蚁群算法易产生未成熟收敛现象及其原因的基础上,设计了一种基于模式记忆的并行蚁群算法,该算法通过模式记忆实现了解空间分解,能够有效地识别、记忆和跳出局部最优解;通过局部细化搜索进一步加强了局部搜索能力;通过并行计算提高了计算速度。某实际77 节点的算例分析表明了该算法具有很高的计算效率和优秀的局部、全局收敛性,有效克服了现代启发式算法在求解输电网规划问题时存在的效率不高及未成熟收敛等现象。

基于Hama并行蚁群算法模型及TSP应用研究

Hama是建立在Hadoop上的分布式并行计算模型,基于BSP(Bulk Synchronous Parallel,BSP)计算技术的开放式并行计算平台,它的主要功能是支持并行及大数据的科学计算.目前改进传统启发式算法,移植到Hama平台提高算法效率是研究热点之一.蚁群算法是适应性极强的启发式算法,应用广泛,但由于蚁群中个体的随机性,解的收敛速度与解的多样性、稳定性之间存在矛盾.而该矛盾可通过将蚁群算法并行化得到缓解,算法求解性能因此得到提升.本文在Hama平台上,选择以信息素矩阵进行交互的策略,建立了并行蚁群算法模型,并通过该模型求解多种规模下的旅行商问题.实验表明,本文提出的并行蚁群算法模型可行,并能有效地提高算法性能.

基于相似度的自适应异类多种群蚁群算法

针对原有的多种群蚁群算法收敛速度慢,运行时间长,容易早熟等缺陷,提出了一种新型异类多种群蚁群算法。算法由多类不同特性蚁群构成,不同蚁群具有不同特质,且优势互补,彼此间具有潜在的合作性。不同种类蚁群搜索时,通过子蚁群间的相似度,自适应选择最互补的蚁群进行信息交换,以加强不同种类蚁群间的协作,增强解的多样性,增强跳出局部最优的能力。TSP仿真结果表明,该算法在搜索速度以及搜索质量方面都有明显的提高。

基于OPENMP求解旅行商问题的并行蚁群算法

蚁群算法具有自组织性、正反馈性、较强的鲁棒性和天生的并行性等优点,不足之处是需要较长的搜索时间.为了解决其搜索时间过长的问题,文中提出了一种并行实现策略,用OPENMP应用编程接口采用C++语言编程实现,能明显减少搜索所用的时间.给出了一种解决旅行商问题(TSP)的并行蚁群算法,并通过串并算法执行时间的比较,说明并行算法的优越性.