A colourful look on evolutionary techniques

Evolutionary techniques are solution methods inspired from natural evolution. They have aroused intense interest in the past few years. Numerous successful adaptations of these techniques have been designed for the solution of both theoretical and real-life optimisation problems. In this article we first describe the main ingredients of evolutionary techniques. We then illustrate how these ingredients have been integrated in known solution methods such as genetic algorithms, scatter search, path relinking and ant systems. The use of evolutionary techniques in combinatorial optimisation will be illustrated through four such approaches which have recently been proposed for the solution of graph colouring problems. We also discuss recent advances that offer an opportunity to create still more effective solution methods by combining evolutionary techniques with standard local search methods.