Improved ant colony optimization algorithm for solving constraint satisfaction problem

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

doi:10.11959/j.issn.1000-436x.2015123

您当前的位置：

首页 >

文章列表页 >

Improved ant colony optimization algorithm for solving constraint satisfaction problem

Academic paper | 更新时间：2024-06-05

- Improved ant colony optimization algorithm for solving constraint satisfaction problem
- Journal on Communications Vol. 36, Issue 5, Pages: 40-46(2015)
- 作者机构：
  
  ．吉林大学计算机科学与技术学院，吉林长春 130012;2．符号计算与知识工程教育部重点实验室，吉林长春 130012
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61170314);The National Natural Science Foundation of China(61373052)
- DOI：10.11959/j.issn.1000-436x.2015123
  CLC： TP18
- Online First：2015-05，
  
  Published：25 May 2015
- 稿件说明：
移动端阅览
HANGYong-gang Z, HANGSi-bo Z, UEQiu-shi X. Improved ant colony optimization algorithm for solving constraint satisfaction problem[J]. Journal on Communications, 2015, 36(5): 40-46.
DOI：

HANGYong-gang Z, HANGSi-bo Z, UEQiu-shi X. Improved ant colony optimization algorithm for solving constraint satisfaction problem[J]. Journal on Communications, 2015, 36(5): 40-46. DOI： 10.11959/j.issn.1000-436x.2015123.

摘要

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

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.

关键词

Keywords

references

LECOUTRE C . Constraint Networks:Techniques and Algorithms [M ] . London : John Wiley ＆ Sons,Inc 2009

GOLOMB S W , BAUMERT L D . Backtrack programming [J ] . Journal of the ACM , 1965 ,( 12 ): 51 - 524 .

DORIGO M . Optimization,Learning and Natural Algorithms [D ] . Politecnico di Milano , 1992

SOLNON C . Ants can solve constraint satisfaction problems [J ] . IEEE Transactions on Evolutionary Computation , 2002 , 6 ( 4 ): 347 - 357 .

CORMEN T H , et al . Introduction to Algorithms [M ] . Cambridge MIT Press , 2001 . 840 - 890 .

EIBEN A E , MICHALEWICZ Z , SCHOENAUER M , et al . Parameter Control in Evolutionary Algorithms [M ] . Springer Berlin Heidelberg , 2007 .

SMITH B , DYER M . Locating the phase transition in binary constraint satisfaction problems [J ] . Artificial Intelligence , 1996 , 81 ( 1 ): 155 - 181 .

CHEESEMAN P , KANEFSKY B , TAYLOR . Where the really hard problems are [A ] . Proceedings of IJCAI [C ] . 1991 . 331 - 337 .

GOMES C , SHMOYS D . Completing quasigroups or latin squares:a structured graph coloring problem [A ] . Proceedings of Computational Symposium on Graph Coloring and Generalization [C ] . 2002 . 22 - 39 .

CARBON B , et al . Radio link frequency assignment [J ] . Constraints , 1999 ,( 4 ): 79 - 89 .

SADEH N , FOX M S . Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem [J ] . Artificial Intelligence , 1996 , 86 ( 1 ): 1 - 41 .

PARLETT P . The Penguin Book of Patience [M ] . Penguin Press , 1996 .

Views

2020

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Novel adaptive branching constraint solving algorithm with look-ahead strategy

Improved density-dased clustering algorithm based on information entropy and ant colony optimization abstract

Related Author

Hai-yan WANG

YANGDan-tong OU

Yong-gang ZHANG

Liang ZHANG

Yong-hua ZHANG

Fei-ming DU

Dai-wen WU

Related Institution

College of Computer Science and Technology, Jilin University

Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University

College of Computer, Jilin Normal University

Department of Economic Management,Hunan Industry Polytechnic

AI问答

⁰