メタヒューリスティクスとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > メタヒューリスティクスの意味・解説 

メタヒューリスティクス

読み方めたひゅーりすてぃくす
【英】:metaheuristics

概要

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

詳説

 メタヒューリスティクス (metaheuristics) とは組合せ最適化問題に対しての, 発見的解法枠組みであり, 従来数理的, 分析的手法基づ厳密解に対し, ある暫定解からより良い解を発見的探索するための方法論である. 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\le 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.


メタヒューリスティクス

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/12/10 02:26 UTC 版)

メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。






「メタヒューリスティクス」の続きの解説一覧

メタヒューリスティクス

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/04/15 03:07 UTC 版)

探索」の記事における「メタヒューリスティクス」の解説

詳細は「メタヒューリスティクス」を参照 汎用的使えるヒューリスティクスをメタヒューリスティクスという。 焼きなまし法 - 確率的探索アルゴリズム一種 タブーサーチ - 探索局所解で停滞するのを防ぐ技法 遺伝的アルゴリズム - 探索空間縮小させるヒューリスティクスとして進化考え方を使う。 蟻コロニー最適化 粒子群最適化

※この「メタヒューリスティクス」の解説は、「探索」の解説の一部です。
「メタヒューリスティクス」を含む「探索」の記事については、「探索」の概要を参照ください。

ウィキペディア小見出し辞書の「メタヒューリスティクス」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

メタヒューリスティクスのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



メタヒューリスティクスのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2022 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのメタヒューリスティクス (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2022 GRAS Group, Inc.RSS