組合せ最適化問題のためのカオス的ニューラルネットモデルの数理と大規模問題への応用

本年度は、本研究課題内で昨年度までに提案した最適化手法(λ-DCN)について、力学的性質などに関する数理的考察を加え、またそれを元に新しい手法を提案した。昨年度までにORで広く用いられている局所探索法であるλopt法のアナログ版を開発した。本手法では、λ近傍と呼ばれる局所的領域において緩和型と呼ばれるダイナミクスを用いて解を探索する。またこれを非平衡に続けることにより逐次的な解の改善を行なう。本手法を非常に難しい組合せ最適化問題として知られる2次割当て問題(QAP)に応用した結果、我々の手法はQAPに対する現在最も強力なアルゴリズムの一つであることが分かった。実際、いくつかのベンチマーク問題について、今までのチャンピオンデータを上回る成績が得られている。本年度は、まず本手法の収束性の証明を得た。これにより応用性が増すと考えられる。また、昨年度までの手法にORで用いられる内点法を応用した新しいアルゴリズム(λ内点法)を開発した。本手法もまた、いくつかのベンチマーク問題について、今までのチャンピオンデータを上回る成績を得ることができた。さらに本研究課題内で開発したアルゴリズムの力学的性質を調べた。その結果、用いている非平衡ダイナミクスに、単に探索に乱数として作用する、あるいは初期値をバラつかせるといった効果を超えて、逐次的に解空間を探索していく効果的な作用があることが分かった。今後後継研究課題において、基盤配線などの実問題に応用する。

本年度は、本研究課題内で昨年度までに提案した最適化手法(λ-DCN)について、力学的性質などに関する数理的考察を加え、またそれを元に新しい手法を提案した。昨年度までにORで広く用いられている局所探索法であるλopt法のアナログ版を開発した。本手法では、λ近傍と呼ばれる局所的領域において緩和型と呼ばれるダイナミクスを用いて解を探索する。またこれを非平衡に続けることにより逐次的な解の改善を行なう。本手法を非常に難しい組合せ最適化問題として知られる2次割当て問題(QAP)に応用した結果、我々の手法はQAPに対する現在最も強力なアルゴリズムの一つであることが分かった。実際、いくつかのベンチマーク問題について、今までのチャンピオンデータを上回る成績が得られている。本年度は、まず本手法の収束性の証明を得た。これにより応用性が増すと考えられる。また、昨年度までの手法にORで用いられる内点法を応用した新しいアルゴリズム(λ内点法)を開発した。本手法もまた、いくつかのベンチマーク問題について、今までのチャンピオンデータを上回る成績を得ることができた。さらに本研究課題内で開発したアルゴリズムの力学的性質を調べた。その結果、用いている非平衡ダイナミクスに、単に探索に乱数として作用する、あるいは初期値をバラつかせるといった効果を超えて、逐次的に解空間を探索していく効果的な作用があることが分かった。今後後継研究課題において、基盤配線などの実問題に応用する。