Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
2014 Impact factor:

Evolutionary Computation

Winter 2006, Vol. 14, No. 4, Pages 433-462
(doi: 10.1162/evco.2006.14.4.433)
© 2006 by the Massachusetts Institute of Technology
Evolving Combinatorial Problem Instances That Are Difficult to Solve
Article PDF (391.76 KB)

This paper demonstrates how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. As a result of this technique, the corresponding algorithms used to solve these instances are stress-tested. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. The problem instances acquired through this technique are more difficult than the ones found in popular benchmarks. In this paper, these evolved instances are analysed with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.