メタ戦略
多くの組合せ最適化問題について,
厳密な最適解を求めることが極めて困難であるこ
とが, 計算の複雑さの理論により明らかにされてきた. NP困難問題はその代表例であ
る. しかし, 現実には, 最適性の保証はなくとも, 十分精度の高い解が求まれば満足
のいく場合が多い. 近似解法はこのような目的に用いられる. 近似解法の基本戦略と
して, 欲張り法(greedy method), 局所探索法(local search)などがあるが, 最近では,
これらを組合わせるなどの方法により, 多少時間はかかっても, より精度の高い解を
求める枠組を提供しようとする, メタ戦略(metaheuristics, メタヒューリスティクス,
メタ解法などとも呼ぶ)の研究が盛んである.
代表的なものとして, ランダム多スタート局所探索法(random multi-start local search)
遺伝アルゴリズム(genetic algorithm)アニーリング法(simulated annealing)タブー
探索法(tabu search)などがある.
柳浦のホームページ