Abstract
We demonstrate how evolutionary computation can be used to acquire difficult to solve
combinatorial problem instances. The technique is applied to three important domains of
combinatorial optimisation: binary constraint satisfaction, Boolean satisfiability,
and the travelling salesman problem. Problem instances acquired through this technique
are more difficult than ones found in popular benchmarks. We analyse these evolved
instances with the aim to explain their difficulty in terms of structural properties,
thereby exposing the weaknesses of corresponding algorithms.
Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |