Evaluating and Improving Steady State Evolutionary Algorithms on Constraint Satisfaction Problems
K. van der Hauw · 1996
Currently there is a growing interest in the evolutionary algorithm paradigm, as it promises a robust and general search technique. Still, in spite of much research, for many people the question remains how good evolutionary algorithms really are. Therefore, in this research, a successful class of evolutionary algorithms, Steady State evolutionary algorithms, is thoroughly examined to find optimal settings on two NP-complete problems: Graph 3-Coloring and 3-Satisfiability. Several versions of the evolutionary algorithm are tested and evaluated and the best version for each NP-complete problem is compared to a good existing algorithm for each problem. Then extensions for the evolutionary algorithm are presented that make the evolutionary algorithms perform better than the more traditional algorithms on the hardest problem instances. i Preface This research was done as a Master's Thesis for graduating in Computer Science at Leiden University. It is about evolutionary algorithms, searc...