大規模スケジューリング問題の特性解析および局所探索とルールに基づく解法の提案

本研究では，大規模スケジューリング問題のための近似解法として，スケジューリング問題特有のヒューリスティクスである割付け規則を解の探索へと応用する方法について研究を進めている．前年度までに，解の探索と使用する割付け規則の更新を同時に進めることで，より有効な割付け規則の抽出および探索への再利用を行う大規模問題向けの効率的な探索方法について研究を進めてきた．当初の研究計画に則り，今年度は特に計算並列性に着目し，蟻コロニー最適化に基づく解法について，動的に更新され続ける割付け規則を適用するためアルゴリズムの更新ならびにパラメータの特定を行った．この研究を通して，蟻コロニー最適化において既存の暫定解を確率的に表現するフェロモンマップの更新を，割付け規則の更新と同時に行う場合の問題点を明らかにした．また，こうした問題点を回避し，有効な並列探索アルゴリズムを構築するためには，フェロモンマップを固定し割付け規則のみを更新するフェーズ，割付け規則を固定しフェロモンマップのみを更新するフェーズの二つを定義し，これらを複数回繰り返す方法について議論を進め，有効性検証を行っている．以上の研究成果に加え，特に蟻コロニー最適化など群知能を基礎とした並列アルゴリズムについて知見を深めるため，前年度から引き続き海外研究機関に長期滞在し，現地の研究者ならびに博士課程の学生とともに研究を進めた．本滞在は同知見獲得の目的のみならず，日常的に英語によってコミュニケーションをとりながら研究を進めていく貴重な経験を得られた．

本研究では，大規模スケジューリング問題のための近似解法として，スケジューリング問題特有のヒューリスティクスである割付け規則を解の探索へと応用する方法について研究を進めている．前年度までに，解の探索と使用する割付け規則の更新を同時に進めることで，より有効な割付け規則の抽出および探索への再利用を行う大規模問題向けの効率的な探索方法について研究を進めてきた．当初の研究計画に則り，今年度は特に計算並列性に着目し，蟻コロニー最適化に基づく解法について，動的に更新され続ける割付け規則を適用するためアルゴリズムの更新ならびにパラメータの特定を行った．この研究を通して，蟻コロニー最適化において既存の暫定解を確率的に表現するフェロモンマップの更新を，割付け規則の更新と同時に行う場合の問題点を明らかにした．また，こうした問題点を回避し，有効な並列探索アルゴリズムを構築するためには，フェロモンマップを固定し割付け規則のみを更新するフェーズ，割付け規則を固定しフェロモンマップのみを更新するフェーズの二つを定義し，これらを複数回繰り返す方法について議論を進め，有効性検証を行っている．以上の研究成果に加え，特に蟻コロニー最適化など群知能を基礎とした並列アルゴリズムについて知見を深めるため，前年度から引き続き海外研究機関に長期滞在し，現地の研究者ならびに博士課程の学生とともに研究を進めた．本滞在は同知見獲得の目的のみならず，日常的に英語によってコミュニケーションをとりながら研究を進めていく貴重な経験を得られた．