遺伝的アルゴリズムの組合せ最適化問題への応用 : トラック配車計画化問題

概要

論文の詳細を見る
遺伝的アルゴリズムを組合せ最適化問題に応用し,良好な結果を得たのでここに報告する.遺伝的アルゴリズム(Genetic Algorithm,以下GAと略記する)は,生物の進化にヒントを得た探索手法のひとつである.その特徴として,解候補(以下,個体と記す)の集団を扱うこと,確率的な手法であること,対象とする問題の構造によらないこと,局所解からの脱出が可能なこと等が挙げられる.GAの基本的な手順は次のようなものである.(1)個体集団の初期化,(2)親となる個体の選択,(3)遺伝的オペレータを親に適用し子を得る,(4)子を個体集団に加える,(5)淘汰,(6)終了条件を満たすまで(2)から(5)を繰り返す.GAをスケジューリングに応用した例としては,問題を変形しTraveling Salesman Problemとして解いた等があるスケジューリング問題であるトラック配車計画問題をGAと全解探索手法とを結合して,組合せ最適化問題に変形することにより探索空間を減少させ,専門家の作成した解よりも良好な結果を得ることができたので報告する.
社団法人情報処理学会の論文
1992-09-28