バイナリー2次計画問題に対する遺伝的局所探索法の適用(自然科学)

概要

論文の詳細を見る
Since many of combinatorial optimization problems are NP-hard, it is known that it is very difficult to calculate an optimal solution. However, actually, if a solution with accuracy high to some extent can be calculated even if there is no guarantee of optimal nature, it is sufficiently satisfactory in many cases. An approximate algorithm is used for such a purpose. It is known that local search (LS), which is one of the basic strategies of an approximate algorithm can calculate a solution with the accuracy high, which is comparatively short time to various combinatorial optimization problems. In this paper, we focus on the most powerful the κ-opt local search heuristic in LS known for the binary quadratic programming problem (BQP). It is shown that the genetic local search (GLS) containing κ-opt local search heuristic can obtain a high quality solution compared with genetic algorithm (GA).
広島商船高等専門学校の論文
2004-03-19