01 现在的位置:首页 > 期刊导读 > 2018 > 01 >

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

【作者】 赵双梅 崔佳旭 张永刚

【关键词】 约束满足问题 Max-CSP 作曲家算法 引领策略 教与学算法 差分进化算法

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

上一篇: 具有掩盖图像的像素不扩展的(2,2)视觉密码方案
下一篇: 面向单调分类的简洁单调TSK模糊系统

版权所有:《南京大学学报(自然科学版)》 苏ICP备10085945号
地址:江苏省南京市鼓楼区汉口路22号,《南京大学学报》编辑部,210093