| 内容要旨 | | 組合せ最適化問題は,組合せ的な制約条件のもとで,ある目的関数を最小(大)にする問題である.組合せ最適化は多くの工学的な応用を持ち,実社会においてもいろいろなところに現れてくる.しかし,現状では問題を人手で解いていることも多く,自動化のニーズが高い. このようなニーズによって,組合せ最適化の研究は古くからオペレーションズ・リサーチの分野で行なわれてきた.しかしほとんどの組合せ最適化問題はNP-困難であることが知られており,実用規模の問題に対しては,分枝限定法のような厳密な解法の効率は急激に悪化することが普通である.また,現実においては厳密な最適解でなくても,最適解に近い解を効率良く求めることが必要とされている問題も数多く存在している. このような観点から,最適解に近い近似最適解を効率良く求めることを目的として,各種の近似解法が開発されてきたが,それでも大規模で難しい問題に対しては,効率が悪くなったり,解の質が十分でなかったりすることもしばしば起こっている.これらの近似解法の性能が十分ではない大きな理由としては,これらの手法が汎用的であり,各問題ごとの固有の構造を利用していないことがあげられる. 逆に,良く知られた特定の問題に対しては,問題の構造を利用した効率的な探索アルゴリズムが開発されているが,現実の複雑で多様な問題に対してこのようなアルゴリズムを個別に開発することは困難である. また,人工知能におけるエキスパートシステムは,人間のエキスパートのもつ知識をルールの形で計算機にいれることによって,個々の問題に適した問題解決を実現しようとする試みである.実際に数百,数千のルールを蓄えることによって,短時間で専門家なみの解を求めるシステムもいくつか開発されてきた.しかし,研究・開発が進むに連れて,専門家から正確で十分な知識を取り出すことの困難さ,いわゆる知識獲得ボトルネックの存在が明らかになり,実用化の大きな障害となってきている. 以上のことから,本研究では,エキスパートシステムのようにルールを外部から与えるのではなくて,システムが自動的に個々の問題の構造を捕らえて,効率的に探索を行なう手法を開発することを目標とした. 本研究では,個々の問題の構造を捕らえるための一つの手法として,極小矛盾という概念に着目し,探索中にこの極小矛盾を発見し,それを保存,利用することによって,効率的な探索を実現することをめざした.極小矛盾は,現在の候補解の部分集合の中で,その部分集合を含むことによって制約を充足することができないような,極小のものである. 組合せ最適化に対して近傍探索を適用する場合の問題点は,局所最適解が存在することである.極小矛盾は,局所最適解に陥ったときに,現在の解のどの部分が悪いのかを分析し,その情報を用いて探索を正しい方向にガイドしていく役割を果たす.この結果,局所最適解から脱出して,サイクルを生じないように探索を続けることができる.また極小矛盾探索は,極小矛盾中の仮説を変更することによって近傍生成を行なうので,山登り法などと比較して無駄な近傍生成を削減することができる.極小矛盾は蓄積され,まだ探索されていない解に対しても作用し,探索空間を枝刈りする効果もある.図1に基本的な極小矛盾探索のアルゴリズムを示す.  図1:極小矛盾探索 この極小矛盾探索を,ほとんどの組合せ最適化問題を定式化することができる汎用性を持っている混合0-1整数計画問題に対して適用した.ここでは,全0-1整数計画問題に対する極小矛盾探索と線形計画問題に対するシンプレックス法を融合する手法を提案した.この手法では,まず0-1変数の値を決定して,残った連続変数によって構成される線形計画問題をシンプレックス法を用いて解く.次に線形計画問題を解いた結果から0-1変数に関する違反制約と極小矛盾を求める.この極小矛盾は極小矛盾集合に蓄えられ,0-1変数に対して近傍探索が行なわれ,新しい線形計画問題が構成される.以上のサイクルを繰り返すことによって,探索が進められる(図2).  図2:混合0-1整数計画問題に対する極小矛盾探索 代表的な混合0-1整数計画問題である多品種生産計画問題を対象として,分枝限定法や従来のヒューリスティック手法との計算機実験による比較を行なった結果,極小矛盾探索は,問題固有のヒューリスティックを用いることなく,従来のヒューリスティック手法を上回る解を求めることができることを示した.また分枝限定法が効率的に動作しないような大規模な問題においても,短時間に良い解を発見することができることを示した. また,組合せ最適化における重要な分野のひとつであるスケジューリング問題に対して,極小矛盾探索を適用した.まず,極小矛盾の概念を用いることによって,スケジューリング問題において重要なクリティカルパスの概念を導出できることを示した.次にクリティカルパスを用いた極小矛盾探索アルゴリズムを提案し,スケジューリング問題の中でも最も困難なジョブショップスケジューリング問題に対する最も有効な手法であるシミュレーテッド・アニーリングとの計算機実験による比較を行なった.極小矛盾探索は同じ実行時間でシミュレーテッド・アニーリングよりも良い解を発見できることがわかった.また極小矛盾探索はシミュレーテッド・アニーリングと比較して,実行の早い時期に良い解を発見することがわかり,大規模な実用的な問題に対する有効な手法となることを示した. 極小矛盾探索を効率化する手法として,(1)極小矛盾をO(nlogn)で発見するアルゴリズム,(2)極小矛盾をビットベクタによって表現することによって,包含チェックを高速に実行する手法,(3)含まれる仮定の数によって極小矛盾集合を分類・管理することによって,チェックする極小矛盾の数を減らす手法を開発した. 極小矛盾探索は問題に依存しない汎用性の高い手法であり,これまでの研究を通して,既存の手法と比較して,効率的に最適解もしくは最適解に近い実用的な解を求めることができることを示した.極小矛盾探索は,効率の良いヒューリスティックが存在しないような大規模で複雑な現実問題に対する有効な手法になると考える. |