结合引领策略的MMC求解最大约束满足问题

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (1): 134–.

结合引领策略的MMC求解最大约束满足问题

赵双梅1，2，崔佳旭1，2，张永刚1，2*

出版日期:2018-01-31 发布日期:2018-01-31
作者简介:1.吉林大学计算机科学与技术学院，长春，130012；
2．符号计算与知识工程教育部重点实验室(吉林大学)，长春，130012
基金资助:
基金项目：国家自然科学基金(61170314，61373052)，吉林省科技发展计划(20170414004GH)
收稿日期：2017－12－22
*通讯联系人，E－mail：zhangyg@jlu.edu.cn

Solving the MaxCSPs using MMC with teaching strategy

Zhao Shuangmei1，2，Cui Jiaxu1，2，Zhang Yonggang1，2*

Online:2018-01-31 Published:2018-01-31
About author:1.College of Computer Science and Technology，Jilin University，Changchun，130012，China；
2．Key Laboratory of Symbol Computation and Knowledge Engineering(Jilin University)，Ministry of Education，Changchun，130012，China

摘要/Abstract

摘要： 约束满足问题(Constraint Satisfaction Problem，CSP)是人工智能的一个重要研究方向，相关技术被广泛应用于配置、调度及规划等问题求解．但实际应用中，很多问题往往不存在满足所有约束的解，即呈现为过度约束．MaxCSP是处理过度约束一个简单而有效的框架，它的思想是求出满足尽可能多约束的解，其本质是约束优化问题．受元启发式算法在求解连续约束优化问题方面大量成功案例的启发，基于新近提出的作曲家算法(Method of Musical Composition，MMC)求解MaxCSP，在标准MMC算法的基础上引入引领策略，并将其离散化，以求解MaxCSP.最后，在广为流行的MaxCSP测试问题实例集上进行了求解测试并与改进的教与学(Teaching－learning－based Optimization，TLBO)算法和差分进化(Differential Evolution，DE)算法进行比较．实验结果表明，改进的算法无论对于求解可满足MaxCSP还是不可满足MaxCSP，都具有明显的优势．

Abstract: Constraint Satisfaction Problem(CSP)is an important research direction of artificial intelligence.It involves finding a value for each one of a set of problem variables which constraints specify that some subsets of values cannot be used together.It can model a wide range of combinatorial problems and has many applications in artificial intelligence，operations search，programming languages，databases and other areas of computer science.Common applications include configuration，scheduling and planning.A solution is an assignment of a single value from its domain to each variable and no constraint is violated.A problem may have one，many，or no solutions.If this problem has one or more solutions，we call it satisfiable or consistent.However，in practical，many problems always don’t have a solution which satisfies all the constraints which can be called “over constraints”．The Maximum Constraint Satisfaction Problem(MaxCSP)is the simplest and most effective framework to solve over－constrained satisfaction problems which we often meet in life.Its idea is to find solutions that satisfies as many constraints as possible.And its essence is to constrain optimization problem.Inspired by a large number of success experiences in solving the continuous constrained optimization problems using metaheuristic algorithm，we solve MaxCSP using the recently proposed MMC(Method of Musical Composition)algorithm.In this paper，we add the leading strategy based on the standard MMC algorithm and make it discretized to solve MaxCSP.Finally，we carry out experiments on the popular MaxCSP instance set and compare it with the improved Teaching－learning－based Optimization(TLBO)algorithm and Differential Evolution(DE)algorithm.The experimental results show that our improved algorithm has obvious advantages both on satisfied CSP and on unsatisfied CSP.

赵双梅1，2，崔佳旭1，2，张永刚1，2*. 结合引领策略的MMC求解最大约束满足问题[J]. 南京大学学报(自然科学版), 2018, 54(1): 134–.

Zhao Shuangmei1，2，Cui Jiaxu1，2，Zhang Yonggang1，2*. Solving the MaxCSPs using MMC with teaching strategy[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(1): 134–.

参考文献

[1]　Freuder E C，Mackworth A K．Constraint satisfaction：An emerging paradigm ∥ Rossi F．Handbook of Constraint Programming.Boston，MA，USA：Elsevier，2006：13－27.
[2] Bessière C．Constraint propagation ∥ Rossi F．Handbook of Constraint Programming.Boston，MA，USA：Elsevier，2006：29－84.
[3] 孙吉贵，高　健，张永刚．一个基于最小冲突修补的动态约束满足求解算法．计算机研究与发展，2007，44(12)：2078－2084.(Sun JG，Gao J，Zhang YG.Amini－conflict repair based algorithm for solving dynamic constraint satisfactionproblems.Journal of Computer Research and Development，2007，44(12)：2078－2084.)
[4] Van Beek P．Backtracking search algorithms.Foundations of Artificial Intelligence，2006，2：85－134.
[5] 李占山，张　乾，张　良．基于实例化次数的约束求解方法研究．计算机研究与发展，2015，52(5)：1091－1097.(Li Z S，Zhang Q，Zhang L．Constraint solving based on the number of instantiation.Journal of Computer Research and Development，2015，52(5)：1091－1097.)
[6] 杨轻云，孙吉贵，张居阳等．基于值序的二元约束满足问题粒子群算法．计算机工程，2006，32(17)：57－59.(Yang Q Y，Sun J G，Zhang J Y，et al.Particle swarm for binary CSPs based on value order.Computer Engineering，2006，32(17)：57－59.)
[7] 张永刚，张思博，薛秋实．求解约束满足问题的改进蚁群优化算法．通信学报，2015，36(5)：40－46.(Zhang Y G，Zhang S B，Xue Q S．Improved ant colony optimization algorithm for solving constraint satisfaction problem.Journal on Communications，2015，36(5)：40－46.)
[8] Mora－Gutiérrez R A，Ramírez－Rodríguez J，Rincón－García E A．An optimization algorithm inspired by musical composition.Artificial Intelligence Review，2014，41(3)：301－315.
[9] Rao R V，Savsani V J，Vakharia D P．Teaching－learning－based optimization：A novel method for constrained mechanical design optimization problems.Computer－Aided Design，2011，43(3)：303－315.
[10] Neri F，Tirronen V．Recent advances in differential evolution：A survey and experimental analysis.Artificial Intelligence Review，2010，33(1－2)：61－106.
[11] 崔佳旭．Mistral求解器扩展与应用研究．硕士论文．长春：吉林大学，2016.(Cui J X．Research on the extension and application of mistral solver.Master Dissertation.Changchun：Jilin University，2016.)
[12] de－los－Cobos－Silva S G，Mora－Gutiérrez R A，Gutiérrez－Andrade M A，et al.Development of seven hybrid methods based on collective intelligence for solving nonlinear constrained optimization problems.Artificial Intelligence Review，2016：1－35，doi：10.1007/s10462－016－9524－4.
[13] Rao R V，Patel V．An improved teaching－learning－based optimization algorithm for solving unconstrained optimization problems.Scientia Iranica，2013，20(3)：710－720.
[14] SilvaLópez R B，Miguel R E C，Rincón－García E A，et al.Method of musical composition and static topologies for resource constrained project scheduling：A case study.2013.
[15] Larrosa J，Meseguer P，Schiex T．Maintaining reversible DAC for Max－CSP.Artificial Intelligence，1999，107(1)：149－163.
[16] Mora－Gutiérrez R A，Rincón－García E A，Ponsich A，et al.Influence of social network on method musical composition.Artificial Intelligence Review，2016，46(2)：225－266.
[17] Benchmarks.XCSP3 is born！http：//www.cril.univ－artois.fr/～lecoutre/benchmarks.html. 2002.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed