Sciences

Abstract- Evolutionary algorithms (EAs) for solving constraint satisfaction problems (CSPs) can be roughly divided into two classes: EAs using adaptive fitness functions and EAs using heuristics. In [8] the most effective EAs of the first class have been compared experimentally using a large set of benchmark instances consisting of randomly generated binary CSPs. In this paper we complete this comparison by studying the most effective EAs of the second class. We test three heuristic based EAs on the same benchmark instances used in [8]. The results of our experiments indicate that the three heuristic based EAs have similar performance on random binary CSPs. Moreover, comparing these results with those in [8], we are able to identify the best EA for binary CSPs as the algorithm introduced in [3] which uses a heuristic as well as an adaptive fitness function.