Improved ant colony optimization algorithm for solving constraint satisfaction problem
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 ba...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2015-05-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015123/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850096331290312704 |
|---|---|
| author | HANGYong-gang Z HANGSi-bo Z UEQiu-shi X |
| author_facet | HANGYong-gang Z HANGSi-bo Z UEQiu-shi X |
| author_sort | HANGYong-gang Z |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c68f0c5cd12c4f31b93afc5efae19983 |
| institution | DOAJ |
| issn | 1000-436X |
| language | zho |
| publishDate | 2015-05-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-c68f0c5cd12c4f31b93afc5efae199832025-08-20T02:41:15ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2015-05-0136404659692761Improved ant colony optimization algorithm for solving constraint satisfaction problemHANGYong-gang ZHANGSi-bo ZUEQiu-shi XThe 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.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015123/constraint satisfaction problemsant colony optimizationarc consistencyparameter adjustment |
| spellingShingle | HANGYong-gang Z HANGSi-bo Z UEQiu-shi X Improved ant colony optimization algorithm for solving constraint satisfaction problem Tongxin xuebao constraint satisfaction problems ant colony optimization arc consistency parameter adjustment |
| title | Improved ant colony optimization algorithm for solving constraint satisfaction problem |
| title_full | Improved ant colony optimization algorithm for solving constraint satisfaction problem |
| title_fullStr | Improved ant colony optimization algorithm for solving constraint satisfaction problem |
| title_full_unstemmed | Improved ant colony optimization algorithm for solving constraint satisfaction problem |
| title_short | Improved ant colony optimization algorithm for solving constraint satisfaction problem |
| title_sort | improved ant colony optimization algorithm for solving constraint satisfaction problem |
| topic | constraint satisfaction problems ant colony optimization arc consistency parameter adjustment |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015123/ |
| work_keys_str_mv | AT hangyonggangz improvedantcolonyoptimizationalgorithmforsolvingconstraintsatisfactionproblem AT hangsiboz improvedantcolonyoptimizationalgorithmforsolvingconstraintsatisfactionproblem AT ueqiushix improvedantcolonyoptimizationalgorithmforsolvingconstraintsatisfactionproblem |