Solving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function (bibtex)

by AE Eiben, van Hemert, J, E Marchiori and AG Steenbeek

Abstract:

This paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in binary CSPs.

Reference:

Solving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function (AE Eiben, van Hemert, J, E Marchiori and AG Steenbeek), In Parallel Problem Solving from Nature (AE Eiben, Th. Bäck, M Schoenauer, H-P Schwefel, eds.), Springer, 1998.

Bibtex Entry:

@article{EHMS98,
	_address = {Amsterdam, The Netherlands},
	_day = {20},
	abstract = {This paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in binary CSPs.},
	author = {AE Eiben and van Hemert, J and E Marchiori and AG Steenbeek},
	journal = {Parallel Problem Solving from Nature},
	date-added = {2008-08-18 12:44:11 +0100},
	date-modified = {2009-01-22 21:45:37 +0000},
	editor = {AE Eiben and Th. B{\"a}ck and M Schoenauer and H-P Schwefel},
	keywords = {constraint satisfaction},
	notedisabled = {\textsc{Cited by 34 (Google Scholar 2008/01/19)}},
	number = {1498},
	pages = {196--205},
	ps.gz = {http://www.vanhemert.co.uk/publications/ppsn98.Solving_Binary_Constraint_Satisfaction_Problems_using_Evolutionary_Algorithms_with_an_Adaptive_Fitness_Function.ps.gz},
	publisher = {Springer},
	series = {{LNCS}},
	title = {Solving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function},
	year = {1998}}