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

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

Abstract

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

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.

Figures/Tables 5

References 12

[1]	LECOUTRE C . Constraint Networks:Techniques and Algorithms[M]. London: John Wiley ＆ Sons,Inc 2009
[2]	GOLOMB S W , BAUMERT L D . Backtrack programming[J]. Journal of the ACM, 1965,(12): 51-524.
[3]	DORIGO M . Optimization,Learning and Natural Algorithms[D]. Politecnico di Milano, 1992
[4]	SOLNON C . Ants can solve constraint satisfaction problems[J]. IEEE Transactions on Evolutionary Computation, 2002,6(4): 347-357.
[5]	CORMEN T H , et al. Introduction to Algorithms[M]. Cambridge MIT Press, 2001. 840-890.
[6]	EIBEN A E , MICHALEWICZ Z , SCHOENAUER M , et al. Parameter Control in Evolutionary Algorithms[M]. Springer Berlin Heidelberg, 2007.
[7]	SMITH B , DYER M . Locating the phase transition in binary constraint satisfaction problems[J]. Artificial Intelligence, 1996,81(1): 155-181.
[8]	CHEESEMAN P , KANEFSKY B , TAYLOR . Where the really hard problems are[A]. Proceedings of IJCAI[C]. 1991. 331-337.
[9]	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.
[10]	CARBON B , et al. Radio link frequency assignment[J]. Constraints, 1999,(4): 79-89.
[11]	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.
[12]	PARLETT P . The Penguin Book of Patience[M]. Penguin Press, 1996.

Metrics

Recommended 0

No Suggested Reading articles found!

随机问题	求解时间/s		冲突数/对
随机问题	Ant-Solver	AC-AS	Ant-Solver	AC-AS
100-8-14-24	18.203	9.500	0	0
100-8-14-25	3.484	3.375	0	0
100-8-14-26	18.829	42.079	2	2
100-8-14-27	6.750	1.437	6	6
100-8-14-28	2.422	1.078	5	5

随机问题
	求解时间/s		冲突数/对
	Ant-Solver	AC-AS	Ant-Solver	AC-AS
35-17-1-bis	1.047	0.594	0	0
40-19-1-bis	1.656	1.016	0	0
45-21-1-bis	0.453	8.984	0	1
50-23-1-bis	12.781	3.015	1	0

随机问题	求解时间/s		冲突数/对
随机问题	Ant-Solver	AC-AS	Ant-Solver	AC-AS
	1.594	1.578	0	0
geom-50-20-d4-75	0.296	0.313	0	0
	2.375	0.578	0	0
	1.250	0.375	0	0
composed-25-10-20	2.203	0.344	0	0
	0.610	0.343	0	0
ehi-85	8.375	1.704	9	9
ehi-90	6.312	2.238	9	9

组合优化问题		求解时间/s		冲突数/对
组合优化问题		Ant-Solver	AC-AS	Ant-Solver	AC-AS
domino	1000-10	5.625	0.125	0	0
	100-100	3.578	1.438	0	0
	100-200	18.641	11.188	0	0
bqwh	15-106	0.297	0.688	0	0
bqwh	18-141	0.625	2.328	0	0
hanoi	6	0.125	0.109	0	0
	14	0.140	0.125	1	0
	30	1.610	0.266	1	0
qwh	10	0.203	0.141	0	0
	15	1.547	1.375	0	0
	20	12.687	13.469	2	0
	p10	0.187	0.140	0	0
	p15	0.938	0.328	0	0
qcp	10	0.203	0.157	0	0
	15	7.000	2.203	0	0
	20	51.328	43.547	0	0
	p10	0.218	0.172	0	0
	p15	5.813	0.375	0	0
	p20	26.797	6.984	0	0
qa	26	0.360	0.219	0	0
	37	8.734	0.937	0	0
	50	24.875	8.718	0	0
rlfap	mGraph	51.188	28.687	1	0
rlfap	mScen	22.797	12.734	1	0
bh	4-7	1.422	0.829	11	10
bh	4-13	27.39	16.922	14	14

Improved ant colony optimization algorithm for solving constraint satisfaction problem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 12

Related Articles 7

Metrics

Recommended 0

[1]	Qiuyang GU, Chunhua JU, Gongxing WU. Social network link prediction method based on subgraph evolution and improved ant colony optimization algorithm [J]. Journal on Communications, 2020, 41(12): 21-35.
[2]	Gang LI,Zhijun WU. Task scheduling algorithm for system-wide information management based on multiple QoS constraints [J]. Journal on Communications, 2019, 40(7): 27-37.
[3]	Xian-min MA,IUN L. Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem [J]. Journal on Communications, 2014, 35(1): 1-6.
[4]	. Novel adaptive branching constraint solving algorithm with look-ahead strategy [J]. Journal on Communications, 2013, 34(6): 12-107.
[5]	Hai-yan WANG,YANGDan-tong OU,Yong-gang ZHANG,Liang ZHANG. Novel adaptive branching constraint solving algorithm with look-ahead strategy [J]. Journal on Communications, 2013, 34(6): 102-107.
[6]	Yong-hua ZHANG,Fei-ming DU,Dai-wen WU. Improved density-dased clustering algorithm based on information entropy and ant colony optimization abstract [J]. Journal on Communications, 2012, 33(Z2): 290-293.
[7]	Yan-jing SUN,Wei FANG,Wei-dong LIU,Chong MENG. Differentiated service and ant colony optimization based routing protocol for wireless multimedia sensor networks [J]. Journal on Communications, 2012, 33(Z2): 9-14.