ジョブショップスケジューリング問題に対する 遺伝的アルゴリズムの交叉の検討 A Discussion on Crossover of Genetic Algorithm for Job-shop Scheduling Problem 同志社大学大学院工学研究科知識工学専攻 博士前期課程 2003年度 724番 森 隆史 はじめに スケジューリング問題 • 交通機関の時刻表の決定 • 病院の看護士勤務順の決定 • 工場での生産スケジュールの決定 最適なスケジュールの生成は非常に重要 スケジューリング問題の1つ ジョブショップスケジューリング問題 （Job-shop Scheduling Problem ： JSP） ジョブショップスケジューリング問題（JSP） 一定数の仕事を一定数の機械で処理する時の 最適なスケジュールを求める 全体の処理にかかる時間（makespan）の最小化 ＜問題による制約＞ • 各仕事が機械を使う順序（技術的順序） • 各仕事が各作業を各機械上で処理する時間 JSPの具体例 JSPの具体例 JSPの具体例 JSPの最適化 JSPには技術的順序などの制約条件がある JSPの最適化は非常に困難 JSPに特化した手法でなければ，簡単に制約を外れてしまう 高性能で汎用性の高い最適化手法 遺伝的アルゴリズム（Genetic Algorithm : GA） による最適化 ＜GAで考慮する点＞ • 個体の表現方法 • 遺伝的オペレータ 遺伝的アルゴリズム（GA） • 生物の進化を模倣した最適化手法 • 多点探索 • 選択，交叉，突然変異を繰り返し適用し 個体を進化させ，最適化を行う 交叉 ： 個体情報の交換手段 GAは多点探索であり， 個体（解）間の情報交換を行うことで最適化を行う 適切な交叉の設定が重要 ＜研究目的＞ JSPの最適化の際に適切な交叉手法について検討 個体の表現方法 交叉 一般的な交叉手法を用いると 制約条件を満たせない可能性が高い 制約を満たすことができる交叉手法 • Inter-machine Job-based Crossover （Inter-machine JOX）[小野,1998] JSPに有効である交叉手法 • Deterministic Multi-step Crossover Fusion （dMSXF）[Ikeda,2002] JSPに有効なMSXFを元に提案された手法 温度パラメータの設定が必要ない Inter-machine JOX Step 1 2つの親個体のペアを選択 Inter-machine JOX Step 1 2つの親個体のペアを選択 Inter-machine JOX Step 2 保存する仕事として1つ以上の仕事を選択（ここではJ2） Inter-machine JOX Step 3 残りの仕事を順序を崩さないように他方の親から継承 Inter-machine JOX Step 3 残りの仕事を順序を崩さないように他方の親から継承 Inter-machine JOX Deterministic Multi-step Crossover Fusion Step 1 2つの親個体のペアを選択 Deterministic Multi-step Crossover Fusion Step 2 親1の周りに子個体を生成 生成される個体は全て親2に近づく Step 3 生成された個体の中でもっとも良い個体を選択 Deterministic Multi-step Crossover Fusion Step 2 親1の周りに子個体を生成 生成される個体は全て親2に近づく Step 3 生成された個体の中でもっとも良い個体を選択 Deterministic Multi-step Crossover Fusion Step 4 もっとも良い個体に関して同じ操作を繰り返す Step 5 生成された個体の中で最も良い個体を選択 • 親個体の周りに個体を生成する方法（近傍） • 他方の親へ近づいているかの判定方法（距離） 近傍 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 近傍 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 近傍 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 近傍 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 近傍 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 近傍 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 個体間の距離 dMSXFにおける個体生成 一方の親個体から他方の親個体に近づくよう個体を生成する 個体間の距離を図る必要がある ＜距離の測定方法＞ • 各機械上である仕事の 次の仕事が違う場合 距離を 1 増加させる • 各機械上である順番で 処理される仕事が異なるとき 距離を1増加させる 距離の測定方法 距離の測定方法 距離の測定方法 ＜処理する作業が異なる順序＞ 1番目 距離の測定方法 ＜処理する作業が異なる順序＞ 1番目，2番目 ・・・ 2個 距離の測定方法 ＜処理する作業が異なる順序＞ 1番目，2番目 ・・・ 2個 ＜次に処理する作業が異なる仕事＞ J1 距離の測定方法 ＜処理する作業が異なる順序＞ 1番目，2番目 ・・・ 2個 ＜次に処理する作業が異なる仕事＞ J1，J2 ・・・ 2個 距離 = 2 + 2 = 4 Inter-machine JOXとdMSXFの比較 以下の2点について検討を行う • Inter-machine JOXとdMSXFの解探索性能の違い • 解探索性能が異なるとき，その原因 ＜比較手法＞ 交叉に以下の2つを適用したGAのモデル ・ Inter-machine JOX ・ dMSXF ＜対象問題＞ ft20（20仕事5機械問題） abz9（20仕事15機械問題） 実験パラメータ パラメータ 個体数 エリート個体数 値 600 5 交叉率 1.0 突然変異率 0.1 選択手法 最大評価計算回数 試行回数 トーナメント選択 （トーナメントサイズ： 2） 8.0e+6 100 解探索性能 ft20 abz9 Inter-machine JOXが良好な結果を示している 解探索性能の違い Inter-machine JOXの方が良好な解探索性能を示した Inter-machine JOXとdMSXFの 探索方法の違いが原因 ＜検討事項＞ • 探索途中での個体の多様性 多様性が失われると交叉が意味を成さない • 1回の交叉による個体の変化量 局所的探索か大域的探索か 個体の多様性 dMSXF ： 1回の交叉で個体を大量に生成し， 最も良い個体を子個体とする 選択圧が非常に高い可能性がある 選択圧が高いと母集団内の個体に多様性が無くなる 個体の多様性が失われると 交叉が無意味になってしまう （同じ親個体から新しい個体は生成されないため） 両交叉手法の多様性の変化について検討する 個体の多様性の変化 個体の多様性の変化について検討を行う ＜検討手法＞ 交叉に以下の2つを適用したGAのモデル • Inter-machine JOX • dMSXF ＜対象問題＞ ft20（20仕事5機械問題） abz9（20仕事15機械問題） 個体の多様性（ft20） Inter-machine JOX dMSXF Inter-machine JOX ： 探索序盤で良好な解を発見 dMSXF ： 良好な解を発見する前に多様性が無くなる 個体の多様性（abz9） Inter-machine JOX dMSXF Inter-machine JOX ： 探索序盤で良好な解を発見 dMSXF ： 良好な解を発見する前に多様性が無くなる 個体の多様性の変化とその影響 両手法ともに個体に多様性がある間は良好な探索 Inter-machine JOX • 探索序盤に多様性は急激に低下する • 探索終盤でもある程度多様性が維持される • 多様性が失われる前にある程度良好な解を発見できる dMSXF • 探索序盤はInter-machine JOXよりも多様性は大きい • 探索終盤は多様性は失われる • 多様性が失われる前にある程度良好な解を発見できない 最終的に発見された解は，Inter-machine JOXの方が良好 良好な解が発見できるまで 十分な個体の多様性が必要 交叉による個体の変化量 dMSXFでは親個体間に大量の個体を生成し，局所探索を行う 複数ステップ個体生成を続けるため， 最終的な子個体は大きく変化している可能性がある Inter-machine JOXとdMSXFの間に 個体の変化量の違いがある場合 一方は局所的探索，もう一方は大域的探索 探索する空間の広さが大きく異なる 交叉による個体の変化量の検討 交叉による個体の変化量について検討を行う ＜検討手法＞ 交叉に以下の2つを適用したGAのモデル • Inter-machine JOX • dMSXF ＜対象問題＞ ft20（20仕事5機械問題） abz9（20仕事15機械問題） 交叉による個体の変化（ft20） Inter-machine JOX dMSXF Inter-machine JOXの方が個体の変化量が大きい 個体の変化量に10倍程度の差が現れている 交叉による個体の変化（abz9） Inter-machine JOX dMSXF Inter-machine JOXの方が個体の変化量が大きい 個体の変化量に10倍程度の差が現れている 交叉による個体の変化量とその影響 Inter-machine JOXの方が個体が大きく変化 変化量の差は非常に大きい Inter-machine JOXは大域的探索 dMSXFは局所的探索 解探索性能はInter-machine JOXの方が良好 局所的探索ではなく 大域的な探索が重要 まとめ JSPをGAで最適化する際の交叉設定の指針について検討 JSPに有効なInter-machine JOX JSPに対して有効性が検討されていないdMSXF • 解探索性能はInter-machine JOXがdMSXFよりも良好 • 個体の多様性が維持されている間は良好な探索が可能 • 交叉による個体の変化が小さいと 個体の多様性が失われるまでに良好な解を発見できない JSPに対して有効な交叉設定の指針 • 十分な個体の多様性の維持 • 局所的探索よりも大域的探索 発表論文 三木光範，廣安知之，勝崎俊樹，森 隆史 「分散遺伝的アルゴリズムにおける 多様性を考慮した世代交代モデルの検討」 同志社大学 理工学研究報告 第45巻 第3号 2004年10月 Multi-step Crossover Fusion Multi-step Crossover Fusion（MSXF）[山田.1997] Step 1 親個体となる2個体を選択 Step 2 親1の周りに複数個の個体を生成する Step 3 生成された個体群を親2との距離が小さいものから順に並び替える Step 4 この順序に基づいたランキングルーレット選択により1個体を選択 Step 5 選択された個体が親個体よりも良好なら受理し， V の確率で受理する T そうでなければ， exp Step 6 選択された個体が受理されれば，その個体に関して処理を繰り返す そうでなければ，親個体に同じ処理を繰り返す 突然変異 距離の測定方法 距離の測定方法 距離の測定方法 ＜処理する作業が異なる順序＞ M1の1番目 距離の測定方法 ＜処理する作業が異なる順序＞ M1の1番目，M1の2番目，M1の3番目，M2の1番目， M1の2番目，M3の1番目，M3の2番目，M3の3番目 ・・・ 8個 距離の測定方法 ＜処理する作業が異なる順序＞ M1の1番目，M1の2番目，M1の3番目，M2の1番目， M1の2番目，M3の1番目，M3の2番目，M3の3番目 ・・・ 8個 ＜次に処理する作業が異なる仕事＞ 距離の測定方法 ＜処理する作業が異なる順序＞ M1の1番目，M1の2番目，M1の3番目，M2の1番目， M1の2番目，M3の1番目，M3の2番目，M3の3番目 ・・・ 8個 ＜次に処理する作業が異なる仕事＞ M1のJ1 距離の測定方法 ＜処理する作業が異なる順序＞ M1の1番目，M1の2番目，M1の3番目，M2の1番目， M1の2番目，M3の1番目，M3の2番目，M3の3番目 ・・・ 8個 ＜次に処理する作業が異なる仕事＞ M1のJ1，M1のJ2，M2のJ2，M2のJ3，M3のJ1，M3のJ3 ・・・ 6個 距離 = 8 + 6 = 14 Minimal Generation Gap Minimal Generation Gap（MGG）［佐藤ら,1996］ Step1 Step2 Step3 母集団からランダムに2個体を選出 同じ親個体から複数の子個体を生成 親個体と子個体の中から 良好な2個体を母集団に戻す ｛ 多様性の維持に優れる 形質遺伝に優れる （形質遺伝：親個体の良好な性質を 子個体に受け継ぐこと） ｓGAとMGGの違い ｓGA sGAは毎世代すべての個体を更新 MGGは2個体だけ更新していく MGG 多様性の維持 分散遺伝的アルゴリズム 分散遺伝的アルゴリズム（DGA）［Tanese,1989］ 母集団を複数のサブ母集団に分割する 各サブ母集団間で移住を行う 部分解を組み合わせて探索を行う 単一母集団GA DGA 解探索性能 Inter-machine JOXとdMSXFの比較 ＜比較手法＞ 交叉に以下の2つを適用したGAのモデル ・ Inter-machine JOX ・ dMSXF ＜対象問題＞ ft10（10仕事10機械問題） ft20（20仕事5機械問題） abz9（20仕事15機械問題） orb01（10仕事10機械問題） 解探索性能（ft20，abz9） ft20 abz9 Inter-machine JOXが良好な結果を示している 解探索性能（ft10，orb01） ft10 orb01 Inter-machine JOXが良好な結果を示している 解探索性能（ft20，abz9） MGG ft20 abz9 Inter-machine JOXが良好な結果を示している 解探索性能（ft10，orb01） MGG ft10 orb01 Inter-machine JOXが良好な結果を示している 解探索性能（ft20，abz9） DGA ft20 abz9 Inter-machine JOXが良好な結果を示している 解探索性能（ft10，orb01） DGA ft10 orb01 Inter-machine JOXが良好な結果を示している 個体の生成位置 個体の生成位置 dMSXFは親個体の間にしか子個体を生成できない 親個体間外（親個体から離れる方向）の 良好な解は発見できない Inter-machine JOXは親個体の間以外にも個体を生成 親個体間外へ個体生成 dMSXFを以下のように変更する • 親個体間外にのみ子個体を生成する（OPdMSXF） • 0.5の確率で親個体間に子個体を生成する それ以外の場合は外に子個体を生成する（EdMSXF） ＜比較手法＞ 交叉に以下の4つを適用したGAのモデル • Inter-machine JOX • dMSXF • OPdMSXF • EdMSXF ＜対象問題＞ ft20（20仕事5機械問題） abz9（20仕事15機械問題） 外へ個体生成（ft20，abz9） ft20 abz9 dMSXF，OPdMSXF，EdMSXFの解探索性能に 大きな違いはない 外へ個体生成（ft10，orb01） ft10 orb01 dMSXF，OPdMSXF，EdMSXFの解探索性能に 大きな違いはない 外へ個体生成（ft20，abz9） MGG ft20 abz9 dMSXF，OPdMSXF，EdMSXFの解探索性能に 大きな違いはない 外へ個体生成（ft10，orb01） MGG ft10 orb01 dMSXF，OPdMSXF，EdMSXFの解探索性能に 大きな違いはない 外へ個体生成（ft20，abz9） DGA ft20 abz9 dMSXF，OPdMSXF，EdMSXFの解探索性能に 大きな違いはない 外へ個体生成（ft10，orb01） DGA ft10 orb01 dMSXF，OPdMSXF，EdMSXFの解探索性能に 大きな違いはない 親個体間外へ個体生成による影響 個体間外に個体を生成する手法 OPdMSXF，EdMSXF ＜解探索性能＞ • dMSXFとの間に大きな差はない • Inter-machine JOXに劣る 個体を個体間外に生成することが Inter-machine JOXに劣る原因ではない 個体の多様性の変化 個体の多様性の変化 個体の多様性の変化について検討を行う ＜検討手法＞ 交叉に以下の2つを適用したGAのモデル • Inter-machine JOX • dMSXF ＜対象問題＞ ft10（10仕事10機械問題） ft20（20仕事5機械問題） abz9（20仕事15機械問題） orb01（10仕事10機械問題） 個体の多様性（ft20） Inter-machine JOX dMSXF Inter-machine JOX ： 探索序盤で良好な解を発見 dMSXF ： 良好な解を発見する前に多様性が無くなる 個体の多様性（abz9） Inter-machine JOX dMSXF Inter-machine JOX ： 探索序盤で良好な解を発見 dMSXF ： 良好な解を発見する前に多様性が無くなる 個体の多様性（ft10） Inter-machine JOX dMSXF Inter-machine JOX ： 探索序盤で良好な解を発見 dMSXF ： 良好な解を発見する前に多様性が無くなる 個体の多様性（orb01） Inter-machine JOX dMSXF Inter-machine JOX ： 探索序盤で良好な解を発見 dMSXF ： 良好な解を発見する前に多様性が無くなる 交叉による個体の変化量 交叉による個体の変化量の検討 交叉による個体の変化量について検討を行う ＜検討手法＞ 交叉に以下の2つを適用したGAのモデル • Inter-machine JOX • dMSXF ＜対象問題＞ ft10（10仕事10機械問題） ft20（20仕事5機械問題） abz9（20仕事15機械問題） orb01（10仕事10機械問題） 交叉による個体の変化（ft20） Inter-machine JOX dMSXF Inter-machine JOXの方が個体の変化量が大きい 個体の変化量に10倍程度の差が現れている 交叉による個体の変化（abz9） Inter-machine JOX dMSXF Inter-machine JOXの方が個体の変化量が大きい 個体の変化量に10倍以上の差が現れている 交叉による個体の変化（ft10） Inter-machine JOX dMSXF Inter-machine JOXの方が個体の変化量が大きい 個体の変化量に10倍以上の差が現れている 交叉による個体の変化（orb01） Inter-machine JOX dMSXF Inter-machine JOXの方が個体の変化量が大きい 個体の変化量に10倍以上の差が現れている 大域的探索 大きく変化するdMSXF 大域的探索ができるように変更したdMSXF 近傍の変わりにInter-machine JOXを適用（dMSXF(JOX)） ＜比較手法＞ 交叉に以下の2つを適用したGAのモデル ・ Inter-machine JOX ・ dMSXF ・ dMSXF(JOX) ＜対象問題＞ ft10（10仕事10機械問題） ft20（20仕事5機械問題） abz9（20仕事15機械問題） orb01（10仕事10機械問題） 解探索性能（ft20，abz9） ft20 abz9 解探索性能がInter-machine JOXにかなり近づいている 解探索性能（ft10，orb01） ft10 orb01 解探索性能がInter-machine JOXにかなり近づいている 解探索性能（ft20，abz9） MGG ft20 abz9 dMSXF(JOX)は Inter-machine JOXと同等以上の解探索性能 解探索性能（ft10，orb01） MGG ft10 orb01 dMSXF(JOX)は Inter-machine JOXと同等以上の解探索性能 解探索性能（ft20，abz9） DGA ft20 abz9 dMSXF(JOX)は Inter-machine JOXと同等以上の解探索性能 解探索性能（ft10，orb01） DGA ft10 orb01 dMSXF(JOX)は Inter-machine JOXと同等以上の解探索性能 I2距離 I2距離 I2距離 I2距離 距離の測定方法による解探索性能の違い 距離測定にI2距離を用いるdMSXF（dMSXF(I2)） ＜比較手法＞ 交叉に以下の2つを適用したGAのモデル ・ Inter-machine JOX ・ dMSXF ・ dMSXF(I2) ＜対象問題＞ ft10（10仕事10機械問題） ft20（20仕事5機械問題） abz9（20仕事15機械問題） orb01（10仕事10機械問題） I2距離を用いたdMSXF（ft20，abz9） ft20 abz9 I2距離を用いたdMSXF （ft10，orb01） ft20 abz9 ジョブショップスケジューリング問題（JSP） 一定数の仕事を一定数の機械で処理する 全体の処理にかかる時間（makespan）の最小化 以下のようなことが問題によって決められている • 各仕事が機械を使う順序（技術的順序） • 各仕事が各作業を各機械上で処理する時間 ジョブショップスケジューリング問題（JSP） 一定数の仕事を一定数の機械で処理する 全体の処理にかかる時間（makespan）の最小化 以下のようなことが問題によって決められている • 各仕事が機械を使う順序（技術的順序） • 各仕事が各作業を各機械上で処理する時間 近傍の生成方法 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 近傍の生成方法 dMSXFにおける個体生成 一つの親個体の周りに子個体を生成する 近傍を決定する必要がある 用いる近傍 ・・・ CB近傍 [山田,1994] 個体間の距離 dMSXFにおける個体生成 一方の親個体から他方の親個体に近づくよう個体を生成する 個体間の距離を図る必要がある ＜距離の測定方法＞ • 各機械上である仕事の 次の仕事が違う場合 距離を 1 増加させる • 各機械上である仕事を 処理する順序が異なるとき 距離を1増加させる 個体の多様性が維持されたときの探索 ft20 abz9 探索終盤でもより良好な解を発見している ただし，ある程度良好な解が発見されると探索は停滞する 解探索性能の違い Inter-machine JOXの方が良好な解探索性能を示した Inter-machine JOXとdMSXFの 探索方法の違いが原因 ＜2つの交叉の違い＞ • 個体間外への個体生成の有無 Inter-machine JOXでは個体間外にも個体が生成される • 探索途中での個体の多様性 多様性が失われると交叉が意味を成さない • 1回の交叉による個体の変化量 局所的探索か大域的探索か 実験結果のまとめ ＜用いた交叉手法＞ • Inter-machine JOX • dMSXF 解探索性能はInter-machine JOXがdMSXFよりも良好 ＜原因として考えられること＞ • 個体間外への個体生成の有無 個体間外へ個体を生成するようにdMSXFを変更し検討したが， 解探索性能に変化はなかった • 個体の多様性の変化 dMSXFは多様性が失われるまでに良好な解を発見できない 多様性が大きいときは良好な探索が可能 • 交叉による個体の変化量 dMSXFでは個体の変化が小さく，局所的探索しかできない まとめ JSPをGAで最適化する際の交叉設定の指針について検討 JSPに有効なInter-machine JOX JSPに対して有効性が検討されていないdMSXF 解探索性能はInter-machine JOXがdMSXFよりも良好 • 個体間外への個体生成による解探索性能の改善は見られない • 個体の多様性が維持されている間は良好な探索が可能 • 交叉による個体の変化が小さいと 個体の多様性が失われるまでに良好な解を発見できない JSPに対して有効な交叉設定の指針 • 十分な個体の多様性の維持 • 局所的探索よりも大域的探索 研究目的 JSPをGAで最適化する場合について検討 GAにおける最適化では 適切な遺伝的オペレータの設定が重要 個体の情報交換を行う交叉は非常に重要 適切な交叉を設定するのは困難 適切な交叉手法を決定するための指針について検討 Inter-machine Job-based Crossover Step 1 1つ以上の仕事を選択（ランダム） Step 2 選択した仕事についての遺伝子を継承 親1から子1へ，親2から子2へ Step 3 残りの仕事を順序を守るように継承 親1から子2へ，親2から子1へ “Step 1” で選択された仕事は必ず技術的順序が守られる “Step 3” で継承される仕事も各仕事内で順序は変わらない 交叉によって技術的順序が崩されることはない Inter-machine JOX 実験結果のまとめ ＜用いた交叉手法＞ • Inter-machine JOX • dMSXF 解探索性能はInter-machine JOXがdMSXFよりも良好 ＜原因として考えられること＞ • 個体の多様性の変化 dMSXFは多様性が失われるまでに良好な解を発見できない 多様性が大きいときは良好な探索が可能 • 交叉による個体の変化量 dMSXFでは個体の変化が小さく，局所的探索しかできない
© Copyright 2024 ExpyDoc
