誘導遺伝的アルゴリズムを用いたスケジューリング問題の解法

カテゴリ: 全国大会

論文No: 3-098

グループ名: 【全国大会】平成19年電気学会全国大会論文集

発行日: 2007/03/15

タイトル(英語): A Method of Solving Scheduling Problems Using Guided Genetic Algorithm

著者名: 王 暁飛(富山大学),田村 宏樹(宮崎大学),淡野公一 (宮崎大学),唐堂 政明(富山大学)

著者名(英語): Gyouhi,Ou|Hiroki,Tamura|Koichi,Tanno|Masaaki,Toudou

キーワード: ジョブショップスケジューリング問題|遺伝的アルゴリズム|誘導遺伝的アルゴリズム

要約(日本語): ジョブショップスケジューリング問題（以降JSPと呼ぶ）は難解な組合せ最適化問題の一つである．遺伝的アルゴリズム（以降GA と呼ぶ）で組合せ最適化問題を解く際，GAの特性上極小値又は極小値と思われる状態に陥る可能性が高く，脱出は確率に大きく依存する．この問題を解決する方法として他の手法とGAを組み合わせるハイブリッドGAが数多く提案されている．本研究ではGAとメタ戦略の1つのテクニックである誘導局所探索法を合わせた誘導遺伝的アルゴリズムをJSPに適した方法に改良する．そして，その有効性を計算機実験により示す．計算機実験の結果，提案法した誘導遺伝的アルゴリズムはGAよりも同じ時間でより良い解を得る確率が高いことが分かった．

原稿種別: 日本語

PDFファイルサイズ: 1,051 Kバイト