組合せ最適化問題に対するアルゴリズム開発と数値実験

本年度の研究実績は,大きく二つに分けられる.一つは,個々の組合せ最適化問題に対する解法の比較であり,もう一つは,種々の解法を総括して一段高い見地から見た一般的な枠組みを提案することである.まず標準的な比較対象として用いられているグラフ分割問題を取り上げ,代表的なメタヒューリスティックであるTabu SearchとSimulated Anncaling法を比較対象した.比較を行うためにTabu Searchをもとにした実験的解析ツールであるLife Span Method(寿命法)およびSimulated Annealing法の改良であるRe-annealing法を設計した.その後,系統的な実験的解析によりLife Span MethodのRe-annealing法に対する有効性を示した.それに伴い,アルゴリズムに内在する種々のパラメータの適正値に対する知見を示した.同様の検討をグラフ上の重要な組合せ最適化問題であるグラフ彩色問題および最大クリーク問題に対して行い,Life Span Methodの有効性を示した.また,スケジューリング問題の中でも最も困難であると言われているジョブショップスケジューリング問題に対してもLife Span Methodを適用し,従来法に対する有効性を実験的解析によって示した.これらの成果を踏まえて,種々のメタヒューリスティックスを一段高い見地から総括した解法(Generic Local Scarch)を構築した.これらの成果は,Life Span Methodとともに「離散構造とアルゴリズムIV」(近代科学社)の中の一章(メタヒューリスティックス)および計測自動制御学会論文誌の特集論文にまとめられている.また,メタヒューリスティックスの代表的な方法であるニューラルネット法,遺伝的アルゴリズムの研究者とともに,メタヒューリステックの有効性を論じるためのシンポジウムおよびセミナーを開催した.題目および講演者は以下の通りである.日本オペレーションズリサーチ学会シンポジウム「モダンヒューリスティックスの新展開Genetic Algorithm,Simulated Annealing,Tabu Search,Neural Net法は本当に有効か?-」(講演者:茨木(京大),武藤(慶大),玉置(京大),久保),日本オペレーションズリサーチ学会セミナー「モダンヒューリスティックス-Neural Network,Genetic Algorithm,Simulated Annealing,Tabu Searchの基礎から最新動向まで-」(講演者:甘利(東大),田中(茨城大),久保)

本年度の研究実績は,大きく二つに分けられる.一つは,個々の組合せ最適化問題に対する解法の比較であり,もう一つは,種々の解法を総括して一段高い見地から見た一般的な枠組みを提案することである.まず標準的な比較対象として用いられているグラフ分割問題を取り上げ,代表的なメタヒューリスティックであるTabu SearchとSimulated Anncaling法を比較対象した.比較を行うためにTabu Searchをもとにした実験的解析ツールであるLife Span Method(寿命法)およびSimulated Annealing法の改良であるRe-annealing法を設計した.その後,系統的な実験的解析によりLife Span MethodのRe-annealing法に対する有効性を示した.それに伴い,アルゴリズムに内在する種々のパラメータの適正値に対する知見を示した.同様の検討をグラフ上の重要な組合せ最適化問題であるグラフ彩色問題および最大クリーク問題に対して行い,Life Span Methodの有効性を示した.また,スケジューリング問題の中でも最も困難であると言われているジョブショップスケジューリング問題に対してもLife Span Methodを適用し,従来法に対する有効性を実験的解析によって示した.これらの成果を踏まえて,種々のメタヒューリスティックスを一段高い見地から総括した解法(Generic Local Scarch)を構築した.これらの成果は,Life Span Methodとともに「離散構造とアルゴリズムIV」(近代科学社)の中の一章(メタヒューリスティックス)および計測自動制御学会論文誌の特集論文にまとめられている.また,メタヒューリスティックスの代表的な方法であるニューラルネット法,遺伝的アルゴリズムの研究者とともに,メタヒューリステックの有効性を論じるためのシンポジウムおよびセミナーを開催した.題目および講演者は以下の通りである.日本オペレーションズリサーチ学会シンポジウム「モダンヒューリスティックスの新展開Genetic Algorithm,Simulated Annealing,Tabu Search,Neural Net法は本当に有効か?-」(講演者:茨木(京大),武藤(慶大),玉置(京大),久保),日本オペレーションズリサーチ学会セミナー「モダンヒューリスティックス-Neural Network,Genetic Algorithm,Simulated Annealing,Tabu Searchの基礎から最新動向まで-」(講演者:甘利(東大),田中(茨城大),久保)