非线性约束最短路问题的启发式算法

多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题。它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法。然而这些方法只能求解一些带有线性约束的RSP。对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性。本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP。主要思想是将非线性约束作为检验条件来使用。当每得到一个解时,检查解是否满足非线性约束。如满足,则得到最终解;否则在原问题中添加一个线性约束。该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解。仿真算例说明了算法的有效性。     

受顶点数限制的最短路问题及其算法

本文提出了若干受顶点数限制的最短路问题。引入非支配路的概念，用双标号和取字典序最小方法，给出求解问题的多项式算法。     

改进的最短路算法

通过对军事后勤运输中运输路线选择问题的分析 ,提出了最短路模型。针对巨型交通网络的路径选优问题 ,以传统的最短路问题的Dijksta算法理论为基础 ,引入并行处理的概念 ,提出了改进的最短路算法 ,给出了算法的证明推导 ;并对算法效率进行了简单的分析 ,同时用示例对算法进行了计算。新算法在处理巨型网络时效率明显提高 ,为后勤运输路线的选择提供了有力的辅助决策工具     

城市应急最优路径算法

提出一种应用于城市应急系统的改进的最优路径搜索算法。它利用道路等级的分层方法,建立优化的层次化路网模型;在此基础上,利用分级搜索技术,解决起始节点和目标节点由低层到高层的最优路径;同时,在高层路网上采用提出的结合道路状况的启发式A＊优化搜索算法进行搜索,得到完整的优化路径。最后通过实际路网的应用验证了提出方法的有效性。     

目标点动态变化的最优路径算法

研究目标点动态变化的最优路径算法,提出了一种改进的启发式最优路径算法,并采用实际路网数据进行了数据仿真实验,结果表明:提出的方法能较好的解决最优路径算法的实时性和精确性之间的平衡,具有较大的应用价值.     

用分解算法在全国铁路网上求最短路

将全国铁路网按路局划分，采用分解算法求解最短路，能使计算量大约降至由全路网直接计算的１０（－８）．     

一类对地观测卫星成像调度系统的设计与实现

针对一类光学小卫星成像调度的应用需求,综合考虑星地等各种资源的载荷使用约束,设计实现了一个成像调度系统.详细分析了载荷约束,针对约束特点,提出了五阶段系统执行流程,并重点介绍了各阶段的关键技术,包括基于成像约束图的观测动作生成算法和基于背包模型的数传动作生成算法.最后给出了应用实例和实验结果,表明了系统的适用性和可行性.该系统已经成功应用于某在轨卫星的日常规划中.     

最短路问题的字典序多目标算法

本文研究了双目标最短路问题,给出了字典序最优解的定义,最后给出了一个时间复杂性为Ｏ（ｎ＾２）的字典序双目标算法。     

板坯最优倒垛问题的有铲启发式算法

板坯库用于存放由炼钢－连铸工艺阶段产生的、供热轧生产阶段进一步轧制成带钢或钢板的板坯,一个板坯库中可分为多个逻辑区域,每个逻辑区域又进一步分为多个垛位。同一垛位的板坯之间是叠放的。最优倒垛问题是如何从M个相关的析以坯垛位中选择N个板坯,在满足相应的轧制单元计划所需要的板坯序列要求条件下,保证总的板坯倒垛次数最少。首先对例垛问题进行了定义,在分析了问题的领域结构基础上,构造了新的多回路启发式算法。通过精选的随机产和的200个问题例子的实验显示,提出的启发算法的性能在计算速度和最优性方面都明显优于原系统的启发式算法,在最优性方面平均改进率达到20％,在计算时间方面,可降低一半以上。新多回路启发式算法不但提高了车间作业率,也大在降低了生产过程控制机（FLS）的负荷。     

蚁群算法在全局最优路径寻优中的应用

移动机器人路径规划是机器人学的一个重要研究领域。针对移动场地的特点对其进行了建模与存储,然后将场地处理成简单的连通图,在此基础上对TSP模型进行了改进以应用到机器人全局最优路径中来,然后利用蚁群算法的基本原理在所建立的模型上进行全局最优路径搜索。为了更好的寻找到全局最优路径,对基本蚁群算法也做了一定的改进。不同的实验结果表明这种方法的确可以准确地找出全局最优路径。     

基于双重遗传算法机制的路径规划

静动态障碍物同时存在的复杂环境下进行路径规划是一个比较难解决的课题.引入双重的遗传算法机制,提出了第一重遗传机制负责静态障碍物的避碰,第二重遗传算法机制以第一重机制规划出的最优路径为基础,负责动态障碍物的避碰的方法;设计优化算子,引入自适应技术提高路径的生成速度.实验表明,该方法能综合考虑多种因素,收敛到全局最优路径.     

遗传算法在时间最优路径规划中的应用

提出一种应用遗传算法在三维区域寻找自主机车的最优路径的方法。路径由Bezier曲线得到 ,代表路径的Bezier曲线的控制点 ,作为遗传算法的未知参数来进行二进制编码。由于机车在行驶过程中受动力学和物理上的某种限制 ,遗传算法的适应值函数采取了适当的路径补偿。仿真结果表明了该方法的有效性。     

用遗传算法求解改进的投资组合模型

在传统Markowitz投资组合模型中考虑了最小交易量、交易费用以及最大投资上限等实际因素，得到了一个改进的投资组合模型。该模型是一个非线性整数规划问题，传统算法难以有效求解。为此，设计了一种基于整数编码的遗传算法求解该模型。实际算例表明，所提出的算法是有效的。     

多段式自动泊车最优路径规划与仿真分析

针对狭小平行泊车位的路径规划和泊车轨迹曲率不连续等问题,同时考虑避撞约束,提出了一种最优化多段式泊车路径规划方法.建立了车辆方向盘转速恒定时的车辆后轴中心运动轨迹方程;其次为保证车辆安全停车,建立了避障约束函数;设置泊车路径后轴中心为控制点,以泊车空间最小、最终泊车姿态角最小等泊车指标求取路径最优解.通过Simulin...     

含重置条款的或有可转债路径分解式定价

为了解决或有可转债在长期没有进行债转股的情况下,可能会出现的由于发行方无力支付高额息票而被迫对债券进行赎回的问题,设计了一种包含重置条款的或有可转债。首先,通过对债券存续期内标的股票价格可能发生的路径进行分解,分析了此类条款下债券价值的路径依赖特征;在此基础上,进一步确定了回售边界以及债券价值。通过数值分析得出,本文设计的或有可转债的价值低于相同参数下的不含任何附加条款的或有可转债的价值,并且条款的可用性与目前市场上普遍存在的可赎回或有可转债相比存在一定的优势。敏感度分析结果显示,债券价值与股价年波动率之间呈负相关关系,与修正条款执行日之间呈正相关关系,因而宜根据对未来市场风险的预测来选取适当的条款执行日。     

Mean Shift算法优化带宽的自动搜索

Mean Shift算法是一种非参数估计方法,能够快速收敛到概率密度函数的模态,在图像处理领域已得到了广泛的应用。算法的带宽参数的选取会直接影响到收敛速度和收敛结果,而手动调试参数需花费大量的时间和资源。为解决这一问题,提出一种Mean Shift算法优化带宽自动搜索策略,采用Mean Shift算法对图像特征空间内的样本点进行聚类分析,以图像结构特征信息作为分割效果的评判准则,自动寻取优化带宽参数。实验结果表明,提出的方法可以实现自动寻取Mean Shift算法的优化带宽参数,为解决Mean Shift算法带宽自寻优问题提供了一种新的思路。     

A New Algorithm for Solving Multicriteria Shortest Path Problem

１　ＩｎｔｒｏｄｕｃｔｉｏｎＭｕｌｔｉｃｒｉｔｅｒｉａｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｉｓａｐａｒｔｉｃｕｌａｒｄｉｓｃｒｅｔｅｌｉｎｅａｒｍｕｌｔｉｏｂｊｅｃｔｉｖｅｐｒｏｂｌｅｍ［１～４］．Ｕｐｔｏｎｏｗ,ｉｔｈａｓｎｏｔｂｅｅｎｗｉｄｅｌｙｓｔｕｄｉｅｄｉｎｌｉｔｅｒａｔｕｒｅ．Ｔｈｅｄｉｆｆｅｒｅｎｃｅｂｅｔｗｅｅｎｍｕｌｔｉｃｒｉｔｅｒｉａｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍａｎｄｔｈｅｃｌａｓｓｉｃａｌｓｈｏｒｔｅｓｔｐａｔｈｐｒｏｂｌｅｍｉｓｔｈａｔｔｈｅｒｅａｒｅｍｏｒｅ…     

一种自主水下航行器路径规划算法

提出了一种自主水下航行器穿越雷区的路径规划算法。将路径规划分为全局路径规划和局部路径规划两个部分,建立了水雷分布的Voronoi图,采用遗传算法规划出初步的全局最优路径。自主水下航行器按照全局最优路径航行时,利用前视声纳作为探测仪器。根据所测得的障碍物相对于自主水下航行器的位置关系设计出一个模糊推理系统(FIS)求解其避障角度,完成局部路径规划。仿真结果表明了这种算法的有效性。