移住 サブ母集団

ジョブショップスケジューリング問題への
分散遺伝的アルゴリズムの適用
Distributed Genetic Algorithm for Job-shop Scheduling Problems
三木
廣安
花田
水田
光範
知之
良子
伯典
(同志社大学工学部)
(同志社大学工学部)
(同志社大学工学部学部生)
(同志社大学大学院)
遺伝的アルゴリズム (GA)
GAの特徴
生物の進化の模倣
- 選択
適合度の高い個体が多く生き残る
- 交叉
個体の情報交換
- 突然変異
個体情報の変更
GAの計算モデルの1つに分散GA(DGA)
分散遺伝的アルゴリズム (DGA)
母集団を複数のサブ母集団に分割
各サブ母集団内でGAを行う
サブ母集団間の移住操作
移住
サブ母集団
研究の背景と目的
連続最適化問題において,DGAは単一母集団GA(SPGA)
と比較して解探索性能がよい
種々の組合せ最適化問題においては,
DGAの性能が明らかとなっていない
ジョブショップスケジューリング問題(JSP)を対象として,
DGAの性能を検証
ジョブショップスケジューリング問題 (JSP)
複数の仕事を複数の機械で処理する
目的
すべての仕事を処理するのに要する時間(Makespan)を最小
にするようなスケジュールを求める
ガントチャート
ジョブショップスケジューリング問題 (JSP)
制約条件
仕事は順序を守って処理されなければならない
機械は同時に複数の作業を処理することはできない
各機械は必ず全ての作業を中断せずに処理する
コーディング法と遺伝的オペレータ (小野 97)
コーディング法
ガントチャートに基づく遺伝子表現
染色体長 = 作業数
例) 10仕事10機械 ・・・ 染色体長 = 100
数値実験で用いた遺伝的オペレータ
交叉
: inter-machine JOX + GT法による修正
突然変異: job-based shift change + GT法による修正
パラメータ
パラメータ
値
母集団サイズ
800
サブ母集団数
1(SPGA), 4, 8, 20
40,100
交叉率
1.0
突然変異率
0.1
移住間隔
20世代
移住率
0.5
探索終了世代
2500世代
象問題
ft10 (10仕事10機械問題)
作業数 100
最適値 930
10
65
探索空間の大きさ (10 !) = 4.0×10
ft20 (20仕事5機械問題)
作業数 100
最適値 1165
5
探索空間の大きさ (20 !) = 8.5×10
91
SPGAとDGAの比較 (ft10)
50試行の平均値 (探索終了世代)
DGAはSPGAと比較して
解の品質が向上する
サブ母集団数を多くすると
性能が向上する
SPGAとDGAの比較 (ft20)
50試行の平均値 (探索終了世代)
DGAはSPGAと比較して
解の品質が向上する
サブ母集団数を多くすると
性能が向上する
JSPにおけるDGAの性能
SPGAと比較してDGAは解の精度がよい
サブ母集団数を多くすると性能が向上する
サブ母集団数が解探索に与える影響
交叉適用後の個体の修正の割合により検証
実行不可能 → 可能
DGAの解探索能力と移住との関係
個体の修正の割合
修正された個体の割合と修正箇所数
(50試行の平
均)
SPGAにおいては,ほぼ全個体において多くの箇所が修正され,
探索が進んでも減少しない
DGAは修正される個体数とその箇所が減少する
個体の修正箇所数と解の品質
10試行の結果
初期母集団
SPGA(500世代)
SPGA
15箇所程度の修正が必要
DGA(サブ母集団数20,500世代)
DGA
修正が少ないほど良好な結果
が得られる
DGAにおける個体の修正箇所数と解の品質
50試行の平均値
修正箇所が少ない方が,解の品質が向上する
サブ母集団数を多くしすぎると修正箇所が増加し,
解の品質が低下する
サブ母集団数が与える影響
SPGA
- 修正される個体数とその修正箇所が多い
ランダムサーチに近くなる
- 良好な解を得るには多くの修正が必要
部分的に良好な仕事列が生成されていない
DGA
- サブ母集団数がある程度多い方が,修正される個体数と
その修正箇所が減少する
- 修正箇所が少ないほど良好な解が得られる
サブ母集団数を多くすると良好な結果が得られる
ただし,サブ母集団内の個体数には下限値がある
JSPにおけるDGAの性能
SPGAと比較してDGAは解の精度がよい
サブ母集団数を多くすると性能が向上する
サブ母集団内の個体数が解探索に与える影響
DGAの解探索能力と移住との関係
DGAにおける移住の有無による比較
50試行の平均値 (探索終了世代) と 最適解を得た確率
移住を行うDGAは移住を行わないDGAと比較して
性能が向上し,最適解を高い確率で得られる
部分解の概念
部分解 : 最適スケジュールにおける各機械の仕事の投入順序
部分解
最適スケジュール
機械3の部分解をもつスケジュール
各機械における最適解の部分解を持つ個体が占める割合
を比較
最適解の部分解をもつ個体の広がり
3機械における最適解の部分解をもつ個体の割合
(サブ母集団数20の平均値, 1試行の結果)
移住なしDGA
移住を行うことにより部分解が大きく増加する
移住ありDGA
サブ母集団内の結果 (移住なしDGA)
あるサブ母集団における部分解の広がり
1つのサブ母集団で複数の
機械における最適解の部分解
を発見するのは困難
サブ母集団内の結果 (移住ありDGA)
あるサブ母集団における部分解の広がり
移住を行うDGAにおいては
全体として3機械の部分解
が移住によって広まる
最適解の部分解をもつ個体の広がり
3機械における最適解の部分解をもつ個体の割合
(サブ母集団数20, 1試行の結果)
移住なしDGA
移住を行うことにより部分解が大きく増加する
移住によって最適解を得やすくなる
移住ありDGA
まとめ
DGAの性能
JSPにおいて,DGAはSPGAに比べ良好な結果が得られる
DGAの解探索能力
母集団の分割により,修正個体および修正箇所が少なくなり,
交叉において親のもつ特徴が子個体に受け継がれやすい.
1つのサブ母集団で生成された最適解の部分解となり得る
仕事列を持つ個体が移住により広がる
タイトル
問題の例 (3仕事3機械問題)
作業
J・・・仕事, M・・・機械
各仕事において使用される機械の順序が決まっている
J3の場合
M2で時間2
M3で時間6
M1で時間1
個体の遺伝子表現
ガントチャートにもとづく遺伝子表現
スケジュール (個
個体の遺伝子表現
体)
各機械への作業の投入順序を遺伝子に用いる
交叉法に用いた手法
inter-machine JOX (小野 97)
交叉法に用いた手法
inter-machine JOX (小野 97)
突然変異に用いた手法
job-based shift change (小野 97)
各機械,独立して突然変異を行う
SPGAとDGAの比較 (ft10)
50試行の平均値
ft10において,DGAはSPGAと比較して収束が早く,性能が
向上する.
SPGAとDGAの比較 (ft20)
50試行の平均値
DGAはSPGAと比較して収束が早く,性能が向上する.
個体の相異
JSP : 各機械において仕事の投入順序を決定する問題
2個体の相異を各機械において投入順序
の異なる仕事の個数と考える
異なる仕事数 ・・・ 4個
SPGAとDGAの比較
SPGAと比較して,移住の有無に関わらずDGAは良好な
結果が得られる
解が生成される過程
25個の異なる最適スケジュールの共通部分 (ft10)
* 印は最適スケジュール
の異なる部分
各機械における最適解
の共通部分を持つ個体
が占める割合を比較
最適解の部分解を持つ個体の広がり
ある1機械における最適解の部分解を持つ個体の割合
(20試行の平均)
移住なしDGA
移住ありDGA
移住を行わないDGAにおいても部分解が生成される
移住を行うことにより部分解が増加する
移住ありDGAにおける解の成長
2 個のサブ母集団における部分解をもつ個体の広がり
機械 1
機械 1 ・・・ サブ母集団 2
機械 2 ・・・ サブ母集団 1
機械 2
サブ母集団1
サブ母集団2
1つのサブ母集団で発見された最適解の部分解が
移住により他と結合している
ジョブショップスケジューリング問題 (JSP)
複数の製品を複数の機械で加工する
数多くの製造現場がジョブショップ型
部品メーカ,加工メーカなど
部品
複数の機械で処理
スケジュール
製品
JSPを取り扱う意義
数多くの製造工程がジョブショップ型
部品メーカ,加工メーカなど
仕事数,機械数が多くなると,すべての組合せを
計算することが困難
65
例) 10仕事10機械問題...4.0×10 通り
遺伝的アルゴリズム
ジョブショップスケジューリング問題 (JSP)
複数の仕事を複数の機械で処理する
すべての仕事を処理するのに要する時間(Makespan)を
最小にするようなスケジュールを求める
仕事数,機械数が多くなると,すべての組合せを
計算することが困難
65
例) 10仕事10機械問題...4.0×10 通り
遺伝的アルゴリズム
SPGAとDGAの比較
50試行の平均 (評価計算回数を一定)
DGAはSPGAと比較して解の品質が向上する
移住による効果
移住によって最適解を得やすくなる
移住を行うことにより部分解が大きく増加する
1つのサブ母集団で複数の部分解を発見するのは
難しい
交叉する2個体の相異
50試行の平均値
SPGAは多様性を保持しているが,収束しにくい