平成
21
年度
学士学位論文
複数の染色体表現によるジョブショップ
スケジューリング問題の
GA
解法
GA for job-shop scheduling problem by plural
chromosome expression
1100303
篠原 達希
指導教員
坂本 明雄
2010
年
3
月
1
日
要 旨
複数の染色体表現によるジョブショップスケジューリング問題
の
GA
解法
篠原 達希
遺伝アルゴリズムは生物集団が環境に適応して進化していく様を模倣する最適化問題の近 似解法の1つである. 問題の可能解を染色体として表現し,選択,交叉,突然変移などの遺伝 的操作を行い世代を重ね近似解を求める. 各染色体は可能解に対応しているので,その解の 良さを求めることができ,その値を適応度という. 次世代へ残る染色体の選択に際しては,適 応度が大きい染色体ほど選ばれる確率が高くなるようにする. 交叉および突然変異は,解の 多様性を生じさせる操作である. 本論文では,ジョブショップスケジューリング問題に対して4種類の染色体表現を考察し た. 実験の結果, 4 種類の表現法で一番良い解を求めることができた作業順序法について交 叉確率, 突然変異確率などのパラメータを調整し最適解に近づける. キーワード 遺伝アルゴリズム,ジョブショップスケジューリング問題,染色体表現Abstract
GA for job-shop scheduling problem by plural chromosome
expression
Tatsuki Shinohara
Genetic algorithm imitates evolution of life a kind of approximate solution of opti-mization problem. Express practicable answer of problem as chromosome, select, cross over and mutation genetic operation repeat generation find approximate solution. Each chromosome corresponds to solution possible, therefore ability is understood, ability is called fitness value. Selection of chromosome left in next generation is chosen by fitness value. Cross over and mutation are operation to cause the variety of the solution.
In this paper, four kind of chromosome expression to job-shop scheduling problem was considered. In the experiment a result, best solution among four kinds chromosome expression is Operation Permutation. Adjust parameters such as cross over probability, mutation probability, approximate solution of Operation Permutation.
目次
第1章 序論 1 第2章 問題の定義 3 2.1 ジョブショップスケジューリング問題 . . . 3 2.2 具体例 . . . 3 第3章 遺伝アルゴリズム 6 3.1 遺伝アルゴリズムの概要 . . . 6 3.2 遺伝アルゴリズムの構成と流れ . . . 6 3.2.1 初期染色体集団生成 . . . 7 3.2.2 遺伝的操作. . . 7 交叉 . . . 7 突然変異 . . . 7 3.2.3 適応度計算. . . 8 3.2.4 終了条件 . . . 8 第4章 JSPに対する染色体表現 9 4.1 仕事順序法 . . . 9 4.2 第1作業選択法. . . 10 4.3 双順序法 . . . 13 4.4 比較. . . 15 4.5 作業順序法 . . . 15 第5章 作業順序法を用いた実験 18 5.1 交叉. . . 18目次 5.1.1 部分一致交叉(PMX) . . . 18 5.1.2 巡回交叉(CX) . . . 20 5.2 突然変異 . . . 21 5.3 交叉確率と突然変異確率 . . . 21 5.4 適応度計算 . . . 22 5.5 終了条件 . . . 23 第6章 実験結果と結論 25 6.1 実験結果 . . . 25 6.2 結論. . . 27 謝辞 29 参考文献 30
図目次
2.1 ガントチャート . . . 4 2.2 スケジュールが異なるガントチャート . . . 5 3.1 GAの流れ . . . 6 4.1 仕事順序法の染色体 . . . 10 4.2 第1オペレーション挿入 . . . 10 4.3 第1オペレーション以降を挿入 . . . 10 4.4 第1作業選択法の染色体 . . . 10 4.5 第1オペレーション挿入 . . . 11 4.6 J2 の前に挿入 . . . 11 4.7 J2 の後ろに挿入 . . . 11 4.8 J1 挿入後のガントチャート . . . 12 4.9 J4 の前に挿入 . . . 12 4.10 J4 の後ろに挿入 . . . 12 4.11 J3 挿入後のガントチャート . . . 13 4.12 第1以降を挿入 . . . 13 4.13 双順序法の染色体 . . . 13 4.14 第1オペレーション挿入後のガントチャート . . . 14 4.15 第1オペレーション以降を挿入 . . . 14 4.16 作業順序法の染色体 . . . 15 4.17 J2 の1番目の作業挿入 . . . 16 4.18 J2 の2番目の作業挿入 . . . 16 4.19 J3 の1番目の作業挿入 . . . 16図目次 4.20 作業挿入終了 . . . 16 5.1 プログラム上の染色体 . . . 18 5.2 作業順序法の染色体 . . . 18 5.3 PMX親 . . . 19 5.4 PMX処理1 . . . 19 5.5 PMX処理2 . . . 19 5.6 PMX子 . . . 19 5.7 CX親 . . . 20 5.8 交叉座標決定 . . . 20 5.9 CX子 . . . 21 5.10 突然変異 . . . 21 5.11 確率の組合せ . . . 22 5.12 仕事15,機械15の問題 . . . 24 5.13 仕事20,機械15の問題 . . . 24 5.14 仕事30,機械15の問題 . . . 24 5.15 仕事50,機械15の問題 . . . 24 6.1 確率の組合せ . . . 25 6.2 最適解にとどかない原因 . . . 28
表目次
2.1 JSPの表示 . . . 4 4.1 例題 . . . 9 4.2 表現法別実行時間 . . . 14 4.3 表現法別実行時間 . . . 15 4.4 表現法別makespan . . . 17 5.1 適応度と交叉の組み合せの比較 . . . 23 6.1 交叉確率75%,突然変異確率10%での結果 . . . 26 6.2 交叉確率55%,突然変異確率50%での結果 . . . 26第
1
章
序論
スケジューリング問題は,多くの仕事をさまざまな制約のもとで実行するとき, 実行可能 なスケジュールの中で,目的とする値が最適となるスケジュールを求める問題である. 目的 とする値としては,すべての仕事が完了するまでの作業時間がよく用いられる. この場合は, 仕事の完了時間が最も短いスケジュールが最適解となる. 効率的な運用がもとめられている あらゆる場面にスケジューリング問題が存在する. 生産,配送,人員の配置などのスケジュー ル問題に対して最適な解が求められれば効率よく業務を行うことができる. 本論文ではジョブショップスケジューリング問題について遺伝アルゴリズムを用いた近似 解法について考察する. ジョブショップスケジューリング問題は機械が処理する仕事のスケ ジュールを決定する問題で, 何台かの機械といくつかの仕事が与えられ, 機械がすべての仕 事を完了するまでの作業時間を最短にするのが目的である. この問題は,仕事と機械の数が 大きくなると最適解を求めることが劇的に難しくなるNP困難な問題である. 本研究室の研究対象であり,近似解法の1つである遺伝アルゴリズムを用いることによっ てジョブショップスケジューリング問題の近似解法を提案する. 遺伝アルゴリズムは,生物の 進化の過程を模倣したものである.最適化問題の可能解を染色体に置き換え, 選択,交叉,突 然変異などの遺伝的操作を繰り返し行い最適解に近づけていく. 本研究ではスケジュールを染色体へ置き換える. 染色体が表すスケジュールで仕事を行う ことによって完了までの時間が計算できる. スケジュールが表されている染色体へ遺伝的操 作を繰り返すことにより, 良いスケジュールを求め仕事完了にかかる時間を短くする. まず, 2章でジョブショップスケジューリング問題の説明を行い. 3章で一般的な遺伝アル ゴリズムについて説明を行う. 4章ではジョブショップスケジューリング問題を扱うにあたり,異なる染色体表現での問題への解法を述べ, 5章で一番良い解を求めることができた作業 順序法のパラメータを決定する実験の結果を述べる. 最後に6章で実験結果と結論を述べる.
第
2
章
問題の定義
2.1
ジョブショップスケジューリング問題
ジョブショップスケジューリング問題(job-shop scheduling problem: JSP)とは, いくつ かの仕事を何台かの機械で処理をする場合に,機械が行う仕事の順序(スケジュール)を決定 する問題である. 全ての仕事を終えた時間 (makespan)を最小になるようなスケジュールを 求めることを目的とする. だたし,各仕事は決められた作業を決められた順序で行う.各機械は同時に複数の仕事を処 理することはできず, 作業を始めるとその作業を終えるまで中断することなく処理する.以 下にまとめる. 目的 全ての仕事完了に要する時間(makespan)を最小にするようなスケジュールを求める 制約条件 1. 仕事は処理順序を決められた作業からなる(技術的順序) 2. 各機械は同時に複数の作業を処理できない 3. 機械は必ず作業を中断せず処理する
2.2
具体例
JSPの具体例は,表2.1のように表すことができる. これは仕事数4,機械数3の場合であ る. 4つの仕事をJ1, J2, J3, J4とし, 3台の機械をM1, M2, M3 とする.2.2 具体例 表2.1 JSPの表示 仕事 1番目の処理 2番目の処理 3番目の処理 J1 (M2,4) (M3,3) (M1,2) J2 (M2,2) (M1,1) (M3,1) J3 (M1,4) (M3,1) (M2,1) J4 (M1,2) (M3,1) (M2,3) この表のJ1 の1番目の処理(M2,4)というのは, J1は最初にM2 を使う作業を時間4を かけて行うということを表す.制約条件 1の「仕事は処理順序を決められた作業からなる」 は, J1は最初に M2 で処理し,次にM3,最後にM1 で処理をして終了というものである. 他 の仕事J2∼J4 も指定された技術的順序を守りながらmakespanを最小にするスケジュール を求める. この具体例では, M2 の全ての仕事にかかる時間の合計が10であるため, makespanは10 より小さくなることなない. またJSP はガントチャートという図でスケジュールを表すことができる. その一例を図 2.1に示す. 図2.1 ガントチャート
2.2 具体例 この図は縦軸が機械,横軸は時間を表し,このスケジュールではmakespanは11となる. また機械M1はJ4, J2, J3, J1の順番で作業を処理する. 表2.1を見ると最初にM2 を使う仕事はJ1 とJ2の2つがあり,制約条件2にあるように 「各機械は同時に複数の作業を処理できない」ので, M2はJ1とJ2 のどちらを処理するか選 ばなければならず,図2.1の場合ではM2は先にJ2 を処理し次にJ1を処理している. 制約条件3の「機械は必ず作業を中断せず処理する」というのは,図2.1でいうとM2 の 2番目に行っているJ1 の処理を本来なら時間4をかけて処理するところを時間2で切り上 げ次の処理を終えてから残りのJ1 の作業を処理をするということはできないということで ある. 図2.1でのスケジュールでは, M2がJ2 を先に処理しているが, M2がJ1 を先に処理した 場合のガントチャートを図2.2に示す. この場合ではmakespanが10となり,この問題では10より小さくなることはないのでこ のスケジュールが最適解の一つである. 図2.2 スケジュールが異なるガントチャート
第
3
章
遺伝アルゴリズム
3.1
遺伝アルゴリズムの概要
遺伝アルゴリズム (Genetic Algorithm: GA)とは,問題の解に相当するものを記号列と して表現した染色体を考え, 個々の染色体をもつ個体が生存する環境を想定し,生物の遺伝 機構と自然選択を比較的忠実に模倣して, 個体集合による離散的な探索空間での適応や最適 化を扱う.個体間で遺伝情報を交換する交叉演算を用いて新しい探索点を生成することを特 徴としている[1]. 生物が環境に適応して良いものへ進化していく過程を模倣する. データ(生物)を問題(環 境)に適応させて最適化(進化)させて行けば良い解が見つかるだろうという考え方である.
3.2
遺伝アルゴリズムの構成と流れ
図3.1にGAの全体の流れを示す. 図3.1 GAの流れ3.2 遺伝アルゴリズムの構成と流れ
3.2.1
初期染色体集団生成
ここでは要素が異なる染色体を発生させる.ここで生成されたものはこれから生成される 子孫に特徴が受け継がれていく. 扱う問題によって0, 1の2進数列や数の順列などさまざま なものが考えられる. 個体数が多すぎると1世代あたりの計算時間が多くなる. 少なすぎても交叉演算を用いて 新しい探索点を生成するという特徴が発揮されにくくなってしまう.3.2.2
遺伝的操作
遺伝的操作は,染色体の情報を交換する交叉と染色体の情報が変化する突然変異を行う. ここで親となる染色体を選択し特徴を受け継いだ子供を生成する. 突然変異で子供の遺伝情 報が親の特徴に関係なく変化する. 交叉 個体集団内の個体をランダムに2個づつ組合せ,ある確率(交叉確率)で, 2つの個体の遺 伝子列を部分的に交換する[1]. 個体集団から交叉させる染色体をランダムに選択する方法 はルーレット選択,トーナメント選択などさまざまあり, 交叉の方法も部分一致交叉,巡回交 叉などある. 突然変異 各個体について,ある確率(突然変異確率)で,各遺伝子の遺伝子座の情報を変更する. 染 色体が0, 1なら反転,順列なら遺伝子座を2つ選び値を交換させるなどがある. 突然変異は単に,あるビットが偶然にすべての場所で同じ値をとるようになってしまった ときに, 集団に多様性を再導入する仕組みに過ぎない[2]. 突然変異確率が高いと親となる染 色体の特徴を崩してしまう恐れがある.3.2 遺伝アルゴリズムの構成と流れ
3.2.3
適応度計算
生成した染色体が求めている解(最適解)に近づいているか, 環境にどれだけ適応している かを計算する. この値は交叉させる親を選択するときに用いる.扱う問題によって計算方法 が異る.3.2.4
終了条件
定めた条件に合えばGAを終了させる. 世代を重ねても解が一定の世代の間改善されなけ れば終了させる,などの条件を定める. この条件に合わなければ個体集団に再び遺伝的操作を施して次世代の個体集団を生成 する.第
4
章
JSP
に対する染色体表現
JSPに対して複数の染色体表現を用いてそれぞれの効果を調べた. この章ではその表現 方法を説明する. まず,参考文献[3]を基に仕事順序法と第1作業選択法,双順序法を作成し た. だが,その染色体表現では満足な解を得ることができなかったので作業順序法を作成し た. 全ての表現法は染色体を元にガントチャートを作成しmakespanを計算するようになっ ている. 全ての説明は表4.1について適用させたものとする.これは2章の表 2.1と同じ表 である. 表4.1 例題 仕事 1番目の処理 2番目の処理 3番目の処理 J1 (M2,4) (M3,3) (M1,2) J2 (M2,2) (M1,1) (M3,1) J3 (M1,4) (M3,1) (M2,1) J4 (M1,2) (M3,1) (M2,3)4.1
仕事順序法
最初に作成したのがこの表現法である.この染色体表現法は図 4.1のような染色体になっ ている. この値はガントチャートに挿入する仕事の順序を表している. まず,各仕事の最初の処理(第1オペレーション)のみを図4.1の染色体を参照しガント チャートに挿入する. この場合だとJ4, J2, J1, J3 の順序で第1オペレーションを挿入する.4.2 第1作業選択法 図4.1 仕事順序法の染色体 すると図4.2のようになる.そしてもう一度染色体を参照し,示す仕事の順序で第2オペ レーション以降の作業を挿入する.まずJ4の2番目と3番目の作業を挿入し, 次にJ2の2, 3番目の作業を挿入というように全ての仕事を挿入し終えるまで続ける. 図4.3のようにな る.この場合だとこの染色体のmakespanは13となり計算が終了する. 図4.2 第1オペレーション挿入 図4.3 第1オペレーション以降を挿入
4.2
第
1
作業選択法
2番目に作成したのがこの表現法である. この染色体表現は仕事順序法と同じで図4.4の ように仕事の順序となるが,ガントチャートの作成手順が異なる. 図4.4 第1作業選択法の染色体 この表現法も第1オペレーションから挿入する.まず染色体を参照しながら挿入する. J44.2 第1作業選択法 を挿入し次にJ2 を挿入する.すると図4.5のようになる. 図4.5 第1オペレーション挿入 次にJ1 の第1 オペレーションを挿入するのだが,この作業はM2 を用いて処理する. J2 の第1オペレーションもM2 を用いて処理している.このとき, J1 の第1オペレーションを 今まで挿入されている第1オペレーションの間に挿入し, 今まで挿入してきた仕事の第1オ ペレーション以降を挿入させて現在のmakespanが小さくなるものを次の挿入場所とする. この場合だとJ1 の第1オペレーションを挿入されているJ2 の前に挿入するか後ろに挿 入するかの 2パターンあり実際に前に挿入した場合と後ろに挿入した場合のmakespanを 計算し低いほうを挿入場所とする. 図4.6に前に挿入した場合,図4.7に後ろに挿入した場 合を示す. 図4.6 J2の前に挿入 図4.7 J2の後ろに挿入
4.2 第1作業選択法 前に挿入するとmakespanは9となり後ろに挿入すると11となる. よって第1オペレー ションの状態は図4.8となる. 図4.8 J1挿入後のガントチャート そして染色体を参照し次のJ3 の第1オペレーションを挿入する. また同じ機械を使用し ている仕事があるので同じ処理を行い図4.9と図4.10のようになりmakespanが10の後ろ に挿入され図4.11となる. 図4.9 J4の前に挿入 図4.10 J4の後ろに挿入 そして全ての第1オペレーションが挿入し終ったら, 残りの仕事の第1オペレーション以 降の作業を仕事順序法のように挿入し図4.12のようになりmakespanは10となる.
4.3 双順序法 図4.11 J3挿入後のガントチャート 図4.12 第1以降を挿入 この表現法では第1オペレーションの場所を良い方へ選択しながらガントチャートを作成 していくので仕事順序法より良い解を求めやすかった. だが, 1台の機械に第1オペレーショ ンが集中している問題や仕事数が多い問題などではこの評価法では時間がかかりすぎた. よって計算時間を短縮するために,次に説明する双順序法を作成した.
4.3
双順序法
この表現法は第1作業選択法では時間がかかりすぎるという問題があるため計算時間を短 縮するために第1作業選択法を基に作成した. この表現法の染色体は図4.13のようになる. 図4.13 双順序法の染色体 この表現法では染色体は2つの順列を持ち, fが第1オペレーションを挿入する順序を意 味し, oが第1オペレーション以降の作業を挿入する順序を表している. まず, fを参照し各仕事の第1オペレーションのみを挿入する.それを図4.14に示す. 次に4.3 双順序法 oを参照し第1オペレーション以降の作業を挿入する.最初にJ1 の2, 3番目の作業を挿入 し, 次にJ4, J2 最後にJ3 の作業を挿入しガントチャートを作成する.それを図4.15に示す. この場合にはmakespanは12となる. 図 4.14 第 1オペレーション挿入 後のガントチャート 図4.15 第1オペレーション以降を挿入 第1作業選択法と比べ,この表現法は第1オペレーション挿入時にmakespanを計算しな がらガントチャートを作成しないのでかなりの時間短縮ができた.表4.3にだいたいの表現 法別実行時間を示す. 交叉確率などのパラメータは全て同じである. 表4.2 表現法別実行時間 仕事数,機械数 仕事順序法 第1作業選択法 双順序法 15, 15 20秒 2分 20秒 20, 20 40秒 5分 60秒 30, 20 60秒 20分 1分30秒 50, 20 2分30秒 2時間 3分 双順序法は,仕事順序法とあまり変わらない実行時間で解を求めることができる. そして 仕事順序法より複雑なガントチャートが表現できるので仕事順序法より良い解を求めやす かった.
4.4 比較
4.4
比較
今まで作成した仕事順序法,第1作業選択法,双順序法の3つの表現法を用いて問題を解 いた. それを表4.3にまとめた.全ての表現法の交叉確率などのパラメータは同じである. 表4.3 表現法別実行時間 仕事数,機械数 最適解 仕事順序法 第1作業選択法 双順序法 15, 15 1231∼1005 1497 1524 1514 20, 20 1626∼1314 2049 2049 2100 30, 20 1983∼1761 2673 2673 2623 50, 20 2868 4018 3911 3955 最適解というのは問題の最適なmakespanがあるとされている範囲である. この範囲の上 限をupper bound,下限をlower boundという. この範囲があらかじめ分かっている問題 [4][5]を試した. 妥協範囲としてupper bound の1割増しぐらいの解を求めたかったがどの表現法も妥協 範囲にもとどかなかった. よって妥協範囲にはいるような別の表現法を考え,作業順序法を 作成した.4.5
作業順序法
この表現法は図4.16のような染色体となる. この染色体の長さは作業の数(=仕事数*機 械数)だけある. 数字の種類は仕事数だけあり,同じ数字は仕事の作業数(機械数)だけある. この問題は仕事数4,機械数 3なので数字は1から 4の4種類あり,同じ数字がそれぞれ3 つずつある. 図4.16 作業順序法の染色体4.5 作業順序法 染色体にある値が挿入する仕事を表し,その値がでた回数によりその仕事の何番目の作業 を挿入するか意味する. 染色体を参照し最初が2なのでJ2 の1番目に処理する作業をガン トチャートに挿入する. 図4.17のようになる.次がまた2なので今度も J2の作業を挿入す る. この2は2回目なのでJ2の2番目の作業をガントチャートに挿入する. 図4.18に示す ように, 1番目の作業が終了した時刻2から2番目の作業が開始される. 図4.17 J2の1番目の作業挿入 図4.18 J2の2番目の作業挿入 次は3なのでJ3の作業を挿入する.この3は染色体に初めて現れたのでJ3 の1番目の作 業を挿入する. 図4.19に示す.このように全ての作業をガントチャートに挿入すると計算は 終了する. 図4.20に終了したものを示す.この場合makespanは11となる. 図4.19 J3の1番目の作業挿入 図4.20 作業挿入終了
4.5 作業順序法 今までの表現法は第1オペレーションを最初に全て挿入してから2番目以降の作業を挿入 していたので第1オペレーションと第1オペレーションの間に2番目以降の作業が挿入され ることが無かった. だが,作業順序法は図4.20のM1のスケジュールのようにJ4とJ3の第 1オペレーションの間に第1オペレーション以外の作業が挿入される場合がある. よって,い ままでの表現法より複雑なガントチャートを作成することができる. 表4.4に今までの表現 法との比較を示す.パラメータは全て同じ値である. 表4.4 表現法別makespan 仕事数,機械数 最適解 仕事順序法 第1作業選択法 双順序法 作業順序法 15, 15 1231∼1005 1497 1524 1514 1372 20, 20 1626∼1314 2049 2049 2100 1879 30, 20 1983∼1761 2673 2673 2623 2348 50, 20 2868 4018 3911 3955 3328 仕事数15,機械数15の問題だけだが作業順序法は妥協範囲にかなり近づくことができて いる. そしてどの問題でも他の表現法より良い解を求めることができている. 以上の結果か ら, JSPに対する染色体表現は作業順序法を採用することとする. 次章では,作業順序法を用 いて各種パラメータを調整する実験の結果を示す.
第
5
章
作業順序法を用いた実験
5.1
交叉
作業順序法の染色体は実際のプログラム上では, 1から仕事数*機械数までの整数の順列と して表現され, 仕事数4,機械数3の場合だと図5.1のような形になっている. 適応度計算時 に仕事数4で除算した余りの値に1を足すと図5.2のようになり,これは前章の図4.16と同 じである.このようにしたのは図 5.2の形では交叉の処理が難しくなるからである. こうす ることにより順列の染色体になり交叉を行いやすくなる. 図5.1 プログラム上の染色体 図5.2 作業順序法の染色体 交叉方法は部分一致交叉と巡回交叉を使用した.交叉する染色体を選択する方法はルー レット選択を用いた. この方法は適応度が高い染色体ほど選ばれやすい選択法である.5.1.1
部分一致交叉
(PMX)
部分一致交叉(partial mapped crossover: PMX) とは, 選ばれた2つの染色体を同じ所 で区切り(切断点)そこを基準に交叉させる. 切断点を1つにする一点交叉と2つにする二 点交叉などがあり,切断点はランダムに選ばれる.例えば図5.3に二点交叉のため切断点を選 んだ2つの染色体P1, P2を示す.
5.1 交叉 図5.3 PMX親 この選ばれた切断点にはさまれた内側を親から受け継ぐ. P1 はP2 の内側を, P2はP1 の 内側を受け継ぐ. P1 の内側をP2 の内側と同じ形にするためにP1 の4と7を入れ換えると,図5.4になる. 図5.4 PMX処理1 図5.5 PMX処理2 次はP1 の8と3を入れ換える.図5.5の形になる. このようにP2の内側と同じ形になる ように値の交換を行う. 同じ手順でP2 もP1 の内側と同じ形になるよう, 値を交換すると図 5.6のC1, C2ような子になる. C1はP2 の染色体情報を受け継ぎ, C2 はP1 の情報を受け継 いでいる. 図5.6 PMX子 また, 右側の切断点を染色体の右端に固定すると, 左側の切断点だけがランダムに選ばれ る. こうすることにより,選んだ切断点から右側の情報を受け継がせる一点交叉となる. 同様 に左側の切断点を染色体の左端に固定し,右側をランダムにすると左側の情報を受け継がせ
5.1 交叉 る一点交叉にできる. さらに切断点ではさんだ内側の染色体情報を受け継がせるのではなく 外側を受け継がせることもできる. 部分一致交叉だけでも4 種類の交叉を行うことができる.
5.1.2
巡回交叉
(CX)
巡回交叉(cycle crossover: CX)とは,選ばれた2つの染色体の1つの遺伝子座を選択し, もう1つの染色体を参照しながら交叉する場所を決定する.図5.7に遺伝子座を選んだ染色 体P1と, 交叉する場所を決定するP2 を示す. 図5.7 CX親 この場合は, P1 の8が選ばれたのでそこの遺伝子座に対応するP2 の値を参照する. 値は 3となっているのでP1 の3に印を付ける.そしてP1 の3がある遺伝子座に対応するP2 の 値を参照する. これを最初に選択された8に印がつくまで繰り返して図5.8のようになる. 図5.8 交叉座標決定 そして,印が付いているP1 とP2 の値を交換する. そうすると図5.9 のようになり, P1, P2の染色体情報を受け継いだC1, C2 を生成できる.5.2 突然変異 図5.9 CX子
5.2
突然変異
突然変異は1つの染色体の遺伝子座を2つランダムに選択して値を交換する.図5.10に示 す. 上にある染色体が突然変異前のもので, 6と11を交換することで下の染色体となり突然 変異が完了する. 図5.10 突然変異5.3
交叉確率と突然変異確率
いくつかの問題で交叉確率と突然変異確率を5%刻みで変更し実行した. 各問題の良い解 を求めることができた組み合わせの1位から3位までをプロットしたものを図5.11に示す. 横軸が交叉確率で縦軸が突然変異確率である.5.4 適応度計算 図5.11 確率の組合せ このグラフを見ると交叉確率が50%以上で,突然変異確率が50%以下の組み合わせが多 い. 実験を行う場合も交叉確率を50%以上にし,突然変異確率を50%以下に設定する.
5.4
適応度計算
makespan は 小 さ い ほ ど 良 い も の で, 適 応 度 は 大 き い ほ ど 良 い も の と 解 釈 さ れ る. makespanをそのまま適応度とすると矛盾が生じてしまうので, 計算したmakespanの逆数 をとることにより小さいものほど大きい値にすることができる. これを逆数法と呼ぶことに する.このままでは1より小さい値なので大きい数の積で小数点以下を切捨て整数にした. 逆数法で計算した適応度で,一番低い染色体の適応度に−1したものを定数とし,全ての染 色体の適応度をその定数で引き, 最小の適応度を1にする方法をシフト法と呼ぶ.適応度を 整数にした理由は−1すると簡単に定数を定めることができるからである. 表5.1に適応度 を逆数法,シフト法の2つの方法を用い,交叉方法を変えて実行した結果を示す.5.5 終了条件 表5.1 適応度と交叉の組み合せの比較 問題 適応度計算法 PMX(内側) PMX(左固定) PMX(右固定) PMX(外側) CX 仕事数15 逆数法 1354 1339 1334 1357 1318 機械数15 シフト法 1275 1329 1273 1304 1305 仕事数30 逆数法 2444 2357 2392 2410 2360 機械数20 シフト法 2214 2299 2246 2265 2294 仕事数15,機械数15の問題の最適解があるとされている範囲は1231∼1005で仕事数30, 機械数20の問題は2064∼1850である. PMXの内側というのは切断点の内側を交叉させた もので,左固定は切断点の左側を染色体の左端に固定したもの. 右固定は切断点の右側を右 端に固定している.外側というのは切断点の外側を交叉させたものである. 全てパラメータ は同じで乱数の種だけ変更し実行した結果の平均makespanを示している. どの交叉方法でもシフト法の方が良い解を求めることができている. 表5.1以外の問題で 試した結果もシフト法が良い解を求めることができた. 定数で引くと適応度の大きいものと 小さいものとの差が大きくなり良いものの方が選ばれやすくなるからだと思われる. 交叉方 法に注目するとPMXの内側と右固定が逆数法とシフト法の両方で他の交叉方法より良い解 を求めることができている. 適応度計算の方法はシフト法を使用し,交叉方法はPMXの内 側と右固定を使用することとする.
5.5
終了条件
終了条件を定めるため,図5.12から図5.15に5000世代まで各問題を実行し, その世代で 一番良い染色体の表すmakespanをプロットしたグラフを示す. 乱数の種以外のパラメータ は同じである.横軸が世代数で縦軸がmakespanである.5.5 終了条件 図5.12 仕事15,機械15の問題 図5.13 仕事20,機械15の問題 図5.14 仕事30,機械15の問題 図5.15 仕事50,機械15の問題 各図を見るとだいたい4500世代までで,解の改善が行われなくなっている. そして解が改 善される間隔がだいたい1500世代以内になっているので,終了条件として以下にまとめる. 終了条件 1. 1500世代の間,解の改善がなければ終了 2. 最低4500世代までは実行する 終了条件はこの2つを定める.
第
6
章
実験結果と結論
6.1
実験結果
交叉確率75%,突然変異確率10%の結果を表6.1に, 交叉確率55%,突然変異確率50%の 結果を表6.2に示す. この組み合わせで実行した理由は,図6.1で, 交叉確率でプロットさ れている数に注目したとき(この図は図5.11と同じものである), 75%に4つのプロットが ある.これは交叉確率で 1番多いプロット数である.そして突然変異確率に注目したときに, 10%に3 つのプロットがある. これも突然変異確率で一番多いプロット数である. よって 75%, 10%という組み合わせを実行した. そして55%, 50%としたのは,この組み合わせだけ プロットが2つ重なっており, さらに交叉確率55%には3つのプロットがありその内2つが 1位のものである. よってこの 2つの組み合わせを試した.パラメータは同じで 2つの乱数 の種で実行し, 2つの結果の内で良い方のmakespanを示している. 図6.1 確率の組合せ6.1 実験結果 表6.1 交叉確率75%,突然変異確率10%での結果 仕事数,機械数 最適解 妥協範囲 PMX(内側) PMX(右固定) 10, 5 666 732 666 666 10, 10 943 1037 948 948 15, 15 1233∼940 1356 1271 1269 20, 15 1345∼1329 1479 1427 1411 30, 20 2057∼1949 2262 2288 2282 50, 20 3071 3378 3309 3250 100, 20 5464 6010 5610 5583 表6.2 交叉確率55%,突然変異確率50%での結果 仕事数,機械数 最適解 妥協範囲 PMX(内側) PMX(右固定) 10, 5 666 732 666 666 10, 10 943 1037 948 943 15, 15 1233∼940 1356 1271 1242 20, 15 1345∼1329 1479 1426 1365 30, 20 2057∼1949 2262 2242 2188 50, 20 3071 3378 3281 3225 100, 20 5464 6010 5631 5501 仕事数10,機械数5の問題では最適なmakespanを求めることができている. 表6.2では 10, 10でもPMX(右固定)で最適なmakespanを求めることができた. 問題の規模が10, 10 より大きなものでは,最適な makespanを求めることができなかったが, 表6.1ではほぼ全 ての問題で, 表6.2では全ての問題でupper boundの1割増しと定めた妥協範囲には到達 している.
6.2 結論
6.2
結論
本論文では,遺伝アルゴリズムを用いたジョブショップスケジューリング問題への近似解法 を提案した. 4つの表現法のうち,良い解を求めることができた作業順序法を用い,パラメー タを調整し実験を行った. 仕事数10,機械数5のような問題の規模が小さなものでは最適解 を求めることができた. 仕事数15,機械数15のような問題では最適なmakespanは得られ なかったが, 妥協範囲にはとどき,ほとんどの問題でupper boundに近い解を求めることが できた. upper boundに近い解を求められた問題ではさらにパラメータ調整を行えば最適解にと どく可能性がある. upper boundに近い解を求められた問題の共通点として仕事数に対して 機械数が少ないということを見つけた. 表にはないが仕事数15,機械数5や20, 5や30, 10 のような仕事数に対して機械数の割合が小さい問題では, 染色体の初期集団ですでに最適解 に近い解をもった染色体が生成されていた. 問題規模30, 20や50, 20などの仕事数に対し 機械数もそれなりにある問題は実行した結果は妥協範囲にとどくのがやっとである. 表6.2 の100, 20の問題でも規模が大きいが仕事数に対し機械数が少ないのでPMX(右固定)では 最適解に近いものを求めることができている. 仕事数に対し機械数もそれなりにある問題が妥協範囲にどどくのがやっとだった原因のひ とつは, 機械が作業をしない無駄な時間が作られやすいことであると考えられる. 図6.2に 示すように, M2 に1番目に挿入した作業が,短い時間で処理されるものだったとき(この仕 事をJ1 とする), J1 の2番目の作業をM2 に挿入したとすると図6.2の左のようになる. 2 番目の作業を挿入した機械(M1 とする)で別の仕事の1番目の作業(J2の作業とする)を挿 入するとき, J1 の2番目の作業の前には空白があり挿入できそうなスペースがあるのだが J1 の1番目の処理が短いので, 今挿入しようとしているJ2 の作業を挿入することができな い. よってM1 はJ1 の2番目の作業の次にJ2 の1番目の作業を処理しなくてはならなく なり, 図6.2の右のようにM1 の最初に無駄な時間ができてしまう. このようなことが機械 数が多い程発生しやすいのではないかと考えた.6.2 結論 図6.2 最適解にとどかない原因 だが無駄な時間と記述したが,このような処理順序になったとき, J1 は次の3番目の作業 を早く処理を開始することができるので本当に無駄であるかどうかは, まだ処理されていな い作業で決まる. なので突然変異などの処理で染色体の順序をランダムに入れ換えるだけで なく, 染色体の順序が図6.2の場合だと 染色体= (1, 1, 2,…)となっているので, 「1, 1と 同じ数字が続いているときに2番目の1とランダムに選んだ1以外の値と入れ換える」のよ うな処理を一定の確率で発生するように追加などすれば最適解を求められる可能性が高くな ると思われる.
謝辞
本論文は著者が高知工科大学情報システム工学科在学中に, 同学科坂本研究室において 行った研究の成果を記したものである. 本論文を著すにあたり遺伝アルゴリズム,プログラミングなど御指導頂いた坂本明雄教授 に深く感謝致します. 御指導頂いた先輩方,プログラム稼働中の暇潰しにつき合ってくれた決闘者の皆様のおか げで大学へ行くことへのモチベーションを保つことができ,本論文を著することができまし た感謝致します. 著者が大学生活を有意義に過ごすことができたのは,本大学入学から卒業 の間で出会うことができた皆様のおかげです. 最後に,講義だけでなく就職活動まで御指導,御支援頂いた情報システム工学科の諸先生方 に深く感謝致します.参考文献
[1] 三宮信夫・喜多一・玉置久・岩本貴司,遺伝アルゴリズムと最適化,朝倉書店, 1998. [2] L. Dabis, Handbook of Genetic Algorithms (嘉数侑昇他訳,遺伝アルゴリズムハンド
ブック,森北出版, 1944).
[3] 松浦春樹, “NEH アルゴリズムに基づくジョブショップ・スケジューリングのための ヒョーリスティック”, 国際経営論集 No.36 2008.
[4] OR-Library, http://people.brunel.ac.uk/~mastjjb/jeb/info.html, 2009/12/18. [5] CP2SAT:JSS benchmark redults, http://bach.istc.kobe-u.ac.jp/csp2sat/jss/,
2010/1/27.
[6] ジョブショップスケジューリング問題,
http://mikilab.doshisha.ac.jp/dia/research/report/2002/0504/018/report20020504018.html, 2009/12/18.
