PowerPoint プレゼンテーション

ジョブショップスケジューリング問題への
分散遺伝的アルゴリズムの適用
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つのサブ母集団で生成された最適解の部分解となり得る
仕事列を持つ個体が移住により広がる