A genetic local search (GLS) algorithm, which is a combination technique of genetic algorithm and local search, for the unconstrained binary quadratic programming problem (BQP) is presented. An effective local search algorithm, which is a variant of the k-opt local search for the BQP by Merz et al., is described, and the performance of the GLS with the variant local search heuristic is demonstrated on several large-scale problem instances. Our computational results indicate that the GLS is able to frequently find the best-known solution with a relatively short running time and obviously our average solution values obtained are better than previous powerful heuristic approaches especially for the large problem instances of 2,500 variables.
展开▼
