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

• 作者: 崔佳旭 张永刚 赵双梅
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 约束满足问题 Max-CSP 作曲家算法 引领策略 教与学算法 差分进化算法
• 年，卷（期）: 2018,（1）
• 页码范围: 134-147
• 页数: 14页
• 分类号: TP181
• 字数: 7537字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2018.01.015

摘要

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