Solving large binary quadratic programming problems by effective genetic local search algorithm
Kengo Katayama, Masafumi Tani, Hiroyuki Narihisa · 2000
A genetic local search (GLS) algorithm, which is a combination technique of ge-netic algorithm and local search, for the un-constrained binary quadratic programming problem (BQP) is presented. An effective lo-cal 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 prob-lem 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 aver-age solution values obtained are better than previous powerful heuristic approaches espe-cially for the large problem instances of 2,500 variables. 1