On fundamental design of iterated local search heuristic for binary quadratic programming

摘要

It is known that Iterated Local Search (ILS) algorithm is one of the met a-heuristics which can be applied to various optimization problems. In order to design the ILS to one optimization problem, we require the following matters: 1) a local search heuristic employed, 2) a method to create different solutions from solutions found by the local search, and 3) selection of solutions used in the method of 2). In this paper we describe the matters required for designing of the ILS and investigate performances of various ILS algorithms for the unconstrained binary quadratic programming problem.