通信学报 ›› 2015, Vol. 36 ›› Issue (5): 40-46.doi: 10.11959/j.issn.1000-436x.2015123

• 学术论文 • 上一篇    下一篇

求解约束满足问题的改进蚁群优化算法

张永刚,张思博,薛秋实   

  1. 1.吉林大学 计算机科学与技术学院,吉林 长春 130012;2.符号计算与知识工程教育部重点实验室,吉林 长春 130012
  • 出版日期:2015-05-20 发布日期:2015-07-17
  • 基金资助:
    国家自然科学基金资助项目;国家自然科学基金资助项目

Improved ant colony optimization algorithm for solving constraint satisfaction problem

HANGYong-gang Z,HANGSi-bo Z,UEQiu-shi X   

  1. 1.College of Comprter Science and Technology,Jilin university,Changchun 130012,China;2.Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education,Changchun 130012,China
  • Online:2015-05-20 Published:2015-07-17
  • Supported by:
    The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要:

为了克服传统的回溯算法在求解大型的约束满足问题时效率低,难以在合理的时间内求解这一问题。提出了基于启发式搜索的不完备性算法。结合不同算法特性,主要在蚁群优化元启发式约束求解算法的基础上提出了改进:一是在搜索之前用弧相容检查进行预处理以压缩搜索空间,二是提出了一种新的蚁群算法参数设置方案,提高算法的适应性。最后将改进后的算法应用于求解随机问题和组合优化问题。实验结果表明,改进后的算法求解效率得到大幅度提高。

关键词: 约束满足问题, 蚁群算法, 弧相容, 参数调节

Abstract:

The traditional backtracking algorithm was less efficient on solving large-scale constraint satisfaction problem,and more difficult to be solved within a reasonable time.In order to overcome this problem,many incompleteness algo-rithms based on heuristic search have been proposed.Two improvements based on ant colony optimization meta-heuristic constraint solving algorithm were presented:First,arc consistency checks was done to preprocess before exploring the search space,Second,a new parameter setting scheme was proposed for ant colony optimization to improve the effi-ciency of the search.Finally,the improved algorithm is applied to solve random problems and combinatorial optimization problems.The results of the experiment have showed its superiority.

Key words: constraint satisfaction problems, ant colony optimization, arc consistency, parameter adjustment

No Suggested Reading articles found!