概要
メタヒューリスティクスは、最適化問題を解決するために使用されるアルゴリズムとなる。最適化問題とは、目的関数を最大化または最小化することが目的の問題で、メタヒューリスティクスは、解空間内で解候補を探索し、最適な解を見つけるために確率的手法を使用する。メタヒューリスティクスには、遺伝的アルゴリズム、粒子群最適化、シミュレーテッドアニーリングなどのアルゴリズムが含まれる。
メタヒューリスティクスの長所と短所を以下に示す。
【長所】
- 汎用性が高い：メタヒューリスティクスは、あらゆる種類の最適化問題に対応できる。そのため、様々な分野で応用されている。
- 局所解に陥りにくい：メタヒューリスティクスは、確率的な探索方法を使用するため、局所解に陥る可能性が低く、グローバル最適解を見つけることができる。
- パラメータの設定が容易：メタヒューリスティクスは、多くの場合、数値的なパラメータの設定が必要だが、設定が容易であり、初期値による影響も比較的小さいため、柔軟性が高い。
【短所】
- 解の品質の保証ができない：メタヒューリスティクスは、確率的な探索方法を使用するため、最適解の品質を保証することができない。そのため、解の品質を評価することが難しく、実行結果に不確実性がある場合がある。
- 計算量が大きい：メタヒューリスティクスは、多くの場合、探索空間内をランダムに探索するため、計算量が多くなる傾向がある。また、一度の評価に時間がかかる問題に対しては、探索に時間がかかり、実用的でない場合がある。
- パラメータの調整が難しい：メタヒューリスティクスは、多くの場合、数値的なパラメータの調整が必要だが、適切なパラメータを選択することが難しく、調整に時間がかかる場合がある。また、適切なパラメータを選択しないと、探索の効率が低下する場合がある。
メタヒューリスティクスとは、難度の高い最適化問題を解くための経験的手法（ヒューリスティクス）を有機的に結合させたものであり、最近では、実務的な問題を楽に解くためのフレームワークとして、実務家の間でよく用いられる最適化アルゴリズムとなっている。実際問題を解くとき、ある程度のプログラミングの腕と、メタヒューリスティクスの選択眼と、設計のコツさえつかんでいれば、比較的短時間でロバスト（頑強）な解法を設計できる。
メタヒューリスティクスの数理
まず最初の参考図書として「メタヒューリスティクスの数理」。
本書では、メタヒューリスティクスを単なるアイディアの羅列ではなく、なぜそのアイディアがうまく働くのかを、数理的に説明することを試みる。また、数理計画とよばれる最適化の一分野とメタヒューリスティクスの融合についても解説する。一般的なアルゴリズムの記述だけでなく、種々の具体的な応用への適用を通して、自分で一から効率的なメタヒューリスティクスを設計できるようなコツを伝授する。
第1章 はじめに
1.1 メタヒューリスティクスとは
メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。
通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみである。ところが近似アルゴリズムのように厳密な答えではなく、なるべく「答えに近い」まで拡大すると、局所探索法や貪欲法など複数の問題に対しても使用できる手法が存在する。メタヒューリスティクスとは特定の問題に限定されず、どのような問題に対しても汎用的に対応できるように設計された、アルゴリズムの基本的な枠組みのことである。言い換えればヒューリスティックアルゴリズムの内、特定の問題に依存せず手法のみが独立したものである。それゆえあらゆる問題に適用可能である。このことはNP困難のような多項式時間で最適解を求めるアルゴリズムが存在しないと思われる問題などに対して有効である。ただし、一般的にメタヒューリスティクスは特定の問題専用のヒューリスティクスより平均的な解の精度が劣ることが多い。これは汎用的な探索をするためには問題に対する事前知識を必要とせずに実装しなければならないので、それらを有効に使用することで解の探索を行う方法に対してどうしても不利な立場で探索を進める必要があるからである。
1.2 最適化問題とは
最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である[1]。こうした問題は総称して数理計画問題（すうりけいかくもんだい、英: mathematical programming problem, mathematical program）、数理計画とも呼ばれる[1]。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る[2]。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった[1]。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。
1.3 メタヒューリスティクスの基本戦略
1.3.1 近傍の利用
1.3.2 構築法の利用
1.3.3 部品の利用
1.3.4 複数の解の保持
1.3.5 ランダム性の利用
1.3.6 問題の変形
1.3.7 探索の履歴の利用
第2章 代表的なメタヒューリスティクス
2.1 局所最適法
局所探索法とは近似アルゴリズムの中でも最も単純なアルゴリズムの枠組みの一つである。広義には後述する手法の枠組みを持つアルゴリズムの総称として使われており、狭義には山登り法の意味で使われている。今日のメタヒューリスティクスの多くの手法がこの枠組みを使用している。
「局所探索法」という言葉は主に探索アルゴリズムに対しての言葉であり、数値解析の分野に於いては「反復法」という言葉が用いられる。両者の違いとしては反復法は対象となる関数の連続性や1階微分方程式などが解っていることが前提の場合が多く、また求める解も最適解を要求されることが多いのに対し、局所探索法では離散的な関数や関数の内容自体が不明なときでも出来る限り良質な近似解を求めるということを主な目的としたものが多い
2.2 他出発局所探索法
2.3 反復局所探索法
局所探索法を繰り返す際に、初期解から解の改善を試みるのではなく、得られた局所的最適解と近い解からさらに良い解を見つけようとする戦略を、反復局所探索法と呼ぶ
2.4 模擬焼きなまし法
焼きなまし法（やきなましほう、英: Simulated Annealing、SAと略記、疑似アニーリング法、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案し[1]、1985年に V. Cerny が再発見した[2]。
その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。
SAアルゴリズムは、解を繰り返し求め直すにあたって、現在の解のランダムな近傍の解を求めるのだが、その際に与えられた関数の値とグローバルなパラメータ T（温度を意味する）が影響する。そして、前述の物理過程との相似によって、T（温度）の値は徐々に小さくなっていく。このため、最初はTが大きいので、解は大胆に変化するが、Tがゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。
2.5 禁断探索法
タブーサーチはメタヒューリスティクスの手法であり、人工知能の概念に基づいた局所探索法の一般化として認知されている。同じメタヒューリスティクスの手法には、遺伝的アルゴリズムや焼きなまし法のように特定の自然現象を模倣した手法がある。
この手法は状態の近傍を複数探索しその中で最も良い近傍状態に遷移する、このときタブーリストと呼ばれるキューに状態遷移時の操作を書き込む。このタブーリストに書き込まれている操作は行わないことにより状態がループするのを防ぐことで探索が停滞せずに最適解を探索する。ここで重要なのはタブーリストに載っていない場合は状態が悪くなっても遷移を行うことである。このことにより局所解で探索が停滞するのを防いでいる。
2.6 誘導局所探索法
2.7 大近傍探索法
近傍のサイズが大きいほど得られる解の質は向上するが，計算時間が上昇する． ・大きな近傍を何らかのテクニックを用いて，効率的に求めることが重要． ・この方法を，大近傍探索法という
2.8 探索空間平滑法と交互平滑法
2.9 部品最適化法
部品最適化法では，メタヒューリスティッ クスにおける近傍解の定義を数理計画問題として以下の ように定義する． 部分問題 SPr の要素数を r として，|J| = r となる 部分集合 J ⊆ I を選択する．I\J の要素の部分問題の 解 xf ix i (I\J) を固定したとき，部分問題 SPr は以下の ように表現できる．
rが十分に小さい場合，部分問題 SPr の解法として動的 計画法や分枝限定法によって効率良く解を得ることがで きる．
2.10 多レベル法
マルチレベルモデルは，社会科学の分野ではすでに多くの研究者が利用している統計手法である。その意味では，「目新しい統計手法」というよりは，もはや「市民権を得た統計手法」になってきたといえるだろう。実際に，多くの論文でマルチレベルモデルが利用されているし，査読においてもレビュワーからマルチレベルモデルを使うよう要求されることもある。マルチレベルモデルの習得の必要性は，年々高まってきている。
2.11 貪欲ランダム適応型探索法
ランダムに発生させた多数の初期解それぞれに対して局所探索法を行い，その. 中で最良のものを近似最適解とするもの
2.12 蜂群生法
実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発するよりも早く補強されるため、フェロモン濃度は高いまま保たれる。従って、あるアリがコロニーから食料源までの良い（すなわち短い）経路を見つけると、他のアリもその経路を辿る可能性が高くなり、正のフィードバック効果によって結局すべてのアリが1つの経路を辿ることになる。蟻コロニー最適化アルゴリズムの考え方は、解決すべき問題を表しているグラフを歩き回る「シミュレーションされたアリ」によってこの行動を真似ることである。蟻コロニー最適化アルゴリズムは、巡回セールスマン問題に近似最適解を生み出すために用いられた。この手法はグラフが動的に変化する場合に焼きなまし法や遺伝的アルゴリズムよりも有効である。蟻コロニー最適化アルゴリズムは継続的に実行されるので、リアルタイムで変化に適応することができる。このことから、ネットワークのルーティングや都市交通システムでの応用が考えられる。
2.13 遺伝的アルゴリズム
遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることである。また、遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。
2.14 散布探索法
第3章 数理計画法とメタヒューリスティクスの適合
3.1 分岐限定法
分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。
3.2 なぜ融合が必要か?
3.3 変数固定法
3.4 打ち切り分岐限定法と飛び込み法
3.5 緩和固定法
3.6 容量スケーリング法
3.7 MIP近傍局所探索法
3.8 局所分岐法
3.9 MIP併合法
第4章 応用
4.1 グラフ分割問題
4.1.1 問題の定義と定式化
4.1.2 近傍
4.1.3 補助メモリによる高速化
4.1.4 ペナルティ関数法
4.1.5 擬似実行可能探索法
4.1.6 擬似焼きなまし法
4.1.7 禁断探索法
4.1.8 Pythonによる実装
4.2 最大安定集合問題
4.2.1 問題の定義と定式化
4.2.2 近傍
4.2.3 禁断探索法
4.2.4 平坦探索
4.2.5 Pythonによる実装
4.3 グラフ彩色問題
4.3.1 問題の定義と定式化
4.3.2 近傍
4.3.3 補助メモリによる高速化
4.3.4 禁断探索法
4.3.5 遺伝的アルゴリズムと禁断探索法の融合
4.3.6 Pythonによる実装
4.4 巡回セールスマン問題
4.4.1 問題の定義と定式化
4.4.2 近傍
4.4.3 局所探索法
4.4.4 初回改善と最良改善
4.4.5 Pythonによる実装
4.5 2次割当問題
4.5.1 問題の定義と定式化
4.5.2 近傍
4.5.3 目的関数の差の計算
4.5.4 禁断探索法
4.5.5 Pythonによる実装
4.6 多制限ナップサック問題
4.6.1 問題の定義と定式化
4.6.2 禁断探索法
4.6.3 線形計画緩和を用いた解法
4.6.4 Pythonによる実装
4.7 数分割問題
4.7.1 問題の定義と定式化
4.7.2 差分法
4.7.3 分割数が3以上の場合
4.7.4 Pythonによる実装
付録 Python解説
メタヒューリスティックと応用
次に紹介するのが、「メタヒューリスティックと応用」。
本書は新たな最適化手法である「メタヒューリスティクス」のアルゴリズムと応用事例を体系的にまとめたものとなる。アルゴリズム編では、Memeticアルゴリズム、人工免疫システム、アントコロニー最適化手法、Particle Swarm Optimizationなどの最新の手法を幅広く網羅しており、応用編では、スケジューリング問題、配送計画問題、構造最適設計への応用などを幅広く取り上げている。ハンドブック的な利用も可能であり、システム工学・情報工学に携わる学生・技術者・研究者必携の書となる。
第1章 進化的最適化法
1-1 遺伝的アルゴリズム
1.1.1 概要
1.1.2 アルゴリズム
1.1.3 個体表現
1.1.4 交差則
1.1.5 突然変異則
1.1.6 選択則
1.1.7 その他の設計
1.1.8 数値計算則
1.1.9 アルゴリズムの改良
1-2 Memeticアルゴリズム
1.2.1 はじめに
1.2.2 MemeとMemeticアルゴリズム
1.2.3 ラマルク則
1.2.4 アルゴリズムの基本構成
1.2.5 アルゴリズムの実装で考慮すべき点
1.2.6 今後の研究課題
1-3 免疫型最適化アルゴリズム
1.3.1 人工免疫システム
1.3.2 免疫型最適化システム
1.3.3 計算例
第2章 マルチエージェント型最適化手法
2-1 市場志向プログラミング(MOP)と最適化
2.1.1 社会性を取り入れた最適化アルゴリズムとしての市場志向プログラミング
2.1.2 ワルラス型仮想市場
2.1.3 市場志向プログラミング
2.1.4 エージェントの定式化
2.1.5 パレート最適解導出の特性解析
2.1.6 計算機十無県による解の特性解析
2.1.7 終わりに
2-2 アントコロニー最適化法
2.2.1 社会性昆虫のstigmergyと最適化
2.2.2 アントコロニー最適化法
2.2.3 数値実験
2.2.4 まとめ
2-3 Particle Swarm Optimization
2.3.1 Particles Swarm Optimizationの概要
2.3.2 Particle Swarm Optimizationのアルゴリズムと特徴
2.3.3 群の活性度の定義とPSOの数値的安定性解析
2.3.4 PSOの解析的・数値実験的安定解析
2.3.5 PSOの代表的な手法と数値例
2.3.6 まとめ
第3章 力学モデルによる最適化手法
3-1 非線形力学系と最適化
3.1.1 はじめに
3.1.2 最急降下勾配系
3.1.3 慣性項付き勾配系
3-2 有界領域上の非線形力学系と制約条件付き最適化
3.2.1 はじめに
3.2.2 緩和手法による制約条件付き最適化問題の主要解法
3.2.3 制約条件を厳密に反映する力学系モデルとその性質
3-3 離散化勾配力学系とパラメータ調節法による大域的最適化
3.3.1 はじめに
3.3.2 連続時間勾配力学モデルの安定性と最適化
3.3.3 勾配力学モデルの離散化と不動点の安定性
3.3.4 離散勾配力学系のパラメータ調節による大域的最適解探索手法
3-4 非線形システムの安定性理論に基づく最適化
3.4.1 前書き
3.4.2 問題の定式化と探索手法の概要
3.4.3 タイプ-1不安定平衡点探索手法
3.4.4 ベンチマーク関数による計算例
3.4.5 結び
第4章 シミュレーティッド・アニーリング、 タブーサーチ、 トンネリングアルゴリズム
4-1 シミュレーティッド・アニーリング
4.1.1 はじめに
4.1.2 組み合わせ最適化問題
4.1.3 LSと近傍構造
4.1.4 シミュレーテッド・アニーリング
4.1.5 漸次的収束性
4.1.6 冷却スケジュール
4.1.7 冷却スケジュールに対する理論的検討
4.1.8 具体的運用について
4.1.9 数値実験
4.1.10 終わりに
4-2 タブーサーチ
4.2.1 前書き
4.2.2 タブサーチ
4.2.3 TSの改良法
4.2.4 TSの研究動向と運用におけるヒント
4.2.5 あとがき
4-3 トンネリング・アルゴリズムとその応用
4.3.1 トンネリング・アルゴリズム
4.3.2 ダイナミック・トンネリング・アルゴリズム
4.3.3 一般化ランダム・トンネリング・アルゴリズム
第5章 ハイブリッド手法および発見的手法の解析・評価
5-1 熱力学的アルゴリズム
5.1.1 はじめに
5.1.2 自由エネルギー最小化原理
5.1.3 TDGAの性質
5.1.4 TDGAの収束の検出および回避
5.1.5 結び
5-2 進化型多目的最適化
5.2.1 はじめに
5.2.2 多目的最適化
5.2.3 伝統的な多目的最適化手法
5.2.4 EMOの考え方
5.2.5 EMOアルゴリズム
5.2.6 EMOにおける研究課題
5-3 分散遺伝的アルゴリズム
5.3.1 はじめに
5.3.2 GAの並列化
5.3.3 分散遺伝的アルゴリズムの分散効果の検討
5.3.4 緩急分散GA
5.3.5 終わりに
5-4 ヒューリスティック手法の解析・評価
5.4.1 はじめに
5.4.2 実験的解析について
5.4.3 理論的実験への招待
5.4.4 終わりに
第6章 スケジューリング問題への応用
6-1 ナーススケジューリング問題への応用
6.1.1 ナーススケジューリング問題
6.1.2 NSPのモデル化
6.1.3 GAに基づく解法
6.1.4 数値実験
6.1.5 まとめ
6-2 複雑な生産スケジューリング問題への応用
6.2.1 金型問題の記述
6.2.2 金型問題の特徴と解法の設計指針
6.2.3 金型問題に対するGAの構成法
6.2.4 金型問題に対する計算例
6.2.5 再スケジューリングの必要性
6.2.6 祭スケジューリング問題の記述
6.2.7 祭スケジューリング問題の特徴と解法の設計指針
6.2.8 再スケジュール問題に対するGAの構成法
6.2.9 祭スケジューリング問題に対する計算例
6.2.10 まとめ
6-3 タブサーチを用いた配送計画システム
6.3.1 はじめに
6.3.2 配送計画問題
6.3.3 配送計画作成方式
6.3.4 配送計画システム
6.3.5 適用例
6.3.6 あとがき
6-4 配送計画への応用(誘導局所探索法)
6.4.1 配送計画問題について
6.4.2 配送計画の定式化
6.4.3 誘導局所探索法について
6.4.4 GLSの配送計画への応用
6.4.5 シミュレーション例
6.4.6 終わりに
第7章 エネルギーシステムへの応用
7-1 電力系統の電圧無効電力制御への応用
7.1.1 前書き
7.1.2 電圧無効電力配分問題の定式化
7.1.3 Particle Swarm Optimization(PSO)
7.1.4 無効電力配分問題へのPSOの適用
7.1.5 適用例
7.1.6 まとめ
7-2 電力系統安定制御への応用
7.2.1 前書き
7.2.2 電力系統の非線形安定化制御系設計
7.2.3 まとめ
7-3 原子炉の炉心設計と炉心制御への応用
7.3.1 はじめに
7.3.2 沸騰水型原子炉の炉心設計と炉心制御
7.3.3 炉心設計と炉心制御の統合型最適化問題の定式化
7.3.4 炉心設計・制御統合型最適化問題に対する2段階遺伝的アルゴリズム
7.3.5 実プラントへの適用
7-4 コジェネレーションシステム最適運用への応用
7.4.1 前書き
7.4.2 こジェネレーション最適運用の定式化
7.4.3 PSOの適用
7.4.4 適用例
7.4.5 結び
7-5 エネルギー供給システムの機器構成設計への応用
7.5.1 はじめに
7.5.2 機器構成最適化問題の定式化
7.5.3 機器構成最適化問題の解法
7.5.4 適用事例
第8章 設計・制御への応用
8-1 ロボットの行動学習への応用
8.1.1 ロボット行動の最適化と学習
8.1.2 知的合成動作制御法の概要
8.1.3 大規模行動の適用的最適化と行動進化
8.1.4 サッカー行動学習への適用
8.1.5 まとめとこれから
8-2 構造最適設計への応用
8.2.1 構造最適設計の歴史
8.2.2 構造最適設計問題のまとめ-設計変数による分類
8.2.3 構造設計問題の特徴-モデル化誤差
8.2.4 製造上の制約
8.2.5 ヒューリスティック法の適用
8.2.6 近似モデルを用いた最適設計
8.2.7 複合領域の最適設計
8.2.8 終わりに
付録・代表的な差異的問題の概要とベンチマーク問題
1 非線形最適化問題
1.1 非線形最適化問題の定式化と解の定義
1.2 非線形最適化問題の代表的ベンチマーク問題
2 巡回セールスマン問題
2.1 はじめに
2.2 TSPの定式化
2.3 アプリケーション
2.4 アルゴリズムの概要
2.5 ベンチマーク問題
2.6 TSPアルゴリズムの性能
2.7 終わりに
3 スケジューリング問題
3.1 フローショップ問題
3.2 ジョブショップ問題
コメント
[…] り返して目標状態に至る計画を見つける手法となる。具体的には、”メタヒューリスティクスの数理 読書メモ“で述べてられているようなヒュリスティック系のアルゴリズムであ […]
[…] メタヒューリスティクスの数理 読書メモ […]