An experimental comparison of SAWing EAs for a new class of random binary CSPs

Evolutionary approaches to constraint satisfaction problems (CSPs) are often tested on a set of randomly generated instances. Recently it has been shown that the frequently used random problem instance generators are not good enough. This implies that conclusions based on the usage of these generators need to be revised. In this paper, we perform an extensive experimental comparison of CSP solving EAs based on a new, improved generator. In particular, we compare two representations, two evaluation functions and EAs with and without the so-called SAWing mechanism, each of these with different population sizes and variation operators. The resulting systematic overview confirms some "myths", while refutes others. Most notably, the role of the population size and that of SAWing itself turn out to be different from what is usually assumed