导读:本文包含了约束满足求解论文开题报告文献综述及选题提纲参考文献，主要关键词:约束满足问题,帝王蝶优化算法,模拟退火策略,多仓库车辆路径问题
约束满足求解论文文献综述
王希彤[1]（2019）在《基于MBO的约束满足问题求解算法研究》一文中研究指出约束满足问题(Constraint Satisfaction Problem,CSP)求解算法研究一直以来都是人工智能领域的研究热点。通常一个变量集合、变量对应的各自论域集合和一个变量间约束的集合,就构成一个基本的约束满足问题。现实世界中许多调度、规划、配置等问题都可以采用约束满足问题来描述。但约束满足问题普遍具有较高的复杂性,除了经典求解算法之外,还可以采用启发式搜索方法在合理的时间内找到可行解甚至是最优解。而车辆路径问题(Vehicle Routing Problem,VRP)就是约束满足问题中的一种。它最早是由Dantzig和Ramser在1959年首次提出,指有特定数量的客户,他们各自都有对货物数量的不同需求,供应商由一个仓库向各个客户供货,选择合适的配送路线,满足客户的需求,并且在特定的约束条件下,能够达到成本最小、需要的时间最少或者路径最短等目标。在学术研究和实践应用中,基本VRP产生了很多变型,例如带有时间窗的VRP、多车型的VRP、带回程载货的VRP、多仓库VRP等。因为VRP是NP难问题,难以用精准算法求解,所以求解VRP的主要办法就是启发式算法。启发式算法中有一种是受自然启发算法。受自然启发算法一般是根据自然界中的某种群体的集体行为而受到启发,产生的新的算法。通常这种群体行为遵循着简单的规则。群智能和受自然启发算法在现在的研究中受到了极大的关注,尤其是基于群智能的算法。事实上,这些受自然启发的元启发式算法在优化、计算智能等领域已经被广泛应用了。受自然启发优化算法从它们探索、搜索空间上进行分析,本质上,均有两个主要的部分:开发和探索,也叫作强化和多样化。开发主要是从邻域的搜索空间中获取相关信息,来生成优于当前解的新解。但是在此过程中新解的产生总是表现为试图找到这个局部的最优,所以开发的优势就是通常会有很快地收敛速率,但它的劣势也很明显,就是很容易陷入局部最优。而探索则恰恰相反,通常来说,探索的搜索空间是全局范围内,这样搜索空间内的多样性更好,所以探索可以产生远离现有解的新解。探索的优点就是它不容易陷入局部最优,找到全局最优的可能性就会大大提高。但探索的缺点就是收敛速度较慢,并且会有一部分的计算量。因此,算法如何平衡好开发和探索的比例是很重要的,才能使算法的性能得到最好的发挥。帝王蝶优化算法(Monarch Butterfly Optimization,MBO)是Gai-Ge Wang等人在2015年提出的一种新的受自然启发算法。该算法通过简化和理想化帝王蝶的迁徙行为而得到的。算法将蝴蝶种群一分为二,一部分用于开发一部分用于探索,在迭代的过程中分别用迁移算子和蝴蝶调整算子来产生新一代种群。MBO算法的优点就是易操作,两个算子的运算过程理论上是可并行计算的。本文研究了MBO算法的原理和框架,分析了算法的搜索过程,在MBO算法对新一代个体做选择的时候,只有表现良好的新个体才会被保留下来。这使得算法容易陷入局部最优,所以我们加入了模拟退火策略来扰动当前的搜索空间,利于算法及时跳离局部最优。并且我们把新得到的算法用于去解决多仓库车辆路径问题,用实际问题来测试新得到的算法在实际应用中的性能。(本文来源于《吉林大学》期刊2019-05-22）
杨罡[2]（2019）在《基于约束满足问题求解算法的改进算法研究》一文中研究指出约束满足问题在人工智能领域有着广泛的应用。目前有许多求解约束满足问题的方法,本文对常用的求解约束满足问题的维持弧相容算法做了改进,对求解约束满足问题的效率起到至关重要的两个部分--弧相容和启发式分别做了改进,从两个方面整体地提高求解约束满足问题的效率。本文通过分析约束满足问题的粗粒度维持弧相容求解算法在弧相容(arc containing,AC)的执行过程,发现在对弧的修正检查算法中存在冗余的弧放回操作,并对弧的冗余放回给出了完整的证明。启发式是约束满足问题求解的一个重要组成部分,它通过一定的策略来选择并确定变量和值来搜索约束满足问题的解。目前已有许多成熟的变量启发式能够针对特定的问题属性进行搜索路径选择,但是由于针对性极强,一旦被求解问题针对的特性并不明显,则相应的启发式不能发挥选择作用,有时甚至使得问题求解效率下降极大。基于此,考虑设计一种鲁棒性强的启发式,来避免断崖式的求解效率波动。本文对约束满足问题求解的改进主要体现在以下两个方面:(1)在AC3算法的基础上提出了一种改进算法AC_AO通过保证弧的唯一性来避免冗余弧的放回队列的操作。这种通过维持弧的唯一性改进弧相容算法的模式可以形成框架并适用于AC系列算法,包括AC3算法、AC2001算法、AC3rm算法,本文将提出的改进算法框架AC_AO应用于AC3、AC2001、AC3rm算法与原算法做实验对比,实验结果表明,应用AC_AO算法框架后的AC系列算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间,AC_AO算法通过减少弧的检查进而减少修正函数的调用次数,从而提高AC的执行效率,缩短弧相容算法的执行时间。将AC_AO算法应用在维持弧相容算法求解的过程中对求解效率提高是非常有意义的。(2)提出了一种基于遗传选择的启发式方法,能够针对问题属性进行自适应地选择合适启发式指导变量选择。本文对该方法进行了详细分析与描述,将之与最新版本的Choco求解器中最常用的默认启发式domOverWdeg启发式、activityBased启发式作对比,并且针对遗传选择的启发式算法,分别做了两组实验,一组弧相容算法选择AC3算法,另一组弧相容算法选择AC_AO算法,分别进行约束满足问题的求解,实验结果表明在约束满足问题的求解上,AC_AO算法优于AC3算法。基于遗传选择的启发式算法的求解效率最高是domOverWdeg启发式的2.35倍,activityBased启发式的2.26倍。在求解效率的鲁棒性上也优于其他启发式算法。(本文来源于《吉林大学》期刊2019-04-01）
马柯帆,肖立权,张建民,黎铁军,周善祥[3]（2018）在《加强约束的布尔可满足硬件求解器》一文中研究指出利用现场可编程门阵列固有的并行性和灵活性,提出在硬件可编程平台上基于随机局部搜索算法的布尔可满足性求解器,用于求解大规模的布尔可满足性问题。相对其他求解器,该求解器的预处理技术能极大提高求解效率;其变元加强策略避免了同一变元被反复连续翻转,降低了搜索陷入局部最优的可能。评估结果表明,求解器最多能处理32 000个变元/128 000个子句的实例。相比当前同类型的求解器,其求解效率明显提高。(本文来源于《国防科技大学学报》期刊2018年06期）
吴拨荣,赵春艳,原志强[4]（2019）在《置信传播和模拟退火相结合求解约束满足问题》一文中研究指出约束满足问题是人工智能领域的一个重要问题。针对一个具有精确相变现象和能产生大量难解实例的随机约束满足问题,提出了置信传播和模拟退火相结合的求解算法。这种算法先通过置信传播方程收敛后得到变量取值的边际概率分布,分别采用最大概率和最小分量熵的策略产生一组启发式的初始赋值,再用模拟退火对这组赋值进行修正。实验结果表明,该算法大大提高了初始赋值向最优解收敛的速度,表现出了显着优越于模拟退火算法的求解性能。(本文来源于《计算机应用研究》期刊2019年05期）
赵双梅,崔佳旭,张永刚[5]（2018）在《结合引领策略的MMC求解最大约束满足问题》一文中研究指出约束满足问题(Constraint Satisfaction Problem,CSP)是人工智能的一个重要研究方向,相关技术被广泛应用于配置、调度及规划等问题求解.但实际应用中,很多问题往往不存在满足所有约束的解,即呈现为过度约束.MaxCSP是处理过度约束一个简单而有效的框架,它的思想是求出满足尽可能多约束的解,其本质是约束优化问题.受元启发式算法在求解连续约束优化问题方面大量成功案例的启发,基于新近提出的作曲家算法(Method of Musical Composition,MMC)求解MaxCSP,在标准MMC算法的基础上引入引领策略,并将其离散化,以求解MaxCSP.最后,在广为流行的MaxCSP测试问题实例集上进行了求解测试并与改进的教与学(Teaching-learningbased Optimization,TLBO)算法和差分进化(Differential Evolution,DE)算法进行比较.实验结果表明,改进的算法无论对于求解可满足MaxCSP还是不可满足MaxCSP,都具有明显的优势.(本文来源于《南京大学学报(自然科学)》期刊2018年01期）
杨明奇,李占山,李哲[6]（2017）在《优化求解约束满足问题的MDDc和STR3算法》一文中研究指出广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc,STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中,MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交迭部分的约束具有很好的压缩效果;STR3同STR2一样,基于动态维持有效元组的思想,当元组集规模缩减较慢时,STR3维持广义弧相容的效率高于STR2.通过深入分析发现,MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势,自适应地选择代价最小的实现方法.得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比,原算法速度提升显着,其中,AdaptiveSTR在一些问题上相比STR3提速3倍以上.(本文来源于《软件学报》期刊2017年12期）
原志强,赵春艳[7]（2017）在《两种改进的模拟退火算法求解大值域约束满足问题》一文中研究指出随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB(revised B)模型是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA(revised simulated annealing algorithm)和GSA(genetic-simulated annealing algorithm)。将这两种算法用于求解RB模型的随机实例,数值实验结果表明,在进入相变区域时,RSA和GSA依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。(本文来源于《计算机应用研究》期刊2017年12期）
吴帆[8]（2017）在《基于生化反应的典型约束可满足问题求解算法研究》一文中研究指出约束可满足问题,广泛存在于科学研究和工程实践中。如人力资源配置问题、农作物布局优化问题、工程设计方案优化问题和资源分配优化问题等,都属于约束可满足问题。这类问题的特点是在特定的约束条件下,寻找问题的解。此类问题的解决往往能带来很高的社会或经济价值。目前还没有高效的精确求解算法,由于这类问题通常可约化为典型的约束可满足问题,如最小顶点覆盖问题。因此可对典型约束可满足问题进行深入的理论研究,以寻找问题求解的新思路和新方法。如何求解约束可满足问题是研究约束可满足问题的核心。对于最小顶点覆盖等典型约束可满足问题,当问题规模较大时,传统的电子计算机求解算法很难实现精确求解。基于生化反应的DNA计算,是一种非传统的高性能计算方法。它具有高度的并行性,并行操作数目超过1018,能在多项式时间内精确求解NP难问题。这为约束可满足问题的精确求解提供了新的思路和方法。另外,受自然界生化反应的启发,科学家提出了化学反应优化算法,研究发现,该方法在近似求解NP问题时,往往能跳出局部极值的限制,比遗传算法、禁忌算法等启发式算法具有更加良好的分布性。基于此,通过分析基于生化反应的DNA计算和化学反应优化算法特征,本文研究了利用DNA计算和化学反应优化智能算法来求解典型约束可满足问题的关键技术,提出了若干相关算法,研究表明这些算法表现出了良好的性能和扩展性。论文的主要研究工作如下:提出了一种基于分治法的N皇后问题DNA计算算法(1)N皇后问题是一种典型的约束可满足问题。研究表明,基于粘贴模型求解该问题的DNA计算算法,可以在多项式时间内精确求解此问题,但参与反应的DNA链数是指数级的,这将导致求解过程中误解率较高,难以求解大规模问题的求解计算等问题。针对这些问题,本文提出了一种结合分治法,基于扩展粘贴模型来求解N皇后问题的DNA计算算法。通过算法分析和模拟实验表明:本算法的DNA链数是亚指数级的,将DNA链数从O(n")减少至O(nn/2),同时减少生物操作数,降低了误解率,测试试管数由所需的O(n)减少至O(1)。(2)提出了一种基于DNA自组装模型来求解最小顶点覆盖问题的DNA计算算法。尽管基于扩展粘贴模型,利用分治法可以以亚指数的DNA链数求解N皇后问题,但由于参与生化反应的是DNA单链分子,其误解率依然较高。为此,本文提出了一种基于DNA自组装模型来求解最小顶点覆盖问题的DNA计算算法。自组装模型是近年DNA计算领域提出的一种计算模型,具有降低问题求解过程中生化操作和生化解误解率等优点。本文描述了编码方案、问题求解算法以及进行了模拟实验。实验表明,本算法能快速精确求解出最小顶点覆盖问题。同时算法通过减少计算过程中操作步骤数,降低了生化解的错误率,提高了生化解的准确性,算法的生化实验复杂度低,具有良好的易操作性。(3)提出一种利用连接分子与自组装模型求解N皇后问题的DNA计算算法最小顶点覆盖问题的约束条件单一。针对具有多约束条件下的N皇后问题,本文研究了基于自组装模型的DNA计算算法。N皇后问题具有四个约束条件,即棋盘行、列和两个对角线上不能存在皇后冲突。本文通过设计连接分子,巧妙地利用它将多个约束条件组合在一起从而实现了基于自组装模型的N皇后问题求解DNA计算算法。模拟实验表明,本方法是有效的,且具有良好的扩展性。算法使用的tiles分子块种类为Θ(2n),生化操作复杂性为Θ(1),其中n为皇后的个数。(4)提出了 一种基于混合CRO求解N皇后问题的算法利用DNA计算在多项式时间内可以精确求解典型约束可满足问题,其实质是利用DNA计算的巨大并行性并利用穷举方法从而实现求解计算,参与计算的DNA分子链数或tiles分子数是指数级或亚指数级的。尽管许多科学家也提出了许多改善生化反应中产生错误解的方法,然而,针对规模较大的问题求解时,目前DNA计算依然无法将误解率减少到可以接受的水平。智能启发式算法依然是约束可满足问题一种高效的近似求解算法。化学反应优化算法是近年提出来的一种智能启发式算法,该算法能避免搜索陷入局部最优,具有提高问题搜索空间的优点,局部最优搜索是基于贪婪法的快速搜索算法,该算法具有收敛速度快等优点。因此本文将这两个算法融入到一起,设计了混合CRO算法来求解N皇后问题。实验分析表明,跟其它启发式算法相比,本算法具有良好的分布性和收敛速度,能提高N皇后问题求解的效率。(本文来源于《湖南大学》期刊2017-01-12）
王瑞伟,李占山,李宏博[9]（2016）在《求解约束可满足问题的eSTR算法优化》一文中研究指出表约束方法是1种外延式知识表示方法,每个约束通过元组集直接枚举出其在1个变量集上允许或禁止的所有元组,直观易于理解,在约束程序中得到了深入的研究,这是因为表约束出现在如设计、数据库、配置以及偏好建模等许多现实世界的应用中.但随着约束的增多及其元组集增大,占有的空间与相容性检测效率成了关键问题.eSTR是1个将STR扩展到高阶相容的算法,通过深入分析eSTR算法后发现有2种优化方式:PWsup数据结构和极小约束范围,同时证明了在极小约束范围上,约束网络仍然能够维持PWC+GAC,其中极小约束范围可以通过删除约束元组集中相应的列来降低eSTR2算法的空间消耗,而PWsup数据结构能够通过避免不必要的PW支持检测来减少eSTR2的CPU运行时间,实验结果表明:2种优化方式和eSTR2相结合后能够同时减少算法的空间消耗和CPU运行时间,在许多类实例上明显优于eSTR2和eSTR2w.(本文来源于《计算机研究与发展》期刊2016年07期）
徐周波,杨新亮,古天龙,宁黎华[10]（2015）在《加权约束满足问题的改进RDS符号代数决策图求解算法》一文中研究指出加权约束满足问题(WCSP)是一类约束最优化问题.文中基于RDS思想,从减少RDS分解的子问题个数及提高各个子问题的求解效率入手,提出WCSP的改进RDS符号代数决策图(ADD)求解算法.通过改进最多约束变量的变量选择法,引入RDS变量引导原问题的子问题分解,进而减少RDS中分解的子问题个数.利用变量的后向度,进一步改进子问题的分解方法.为提高各个子问题的求解效率,利用桶消元算法并结合ADD操作消去子问题中的非RDS变量,进而减少子问题中的变量个数,提高深度优先分支界定法的下界.在大量随机生成的测试用例上的实验证明文中算法的优越性.(本文来源于《模式识别与人工智能》期刊2015年12期）
约束满足求解论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
约束满足问题在人工智能领域有着广泛的应用。目前有许多求解约束满足问题的方法,本文对常用的求解约束满足问题的维持弧相容算法做了改进,对求解约束满足问题的效率起到至关重要的两个部分--弧相容和启发式分别做了改进,从两个方面整体地提高求解约束满足问题的效率。本文通过分析约束满足问题的粗粒度维持弧相容求解算法在弧相容(arc containing,AC)的执行过程,发现在对弧的修正检查算法中存在冗余的弧放回操作,并对弧的冗余放回给出了完整的证明。启发式是约束满足问题求解的一个重要组成部分,它通过一定的策略来选择并确定变量和值来搜索约束满足问题的解。目前已有许多成熟的变量启发式能够针对特定的问题属性进行搜索路径选择,但是由于针对性极强,一旦被求解问题针对的特性并不明显,则相应的启发式不能发挥选择作用,有时甚至使得问题求解效率下降极大。基于此,考虑设计一种鲁棒性强的启发式,来避免断崖式的求解效率波动。本文对约束满足问题求解的改进主要体现在以下两个方面:(1)在AC3算法的基础上提出了一种改进算法AC_AO通过保证弧的唯一性来避免冗余弧的放回队列的操作。这种通过维持弧的唯一性改进弧相容算法的模式可以形成框架并适用于AC系列算法,包括AC3算法、AC2001算法、AC3rm算法,本文将提出的改进算法框架AC_AO应用于AC3、AC2001、AC3rm算法与原算法做实验对比,实验结果表明,应用AC_AO算法框架后的AC系列算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间,AC_AO算法通过减少弧的检查进而减少修正函数的调用次数,从而提高AC的执行效率,缩短弧相容算法的执行时间。将AC_AO算法应用在维持弧相容算法求解的过程中对求解效率提高是非常有意义的。(2)提出了一种基于遗传选择的启发式方法,能够针对问题属性进行自适应地选择合适启发式指导变量选择。本文对该方法进行了详细分析与描述,将之与最新版本的Choco求解器中最常用的默认启发式domOverWdeg启发式、activityBased启发式作对比,并且针对遗传选择的启发式算法,分别做了两组实验,一组弧相容算法选择AC3算法,另一组弧相容算法选择AC_AO算法,分别进行约束满足问题的求解,实验结果表明在约束满足问题的求解上,AC_AO算法优于AC3算法。基于遗传选择的启发式算法的求解效率最高是domOverWdeg启发式的2.35倍,activityBased启发式的2.26倍。在求解效率的鲁棒性上也优于其他启发式算法。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
约束满足求解论文参考文献
[1].王希彤.基于MBO的约束满足问题求解算法研究[D].吉林大学.2019
[2].杨罡.基于约束满足问题求解算法的改进算法研究[D].吉林大学.2019
[3].马柯帆,肖立权,张建民,黎铁军,周善祥.加强约束的布尔可满足硬件求解器[J].国防科技大学学报.2018
[4].吴拨荣,赵春艳,原志强.置信传播和模拟退火相结合求解约束满足问题[J].计算机应用研究.2019
[5].赵双梅,崔佳旭,张永刚.结合引领策略的MMC求解最大约束满足问题[J].南京大学学报(自然科学).2018
[6].杨明奇,李占山,李哲.优化求解约束满足问题的MDDc和STR3算法[J].软件学报.2017
[7].原志强,赵春艳.两种改进的模拟退火算法求解大值域约束满足问题[J].计算机应用研究.2017
[8].吴帆.基于生化反应的典型约束可满足问题求解算法研究[D].湖南大学.2017
[9].王瑞伟,李占山,李宏博.求解约束可满足问题的eSTR算法优化[J].计算机研究与发展.2016
[10].徐周波,杨新亮,古天龙,宁黎华.加权约束满足问题的改进RDS符号代数决策图求解算法[J].模式识别与人工智能.2015