メタヒューリスティクス

メタヒューリスティクスは，生物現象や物理現象などの経験的に優れたメカニズムに基 づくアルゴリズムから構成される最適化手法である。メタヒューリスティクスのアルゴリ ズムでは，対象問題の解情報と目的関数値情報のみを用いて，探索点が解空間内を逐次移動 し，最適解あるいは準最適解を探索する。特に多点型最適化手法に分類されるメタヒュー リスティクスを多点探索型メタヒューリスティクスという。数理計画法とは異なり，求め る解に数学的な保証がないため，探索点同士に経験的に優れたメカニズムに基づく相互作

第2章 最適化手法の基礎と数理 27

用を与えることで，多様なダイナミクスを生み出し，そのダイナミクスを解の探索に巧み に活用する。

代表的なメタヒューリスティクスとして，Particle Swarm Optimization［28］や，Differential

Evolution［29］が知られている。1.1節でも述べたように，これらの手法は，高い探索性能・

汎用性を有していることから，近年では，産業応用の場面でも使用されることが多い。しか し，メタヒューリスティクスの課題点として，①数学的な背景を有していないため，得ら れた解に対する最適性は保証されていないこと，②十分な探索性能の発揮には，パラメー タ設定に関する使用者の専門的な知識・経験や試行錯誤を必要とすること，がよく指摘さ れる。これに対して，近年では，メタヒューリスティクスの実システムへの応用や更なる 有用性の向上のために，探索ダイナミクスに対する数理的・数値実験的解析や，解析に基 づく手法の改良・開発に関する研究が盛んになっている［34］［35］［36］［37］［38］［39］［40］

［41］［42］。今後も，数値実験や解析を通じて，①パラメータの設定・調整に対する有効な 知見の抽出による系統的な分類・整理，②パラメータの調整方法の開発，③_{メタヒューリ} スティクスの設計論の確立，などの更なる発展が期待されている。例えば，数理計画法に おいても，効率的な探索を行うための理論・技術は整備されている。関数の解析的情報に 基づかない理論・技術であれば，メタヒューリスティクスに対して適用することは，上述 の課題解決に資すると考えられる。

また，2.3節まで様々な数理計画法を概観したように，数理計画法は「対象の問題の特徴 を大いに把握し，その情報を最大限に活用して数理的に保証された方向へ探索を行う」こ とが基本概念である。これは，1.1節でも述べたように，対象の問題の特徴を大いに把握す るために，あるいは数理的に解の最適性・収束性を保証するために，探索に関数の解析的 情報が必要となった結果，「適用可能な問題のクラス」が限定されることを意味する。言い 換えると，数理計画法は「適用範囲は限定されるが，適用範囲内の問題に対する究極的な 適応能力を有している」といえる。これに対して，メタヒューリスティクスは，数理計画 法とは構築のプロセスが全く異なるため，勾配に基づく解の最適性・収束性を議論するこ とができない。そのため，「探索点群による多様なダイナミクスによって，対象の問題の特 徴を把握し，その情報を最大限に活用した探索を行う」ことが基本概念である。したがっ て，数理計画法とメタヒューリスティクスの共通点を考えると，優れた探索性能を有する 最適化手法を構築するには，優れた適応能力を具備することが必要となる。

本論文では，メタヒューリスティクスの探索構造と適応能力の関係に着目する。様々な

第2章 最適化手法の基礎と数理 28

メタヒューリスティクスの探索構造の解析を行い，統一的な視点に基づき，メタヒューリ スティクスの適応能力・探索性能に資する探索戦略を系統的に分類・定義する。これらの 解析を踏まえることで，上記の課題の③であるメタヒューリスティクスの設計論となる汎 用的フレームワークの確立と，汎用的フレームワークに基づく優れた適応能力を有するメ タヒューリスティクスの開発を目的とする。

3 メタヒューリスティクス の探索構造の解析

本章では，これまでに提案されているメタヒューリスティクスのアルゴリズムを概観す る。さらに，探索構造を解析し，メタヒューリスティクスに共通する探索戦略を抽出する。4 章以降でメタヒューリスティクスに対して統一的な視点で議論するための土台を形成する。