受时间、空间约束VRP问题蚁群优化模型及算法的研究

蚁群算法求解组合优化问题是当今智能优化算法的发展方向之一.通过对M.Dorigo提出的传统蚁群优化元启发模型改进,提出了多参数约束蚁群优化元启发式模型.该模型将所有优化约束条件映射为影响人工蚂蚁搜索行为的诱导素;模型中的人工蚂蚁智能行为简单,只根据信息素和诱导素在求解空间中进行搜索,而不进行复杂的运算;该模型减少了人工蚂蚁的求解搜索空间.并通过受时间、空间约束问题VRP(Vehicle Routing Problem)验证了本文提出模型算法较传统蚁群算法简单、收敛性快.     

基线矢量约束GNSS单频单历元可靠姿态解算方法

针对全球导航卫星系统(GNSS)单频、单历元姿态测量,将传统的基线长度约束扩展到包括角度和长度在内的基线矢量约束,提出了一种新算法.该算法利用基线三维先验信息,构造更加严格的模糊度代价函数,在搜索过程中将模糊度和基线坐标共同分为部分固定模糊度向量和实向量,由部分固定模糊度在基线矢量约束条件下逐步最优化求解实向量,压缩搜索空间,构建搜索树.相比于传统基线长度约束LAMBDA算法,模糊度固定成功率更高,实验条件下达到100%,并且具有相当的搜索效率和测角精度.实验同时验证了新算法对于先验姿态信息的容错程度,证明了算法的鲁棒性.     

多约束最优路径算法比较研究

针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究.基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法;引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法;为克服IDA* _MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法——Fringe_MCOP算法.实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优;当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显;当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.     

方差约束因子耦合搜索区域判定模型的图像修复算法

为了解决Criminisi算法在图像修复过程中无法保证修复块的优先级顺序,从而导致修复质量不佳的问题,提出了方差约束因子耦合搜索区域判定模型的图像修复算法.首先,将待修复块分割为两个子块,通过子块的方差构建方差约束因子,并利用方差约束因子改进Criminisi算法中的优先权函数;然后,在二维直角坐标系中对损坏区域进行测量,根据测量结果选取损坏基准值,以构建搜索区域判定模型,确定最优匹配块的搜索范围;最后,引入SSD(Sum of Squared Differences)模型在搜索区域中选取最优匹配块,利用最优匹配块中像素点与待修复块中对应像素点的像素差值构造置信度更新模型,对置信度进行更新,实现图像的修复.实验结果表明,与其他图像修复算法相比,本文算法具有更好的图像修复视觉质量.     

采用群智能算法的多约束问题优化

为了解决约束优化问题,采用一种基于群智能算法优化的多约束问题优化方法.首先构造同时计及约束条件和优化适应度的目标函数,然后分别利用粒子群算法和人工蜂群算法优化其函数,从而获得约束条件下的优化解.仿真结果表明,该多约束问题优化方法是可行性的,人工蜂群算法比粒子群算法具有更好的搜索和收敛能力.     

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.     

基于遗传算法的多约束背包问题求解方案

采用混合遗传算法求解多约束背包问题.首先构建多约束背包问题的数学模型,然后采用多维实数编码方式的遗传算法,结合附带染色体库技术、局部启发式算子和扰动算子对问题进行求解,并给出了一个实验实例.实验证明文中采用这种混合遗传优化算法解决多约束背包问题切实可行,有较高的搜索效率.     

基于曲率约束因子与边缘加权法则的图像修复算法

针对当前较多图像修复算法主要通过对图像块进行方差和度量的方法来完成图像修复,忽略了图像块的显著边缘特性,使得修复图像容易出现模糊效应以及不连续效应等不良现象,导致算法修复性能不佳的不足,提出了基于曲率约束因子耦合边缘加权法则的图像修复算法.首先,通过像素点的等照度线方向构造曲率约束因子,对数据项进行约束,形成优先级度量函数,利用优先级度量函数选取优先修补块;然后,利用像素点的均值之差构造像素自相关模型,对样本块的大小进行了调整;最后,以样本块显著边缘为约束,构造了边缘加权模型,通过边缘加权模型联合SSD(sum of squared differences)模型建立了边缘加权法则,对最优匹配块进行搜索,用于对待修补块进行修复.仿真实验结果表明,与当前图像修复算法相比,本文设计的图像修复算法修复的图像具有良好的视觉效果.     

基于权图搜索的约束求解

介绍一种基于加权约束图搜索的二维几何约束的求解方法或称之为求解过程 ,并对一些相关的概念进行阐述 .该几何约束的求解是在几何实体自由度衰减的基础上进行的 .求解过程中 ,在图的基础上提出循环约束的查找算法 ,并通过实例描述二维几何约束的求解过程     

Kriging模型与优化算法在汽车乘员约束系统仿真优化中的应用研究

汽车乘员约束系统的优化涉及到安全带、安全气囊等部件的众多参数.首先采用一阶线性响应表面模型、正交实验设计方法进行参数筛选.然后构造Kriging代理模型来代替计算机仿真,并结合两种不同的优化算法来进行乘员约束系统参数的优化设计.结果表明:该方法对汽车乘员约束系统参数优化具有明显效果,可行方向法在该优化中优于多目标遗传算法.     

基于粒子群算法的共享单车站间调度优化方法

对单车实行精准高效的调度是目前共享单车系统亟须攻克的重要难题之一。共享单车的调度问题可以看作是一个受时间、地域、人流等多因素影响的NP完全问题(Non-deterministic Polynomial Complete Problem)。目前,我国在这一方面的研究工作尚不成熟。根据单车调度实际情况,考虑调度车容量与站点满意度约束,以旅行商问题为基础,建立综合优化最大化的共享单车站间调度数学模型,通过优化多目标问题的混合禁忌-粒子群算法,对上述模型进行求解。最后以合肥市大学城实际单车站点为算例,以该算法进行求解。结果证实该算法可以得到综合最优的调度路线。     

针对CVRP的2-OPT算法的时间复杂度均值分析

分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2 - OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点 ,将车辆路径问题 (VRP)转化为多旅行商 (MTSP)问题 ,并通过分析 MTSP进行 2 -OPT操作的可行性条件 ,建立起该算法运行所需的迭代次数的分布函数 ,进而求得平均运算时间复杂度的上界。该文为有效评价针对 VRP的 2 - OPT算法 ,提供了理论依据 ,并为VRP领域的启发式算法的复杂度分析 ,提供了一种新思路。     

基于项目拆分决策的多模式资源投入

结合一类实际生产决策需求,提出了基于项目拆分决策的多模式资源投入调度问题,并以资源投入最小化为优化目标,建立了问题的数学模型.针对模型特点,提出了包含项目拆分算法和多模式资源投入型项目调度算法的双层优化算法,其中项目拆分算法通过将作业在不同子项目之间有效移动获得合理的拆分方案,多模式资源投入型项目调度算法通过分析不同作业对时间约束和资源约束的影响来确定优先级规则,进而得到最佳调度方案.应用PSPLIB标准算例进行数据实验,结果证明了算法的有效性和可靠性.     

子集和问题的扩展研究

基于文献所提出的子集和改进求解算法,我们提出了一些针对具体实际问题的改进方法。基本的思想是将子集和问题进行转化。实验和分析都显示我们方法的有效性。     

一种基于稀疏规则库的定性插值推理方法

提出一种基于三元组定性分析理论的插值推理方法,提供了该方法的具体算法, 并将此方法应用到有限推理问题的一个典型实例中, 验证了该方法在解决有限推理问题上的有效性和准确性。     

反应动力学参数的优化模型及算法

干酪根降解过程中的反应动力学参数（即频率因子和活化能）是油气生成数值模 拟中必不可少的关键参数，确定这些参数的问题是个常微分方程组初值问题的反问 题。本文将该问题转化为隐式约束（即动态约束）非线性规划，并讨论规划的分解及 目标函数的性质，从而给出了可在微机上实现的优化算法和实际应用。     

有流量附加约束动态交通网络平衡的变分不等式表示

为了研究有流量附加约束的动态交通网络平衡问题,将附加约束等价地当作路径的新增阻抗,得到了基于有流量附加约束条件下的Wardrop用户平衡的变分不等式表示,并提供了计算这种平衡配流的另一种方法。该方法由于考虑了路径容量约束,使得这种变分不等式表示更接近现实中有路径流量限制的情形。     

一种基于区域选择的视频对象分割算法

视频对象分割对于行动识别和视频检索等领域具有重要作用。针对现有方案的不足,提出一种新的视频对象分割算法。首先,基于物质度构建出视频主要对象的区域图,然后,视频对象的区域选择被建模为区域图中最大权重派系的寻找问题,为了避免不合理的区域选择所导致的无法求解问题,对同一派系的区域引入两种互斥约束:帧内约束和帧间约束,最后提出了一种新的最大权重派系(MWC)算法来计算满足约束条件的最大加权派系,从而实现视频对象的精确分割。将本文算法用于SegTrack数据库中的多个高难度基准视频进行测试,实验结果表明,本文算法能够实现每帧视频主要对象检测和分割自动化,且分割误差也要明显小于已有的算法。     

Pushing Multiple Convertible Constrains into Frequent Itemsets Mining

Constraint pushing techniques have been developed for mining frequent patterns and association rules. How ever, multiple constraints cannot be handled with existing techniques in frequent pattern mining. In this paper, a new algorithm MCFMC （mining complete set of frequent itemsets with multiple constraints） is introduced. The algorithm takes advantage of the fact that a convertible constraint can be pushed into mining algorithm to reduce mining research spaces. By using a sample database, the algorithm develops techniques which select an optimal method based on a sample database to convert multiple constraints into multiple convert ible constraints, disjoined by conjunction and/or, and then partition these constraints into two parts. One part is pushed deep inside the mining process to reduce the research spaces for frequent itemsets, the other part that cannot be pushed in algorithm is used to filter the complete set of frequent itemsets and get the final result. Results from our detailed experi ment show the feasibility and effectiveness of the algorithm.     

一种求解TSP问题的均匀设计抽样混合遗传算法

旅行商问题是经典的NP-hard组合优化问题,在许多领域有着重要应用。近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想。基于理想浓度模型的机理分析,利用均匀设计抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在旅行商问题特点的基础上,结合2-opt局部搜索策略,给出了一个解决旅行商问题的新的遗传算法。通过将该算法与简单遗传算法和佳点集遗传算法进行实例仿真比较,可以看出新算法在求解旅行商问题上提高了求解的质量、速度和精度,而且避免了其它方法常有的早期收敛现象。