Evolving instances of unconstrained binary quadratic programming that challenge a tabu search heuristic
Michael Porta, Bryant A. Julstrom · 2012
A Tabu Search heuristic for unconstrained binary quadratic programming performs perfectly on a range of random problem instances. A genetic algorithm searches spaces of UBQP instances for instances that challenge the heuristic. The GA's evaluation step compares the performance of the Tabu Search to that of a memetic algorithm on the candidate instance being evaluated. On UBQP instances evolved by the GA, the TS heuristic returns solutions that are inferior to those of the memetic algorithm by significant margins.