基于差分进化的约束求解算法研究

《基于差分进化的约束求解算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP31单位代码：10183研究生学号：2013534020密级：公开吉林大学硕士学位论文（专业学位）基于差分进化的约束求解算法研究ResearchonConstraintSolvingAlgorithmsBasedonDifferentialEvolution作者姓名：刘文壮类别：工程硕士领域（方向）：计算机技术指导教师：张永刚副教授培养单位：计算机科学与技术学院2016年5月未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行Ｖ出租、改编等有碍作者著作权的商业性

2、使用。否（但纯学术性使用不在此限）则，应承担侵权的法律责任。吉林大学硕：ｔ学位论文原创性声明，本人郑重声明，是本人在指导教师的指导下；所呈义的硕±学位论文。独立进行研究王作所取得的成果除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究。做出重叟贡献的个人和集体，均已化文中＾义明确方式标明本人完全意识到本声明的法律结果由本人承担。是－．学位论文作者签名：句＞１＾日期：２０１６年ｔ月基于差分进化的约束求解算法研究ResearchonConstraintSolvingAlgorithmsBas

3、edonDifferentialEvolution作者姓名：刘文壮领域（方向）：计算机技术指导教师：张永刚副教授学位类别：工程硕士答辩日期：2016年5月25日摘要摘要基于差分进化的约束求解算法研究约束满足问题（ContraintSatisfactionProblems,CSPs）是运筹学和人工智能研究领域的一个重要方向，在人们身边，众多实际问题都能够转化为CSPs来求解。CSPs研究大体上分为表示领域的语言方向和推理领域的算法方向，这两个方向是CSPs研究的两大重要方向，若再细分，表示可分为通用表示和专用表示，推理又可分为约束传播和搜索。CSPs通常都是NP-hard问题

4、，它是由一个变量集合和一个约束集合组成的，求解CSPs也就是为它的变量集合寻找一组赋值，并使其满足它的约束集合，这样的一组赋值就称为CSPs的解。而求解CSPs的方法一般可分为完备性求解算法和非完备性算法。完备性求解算法是基于回溯的搜索算法(BT-backtrackingalgorithm)，该算法在选择实例化变量时，采用深度优先策略，若未找到解则启动回溯机制，直到找到一组解，或者证明该问题是无解的；非完备性求解算法一般是指群体智能算法，通过模拟生物群体的一些行为（如觅食，集聚，进化等），经过迭代最终寻找到最优解，本文所涉及的群体智能算法是差分进化算法。在差分进化算法中，变

5、量的每个可能解叫做参数向量或者基因，差分进化的求解步骤与标准进化算法（EvolutionaryAlgorithm,EA）大体相同，但却不同于传统进化算法，差分进化算法主要依赖差分向量来扰动当前的试验向量，利用参数向量的差异来探索目标区域。自上世纪90年代后期，在科学与工程领域的优化问题中，差分进化算法的影响力逐步增强，并且有着重要的地位。它的优势明显，首先，与其它进化算法相比，差分进化算法更易直接实现，无论用什么程序语言，算法的主体仅需四到五行代码就可以编写出来；其次，在求解单峰、多峰、离散、连续等问题时，差分进化算法展现出了较好的性能优势，超越了很多算法；再次，差分进化算

6、法的控制参数较少，主要包括种交叉概率CR、缩放系数F、种群规模NP三个控制参数，算法的性能主要也是取决于这三个控制参数；最后，与一些最有竞争力的实参优化器（如自适应协方差矩阵进化策略CMA-ES）相比，差分进化算法的空间复杂度较低。本文提出了基于弧相容技术AC的自适应差分进化算法——AC-FSADE算法，I摘要与SADE算法相比，该算法有着三处改进部分，首先，对控制变异操作的缩放系数F进行基于个体适应度的更新，进化开始阶段，缩放系数F较大，搜索步长，有助于算法开拓探索空间，进化后期，缩放系数F较小，搜索步短，有助于算法快速收敛；其次，对控制交叉操作的交叉概率CR也进行基于个

7、体适应度的更新，进化开始阶段，交叉概率CR较小，防止早熟收敛，有助于保持种群多样性，进化后期，交叉概率CR较大，有助于个体保留较好的基因；最后，将弧相容技术AC融入SADE算法中，剔除变量论域中的无效值，减小变量论域，简化算法求解的问题，提高求解成功率。实验结果表明，本文提出AC-FSADE算法有效地提高了算法的求解成功率,与SADE算法相比求解成功率提高了22%左右。所以，在求解CSPs时，AC-FSADE算法是一种比较有潜力的差分进化算法，发展前景广阔。关键词：约束满足问题、差分进化算法，弧相容，自适应，参数调