| タイトル |
-
組合せ最適化問題における近接最適性原理の定量的評価と最適化手法への応用
|
| 作成者 |
|
| 内容注記 |
-
Abstract
近年のシステムの大規模化・複雑化により，人間の経験や試行錯誤によるシステム設計では，より一層のシステムの高効率化・高信頼化は難しいものになってきている。電力や通信，交通など様々な社会基盤をシステム化して運用する現代において，システムの高効率化・高信頼化はより一層求められており，システム最適化の必要性は高まってきている。施設の配置，商品配送計画，カーナビの最短ルート検索および作業シフトや補修計画のスケジューリングなど，現実のシステムの計画・運用問題を最適化する際，多くの問題は組合せ最適化問題として定式化が可能である。そのため，組合せ最適化問題に有効な最適化手法の開発は重要な課題となっている。しかし，多くの組合せ最適化問題はNP 困難であることが知られており，大規模・複雑な組合せ最適化問題の厳密解を実用的な時間内に求めることは実質的に困難とされている。ところが，実際の計画・運用を考える際には，厳密な最適性の保証は必ずしも必要なものではなく，現実的な時間内に十分最適性の高い近似解が得られれば十分な場合が多い。そこで本論文では，組合せ最適化問題の解法として，近似解法の一種であるメタヒューリスティクスに着目した。メタヒューリスティクスとは，経験的・数値実験的に有用性が確認されている近似解法であり，計算量に応じた解が得られることや，探索に必要な情報が決定変数とその評価値情報のみであるため適用範囲が広いといった特徴を持つ最適化手法である。数理計画法では目的関数の微分可能性が最適化手法を適用する上で必須となるのに対し，メタヒューリスティクスで必須となる情報は決定変数とその評価値情報のみであるため，目的関数が不明な場合でも近年発展しているシミュレータや計測技術を使用することによって，数式モデルで表現できない，あるいは最適化手法を適用できる形にモデルを定式化できないシステムに対しても最適化手法の適用が可能であるため汎用性の面で大きな利点がある。また，任意の計算時間で探索を行うことができ，その計算量に応じて最適性の高い解を得ることができる。これまで開発された代表的なメタヒューリスティクスの多くは，何らかの自然現象・物理現象などの構造に着目し，その構造を類推することで効率的な探索を実現してきた。例えば，Particle Swarm Optimization(PSO) は鳥などの群れの動き，Simulated Annealing(SA)は金属の焼鈍し，Genetic Algorithm(GA) は生物の進化といったアナロジーに立脚して構築されている。本論文では，自然現象のアナロジーに基づいて開発された個々のアルゴリズムのダイナミクスに着目するのではなく、多くのメタヒューリスティクスに共通する，最適化手法として用いるために必要な基本的な探索構造・探索戦略を解析し，最適化手法として本質的に必要な構造を有した組合せ最適化手法の枠組みの構築を目的とする。組合せ最適化問題はスケジューリングや割り当て，最短経路探索など問題によって解構造や問題の性質が全く異なってくる。そこで，現実にある多くの最適化問題において成立すると考えられる近接最適原理（Proximate Optimality Principle : POP) に着目して研究を行う。POP とは「よい解同士は何らかの類似構造を持つ」という漠然とした概念である。メタヒューリスティクスの多くは数学的な最適性の証明ができない代わりに、アナロジーと数値実験においてその妥当性を主張している。自然現象などのアナロジーに基づいて開発されたメタヒューリスティクスが最適性の高い解を得られる背景にあるのがPOPであり，メタヒューリスティクスにはPOP を活用する何らかの探索戦略が用いられている。POPを有効に活用することで組合せ最適化問題の持つ広大な解空間全域を探索することなく，良い解があると予測される有望な領域のみを効率的に探索し，短い時間で最適性の高い解を得ることが可能になる。本論文では，漠然とした概念であるPOP を「部品」・「距離」の観点から定量的に評価し，最適化手法の改善ツールとして用いることで，POPを容易に探索に取り入れることを可能とした。定量的に評価したPOP を探索構造に組み入れることで，様々な観点から従来の最適化手法を改善し，多種多様にある組合せ最適化問題の多くに適用できる高い汎用性と探索性能を持った新たな最適化手法の開発を行う。本論文では，定量的に評価したPOP の活用の有効性を確認するため，POP に基づく組合せ最適化手法の一例として，新たな近傍生成構造を持つ最適化手法を提案する。提案手法では，最も単純な局所探索を行うLocal Search の探索構造に着目し，「部品」を用いて支配的な計算負荷となっている近傍の生成・評価を効率的に行う。改善可能性の高い近傍のみを生成することで近傍の生成・評価回数を減少させて計算時間を短縮し，大規模問題におルを定式化できないシステムに対しても最適化手法の適用が可能であるため汎用性の面でける適用を容易にした手法となっている。また，「距離」を用いることで探索範囲の制御を行い，探索性能の向上を図っている。解表現や問題の性質が異なるいくつかの代表的な組合せ最適化問題を用いて数値実験を行い，提案手法の汎用性と有用性を検証した。
-
Other
首都大学東京, 2012-03-25, 修士（工学）
|
| 日付 |
|
| 言語 |
|
| 資源タイプ |
thesis |
| 出版タイプ |
VoR |
| 資源識別子 |
HDL
http://hdl.handle.net/10748/5107
,
URI
https://tokyo-metro-u.repo.nii.ac.jp/records/2510
|
| 収録誌情報 |
|
| ファイル |
|
| コンテンツ更新日時 |
2023-08-21 |
