两种改进的最优路径规划算法

在对经典Dijkstra算法和A*算法分析的基础上对它们分别进行了改进.在经典Dijkstra算法中,针对当前不相连节点间路径长度为无穷大这一特点,首先对两个节点是否相连进行判断;若发现两个节点并不相连时,则舍去相应计算,从而减小计算量.针对A*算法在实际应用中搜索效率低的缺点,将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后,再按照经典A*算法搜索出相应的新最优路径,最后再将原始最优路径与这些新最优路径进行对比,以便确定最终的最优路径.仿真研究表明:改进的Dijkstra算法可以减少大量的无关节点计算,提高运算的效率;改进的A*算法则可以提高搜索到最优路径的成功率.     

基于免疫克隆算法的物流配送车辆路径优化研究

物流配送车辆路径优化问题是近年来物流领域中的研究热点,该问题属于NP难题,较难得到最优解和满意解．在物流配送车辆路径优化问题数学模型的基础上,构造了一种免疫克隆算法来求解该问题,并在算法中引入了克隆选择、克隆删除、受体编辑、体细胞高频变异、抗体循环补充等思想．仿真计算结果表明,免疫克隆算法能快速收敛于全局最优解,克服了遗传算法中易陷入局部最优解和收敛速度慢的缺点,可有效地解决物流配送车辆路径优化问题．     

基于双向 A￣* 算法的自主车全局路径规划

本文采用Ｑ－Ｍ法寻找素蕴涵（ｐｒｉｍｅｉｍｐｌｉｃａｎｔｓ）的思想构造连通图．在此基础上，提出了使用双向Ａ＊算法搜寻连通图中的最优节点路径，提出了超前尽可能多个节点的思想用于规划实际几何路径．仿真研究表明，本文方法计算简单，规划的路径可以达到或接近最优路径．     

有界变量约束优化的非单调最优路径内点算法

采用最优路径结合非单调内点回代算法解有界变量约束的非线性优化问题．从构建的最优路径解二次模型获得迭代方向，通过线搜索获得步长因子以保证迭代点既落在严格可行域内，又能使目标函数产生足够下降，基于导出的最优路径的良好性质，在合理的假设下，证明了此算法不仅具有整体收敛性，而且保持局部超线性收敛速率．引入非单调技术将克服病态问题，从而加速收敛性进程．数值计算表明了算法的可行性和有效性．     

基于混合遗传算法的车辆优化配置的数学模型

研究了物流运输系统车辆数优化问题的数学模型,构造出了模拟退火算法的能量函数,根据该函数可以求最优车辆数,又可以求最优车辆数下的最优行驶路径。用遗传模拟退火算法实现了车辆数的优化计算与路径优化计算。     

一种求解次优路径的算法

根据动态规则的原理，利用最优路径的中间轨迹结果，给出一种快速优选次优路径的算法，并将求解最优和次优路径的算法归纳完整．本算法已在IPM－PC机上编程调试通过．     

投影信赖域最优路径内点算法解有界变量的约束优化问题

基于最优路径(optimal path),提供一种投影信赖域内点算法解有界变量的线性等式约束优化．在合理的条件下,证明了所提供的算法不仅具有整体收敛性并且保持局部超线性收敛速率．数值计算结果表明了算法的有效性．     

仿射内点最优路径法解线性不等式约束的优化问题

提供了仿射内点回代技术的最优路径法解线性不等式约束的非线性优化问题，通过构造的最优路径得到搜索迭代方向，结合非单调内点回代线搜索技术获得可接受的步长因子，从而产生保证目标函数值非单调下降的严格内点可行迭代序列．基于最优路径的良好性质，证明了在合理的假设条件下，算法不仅具有整体收敛性而且保持超线性收敛速率．引入非单调技术能克服高度非线性的病态问题，加速收敛性进程，数值计算结果表明了算法的有效性．     

基于改进蚁群算法的配电网优化规划

提出了一种基于改进蚁群算法的配电网优化规划算法．对于给定的配电网模型，该算法根据各配电网站点建立初始信息素矩阵，然后利用蚁群算法所特有的路径寻优功能来搜索配电网布局路径，并结合改进信息素刷新的方式和在蚁群搜索过程中引入曼哈顿距离以及弹性伸缩调节因子，使蚁群以较快的速度找到当前布局上的最优路径．通过具体的算例表明，该算法比一般蚁群优化规划算法具有更高的计算效率和优秀的全局搜索能力，同时有效地克服了在求解配电网规划问题时蚁群在局部最优解上的巡回而存在的效率不高以及未成熟收敛等现象．     

基于图形的加权蚁群算法

针对蚁群算法在开始的时候由于信息素较少导致收敛速度慢的问题,提出了基于图形的加权蚁群算法,利用蚁群算法最优路径的特点,对每个城市分别加权,从比较离散的点开始进行寻优,节省了在不可能构成最优路径上的计算时间,提高了运算速度.通过TSP问题检验的结果表明,新算法提高了标准蚁群算法的效率和计算结果的质量.     

基于遗传算法优化多出口疏散路径问题

提出了一种基于遗传算法来优化疏散路径问题的方法．首先将疏散路径图转换为等价的距离完全图,将目标点、源点和中间点分离,随机选取中间点构造最小生成树,最终用遗传算法得到最优路径．通过数值实验,验证了算法的有效性,并与传统方法进行了比较．     

基于离散优化的无人驾驶汽车轨迹规划

针对双向两车道无人车行驶场景,基于离散优化的方法,提出一种新的轨迹解耦规划算法。该算法将带有时间戳的三维轨迹规划问题,解耦成分别对路径和速度规划,速度规划时引入ST图,用以描述无人车与障碍物之间的运动关系。通过分层采样的方法构建路径Lattice图搜索初始路径,以及基于多目标A*搜索算法在ST图中规划出初始速度剖面,减少算法的计算量。同时,结合优化的方法对轨迹进行优化,使轨迹收敛到全局最优解。最后,通过仿真实验,验证了该算法的有效性和可靠性。     

最大路径算法在原条量材优化中的应用及其优化

在分析求解最短路径问题与求解最大路径问题差异的基础上,给出了一种在有向图中采用动态规划策略求解最大路径的算法,将其应用到原条量材网络图中求解原条最优量材问题;并提出了采用量材三角形优化原条量材网络图的一种优化方法,降低了算法的复杂度.通过实验验证了算法与优化方法的正确性与可行性.     

基于免疫遗传算法的网格任务调度

研究了网格环境下任务调度问题,提出了一个任务调度机制:基于任务图将每一个可能的任务调度方案表示成一个任务-资源分配图,将网格任务调度问题转化为任务-资源分配图优化选取问题.提出了一种基于免疫遗传算法的、实现任务-资源分配图优化选取的任务调度算法.该算法将任务-资源分配图的最长路径作为抗原,每一个任务-资源分配图对应一个抗体.实验结果表明这个算法在全局优化能力及收敛速度上均有显著提高.     

共享波长转换器全光网的路由和波长分配算法

针对节点共享和链路共享波长转换器的节点交换结构,提出了全光网的分层图模型构造方法,将路由和波长分配两个子问题转化为在分层图中求解最短路问题。这类分层图具有特殊性,不能使用经典的最短路算法求解,因此提出了相应的最短路算法,计算机仿真说明该算法的阻塞性能比固定路由算法好,节点共享结构的阻塞性能比链路共享结构好。     

卫星网络中基于蚁群优化的概率路由算法

为了提高空间信息传输的有效性和可靠性,针对传统蚁群优化(ant colony optimization,ACO)容易造成最优路径负载过重而发生拥塞的问题,提出了一种基于蚁群优化的概率路由算法(ant colony optimization based proba-bilistic routing algorithm,ACO-PRA).根据卫星网络拓扑动态周期时变的固有特点,将拓扑周期均匀分为若干个时间片,形成基于不同时间片的卫星网络拓扑连通图;根据网络拓扑连通图,将星间链路带宽和链路容量引入到目标函数中,建立时延最小的优化模型;根据蚁群算法的节点概率函数选择下一跳节点,进而找到一条能同时满足时延带宽和链路容量要求的最佳信号传输路径.仿真结果表明,提出的基于蚁群优化的概率路由算法不仅能够降低平均端到端时延和丢包率,而且能够有效地提高网络吞吐量、平衡网络负载.     

基于带随机网络的多种群粒子群优化算法求解多资源受限柔性作业车间调度问题

多资源受限柔性作业车间调度问题(MRC-FJSP,multi-resource constrained flexible job shop scheduling problem)是一类复杂的组合优化问题。针对以最小化最大完工时间为目标的MRC-FJSP,提出了一种带随机网络的多种群粒子群优化算法(MPSO-RDnet, multi-population particle swarm optimization algorithm with random network)。首先,设计了一种半主动解码和基于启发式规则解码相结合的新型解码方式,对原有解空间进行有效裁剪。其次,提出了基于关键路径的两种邻域结构,提高算法局部搜索能力;引入了基于随机网络的多种群策略,提高算法全局搜索能力;提出了面向算法搜索停滞问题的重新初始化策略,增强算法的鲁棒性。最后,采用MRC-FJSP基准算例SFTSP进行测试,验证了算法的可行性和有效性。     

一种增量式多目标优化的智能交通路径诱导方法

路径诱导是一种主动引导车辆合理分流来解决城市交通拥堵的方法.本文提出了一种基于增量搜索的多目标优化路径诱导方法.该方法首先利用图论法将复杂路网抽象为点线的赋权图,引入多目标优化变量,建立路网模型;然后在启发式搜索基础上引入增量搜索,结合全局规划和局部动态重规划,实现车辆的实时路径诱导.仿真结果表明该方法能有效地解决复杂路网中车辆的实时路径诱导问题.     

基于改进分散搜索算法的无人机路径规划

针对在敌情信息不明环境中无人机侦查路径规划问题,建立了车辆路由问题模型(VRP),提出了基于分散搜索的改进混合搜索算法.基于Bayes方法计算出点到点之间的威胁概率,并生成了一个赋权图,将无人机路径规划问题转化为车辆路由寻优模型.采用混合路径规划算法求解.该算法将模拟退火嵌入到分散搜索算法的框架中,充分利用了分散搜索的全局搜索能力与模拟退火的局部搜索能力来优化无人机的侦查路径,混合算法在保证时效性的同时提升了求解的质量.仿真结果验证了算法的有效性.     

基于DSO算法的印刷电路板焊点测试路径优化

针对印刷电路板焊点测试中的测试时长、测试效率等路径优化问题,提出了一种用于电路板自动测试的基于DSO(don-key and smuggler optimization)算法的路径优化方法,通过电路板上焊点坐标信息,编写DSO的优化程序,与蚁群算法、遗传算法和模拟退火算法进行算法有效性的比较与分析,并将其对试际电路板焊点测试路径进行仿真验证.结果表明:该算法能够有效优化电路板上的焊点测试路径,缩短测试时间,为解决电路板自动测试中的路径优化问题,提供了有效理论依据和解决办法.