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