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

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

求解可满足性问题的改进的模拟退火算法

该文为可满足性问题的高效近似求解提出了改进的模拟退火算法。数值实验表明,对于该文随机产生的测试问题例,改进的模拟退火算法完全胜过局部搜索算法、模拟退火算法以及目前国际上流行的WSAT算法。     

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

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

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。     

基于动态度的回溯算法求解大值域约束满足问题

针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域与动态度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容（MAC）技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明：在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。     

置信传播和模拟退火相结合求解约束满足问题

约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明：该算法大大提高了初始赋值向最优解收敛的速度,表现出了显著优越于模拟退火算法的求解性能。     

值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析

值域增长的约束满足问题模型是计算复杂性理论中一类重要的实际问题模型,针对解决这类问题的算法研究仍然很少。通过研究RB模型这一典型的值域增长约束满足问题,发现当问题规模很大时,无回溯策略比随机行走策略更加有效。这与典型的值域确定的约束满足问题如SAT问题不同,是值域增长的约束满足问题所特有的性质。通过实验研究了两种策略的表现,并进一步对两种策略的表现进行了分析。     

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。     

改进求解约束满足问题粗粒度弧相容算法

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.     

约束满足问题求解途径之比较与分析

本文从逻辑,自动机理论,代数方法,连接主义框架和遗传算法的角度深入地探讨了ＣＳＰ问题的不同表示框架和求解风范,详细分析和讨论了不同表示和求解方法的特点以及它们之间的内在联系和可能的结合。     

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

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

基于模拟退火遗传算法的关联规则挖掘

将模拟退火遗传算法加以改进,应用于关联规则挖掘,提出一种新的基于改进的模拟退火遗传算法的关联规则挖掘算法,并在该算法中,采用自适应方式动态选取交叉和变异概率,有效地抑制了早熟收敛现象,实验结果显示该方法能高效地解决关联规则挖掘问题。     

两种空间约束求解算法

进行了3个方面的研究：(1)对由3点3面组成的空间约束系统进行了几何分析和推导,并且利用数值解验证了几何分析和推导的正确性,从而进一步完善了Hoffmann提出的基于图构造方法的约束求解方法;(2)将遗传模拟退火算法结合于空间约束求解中,有效地克服了基于图构造方法的可扩展性差的缺陷,并可以解决过约束和欠约束的情况;(3)应用遗传模拟退火算法对3点3面约束系统进行求解,分析比较了基于图构造方法和基于遗传模拟退火算法两种约束求解算法．     

一种融合模拟退火和单亲遗传的优化求解算法

度约束最小生成树是一个经典的组合优化NP难题,其在网络设计和优化中有广泛的应用;现有求解方法往往不能很好地兼顾求解效率和求解精度;为了在缩短求解时间的同时,更好地获得最优解,提出了一种结合模拟退火算法和单亲遗传算法的改进求解算法;首先,改进遗传算法中变异因子的生成方式,避免不可行解个体的产生,并且设计自适应变异率,以提高算法的求解效率;其次,针对单亲遗传算法仅有变异操作可能导致最优解个体跳跃的问题,结合模拟退火的思想,来保证解的全局最优性;最后,在具体的度约束最小生成树问题中进行了三组实验,从运行时间和最优解的情况等方面与传统单亲遗传算法进行对比,实验表明该算法在求解效率和获得最优解方面都有较好的改进效果。     

RB模型实例集上置信传播算法的收敛性

置信传播算法求解RB（k,n,α,r_c,p）模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k,n,α,r_c,p）模型中,取k=2,α>（1/k）,r_c>0均为常数,且满足ke^{-（α/（r_c））}≥1.证明了如果p∈（0,n^-2α）,则置信传播算法在RB（k,n,α,r_c,p）模型产生的随机实例集上高概率收敛.最后,在RB（k,n,α,r_c,p）模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB（k,n,α,r_c,p）模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB（k,n,α,r_c,p）模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.     

一个基于模拟退火的多主体模型及其应用

近些年,多主体系统的理论及应用得到了人们的广泛关注,并得以迅速发展.研究者提出了很多基于多主体系统理论的模型,用于求解各种问题.AER(Agent-environment-rules)模型正是一个用于求解约束满足问题较为成功的例子.但是,主体的静态策略选择在一定程度上限制了模型的求解性能.将模拟退火算法与多主体系统思想相结合,并赋予主体更为高效的动态策略选择的能力,提出了SAAER模型(simulated annealing based AER model).基于约束满足问题经典实例--N-Queen问题和染色问题的实验表明,改进后的模型较之原模型获得了更高的效率和稳定性.对于N=10000的大规模N-Queen问题,能在200s左右的时间求得精确解.     

网格环境下资源负载均衡和优化调度研究

为了有效解决网格环境下资源的负载均衡问题,结合克隆算法,模拟退火算法和遗传算法的优点,提出了一种基于遗传模拟退火克隆算法的任务调度优化方法。仿真实验结果表明,该算法全局寻优能力强,能有效地实现资源的负载均衡,同时克服了遗传算法容易陷入局部最优的缺点,可以成功地应用于网格任务调度中。