三木 光範 （同志社大学工学部） 廣安 知之 （同志社大学工学部） 花田 良子 （同志社大学工学部学部 生） 水田 伯典 （同志社大学大学院） ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop.

Presentation on theme: "三木 光範 （同志社大学工学部） 廣安 知之 （同志社大学工学部） 花田 良子 （同志社大学工学部学部 生） 水田 伯典 （同志社大学大学院） ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop."— Presentation transcript:

1 三木 光範 （同志社大学工学部） 廣安 知之 （同志社大学工学部） 花田 良子 （同志社大学工学部学部 生） 水田 伯典 （同志社大学大学院） ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop Scheduling Problems

2 遺伝的アルゴリズム (GA) GA の計算モデルの 1 つに分散 GA （ DGA ） GA の特徴 - 選択 適合度の高い個体が多く生き残 る 生物の進化の模倣 - 交叉 - 突然変異 個体の情報交換 個体情報の変更

3 分散遺伝的アルゴリズム （ DGA ） 母集団を複数のサブ母集団に分割 各サブ母集団内で GA を行う サブ母集団間の移住操作 移住 サブ母集団

4 研究の背景と目的 連続最適化問題において， DGA は単一母集団 GA （ SPGA ）と比較して解探索性能がよい 種々の組合せ最適化問題においては， DGA の性能が明らかとなっていな い ジョブショップスケジューリング問題 （ JSP ）を対象として， DGA の性能を検証

5 ジョブショップスケジューリング問題 （ JSP ） 複数の仕事を複数の機械で処理する すべての仕事を処理するのに要する時間 （ Makespan ）を最小にするようなスケジュールを求 める 目的 ガントチャー ト

6 ジョブショップスケジューリング問題 （ JSP ） 各機械は必ず全ての作業を中断せずに処理 する 仕事は順序を守って処理されなければな らない 機械は同時に複数の作業を処理することはで きない 制約条件

7 コーディング法と遺伝的オペレータ ( 小 野 97) 交叉 ： inter-machine JOX + GT 法による 修正 突然変異： job-based shift change + GT 法による 修正 数値実験で用いた遺伝的オペレータ コーディング法 ガントチャートに基づく遺伝 子表現 染色体長 = 作業 数 例） 10 仕事 10 機械 ･･･ 染色体長 = 100

8 パラメータ 値 母集団サイズ 800 サブ母集団数 1 （ SPGA ）, 4, 8, 20 40 ， 100 交叉率 1.0 突然変異率 0.1 移住間隔 20 世代 移住率 0.5 探索終了世代 2500 世代

9 対象問題 ft20 （ 20 仕事 5 機械問 題） 最適値 1165 探索空間の大きさ （ 20 ! ） = 8.5×10 5 91 ft10 （ 10 仕事 10 機械問 題） 最適値 930 探索空間の大きさ （ 10 ! ） = 4.0×10 1010 65 作業数 100

10 SPGA と DGA の比較 (ft10) 50 試行の平均値 ( 探索終了世代 ) サブ母集団数を多くす ると性能が向上する DGA は SPGA と比較 して解の品質が向上 する

11 SPGA と DGA の比較 (ft20) 50 試行の平均値 ( 探索終了世代 ) サブ母集団数を多くす ると性能が向上する DGA は SPGA と比較 して解の品質が向上 する

12 JSP における DGA の性能 SPGA と比較して DGA は解の精度がよい サブ母集団数が解探索に与える影響 サブ母集団数を多くすると性能が向上する DGA の解探索能力と移住との関係 交叉適用後の個体の修正の割合により検 証 実行不可能 → 可能

13 個体の修正の割合 修正された個体の割合と修正箇 所数 SPGA においては，ほぼ全個体において多くの箇所が修 正され，探索が進んでも減少しない DGA は修正される個体数とその箇所が減少 する （ 50 試行の平 均）

14 個体の修正箇所数と解の品質 SPGA 初期母集団 SPGA （ 500 世 代） DGA （サブ母集団数 20 ， 500 世 代） 10 試行の結果 15 箇所程度の修正が必 要 DGA 修正が少ないほど良好な結 果が得られる

15 DGA における個体の修正箇所数と解の品質 修正箇所が少ない方が，解の品質が向上 する 50 試行の平均 値 サブ母集団数を多くしすぎると修正箇所が 増加し，解の品質が低下する

16 サブ母集団数が与える影響 - サブ母集団数がある程度多い方が，修正される個体 数と その修正箇所が減少する - 良好な解を得るには多くの修正が必要 SPGA DGA 部分的に良好な仕事列が生成されてい ない - 修正される個体数とその修正箇所が多 い ランダムサーチに近 くなる - 修正箇所が少ないほど良好な解が得ら れる サブ母集団数を多くすると良好な結果が得 られる ただし，サブ母集団内の個体数には下限値が ある

17 JSP における DGA の性能 SPGA と比較して DGA は解の精度がよい サブ母集団内の個体数が解探索に与える影響 サブ母集団数を多くすると性能が向上する DGA の解探索能力と移住との関係

18 DGA における移住の有無による比較 50 試行の平均値 ( 探索終了世代 ) と 最適解を得た確 率 移住を行う DGA は移住を行わない DGA と比較して 性能が向上し，最適解を高い確率で得られる

19 部分解の概念 各機械における最適解の部分解を持つ個体が占める 割合を比較 部分解 最適スケジュー ル 部分解 : 最適スケジュールにおける各機械の仕事の投入順序 機械 3 の部分解をもつスケジュール

20 最適解の部分解をもつ個体の広がり 移住あり DGA 移住なし DGA 移住を行うことにより部分解が大きく増加する 3 機械における最適解の部分解をもつ個体の割合 （サブ母集団数 20 の平均値， 1 試行の結 果）

21 サブ母集団内の結果 ( 移住なし DGA) 1 つのサブ母集団で複数の 機械における最適解の部分 解を発見するのは困難 あるサブ母集団における部分解の広がり

22 サブ母集団内の結果 ( 移住あり DGA) 移住を行う DGA におい ては全体として 3 機械の 部分解が移住によって 広まる あるサブ母集団における部分解の広がり

23 最適解の部分解をもつ個体の広がり 移住あり DGA 移住なし DGA 移住を行うことにより部分解が大きく増加する 3 機械における最適解の部分解をもつ個体の 割合 （サブ母集団数 20 ， 1 試行の結果） 移住によって最適解を得やすくなる

24 まとめ JSP において， DGA は SPGA に比べ良好な結果が得 られる 1 つのサブ母集団で生成された最適解の部分解とな り得る仕事列を持つ個体が移住により広がる 母集団の分割により，修正個体および修正箇所が少 なくなり，交叉において親のもつ特徴が子個体に受 け継がれやすい． DGA の解探索能力 DGA の性能