メタ戦略


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