基于启发式策略的最短路径算法

在讨论经典Dijkstra算法和启发式策略算法（A^＊,矩形算法等）的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径．该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间．该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果．实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50％的搜索节点数和搜索时间．     

复杂系统可靠性优化的混合万有引力搜索算法求解

复杂系统可靠性优化问题是一类有约束限制且目标函数具有多个局部极值的非线性优化问题.为求解该类问题,提出了一种混合万有引力搜索算法的求解方法.算法利用基于万有引力定律的寻优机制指导群体进行全局搜索,并采用序列二次规划算法进行局部搜索,避免基本万有引力搜索算法陷入局部最优,改善优化性能,加快寻优速度.通过实例计算,并与蚁群优化算法、微粒群算法、蜂群算法和基本万有引力搜索算法等进行比较,验证了算法的可行性和有效性.     

基于并行迭代动态规划的聚合物驱最优控制求解

针对迭代动态规划计算量大,耗费时间长的特点,基于实验室搭建的PC机群,以消息传递库MPICH为编程工具,搭建一个并行计算平台,给出一种主从式的并行迭代动态规划算法,利用该算法对聚合物驱最优控制问题进行求解,并与串行计算结果进行对比.结果表明:在大规模的优化问题中并行迭代动态规划算法与串行算法结果一致,但表现出较高的并行效率和加速比;并行算法求解的效率受到主节点分配任务时是否均衡的影响.     

变容差遗传算法求解多约束问题的研究

提出一种基于实数编码的变容差遗传算法,该算法是将自适应遗传算法的随机性与可变容差算法的确定性相结合,利用可变容差算法的准行域搜索准则,对具有非线性、多峰、多约束的问题寻优.运用该混合算法对有边界限制的6个峰值、4个性能约束的复杂函数最大值多次寻优,并与罚函数处理约束条件后的结果相比较,表明该算法依据容差准则具有较高的可靠性,尤其对于隐性约束,在一定精度范围内能够提高收敛精度,减少计算量,提高优化效率.     

并联型混合动力汽车燃油经济性最优控制

以某并联混合动力汽车（HEV）为例,建立了燃油经济性最优控制数学模型及相应的动态规划（DP）递归方程,提出了换档和发动机启动2个附加代价函数以限制频繁换档和启停发动机.为解决数值DP中“维数灾”问题,提出了搜索区域限制算法,并利用MATLAB/RTW将系统模型转换成实时仿真代码以进一步提高计算效率.对实车试验、仿真和DP结果三者进行了比较,结果表明,该方法能在可接受的时间内计算出HEV的最优性能,从而进行控制策略的评价和优化.     

动态规划算法的时间效率改进

分析了影响动态规划算法时间复杂度的3个因素,分别从3个方面给出了改进动态规划算法时间复杂度的优化措施,从理论上分析了优化方法的有效性和正确性.与传统算法相比,优化后的算法时间复杂度有一定程度的提高,能够适用于数据规模更大的问题.     

钢铁企业产成品转库车辆路径问题优化

分析了钢铁企业产成品转库问题的特点,通过将转库任务分解的方法将原问题转化为具有最迟访问时间约束和同时访问车辆数限制的车辆路径优化问题,建立了转换后问题的0-1规划数学模型,针对模型的特点设计了迭代局域搜索算法.算法初始解由贪婪算法生成,局域搜索过程采用4种常用局域搜索算子的混合,摄动过程采用变强度的2-opt*算子.该算法可以同时实现转库车辆指派和车辆路径优化.通过仿真生成的算例对模型和算法进行了验证.实验结果表明,该模型和算法是解决该类问题的有效方法.     

TSP问题启发集的分析及应用

建立了描述TSP问题启发集性质的概率模型,并指出了改进启发集的一般方法.进一步,利用局部最优解交集作为近似骨架,提出了一种动态改进启发集的宏启发算法--自适应可变启发集搜索.并将自适应可变启发集搜索与目前广泛使用的算法ILK、LKH相结合,TSPLIB中典型实例上的实验结果表明,改进后的算法在求解质量上有了较大的改进.     

基于改进蚁群算法的二维码移动机器人路径规划方法

针对在结构化栅格工作环境下,基于蚁群算法的路径规划存在停滞和收敛速度慢的问题,提出了一种基于改进蚁群算法的二维码移动机器人路径规划方法.通过限制蚂蚁的搜索方向,即将机器人置于结构化栅格工作环境下,使其只能在水平和垂直方向上移动,进而提高算法的搜索效率.引入自适应期望函数和启发因子,动态调整状态转移概率,避免算法陷入停滞状态,提高算法的收敛速度.针对机器人在转弯过程中耗费时间较长的问题,通过引入转弯影响因子得到扩展路径长度,进而根据扩展路径长度选取最优路径.实验结果表明,提出的方法可以为二维码移动机器人规划出最优路径.     

限制搜索区域的距离最短路径规划算法

提出一种时间复杂度为O(n)的限制搜索区域距离最短路径规划算法(n为路网节点数).算法设计的基础是,经典Dijkstra算法搜索时的无方向性及实际城市道路网络特有的空间分布特性.算法实现采用邻接表数据结构和限制搜索区域的搜索机制,即利用实际城市道路网络的空间分布特性,合理限制算法的搜索区域.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的应用实例,实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在3 s以内.     

高校排课问题的模型与求解

给出了以行政班为编排单位的排课问题的模型，探讨了其有解性和约束条件的一致化表示，并针对传统回溯法的不足，通过动态规划的方法找出了克服策略，提出求解算法。指出了下一步的研究方向。     

正交频分复用系统多播资源分配的动态规划算法

针对现有正交频分复用系统采用多播资源分配算法时效率较低的问题,提出了一种多重描述编码的多播资源分配算法.首先将系统的功率划分为等长的基本分配单元,之后使用动态规划算法计算每个子载波上的功率分配和用户分配.该算法可以从全局进行子载波分配和功率分配,从而提高了资源分配的效率,实现了系统总吞吐率的最大化.由于不需要重复计算相同子问题,因此算法能在很短的时间内完成资源的分配计算.仿真结果表明,所提动态规划算法可以有效地利用系统资源,使得系统总吞吐率与最优算法计算结果之差小于2%.     

无环网络最大流的一种新算法

网络最大流问题是运筹学和网络优化的重要问题之一.基于动态规划基本思想,提出了在无环网络中适用的一种网络最大流算法.该算法通过判断在各个动态阶段各节点允许通过的最大流量,最终得到终点的最大流量-网络最大流,从而大大提高了执行的效率.最后算法分析和算例表明了新算法的有效性.     

遗传算法在单层球壳动力响应优化中的应用

针对标准遗传算法存在局部搜索能力不强、后期收敛速度放慢等缺陷,对遗传算法的杂交算子和变异算子采用自适应策略,同时引入基于预选择机制的小生境技术,提出一种小生境遗传算法(ANGA).以70m跨单层球壳为研究对象,将ANSYS非线性动力响应分析与ANGA算法相结合进行倒塌模式优化.分别以结构在某级水平的地震作用下结点动位移的最大值和结构最大结点动位移的给定区间为优化目标,对球壳进行全局优化和局部优化(径向杆件不变,只优化环向杆件和斜向杆件).结果表明,优化后的球壳可以避免出现无征兆的动力失稳,说明该算法可以有效解决优化变量繁多的大中型网壳结构动力响应优化问题.     

二机流水作业带不可用区间、工件可拒绝的调度问题

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.     

一种面向HPC Cloud系统的在线作业调度算法

针对HPC Cloud中的作业之间对网络I/O资源的竞争问题,提出了一种基于动态规划算法、二分搜索算法和网络最大流算法的在线作业调度算法——DBMF算法.DBMF算法专注于物理节点上网络I/O的负载均衡,通过物理节点之间的网络I/O负载均衡来减少对网络I/O资源的竞争.通过与FCFS和RSF算法进行对比,DBMF调度算法有效提高了HPC Cloud的系统负载,减少了作业之间对网络I/O资源的竞争.     

大型0—1目标规划的启发式算法

提出了一个０－１线性目标规划新的启发式算法,该算法以新的算法准则及评价标准,改进了旧算法中的系数限制,并能通用于任何０－１线性目标规划问题,特别能够有效地解决大规模０－１线性目标规划问题。     

汉江上游梯级水电站水库优化运行研究

根据汉江上游石泉、喜河、安康梯级水电站水库群的特点和任务,分别以梯级水电站发电量最大和发电效益最大为目标函数建立优化模型,将逐次逼近动态规划法(DPSA)与逐步优化算法(POA)相结合求解模型,获得梯级水电站长系列优化运行结果.结果表明,梯级水电站水库群优化运行能够充分发挥水库的补偿作用,相比梯级水库群常规调度和单一水...     

一种基于双启发式退出规则的多星实时调度算法

多星实时调度问题是目前卫星调度领域的研究热点.针对实时任务动态到达的情况,建立了多星实时调度数学规划模型.提出了基于任务紧迫度和最大比例自由度的双启发式退出规则的多星实时调度算法.仿真实验结果表明,该算法较好地平衡了调度收益和稳定性,适用于多星实时调度问题.     

多阶段多目标洗钱网络路径优化模型及算法研究

针对多阶段洗钱资金转移路径的决策问题,基于多目标优化的思想,构建了以时间约束、总体资金转移量尽可能大以及总体风险尽可能小为决策目标的多阶段洗钱路径优化模型,并利用多重动态规划方法和最大流理论给出了求解该模型的算法,最后通过实例应用验证了该算法的可行性.通过该模型,不仅能够从洗钱资金转移路径观察洗钱行为特征,还能够发现和追踪到洗钱者的洗钱踪迹和全过程,有助于对洗钱行为的各个环节进行有效监控,降低反洗钱侦测成本.