启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

两种改进的模拟退火算法求解大值域约束满足问题

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB模型（Revised B）是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这一类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA（Revised Simulated Annealing Algorithm）和GSA（Genetic-simulated Annealing Algorithm）。将这两种算法用于求解RB模型的随机实例,数值实验结果表明：在进入相变区域时,RSA和GSA算法依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。     

基于启发式的约束满足问题AC系列算法改进研究

约束满足问题是人工智能领域中一个重要的研究方向,其研究结果在符号推理、系统诊断、真值维护系统、资源分配和产品配置等问题中有广泛的应用。局部相容性定义了约束满足问题在约束传播过程中必须满足的性质,是约束传播发展的主要方向。而对于较为复杂的相容性问题中的AC系列算法的改进可谓难上之难。本文围绕着以弧相容、Singleton弧相容为代表的相容性技术和求解算法展开,主要针对AC-2001算法、SAC算法等进行优化改进,重点基于启发式进行改进,使之获得了更快的筛选速度。尤其对于SAC算法,大大减少了约束检查次数,获得了较为成功的基于启发式的改进结果。     

两种高效局部搜索算法求解RB模型实例

RB （revised B）模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。     

基于实例化次数的约束求解方法研究

启发式是约束满足问题领域的重要研究课题,有效的启发式方法可以极大地提高问题的求解效率.在求解约束满足问题时,发现变量实例化失败次数与值实例化成功次数反映了变量和值与已实例化集合之间的关系,将实例化次数加以利用可以对问题求解效率有很大的影响.据此,提出了实例化次数的权值统计方法,并将其与现有启发式方法相结合,提出了实例化次数启发式及其相应的约束求解算法MAC_Try,并证明了其在一个分支上的最坏时间复杂度是O(ned3).大量实验结果表明,新的MAC_Try方法在求解效率上明显优于国际上流行的MAC3rm方法.     

车辆路径问题（VRP）算法研究

车辆路径问题（VRP）是图论中的NP问题,目前求解这类问题的算法可分为：精确算法、经典启发式算法和现代启发式算法三类;对这三类算法中最具代表性的几种算法进行了分析指出了其适用范围和场合、存在的问题以及改进的方案;最后,对其研究前景进行了展望。     

车辆路径问题(VRP)算法研究

车辆路径问题(VRP)是图论中的NP问题,目前求解这类问题的算法可分为:精确算法、经典启发式算法和现代启发式算法三类;对这三类算法中最具代表性的几种算法进行了分析指出了其适用范围和场合、存在的问题以及改进的方案;最后,对其研究前景进行了展望。     

一种基于变量熵求解约束满足问题的置信传播算法

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.     

带投资约束P-中位问题的混合蚁群算法

将投资限制引入经典约束p-中位问题,提出带投资的约束P-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束P-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉格朗日启发式算法和蚁群算法相结合,设计了求解该问题的拉格朗日混合蚁群算法。实验结果表明：带投资的约束P-中位问题能够根据投资金额规划不同的投资方案;且提出的混合蚁群算法较大程度上提高了蚁群算法和拉格朗日启发式算法的求解精度,具有较好的收敛性。     

Overlay多播网络中带度约束的最小带宽多播树的求解

本文研究了Overlay网络中带有度约束的最小带宽多播路由问题,建立了相应的数学优化模型,设计了求解模型的启发式算法,对算法的复杂性进行了分析,并进行了数值模拟。     

约束满足技术在板坯排序中的应用

热轧调度中的板坯排序问题是一类特殊的排序问题,具有约束条件复杂、NP难特点。为了简化问题,将板坯排序问题转化为一个约束满足问题处理。给出板坯排序问题的约束满足模型,设计了基于约束满足和启发式混合求解算法。用3组实际生产数据对算法性能进行验证,说明了算法的有效性。     

同时送取货车辆路径问题算法研究综述

针对同时送取货车辆路径问题的研究算法进行了评述.将该问题的求解方法分为精确算法、构造型启发式、现代启发式以及并行算法四个大类.从算法的原理、性能、适用环境,以及算法之间差异性等方面对各类算法进行了较为全面的介绍.最后,说明了VRPSDP算法研究在节点具有双重需求车辆路径问题理论研究方面的意义,并提出未来VRPSDP算法研究的两个发展方向,即适合多处理器上运行的并行现代启发式算法,以及有效的混合算法如量子行为粒子群算法.     

A Context for Constraint Satisfaction Problem Formulation Selection

Much research effort has been applied to finding effective ways for solving constraint satisfaction problems. However, the most fundamental aspect of constraint satisfaction problem solving, problem formulation, has received much less attention. This is important because the selection of an appropriate formulation can have dramatic effects on the efficiency of any constraint satisfaction problem solving algorithm.In this paper, we address the issue of problem formulation. We identify the heuristic nature of generating a good formulation and we propose a context for this process. Our work presents the research community with a focus for the many elements which affect problem formulation and this is illustrated with the example adding redundant constraints. It also provides a significant step towards the goal of automatic selection of problem formulations.     

蚁群算法在求解旅行商问题中的应用综述

旅行商问题作为组合优化研究中最具挑战的问题之一, 自被提出以来就引起了学术界的广泛关注并提出了大量的方法来解决它. 蚁群算法是求解复杂组合优化问题的一种启发式仿生进化算法, 是求解旅行商问题的有效手段. 本文分别介绍蚁群算法中几个有代表性的算法, 综述了蚁群算法的改进、融合和应用的文献研究进展, 以评价近年来不同版本的蚁群算法为解决旅行商问题的发展和研究成果, 并针对改进蚁群算法结构框架、算法参数的设置及优化、信息素优化和混合算法等方面, 对现被提出的改进算法进行了分类综述. 对蚁群算法在未来对旅行商问题及其他不同领域的研究内容和研究热点的进一步发展提供了展望和依据.     

改进蚁群算法在QoS组播路由中的应用

QoS组播路由是网络传输中的一项关键技术,蚁群算法是解决多QoS约束组播路由问题的一种启发式算法。针对蚁群算法的缺点,提出了一种双向蚁群算法对该问题进行求解,并改进了蚁群算法的信息素更新策略。仿真实验表明,该算法能快速搜索并收敛到全局（近似）最优解,且随着网络规模的增大,算法保持了良好的特性。     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

高效求解三维装箱问题的剩余空间最优化算法

为实现三维装箱问题的高效求解，提出了一个三维的剩余空间最优化算法（Three-Dimensional Residual-Space-Optimized Algorithm，3D-RSO）。在满足3个著名约束的条件下，该算法将三维问题转化为带有高度约束的二维问题，通过对箱子放置后的剩余空间状态分析，提出了基于概率较优的空间分割方法和箱子布置规则。相比于传统算法，3D-RSO在求解过程中不需要任何的预处理和搜索操作，是一种最坏计算复杂度为[O(2n2)]的直接求解算法。针对强异构体的实验表明，该算法能够在极短的时间内对算例进行高效求解，适合应用在大规模或者需要被快速求解的三维装箱问题中。