メタヒューリスティクス

【めたひゅーりすてぃくす (metaheuristics)】

概要

組合せ最適化問題において, 遺伝アルゴリズム, アニーリング法, タブー探索といった発見的な探索を行う手法を総合した枠組. 暫定解に対し局所探索によって解の更新を行うが, 局所最適解に捕捉されることを防ぐための工夫を付加するというのが基本的な考え方である. 一般に最適性は保証できないが, 少ない計算時間で質の良い解を求めることができる場合が多いので極めて実用性が高く, 様々な問題への応用がなされている.

詳説

　メタヒューリスティクス (meta-heuristics) とは組合せ最適化問題に対しての, 発見的解法の枠組みであり, 従来の数理的, 分析的手法に基づく厳密解法に対し, ある暫定解からより良い解を発見的に探索するための方法論である. 1) 個々の問題の性質に依拠しないより包括的な枠組みである, 2) 最適解を求めることではなく, より良い解を現実的な時間で求めることを目的とする, といった特徴が挙げられる. メタヒューリスティクスに含まれる多くの手法は局所探索法 (local search) を元にしているが, 局所最適解で探索が終了してしまうという欠点を補うためのさまざまな工夫がなされている[7].

　多スタート局所探索 (multi start local search) は適当な方法で生成した初期解からの局所探索法を繰り返し行うことにより, 改善された局所最適解を求めるものである.

　可変近傍法 (variable neighborhood search) は複数の近傍を定義し, 暫定解 （それまでに得られた最善解） に対しある近傍から一つ初期解を選択し, その解に対して局所探索法を適用するという手順を繰り返す. この反復において暫定解が更新されたか否かによって初期解を選択するための近傍を変える点に特徴がある.

　アニーリング法 (simulated aneealing) は局所探索法の実行過程に確率的な振る舞いを加え局所最適解に陥らないようにしたアルゴリズムであり, Kirkpatrickらによって提案された [2]. アニーリング法では改悪の方向への移行を確率$P\,$で受け入れる. $P\,$は温度$t\,$と呼ばれる制御パラメータを含む関数で定義され, 目的関数が改悪される度合が大きくなれば小さくなるように定義される. 一般に用いられるのは, 変更にともなう目的関数値の変化量を$\Delta \,$(改悪ならば正、改良ならば負の値をとる)とすると,

$P=\left\{{\begin{array}{l}1,\;\Delta \leq 0\\\exp(-\Delta /t),\Delta >0\end{array}}\right.$

と定義される. パラメータ$t\,$は最初は大きな値に設定されるが、その後$t\,$を徐々に小さくすることによって, 探索の初期の段階では広い領域を探索し, 後期では探索が最適解に落ち着くことをねらっている.

　タブー探索　(tabu search)　は局所探索法において局所最適解から脱出するため, 近傍内の最良解（改悪解であっても）へ移行するという操作を加えたものである [3, 4] . 一つの局所最適解とその近傍のみの移行という繰り返しを避けるために, 現在までの移行の履歴を保持し, 移行に制約を設ける. この制約をタブーという. またタブーにより良い最適解への移行を妨げる場合があるのでタブー保有期間と呼ばれる一定期間を経るとタブーは解消される. これにより局所最適解に陥ることなく広範囲の最適解を探索することが可能になる.

　遺伝アルゴリズム (genetic algorithm) は生物の形質遺伝による進化を組合せ最適化問題における解の進化, すなわち目的関数値を向上させることに利用した解法である [6]. まず候補解を記号列として表現したものを遺伝子と名付け, これらの遺伝子からなる集団に対し1) 次世代に子孫を残す解を選択し (選択), 2) $2\,$つの親の遺伝子より子の遺伝子を生成し (交叉), 3) 遺伝子の一部を一定の確率で変化させ (突然変異), 4) 劣っている解は集団より除去する (淘汰), という操作を繰り返し行う. 交叉において遺伝子の特徴がどのように次の世代に遺伝していくかということはスキーマ定理 (scheme theorem) によって確率的に示されている [5]. ここでスキーマ$H\,$とは遺伝子を2進数で表現したときの部分列であり, その次元を$o(H)\,$, 定義長を$\delta (H)\,$とし, $m(H,t)\,$を次世代$t\,$でスキーマ$H\,$を含む個体の数, $f(H)\,$スキーマ$H\,$を含む個体の適応度の平均値, ${\overline {f}}(t)\,$を世代$t\,$での固体の平均適応度とすると

${\begin{array}{lll}m(H,t+1)&\geq &m(H,t)f(H)\{1-p_{c}\delta (H)/(l-1)\}(1-p)^{o(H)}/{\overline {f}}(t)\\&\approx &m(H,t)f(H)\{1-p_{c}\delta (H)/(l-1)-po(H)\}/{\overline {f}}(t)\end{array}}\,$

が成立する.

　遺伝アルゴリズムは進化的計算 (evolutionary computation), 進化的プログラミング (evolutionary programming) といった生物の遺伝, 進化の過程を模倣して最適化問題における最適解を探索するという枠組みの中のひとつであり、さらには人工生命 (artificial life) という生命システムをコンピュータでシミュレートする研究との関連においても注目されている.

---

参考文献

[1] G. Hansen and N. Mladenovic, "An Introduction to Variable Depth Search," in Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, eds., Kluwer Academic Publishers, 1998.

[2] S. Kirkpatrick, C. D. Gellat and M. P. Vecchi, "Optimization by Simulated Annealing," Science, 220 (1983), 671-680.

[3] F. Glover, "Tabu Search I," ORSA Journal on Computing, 1 (1989), 190-206.

[4] F. Glover, "Tabu Search II," ORSA Journal on Computing, 2 (1989), 4-32.

[5] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

[6] J. H. Holland, Adaptation in Natural and Artificial Sytems, University of Michigan Press, 1975.

[7] 柳浦睦憲, 茨木俊秀, 「組合せ最適化」, 朝倉書店, 2001.