大規模組合せ最適化問題に対する効率的メタ戦略の設計と評価

多くのシステム工学的、情報工学的問題は、組合せ最適化問題として定式化できる。しかし、その多くに対して、取り扱おうとする問題の規模が大きい場合、厳密な最適解を求めることがきわめて困難である。このような問題に現実的に対処するための一手法として、メタ戦略の研究が盛んである。メタ戦略の代表的なものとして、遺伝アルゴリズム、アニーリング法、タブー探索法などがあるが、本研究では、これらを局所探索の一般化と考えることで統一的に捉えて、様々なアイディアを体系的に整理し、そのような視点のもとで、効率的なアルゴリズムを設計するための指針を得るべく研究を行った。メタ戦略アルゴリズムの一つの魅力として、その手軽さが挙げられる。すなわち、多くの問題に対して比較的容易に適用でき、しかもかなりの精度が期待できる点である。この観点から、これまでに1機械スケジューリング問題と最大充足可能性問題に対して計算実験を行い、一定の成果を上げていた。本年度は、最大充足可能性問題に対する計算実験を継続して行うとともに、集合被服問題、一般化時間枠制約つき配送計画問題など、より多くの問題に対して計算実験を行い、「手軽なツール」としてのメタ戦略の設計指針を考察した。その結果、反復局所探索法がこの目的に適しているという結論を得ている。反復局所探索法は、過去の探索で得られたよい解(暫定解など)にランダムな変形を加えたものを局所探索の初期解として、局所探索法を反復する方法で、単純であるが、比較的高性能であることが我々の計算実験を通して確認されたからである。メタ戦略のもう一つの魅力として、様々な工夫を加えることでより性能の高いものを作ることができる点が挙げられる。本研究では、メタ戦略に加える工夫の中でも、とくに、局所探索の基本的な部分にかかわる性能向上・効率化に重点を置いた。本年度は、一般化割当問題や、それをさらに一般化した問題などに対して、単純な近傍をより高度に組み合わせる、排除連鎖法と呼ばれる手法を適用し、高い能力を有するメタ戦略アルゴリズムの設計に成功した。集合被服問題に対しても、近傍の探索効率を大幅に落とすことなくより広い近傍を探索する工夫を加えることにより、性能の向上を図った。研究費により購入した計算機器は、上述の計算実験を遂行し、また、それらの結果を取りまとめるのに利用した。さらには、研究成果を報告するための海外渡航費としても利用した。

多くのシステム工学的、情報工学的問題は、組合せ最適化問題として定式化できる。しかし、その多くに対して、取り扱おうとする問題の規模が大きい場合、厳密な最適解を求めることがきわめて困難である。このような問題に現実的に対処するための一手法として、メタ戦略の研究が盛んである。メタ戦略の代表的なものとして、遺伝アルゴリズム、アニーリング法、タブー探索法などがあるが、本研究では、これらを局所探索の一般化と考えることで統一的に捉えて、様々なアイディアを体系的に整理し、そのような視点のもとで、効率的なアルゴリズムを設計するための指針を得るべく研究を行った。メタ戦略アルゴリズムの一つの魅力として、その手軽さが挙げられる。すなわち、多くの問題に対して比較的容易に適用でき、しかもかなりの精度が期待できる点である。この観点から、これまでに1機械スケジューリング問題と最大充足可能性問題に対して計算実験を行い、一定の成果を上げていた。本年度は、最大充足可能性問題に対する計算実験を継続して行うとともに、集合被服問題、一般化時間枠制約つき配送計画問題など、より多くの問題に対して計算実験を行い、「手軽なツール」としてのメタ戦略の設計指針を考察した。その結果、反復局所探索法がこの目的に適しているという結論を得ている。反復局所探索法は、過去の探索で得られたよい解(暫定解など)にランダムな変形を加えたものを局所探索の初期解として、局所探索法を反復する方法で、単純であるが、比較的高性能であることが我々の計算実験を通して確認されたからである。メタ戦略のもう一つの魅力として、様々な工夫を加えることでより性能の高いものを作ることができる点が挙げられる。本研究では、メタ戦略に加える工夫の中でも、とくに、局所探索の基本的な部分にかかわる性能向上・効率化に重点を置いた。本年度は、一般化割当問題や、それをさらに一般化した問題などに対して、単純な近傍をより高度に組み合わせる、排除連鎖法と呼ばれる手法を適用し、高い能力を有するメタ戦略アルゴリズムの設計に成功した。集合被服問題に対しても、近傍の探索効率を大幅に落とすことなくより広い近傍を探索する工夫を加えることにより、性能の向上を図った。研究費により購入した計算機器は、上述の計算実験を遂行し、また、それらの結果を取りまとめるのに利用した。さらには、研究成果を報告するための海外渡航費としても利用した。