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

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

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

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

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

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

非布尔问题系统求解算法的一种新思路

非布尔变量的约束可满足性问题有两种较为普遍的求解方法,系统求解算法就是其中的一种。该算法的基本思想是对变量的值域空间逐个进行搜索,其优点是只要问题有解,算法就一定能给出正确答案。在最不理想的情况下,该算法时间复杂度为变量数目的指数级。该文给出一种新策略,虽然在本质上仍然是在值域空间中进行搜索,但在实现过程中根据启发式思想,有针对性地设置搜索的优先次序。它的目的是尽可能的缩小搜索空间的范围,因为实践证明算法计算过程中许多状态不需要搜索。几个实例证明该策略在许多情况下有较为令人满意的性能。同时该文还给出相应的理论分析。     

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

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

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

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

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

基于ParetoHeu和实例化失败统计的关联启发式方法

变量排序启发式是约束规划求解约束满足问题中的一项关键技术,对求解效率有着重要影响。为进一步提高基于关联的变量排序启发式方法CRBS对问题求解的效率和能力,提出了一种基于ParetoHeu和实例化失败统计的关联启发式PICRBS。PICRBS采用源于帕累托最优的启发式组合方式ParetoHeu,将CRBS与经典的通用启发式dom/wdeg进行结合,同时加入基于实例化失败次数的权值统计方法,为问题求解选择最有可能导致搜索发生回溯的变量。实验结果显示,针对多个问题实例,该方法在问题求解效率上高于CRBS和主流变量排序启发式。     

钢铁企业生产能力平衡模型及启发式算法

针对钢铁企业生产能力平衡配置问题,建立了非线性数学模型,形式化地描述了钢铁产品对资源和能力的竞合关系,提出了平衡下的多个优化目标。针对问题的模型及其特点,提出了基于约束满足技术的启发式算法,算法通过优化目标指导变量排序,在变量赋值过程中采用约束传播和回溯技术,缩减变量值域、解消约束冲突,提高了计算效率。基于企业实际生产数据的仿真实验结果验证了模型和算法的有效性。     

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

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

基于动态奖惩的CDCL SAT求解器分支启发式算法

分支启发式算法在CDCL SAT求解器中有着非常重要的作用,传统的分支启发式算法在计算变量活性得分时只考虑了冲突次数而并未考虑决策层和冲突决策层所带来的影响。为了提高SAT问题的求解效率,受EVSIDS和ACIDS的启发,提出了基于动态奖惩DRPB的分支启发式算法。每当冲突发生时,DRPB通过综合考虑冲突次数、决策层、冲突决策层和变量冲突频率来更新变量活性得分。用DRPB替代VSIDS算法改进了Glucose 3.0,并测试了SATLIB基准库、2015年和2016年SAT竞赛中的实例。实验结果表明,与传统、单一的奖励变量分支策略相比,所提分支策略可以通过减少搜索树的分支和布尔约束传播次数来减小搜索树的规模并提高SAT求解器的性能。     

Sizing optimization of truss structures using flower pollination algorithm

The recently developed flower pollination algorithm is used to minimize the weight of truss structures, including sizing design variables. The new algorithm can efficiently combine local and global searches, inspired by cross-pollination and self-pollination of flowering plants, respectively. Furthermore, it implements an iterative constraint handling strategy where trial designs are accepted or rejected based on the allowed amount of constraint violation that is progressively reduced as the search process approaches the optimum. This strategy aims to obtain always feasible optimized designs. The new algorithm is tested using three classical sizing optimization problems of 2D and 3D truss structures. Optimization results show that the proposed method is competitive with other state-of-the-art metaheuristic algorithms presented in the literature.     

Variable ordering and constraint propagation for constrained CP-nets

A Conditional Preferences network (CP-net) is a known graphical model for representing qualitative preferences. In many real world applications we are often required to manage both constraints and preferences in an efficient way. The goal here is to select one or more scenarios that are feasible according to the constraints while maximizing a given utility function. This problem has been modelled as a CP-net where some variables share a set of constraints. This latter framework is called a Constrained CP-net. Solving the constrained CP-net has been proposed in the past using a variant of the branch and bound algorithm called Search CP. In this paper, we experimentally study the effect of variable ordering heuristics and constraint propagation when solving a constrained CP-net using a backtrack search algorithm. More precisely, we investigate several look ahead strategies as well as the most constrained heuristic for variable ordering during search. The results of the experiments conducted on random Constrained CP-net instances generated through the RB model, clearly show a significant improvement when adopting these techniques for specific graph structures as well as the case where a large number of variables are sharing constraints.     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

An adaptive penalty based covariance matrix adaptation–evolution strategy

Although most of unconstrained optimization problems with moderate to high dimensions can be easily handled with Evolutionary Computation (EC) techniques, constraint optimization problems (COPs) with inequality and equality constraints are very hard to deal with. Despite the fact that only equality constraints can be used to eliminate a certain variable, both types of constraints implicitly enforce a relation between problem variables. Most conventional constraint handling methods in EC do not consider the correlations between problem variables imposed by the problem constraints. This paper relies on the idea that a proper genetic operator, which captures mentioned implicit correlations, can improve performance of evolutionary constrained optimization algorithms. With this in mind, we employ a (μ+λ)-Evolution Strategy with a simplified variant of Covariance Matrix Adaptation based mutation operator along an adaptive weight adjustment scheme. The proposed algorithm is tested on two test sets. The outperformance of the algorithm is significant on the first benchmark when compared with five conventional methods. The results on the second test set show that algorithm is highly competitive when benchmarked with three state-of-art algorithms. The main drawback of the algorithm is its slightly lower speed of convergence for problems with high dimension and/or large search domain.     

A heuristic method for learning Bayesian networks using discrete particle swarm optimization

Bayesian networks are a powerful approach for representing and reasoning under conditions of uncertainty. Many researchers aim to find good algorithms for learning Bayesian networks from data. And the heuristic search algorithm is one of the most effective algorithms. Because the number of possible structures grows exponentially with the number of variables, learning the model structure from data by considering all possible structures exhaustively is infeasible. PSO (particle swarm optimization), a powerful optimal heuristic search algorithm, has been applied in various fields. Unfortunately, the classical PSO algorithm only operates in continuous and real-valued space, and the problem of Bayesian networks learning is in discrete space. In this paper, two modifications of updating rules for velocity and position are introduced and a Bayesian networks learning based on binary PSO is proposed. Experimental results show that it is more efficient because only fewer generations are needed to obtain optimal Bayesian networks structures. In the comparison, this method outperforms other heuristic methods such as GA (genetic algorithm) and classical binary PSO.