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

张永刚; 张思博; 薛秋实

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 求解约束满足问题的改进蚁群优化算法
- Improved ant colony optimization algorithm for solving constraint satisfaction problem
- 通信学报 2015年36卷第5期页码：40-46
- 作者机构：
  
  ．吉林大学计算机科学与技术学院，吉林长春 130012;2．符号计算与知识工程教育部重点实验室，吉林长春 130012
- 作者简介：
- 基金信息：
  
  国家自然科学基金资助项目(61170314);国家自然科学基金资助项目(61373052)
- DOI：10.11959/j.issn.1000-436x.2015123
  中图分类号： TP18
- 网络出版日期：2015-05，
  
  纸质出版日期：2015-05-25
- 稿件说明：
移动端阅览
张永刚, 张思博, 薛秋实. 求解约束满足问题的改进蚁群优化算法[J]. 通信学报, 2015,36(5):40-46.

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.
张永刚, 张思博, 薛秋实. 求解约束满足问题的改进蚁群优化算法[J]. 通信学报, 2015,36(5):40-46. DOI： 10.11959/j.issn.1000-436x.2015123.

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 .

浏览量

1616

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

结合look-ahead值排序的自适应分支求解算法

基于信息熵的蚁群聚类DBSCAN改进算法