ホーム » 研究紹介 » 組合せ最適化のためのGAの開発

組合せ最適化のためのGAの開発

組合せ最適化は,決定変数が連続値でない最適化問題であり,さまざまな分野において幅広く現れる非常に重要な問題です.代表的な組合せ最適化問題としては,ナップザック問題,巡回セールスマン問題(TSP),ジョブショップスケジューリング問題(JSP)などがあります.

これまで,最も困難な組合せ最適化問題のひとつであるJSPを対象に,Inter-machine Job-order Crossover (Inter-machine JOX)などの交叉を開発してきました.JSPは,n個の仕事を完成させるためのm台の機械の処理順序(技術的順序)および各仕事の各機械上での処理時間が与えられたとき,総所要時間を最小化するような各機械に対する仕事の投入順序を求める問題です.

小野研究室では,困難な組合せ最適化問題を解決するためのコード化/交叉,世代交代モデルの開発に取り組んでいます.