SDGsの分類
研究テーマ
IT・IoT・AI・ロボティクス
学科の分類
工学部電気電子システム工学科

超大規模組合せ最適化問題に対する新解法の提案

工学部

電気電子システム工学科

システム最適化研究室

重弘裕二 教授

設計、割り当て、スケジューリング等、様々な問題は組合せ最適化問題として定式化できる。しかし、実応用において厳密に最適な解を求めるのが不可能な場合も多い。そのような状況においても可能な限り良質な解を探索するために、これまでにも遺伝的アルゴリズムのような手法が提案されているが、万能ではない。本研究では、特に超大規模な組合せ最適化問題を対象とし、確率論、統計論的な観点から、最適と考えられる方法を追究している。

背景

設計、割り当て、スケジューリング等、実社会には様々な問題が存在する。それらの問題に対し、設計結果や割り当て結果は「解」と呼ばれる。例えば「与えられた制約にしたがって配置設計を行え」という問題に対しては、「制約を満たした配置結果」が解（実行可能解）に当たる。

例えば配置設計問題に対しては、様々な配置結果が考えられる。その中には良いものもあれば悪いものもある。もちろん、設計を行うにあたっては、良い配置結果を得たい。したがって、良い配置結果を得るためにはどうすれば良いのだろうかという研究が行われてきた。

残念ながら、実応用上の多くの配置設計問題では（例えばLSIのレイアウト設計問題など）、最良の配置結果を「組み立てるようなやり方で」構成する方法が存在せず、「実際に全ての配置結果を構成してみて、その中で一番良いものを選ぶ」といったようなやり方でしか最良の配置結果を求めることができない。しかし、問題の規模が大きくなると考えられる配置結果の数が爆発的に増大するため（組合せ爆発と呼ばれる）、規模の大きな問題に対しては、全ての配置結果を調べることは不可能となる。これは、最も良い配置結果を求めることは不可能であるということを意味している。

目的・内容

ここまでは配置設計問題で説明したが、その他の設計問題や、あるいは割り当て問題、スケジューリング問題等々、多くの問題が「組合せ最適化問題」として記述でき、それらは全て同じ状況に置かれている。そこで本研究では組合せ最適化問題において、できる限り良い解を探索する方法を追究し、その結果として例えば配置設計問題に対して、できる限り良い配置結果を探索することを目指している。

特に、規模が大きな問題においては、できる限り少ない計算資源（計算時間等）で、できる限り良い解を探索する必要がある。そこで本研究では、解を探索するための手順を複数用意しておき理論的に（確率・統計論的）に最も良い手順を選んで探索を行うための方法について考察している。特に、解の探索を行いながら統計量を推定する方法について研究を進めている。

用途

研究では、既存の組合せ最適化問題に対する手法では扱うことができないような巨大な問題あるいは既存の組合せ最適化問題に対する手法では時間が掛かり過ぎてしまうような問題に対して良い解を求めることを目指している。

研究者INFO: 工学部 電気電子システム工学科 システム最適化研究室 重弘裕二 教授

研究シーズ・教員に対しての問合せや相談事項はこちら

技術相談申込フォーム