基于双重启发式动态规划算法的列车运行调整研究

通过对列车行车组织特点及运行调整策略的研究,采用自适应动态规划体系中的双重启发式动态规划算法,建立了列车运行调整模型。双重启发式动态规划算法适合处理具有实时性、约束性、非线性、随机性等特点的列车运行调整复杂动态系统的优化控制问题,通过仿真验证,该算法求解速度快、精度高,对列车晚点的调整起到了良好的控制作用。为列车运行调整的深入研究提供了一定的参考价值。

基于多目标混合启发式算法的协同无冲突4D航迹规划

为促进基于航迹运行的框架下未来空中交通管理系统的协同决策,本文提出了一种协同无冲突4D航迹规划方法。首先以提高航班效率和航空公司间的公平性为目标,以无冲突为约束构建了一个多目标整数线性优化模型。其次,提出了一种基于基尼系数的指标以量化航空公司间的成本分配公平性。为了提高问题求解效率,采用了基于网格的探测方法以加速冲突检测,并设计了一种多目标混合启发式算法(Multi-objective hybrid-meta-heuristic optimization algorithm,MHMOA),通过结合模拟退火(Simulated annealing,SA)和爬山局部搜索算法来近似最优的非支配解。最后,利用实际航班计划和航路网络数据比较和分析了MHMOA、SA和两种常规多目标优化算法的优化结果。结果表明,MHMOA所获得的非支配解的质量更高、延误更低且航空公司间公平性更优,在3个多目标优化性能指标方面表现优异,可为空中交通管理员提供更详细的决策支持。

A^(*)蚁群融合的复合启发式路径规划算法

为提高无人机执行巡飞探查任务的效率,规划出一条最优的飞行路径,针对传统蚁群算法应用于路径规划时存在搜索效率低、迭代次数多、路径拐点多的问题,提出一种A^(*)蚁群融合的复合启发式路径规划算法。利用A^(*)算法预搜索差异化初始信息素,减少蚁群算法前期搜索盲目性,提高搜索效率。构造一种复合启发函数,引入A^(*)算法启发思想改进蚁群原本的启发式信息,设计路径平滑启发函数减少路径拐点。改进信息素更新规则,引入路径综合评分指标,使得每次迭代保留综合性能评分最优的路径。仿真实验表明,改进算法提高了搜索效率,一定程度上解决了拐点过多的问题,综合性能指标优于基本算法与对比文献算法,具有一定工程实践与理论研究意义。

基于多层次启发式动态规划算法的电力系统动态等值

针对电力系统运行工况变化后动态等值系统响应精度不够的问题,提出一种基于多层次启发式动态规划(Global representation heuristic dynamic programming,Gr HDP)算法的动态等值方法。该方法在基于同调等值得到的模型的基础上,在等值边界上加入基于Gr HDP算法的动态补偿环节,实时补偿同调等值系统与原系统间动态特性的差额,从而实现精确跟踪原系统的动态特性。以10机39节点系统为例进行仿真研究,结果表明:在不同运行工况、故障方式和故障地点下,基于所提算法的动态等值系统相比传统的同调等值能更精确地跟踪原系统的动态特性。

对地观测卫星任务规划的启发式动态调整算法

针对对地观测卫星任务规划,分析了单个资源失效与多个高优先级任务动态插入情况下已有任务规划方案的动态调整问题。以最大化规划方案任务权值总和为优化目标,提出了基于任务替换的启发式动态调整算法,包括选择替换任务的五种启发式策略:最大灵活度、最小冲突集、最小争议部分、区间剪枝以及任务剪枝策略。分析了影响动态调整算法运行效率的两个关键因素:冲突任务集与动态搜索深度。采用任务重规划率、规划权值变化率与算法运行时间三项指标考察算法效果,通过仿真实验验证了算法的可行性和有效性。

求解基于专用道设置的动态交通规划问题的启发式算法

基于专用道设置的策略,该文提出了一个新的动态交通规划问题。大型运动会要求主办方在规定时间内将指定人员从运动员村运送到指定地点。该问题便是源自2010年广州亚运会的交通需求。其要求在保证30分钟内将运动员从运动员村运送到指定场馆的条件下,最小化设置专用通道的总成本。由于该问题的规模较大,本文提出了三种启发式算法用以求解已提出的线性整数规划模型。计算结果表明,通过该文提出的启发式算法得到的解与相对应的采用数学规划软件Lingo8.0得到的解之间的平均误差均小于1.89%。同时,启发式算法的计算时间远小于Lingo8.0所需的计算时间。

移动机器人自主寻路避障启发式动态规划算法

用启发式动态规划算法解决移动机器人自主寻路、避障问题。提出了传感器检测环境状态的方法,以及对传感器检测信息进行归一化处理的方案。对输入、输出量以及学习系统的强化信号进行定义,设计了机器人自主学习寻路、避障的控制策略。定义了连续型强化信号,使机器人通过学习,对优先寻路还是优先避障做出决策判断。为验证启发式动态规划算法在移动机器人寻路、避障问题上的学习能力,设计了3种不同的寻路、避障仿真实验:同目标、不同起始点,同起始点、不同目标,和移动目标仿真实验。仿真结果表明,对于不同的寻路、避障要求,基于启发式动态规划算法的移动机器人具有良好的学习及适应能力。

基于极大代数的阻塞流水车间启发式动态规划调度算法

基于极大代数理论,引入任务排序函数与时间D子集,建立阻塞流水车间排序与调度代数模型,并提出启发式动态规划调度算法,实例计算表明算法十分有效.

融合改进A^(*)算法与动态窗口法的煤矿足式机器人路径规划

为提高煤矿足式机器人路径规划算法的运行效率、搜索精度及避障灵活性,提出了一种融合改进A^(*)算法与动态窗口法(DWA)的煤矿足式机器人路径规划方法。首先对A^(*)算法进行改进,通过去冗余节点策略减短规划路径的长度,通过改进邻域搜索方式和代价函数提高路径规划速度,采用分段二阶贝塞尔曲线进行路径平滑。将改进A^(*)算法规划出的路径节点依次作为局部路径规划DWA的局部目标点进行算法融合,筛选邻近的障碍物节点,从而再次缩短路径长度,并通过调整DWA代价函数中的权值比例提升避障性能。针对机器人遇到无法避开的障碍物而陷入“假死”状态的问题,以当前初始点为起点,重新调用融合算法,即重新进行全局路径规划,将得到的新节点代替原有的局部目标点,按照新路径进行后续工作。仿真结果表明:在保证机器人行走安全稳定的基础上,改进A^(*)算法较传统A^(*)算法的计算时间缩短了65%,路径长度缩短了24.1%,路径节点数量减少了27.65%,最终得出的路径更为平滑;融合算法进一步提升了全局路径规划能力,在多障碍物环境下能够绕开新增的动态和静态障碍物;机器人遇到“L”型障碍物进入“假死”状态时,在“假死”位置重新进行全局路径规划,更新行走路径,成功到达了最终目标点。基于融合算法的JetHexa六足机器人路径规划实验结果验证了融合算法的有效性和优越性。

基于多次采样启发式策略的改进RRT路径规划算法

在路径规划领域,快速探索随机树(RRT)算法是机械臂解决复杂环境中的路径规划问题的重要工具,然而其纯随机的采样环节导致大量的无效或低效尝试,浪费了计算资源;为解决此问题,提出一种基于多次采样启发式策略的改进RRT算法(MH-RRT);利用启发式函数评估多个采样点的代价值,选择代价值最低的采样点,引导路径树更快地向目标点生长;将启发式函数策略类似地有效改进了RRT*算法和双向RRT*算法;深入探讨不同参数对改进算法性能的影响,并确定最优参数组合;实验结果表明,改进算法在路径搜索时间、路径长度以及采样点数量等方面均能取得显著提升,提高了路径规划的有效性。

基于启发式遗传算法的通信光缆网络线路规划布局方法

由于通信光缆网络线路规划受到多种限制条件的制约,导致最优解比例低。针对上述问题,提出基于启发式遗传算法的通信光缆网络线路规划布局方法。通过建立数学模型明确目标和约束条件,利用启发式遗传算法进行线路初始化,并通过选择、交叉、变异等方法持续优化群体,直至满足终止条件。实验结果表明:这种方法通过明确约束条件,获取高比例最优解,为通信光缆网络线路规划布局提供了更优方案。

低轨预警系统动态任务规划启发式算法

该文针对低轨预警系统任务动态规划需求,从预警传感器资源和导弹跟踪任务角度对低轨预警系统动态任务规划问题进行了形式化描述,建立了系统动态任务规划的动态约束满足问题模型。该模型包括两级优化目标——跟踪精度、资源利用率、传感器切换率、松弛度综合优化指标和方案调整幅度(调整率)指标;提出了求解动态规划问题的变邻域启发式搜索算法,设计了算法的直接插入、重新分配、替换和删除邻域结构及算子。通过仿真实验验证了基于梯度优化目标的动态规划模型的合理性,并说明启发式算法能有效求解低轨预警系统动态任务规划问题。

一种物流配送机器人路径搜索启发式算法研究

针对带有时间窗和配送机器人的车辆路径问题,提出了一种自适应大邻域搜索启发式算法(ALNS)。首先研究了带时间窗口的车辆路径问题,分析了在调度-等待-检索系统中,时间窗约束引起的同步问题以及两种不同的配送资源在时间问题上的关系,在此基础上提出了改进的自适应大邻域搜索(ALNS)启发式算法。该算法通过破坏和修复部分现有解,在每次迭代时改变大部分解,通过创建初始解决方案,并在自适应机制的基础上获得最优解决方案。通过实验证明了该算法在解决带有时间窗和配送机器人的车辆路径问题上的性能和有效性,最后对配送机器人的应用情况进行了敏感性分析。

基于元启发式优化的机器人智能体无碰撞轨迹规划

针对机器人智能体在复杂三维环境中的安全运动,提出一种基于元启发式优化的无碰撞轨迹规划方案。轨迹点采用五次样条插值,以确保运动轨迹足够平滑,且起始点和目标点的速度与加速度均为零。以轨迹长度最短为优化目标,将轨迹与障碍物的最近距离限制在约束条件中,从而表述为一个优化问题,并采用基于元启发式的灰狼算法进行求解。随后,在复杂的三维地形中对该方案开展2个模拟仿真。结果表明:该方案能够有效地在规划空间内求解出预定数目的最优轨迹插值点,通过五次样条插值形成的轨迹长度达到最短,且不与障碍物发生任何碰撞。

考虑工序相关性的动态Job shop调度问题启发式算法

提出一类考虑工序相关性的、工件批量到达的动态Job shop调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop调度问题的优越性能。

利用增量二次规划和启发式方法的电力系统动态无功优化

针对电力系统动态无功优化数学模型存在优化过程长、收敛稳定性差的问题,导出了以控制变量增量为求解变量的电力系统动态无功优化的二次规划模型,并以具有有限次迭代收敛的Lemke算法求解,这样的动态无功优化控制计算量小,非常适合于对计算速度和算法稳定性要求高的动态无功优化控制问题.针对控制变量控制次数约束,采用启发式归并方法对其进行约束限制,有效避免了将控制变量动作次数约束纳入优化过程的复杂性.实际算例表明,文中方法不仅运算速度快,且收敛稳定性好.

基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术 ,提出一种用于解决有限资源、不同重要性要求的任务路径规划问题的有效算法 ,通过对不同重要程度的任务进行分层调度 ,得到较为满意的决策结果。该算法具有搜索空间小、求解速度快的优点。

基于启发式算法和Bender’s分解的无功优化规划

针对城市高中压配电网的长期无功优化规划问题，提出了基于启发式算法和Bender’s分解技术的两段式求解方法。该方法将启发式算法、Bender’s分解和线性规划等技术相结合，充分保证了系统的可求解性和解的合理性，将其应用于实际电力系统规划中取得了良好的效果。

大规模风电接入下输电网扩展规划的启发式优化算法

提出了大规模风电接入下的输电网有功和无功扩展规划的解决方法。计及了风电与负荷的全年时序数据,并将网络设备投资的年值成本与方案在全年所有不满足安全约束场景下采取控制措施的成本之和最小作为规划目标。为了降低求解计算的复杂性,将原问题分解为网络设备投资决策与方案的控制措施成本评估2个子问题,二者借助原问题的规划目标进行总体协调。在此基础上,通过分析规划目标与问题本身的特性,设计了启发式的优化算法,明显地提高了计算速度。算例分析验证了所提方法的正确性和求解算法的有效性。

开放式频谱系统中启发式动态频谱分配算法

在回顾了现有的开放式频谱系统中的动态频谱分配算法后,基于快速收敛和公平性两方面的性能因素并兼顾系统总带宽性能,提出了两种易于实现且具有良好收敛性能的启发式频谱动态分配算法——兼顾最大化系统总带宽的快速收敛算法(fast convergency algorithm with maximum bandwidth,简称FCMB)和兼顾最大化系统总带宽的启发式公平性分配算法(heuristic fairness algorithm with maximum bandwidth,简称HFWB).通过大量的仿真实验,就系统总带宽、公平性以及收敛性能3个方面,与现有的协调式最大化系统总带宽(collaboration max-sum-bandwidth,简称CMSB)算法、随机分布式算法(randomized distributed algorithm,简称RAND)以及以最大化系统总带宽为目标的理论最优(theoretical max-bandwidth optimal,简称OPTL)算法进行了比较,并针对主、次用户数目变化、系统中信道数目以及次用户干扰区域半径大小变化等不同系统参数情况下各种算法的性能进行了对比分析.仿真结果表明,在综合考虑系统总带宽的基础上,FCMB算法和HFWB算法在快速收敛和兼顾系统带宽的公平性能上分别表现突出,尤其是FCMB算法,其在收敛速度上远远优于其他算法(和与其在系统吞吐性能上表现相近的CMSB算法相比,在收敛性能上至少有300%的提高).