学位論文 適応化のフレームワークの構築と適応型メタヒューリスティクスの開発に関する研究

熊谷, 渉

pp.1 - 139 , 2016-03-25
内容記述
最適化は工学に限定されることなく,経済学,社会学などの幅広い分野に及んで応用され,その重要性が広く認識されている。近年のシステムの大規模化・複雑化により,システムの設計・運用・制御に対する要求は高度化している。また,シミュレーション技術・計測技術などの最適化分野の周辺技術は急速に発展している。さらに,コンピュータパワーの飛躍的な増大が,数値計算に多大な貢献をしている。このように,最適化分野を取り巻く環境の変化に応じた実用的かつ新たな最適化手法への要求が高まっている。上述の背景に対応可能な最適化手法の枠組みとして,メタヒューリスティクスが注目されている。従来から使用されてきた数理計画法は,対象関数の解析的情報(勾配やHesse行列など)を要することに対して,メタヒューリスティクスは,決定変数値情報と評価値情報のみを用いる。また,実用的な時間に応じて最適性の高い近似解を求めることができる。さらに,多くの手法は生物現象などの経験的に優れたメカニズムからのアナロジーにより構築されている。例えば,Cuckoo Search(CS)はカッコウの托卵行動のメカニズムに基づいており,解が実数空間で定義される連続値最適化問題を対象とした手法である。メタヒューリスティクスは調整可能なパラメータを有しているが,十分な探索性能の発揮には,パラメータ設定に関する使用者の高い専門的な知識・経験や試行錯誤を必要とする。一方,多様な環境下での使用が想定されるメタヒューリスティクスは,多様な環境下においても高い探索性能を発揮可能な適応能力が不可欠である。従って,メタヒューリスティクスの適応能力の向上,及び高い適応能力を有する新たなメタヒューリスティクスの開発には,適応能力向上を実現し得る「汎用的フレームワークの構築」が最も重要な課題となる。まず本論文では,アナロジーではなく,探索構造の観点から,様々なメタヒューリスティクスを解析した。そして,構造解析を通じて得た「最適化手法として優れた戦略」に基づき,様々なメタヒューリスティクスに適用可能な,適応化のフレームワークを構築した。さらに,適応化のフレームワークに基づき,連続値最適化問題を対象とする適応型メタヒューリスティクスの開発を行った。メタヒューリスティクスでは,「探索序盤では多様化の実現,探索終盤では集中化の実現」という探索戦略が知られている。本論文では,様々なメタヒューリスティクスの構造解析を通じて,多様化・集中化の実現状態(探索状態)を調整する操作を定義・分類した。このように,共通概念である多様化・集中化に影響を与える操作を定義・分類しておくことで,各手法の多様化・集中化に対する解析が可能となる。さらに,メタヒューリスティクスは探索過程で多様化・集中化を適切に実現することで,問題構造や探索条件に適応すると同時に,優れた探索性能を発揮する。従って,定義した多様化・集中化に影響を与える操作を巧みに調整することで,高い適応能力・探索性能が期待できる。メタヒューリスティクスの更なる有用性の向上のために,これまでに適応化のためのアプローチはいくつか提案されている。しかし,これらのアプローチの多くは,① 統一的な視点に基づく適応能力を具備したメタヒューリスティクスの設計論が存在せず,既存の手法に対するパラメータ調整機能の付加のみに留まっていること,② 対象の手法に特化した観点に基づいており,明確な多様化・集中化の観点に基づいていないこと,などの課題が存在する。そこで本論文では,多様化・集中化に基づく適応化のための汎用的フレームワークを構築した。適応化のフレームワークは,既存のアプローチとは異なり,① 既存の手法に対して適用可能であること,② 新たな手法を構築し,その手法に対して適用可能であること,から,汎用性が高い。既存の手法に対しては,① 探索状態を定量的に評価すること,② 探索状態の指標をフィードバックし,パラメータを調整することで,探索状態を制御すること,を実現する。また,優れた適応性を有する新たな手法を構築し,上述の方法でその手法を適応化する。このように,探索状態の評価と制御に基づく探索能力を開発・付加することで,適応型メタヒューリスティクスを構築する枠組みを「適応化のフレームワーク」とする。これは,パラメータ調整機能の付加に限らず,高い適応能力・探索性能を具備した新たな適応型メタヒューリスティクスの設計に繋がる。上述した通り,適応化のフレームワークに基づくことで,既存の手法の系統的な適応化が可能となり,適応能力・探索性能の向上が期待できる。そこで本論文では,適応化のフレームワークに基づき,適応型CS の開発を行った。さらに,適応化のフレームワークに基づくと,新たな適応型メタヒューリスティクスの開発が可能となる。そこで本論文では,適応性に優れた探索構造を具備する新たなメタヒューリスティクスを構築した。さらに,この手法を基礎とすることで,より優れた適応型メタヒューリスティクスの開発を実現した。最後に,典型的なベンチマーク関数を対象とした数値実験を通じて,既存手法と比較することで,提案手法の探索性能・適応能力を検証した。本論文では,メタヒューリスティクスの更なる有用性の向上のために,適応化のフレームワークを構築した上で,このフレームワークに基づき,適応型CS や新たな適応型メタヒューリスティクスを開発した。最後に,数値実験を通じて提案手法の探索性能を検証し,適応化のフレームワークの有用性を確認した。
首都大学東京, 2016-03-25, 修士(工学)
本文を読む

https://tokyo-metro-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=2532&item_no=1&attribute_id=18&file_no=1

このアイテムのアクセス数:  回

その他の情報