A comparison of genetic local search algorithms for binary quadratic programming

摘要

It is known that Genetic Local Search (GLS) is one of the most powerful meta-heuristics for a wide variety of optimization problems. The GLS is generally composed of local search and genetic operators such as selection, crossover and mutation operators. In this paper, we apply the GLS to the unconstrained binary quadratic programming problem (BQP) and conduct to compare search performance of four GLS algorithms implemented according to the GLS framework we provide. Difference among four algorithms is only a phase of the local search in the framework. Comparison results show that the difference of the local search incorporated has a strong influence on the quality of resulting solutions found by the GLS algorithms.