宇都宮大学 研究シーズ集 2024.04
196/324

組合せ最適化問題には、ネットワーク設計問題、配送計画問題、施設配置問題(図1)、スケジューリング問題などがあり、社会に現れる現実問題の多くが組合せ最適化問題として定式化できます。企業においても、製品開発やシステム開発で、組合せ最適化問題を解かなければならない事例が数多く存在します。これら組合せ最適化問題の多くは、問題の規模が大きい場合に厳密に最適解を求めることが極めて困難であるNP困難な問題として、計算の複雑さの理論により明らかにされてきました。NP困難な問題では、問題サイズが大きくなると組合せ数が爆発的に増加するため(図2)、すべての組合せを調べることは現実的ではありません。本研究室では、このようなNP困難な問題に対して、現実的な時間内にできるだけよい近似解を求めることを目的とした、進化計算などのメタ戦略を用いたアルゴリズムの開発を行っています。NP困難な問題の中でも、さらに難しい、大規模な組合せ最適化問題(約1030000通りの組合せ)に関する研究を行っています。教育・研究活動の紹介最適化問題は、対象となる問題によって様々な特徴があり、これらの特徴を最適化アルゴリズムに組み入れることにより、より効率の良い探索アルゴリズムの開発が可能となります。本研究室では、2次割当問題やバイナリー2次計画問題、最大多様性問題など、様々な最適化問題に対するアルゴリズムの開発経験があり、これらの経験を生かしたアルゴリズムの開発が可能です。また、大規模な組合せ最適化問題に対する研究を行っている所はまだ少ないため、こうした問題への対応も可能です。今後の展望近年の情報技術の急速な発展や、ビッグデータに代表される解析データサイズの巨大化等に伴い、組合せ最適化問題における応用上重要な問題はますます大規模化・複雑化してきています。本研究室では、こうした、大規模化・複雑化する問題に対応できるよう、研究を進めています。社会貢献等特許出願状況・特願2013-124241(特徴と強み等)(社会活動特許等取得状況産学連携・技術移転の対応等)ー情報通信、その他(ソフトコンピューティング)・大規模な組合せ最適化問題に対するメタ戦略アルゴリズムの開発・進化計算を用いた最適化アルゴリズムの開発進化計算,遺伝的アルゴリズム,メタ戦略,組合せ最適化電子情報通信学会、情報処理学会、映像メディア学会とやまふびと2017年4月更新分野研究テーマキーワード所属学会等特記事項URL: Mail: fubito[at]is.utsunomiya-u.ac.jp研究概要図1 施設配置問題の例(問題サイズ:4)図2 問題サイズと組合せ数基盤工学科情報電子オプティクスコース外山研究室工学部教授外山史

元のページ  ../index.html#196

このブックを見る