基于融合任务规则优先级蚁群算法的多AGV路径规划实现研究

蚁群算法所具备的合作搜索能力被广泛用于寻找单台AGV最短路径,却不适用解决现实情况中多台AGV同时使用的问题,为此提出了融合任务规则优先级的蚁群算法实现多AGV路径规划,用于解决现实问题中多台AGV同时使用而且存在多种碰撞冲突的情形。通过将AGV运行的路径环境进行建模等针对性措施,把蚁群算法引入到AGV路径规划的现实问题中,然后考虑多AGV路径规划可能存在的不同碰撞冲突类型,并考虑不同AGV拥有不同的任务优先级的现实情况,提出了避免AGV碰撞的策略,形成了基于融合任务规则优先级蚁群算法的多AGV路径规划算法。通过仿真实验结果,证实所提出的算法可以避免多台AGV之间的路径冲突,同时利用了蚁群算法寻求最优路径的能力,改进后的蚁群算法能够用于多AGV路径规划的实际场景中。

最早截止期优先算法在CAN FD网络中的改进

针对应用于CAN FD网络中的调度算法,平均分区编码方式的最早截止期算法对报文进行非抢占调度时,其对大范围的截止期编码能力有限,报文易出现较大概率优先级反转以及总线负载较高等问题。通过分析造成报文传递延迟的各种原因并结合之前相关分区调度算法的不足,文中提出了基于指数–幂函数分区的最早截止期优先算法对报文进行调度的改进方式,即在对报文的截止期进行指数分区的基础上,进一步采用幂函数分区细分。文中对该算法的可调度性进行了分析,并使用CANoe进行了仿真验证。实验表明,与现有的平均分区调度算法相比,改进后的算法扩大了截止期的表示范围,降低了总线负载,优化了优先级反转问题,达到了更好的调度效果。

最早截止期优先调度算法的改进

在基于IEEE802.16d协议的服务流调度过程中,为了保证优先级较高的任务优先得到服务,并尽量将调度过程对系统资源的消耗控制在可承受的范围内,在分析已有的非抢占式及抢占式两种方案的最早截止期优先(EDF)算法优缺点的基础上,重点考虑时间特性、重要性特性、顺序参考三方面作为调节参数,同时兼顾传输距离,对已有的EDF算法进行改进。提出了基于重要性因素抢占的半抢占式EDF算法。通过仿真实验,把改进后的EDF算法应用到IEEE802.16d协议的实时轮询业务(RTPS)服务流调度中。结果表明,改进后的EDF算法较好地平衡了抢占及非抢占式EDF算法的优缺点,具备较前两者更小且更稳定的延时。

基于最早截止期优先算法的过渡过程研究

在以最早截止期优先算法调度的实时系统中,如果出现新任务插入和/或现行任务加速要求,而系统所剩带宽又不足时,必须进行带宽转让,系统运行模式将被迫发生改变。针对该问题,研究新任务插入和/或现行任务加速的动态过程,分析带宽转让对系统可调度性的影响。应用处理器需求准则,证明截止期丢失只可能出现在某一时间点之前。通过该结论可以合理定义过渡过程的长度,从而展示一个清晰的三阶段模型。最后给出相关仿真实例。

蚁群融合动态窗口法的分布式多机器人运动规划研究

为更好地协调分布式多移动机器人在动态环境下的运动,将蚁群算法与动态窗口法相融合构造多机器人系统,并利用优先级策略来化解运动冲突。为提升多机器人全局路径的综合最优性能,提出了多指标寻优的启发式函数和信息素更新策略来提升蚁群的寻优能力,通过冗余点删除策略进一步提升路径质量;融合蚁群与动态窗口法构造机器人运动学模型,通过自适应导航策略来提升未知环境下机器人的局部运动能力;将单机器人避障策略和多移动机器人优先级策略相结合,将多机器人路径规划简化为单个移动机器人的动态路径规划问题。仿真实验结果表明,所提方法能够实现多移动机器人系统在未知环境中的协同避障,具有较高的安全性。

面向多目标测试用例优先排序的蚁群算法信息素更新策略

针对蚁群算法在求解多目标测试用例优先排序(MOTCP)时收敛速度缓慢、易陷入局部最优的问题,提出一种基于上位基因段(ETS)的信息素更新策略。利用测试用例序列中ETS可以决定适应度值的变化,选取ETS作为信息素更新范围,再根据ETS中测试用例间的适应度增量和测试用例的执行时间更新路径上的信息素值。为进一步提升蚁群算法求解效率、节省蚂蚁依次访问测试用例序列的时间,优化的蚁群算法还通过估算ETS长度重新设置蚂蚁遍历测试用例的搜索终点。实验结果表明,与优化前的蚁群算法及NSGA-Ⅱ相比,优化后的蚁群算法能提升求解MOTCP问题时的收敛速度,获得更优的Pareto解集。

基于蚁群算法的测试用例优先排序

测试用例优先排序技术通过优化测试用例的执行次序来提高软件测试的效率,是增强型软件测试和回归测试的重要研究课题。针对基于需求的测试用例优先排序问题,提出了一种基于蚁群算法的求解方法,采用不同的测试用例间距离及用例序列评价策略,给出了该方法的2种不同实现方式。首先,针对黑盒测试特点,设计了基于需求的一般性测试用例序列评价指标;其次,提出测试用例吸引度概念,基于测试用例吸引度定义了测试用例间的距离;然后,给出了信息素更新策略、最优解集更新策略、局部最优解突变策略等主要设计策略,分别实现了该方法基于距离和基于指标的2种实现方式。实验结果表明,该方法具有很好的全局寻优能力,整体效果上优于粒子群算法、遗传算法和随机测试。

基于广度优先搜索-改进蚁群算法的配电网故障恢复

自然灾害导致配电网故障恢复具有很高的复杂性,传统配电网故障恢复算法难以兼顾重要用户快速恢复和全局恢复最优。本文在考虑分布式电源和重要用户的前提下,将配电网故障恢复分为优先恢复重要用户的骨干通道恢复阶段和剩余负荷恢复阶段,针对每一阶段的恢复目标,利用广度优先搜索算法快速恢复骨干通道、改进的蚁群算法恢复剩余负荷。考虑加入分布式电源和故障恢复后可能导致节点电压越限的情况,采用适当调节变压器分接头的方法调节节点电压。最后将所提出的方法用C^#语言编程实现,并通过两个算例进行了验证。

基于动态优先权蚁群算法的分布式自动化测试调度

针对分布式自动化测试平台中的测试任务调度模块进行了研究分析,采用了基于动态优先权的蚁群算法。该算法主要将动态优先权应用于蚁群算法中的选择搜索最优解的策略中,通过对测试任务优先权的执行情况和任务等待时间增加的改变,优先权高的任务先执行,从而减少蚁群算法的搜索时间,提高搜索能力。通过在Gridsim中的模拟仿真,实验结果表明,此算法可以提高系统的调度性能和测试资源的利用率,提高了系统自动化测试效率。

基于DFS与蚁群算法的电弧增材复合路径规划算法优化

为提高电弧增材制造的成形效率,分析了目前路径规划算法的优缺点,提出了基于深度优先搜索(DFS)算法与蚁群算法相结合的复合路径规划优化方法。在zigzag扫描与轮廓偏置相结合的复合路径规划算法的基础上,采用多种不同扫描倾角的zigzag路径算法对多孔洞截面轮廓进行填充,并通过深度优先搜索算法进行zigzag扫描路径分区进行连接,以减少zigzag扫描路径的路径条数和起弧熄弧次数,然后采用蚁群算法搜索路径规划顺序和起弧熄弧点的优化组合,使填充路径的总空行程长度最小。仿真结果表明,DFS分区连接算法对不同扫描倾角的zigzag路径规划皆能起到良好连接作用,采用蚁群算法的电弧增材制造路径规划方法可以有效减少扫描空行程长度。

基于蚁群算法的模具制造动态调度研究

为解决模具制造动态调度问题,建立了动态调度系统。该系统利用蚁群算法和优先分配启发式算法相结合的调度算法,解决具有工件约束的模具零件的调度问题。该算法首先由蚁群算法确定模具零件各工序所用加工机床,然后利用优先分配启发式算法确定在同一台机床上加工的各零件的先后顺序。考虑动态调度的实时性,提出了局部更新和全局更新相结合的、基于滑动窗口机制的动态调度方法。对于发生频率高但对调度计划执行影响不大的扰动事件采用局部更新策略,反之则采用全局更新策略,在保证获得近优解的同时提高了动态调度的效率。

解决作业车间调度问题的改进蚁群优化算法

针对作业车间调度问题,提出一种改进的蚁群优化算法.首先设计禁忌表以产生活动调度,然后对传统的蚁群优化算法进行简化,并提出一种新型优先规则作为启发式信息.为增强算法的收敛性和提高求解质量,引入基于作业车间调度问题邻域结构的局部搜索.实验表明该文算法有效.

多约束下多车场车辆路径问题的蚁群算法研究

为节约物流配送费用,提出一类多约束条件下的多车场车辆路径问题。首先建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题的数学模型;然后提出了一种自适应的最大-最小蚁群算法,算法结合自适应方法和最大-最小蚁群算法的优点,能适时地控制蚁群算法中的信息素更新过程,扩大搜索范围,避免基本蚁群算法易陷于早熟和"局部最优"以及求解速度慢的不足;最后通过一个实例与禁忌搜索算法进行了对比。实验结果表明:自适应的最大-最小蚁群算法在车辆数、路径长度、路径时间和计算速度方面具有优势。

发电机组组合的混合蚁群优化算法

电力系统中的机组组合作为一个非确定型多项式困难问题,一直难以获得其理论最优解。针对算法的精度和速度这一矛盾,提出了一种结合启发式算法和蚁群算法的混合优化算法。用优先级排序法获得次优解,并在附近形成一个搜索邻域;采用蚁群算法在此邻域内寻优,减小了蚁群算法的空间复杂度。同时,在蚁群算法中引入了人工鱼群算法的拥挤度概念。拥挤度阈值在迭代过程中是自适应变化的,从而增强了算法的遍历寻优能力,也保持了较快的收敛速度。经济负荷分配采用简化梯度法。对一个10机系统算例仿真计算,验证了所提算法对解决机组组合问题具有很强的搜索能力和快速收剑性。

基于蚁群优化算法的目标拆卸序列规划

为了能够以较高的效率求解出产品中目标零件的拆卸方案,基于产品中零件间的拆卸优先约束关系,提出并建立目标零件的拆卸层次信息图模型,将目标零件的拆卸序列规划问题转化为对该图模型中具备最优值的路径的搜索和寻优问题.同时,提出一种改进蚁群优化算法,以实现对目标零件拆卸层次信息图的构建和对拆卸方案的搜索与寻优.最后通过实例验证了该方法的可行性和计算效率.

基于蚁群算法的树环结构应用层组播树构建算法

作为对IP组播技术的改进,应用层组播(ALM)技术具有不受网络架构限制、资源丰富、数据传输速率高等优势。综合考虑节点性能和端到端延迟,提出一种快速且高效的建立应用层组播树的方法:基于蚁群算法的树环结构ALM模型(ACOTRM)。目前对ALM结构的研究大部分都是仅仅粗略地给出拓扑结构,而对整个构建过程却缺乏完整且清晰的描述。鉴于此,完整地给出了一种树环结构ALM树的具体构建过程,主要包括网络节点分簇、簇内成环连接、数据转发数的建立等关键步骤。另外,为每个节点设定特有的优先级,使得整个ALM树达到最优化状态。仿真结果表明,该模型得到了较低的平均时延以及较高的平均数据传输率,在增加系统稳定性的同时也提高了其转发效率。

基于遗传-蚁群融合算法的OSPF路由算法QoS扩展

OSPF路由协议是现代计算机网络应用最为广泛的路由协议之一,为了适应现代网络应用对路由选择的QoS要求,IETF对其进行了扩展,最短路径算法也采用BF算法。但是,这些算法只能计算满足某一条件的路径集合中最短路径,不能满足对带宽、时延和差错率等多项QoS参数都有要求的最优路由选择。采用遗传算法和蚁群算法相结合的融合算法,继承了遗传算法和蚁群算法的优点,在求精解效率上优于遗传算法,在时间效率上优于蚁群算法,能很好地实现多QoS要求的最优路径计算。测试证明融合算法优化性能和时间性能都取得了很好的效果,可以应用于OSPF协议。

基于细菌觅食和蚁群算法的工艺路线优化

针对工艺路线规划中满足多重约束的最优方案选择问题,提出一种细菌觅食和蚁群优化(bacteria foraging ant colony optimization,BFACO)算法。首先,将工艺路线规划转化为对加工元顺序的优化问题,构造满足多种工艺准则的加工元拓扑优先顺序图,并构建了在缩短加工周期、提高加工质量和降低加工成本目标下的最低加工资源更换成本的目标函数;其次,设计加工元序列与加工资源两个搜索阶段的蚁群搜索,拓扑优先顺序图可弥补加工元序列搜索阶段信息素匮乏的缺点,而在加工资源搜索阶段引入细菌觅食优化算法的复制与趋向操作,可使加工元在多个可选加工资源的情况下获得加工资源更换成本最低的加工序列;最后,基于细菌觅食与蚁群算法的融合优化,完成多个加工元序列的信息素积累并输出最优解,解决蚁群算法局部收敛且计算速度慢的问题。将BFACO算法应用于实例并与其他优化算法的优化结果进行对比,结果显示BFACO算法在工艺路线优化方面较其他优化算法具有较高的计算效率,验证了BFACO算法的可行性与有效性。研究表明,BFACO算法可有效应用于同时考虑工艺约束与加工资源更换成本的工艺规划,为实际生产提供高效且灵活的工艺路线的优化选择。

基于蚁群算法WDM网络故障恢复路由研究

蚁群故障恢复算法是一种新颖的模拟进化算法。该算法基于群以正反馈作为首要的搜索机制,为复杂的组合优化问题提供了一种新方法。本文在传统蚁群算法的选择策略,本地搜索,以及信息更新三方面做出改进。改进后的算法用于解决波分复用光网络中不同故障条件下的优化恢复路由问题。通过对一个典型网络CHINANET的数值仿真,证明了蚁群故障恢复算法在WDM网络中故障恢复路由的可行性。

基于蚁群算法的P2P网络资源发现服务研究

针对P2P网络的动态性、分布性等特点，提出了一种非集中式的网络资源管理模式，并在此基础上引入了蚁群算法（Ant Colony Optimizadon，ACO）。它通过对信息素的更新，为智能选择下一搜索节点提供依据。通过实验证明，此种方法同BFS算法相比，在很相近的资源发见成功率的前提下，资源开销明显减少，整个系统具有较好的性能。