リフレッシュ型分散遺伝的アルゴリズムの 組み合わせ最適化問題への適用 同志社大学 三木 光範 同志社大学 廣安 知之 同志社大学大学院 勝崎 俊樹 ○

組み合わせ最適化問題とは ・設計変数がそれぞれ離散値をとる問題 ・最適解を求めることが極めて困難 ≫TSP(Traveling Salesman Problem) 複数の都市とその都市間の距離が与えられたとき，全ての都市を巡り，元に戻る最短の巡回路を求める問題 ≫JSP(Job-shop Scheduling Problem) ある製品の製造工程において，複数の仕事を複数の機械に割り当て，総所要時間の最小化を目指す問題

Job-shop Scheduling Problem (JSP) ・総作業時間(Makespan)を最小化する問題 ≫仕事は定められた順序で機械に処理されなければならない ≫1つの機械は同時に2つ以上の仕事を処理できない ・組み合わせのパターンが膨大なため，厳密解法で解く　ことは極めて困難

遺伝的アルゴリズム（GA） 長所 ・初期生成した個体を選択・交叉・突然変異で進化させる ことによる解探索 ・初期生成した個体を選択・交叉・突然変異で進化させる　ことによる解探索 長所 ・傾向の異なる個体を組み合わせて解探　索を行うので、広域な探索が可能 そこで、まずGAについて説明します。GAは、初期精製した個体を選択・交叉・突然変異で進化させることによって解探索を行う手法です。GAの長所としては、初期生成によって与えられた傾向の異なる個体を組み合わせて解探索を行うため、様々な傾向を持つ解を探索することができることがあげられます。

遺伝的アルゴリズム（GA） 短所 局所解への早熟収束 ・初期生成した個体を選択・交叉・突然変異で進化させる ことによる解探索 ・初期生成した個体を選択・交叉・突然変異で進化させる　ことによる解探索 短所 ・個体同士の情報交換によって解探索を 　行うため，世代が進むと個体の傾向　　が同じになる ・一度全ての個体が同じ傾向になって 　しまうと，他の傾向の個体を生み出す 　ことができない しかし、GAには短所も存在します。GAは個体同士の情報交換によって解探索を進めるため、この図のように世代が進むに従って似た傾向の個体が増えてしまいます。そして、一度全ての個体が似た傾向となってしまうと、他の傾向の個体を生み出すことができなくなってしまいます。つまり、局所解から脱出ができなくなってしまいます。このGAの短所は早熟収束と呼ばれます。 局所解への早熟収束

分散遺伝的アルゴリズム（DGA） ・単一母集団GA(SPGA)の短所 早熟収束によって局所解から脱出できなくなる

分散遺伝的アルゴリズム（DGA） ・分散遺伝的アルゴリズム(DGA)の特徴 ≫個体が複数のサブ母集団(島)に分割されている 全ての個体が同じ傾向になりにくい ≫サブ母集団間で個体を一定間隔ごとに交換する(移住) 異なる傾向の個体同士が交叉しやすくなる GA、特に母集団が１つしかない単一母集団GA、SPGAの短所として、早熟収束によって局所解から脱出できなくなることをせつめいしました。この短所を軽減するために、分散遺伝的アルゴリズム、DGAを用いることが有効であると報告されています。そこでまず、DGAについて説明します。 DGAはSPGAと比較して局所解に収束しにくい

Minimal Generation Gap(MGG) 局所的な世代交代を実現する世代交代モデル[佐藤 1997] ≫初期収束の回避，探索終盤の多様性維持に優れている MGGは他の世代交代モデルと比較して局所解に収束しにくい

JSPへのGAの適用 ・コーディング法 各機械ごとの仕事列 ・交叉法 Inter-Machine JOX（小野 1998） ・突然変異 Job-Based Shift Change（小野 1998） ・アクティブスケジュールを得るための強制操作 GT法による強制操作（Kobayashi 1995）

パラメータ(ft10，orb1) ・対象問題 ft10問題，orb1問題 Onamax問題、部分だまし問題について行った数値実験のパラメータは次のようにしました。 （5秒ほど待つ）

最適解発見率(ft10問題) ・SPGAと比較して，DGAは最適解発見率が高い ・サブ母集団数40のとき，最も良好な結果を示すが， これがOnemax問題の結果です。横軸を評価計算回数、縦軸を評価値としました。Onemax問題は局所解を持たないため、SPGA、DGAともに最適解を得られています。 ・SPGAと比較して，DGAは最適解発見率が高い ・サブ母集団数40のとき，最も良好な結果を示すが， 　最適解発見率は30%に満たない

最適解発見率(ft10問題・MGG) ・SPGAとDGAは最適解発見率が変わらない ・ルーレット選択を使用した場合より良好な結果が 　得られる

最適解発見率(orb1問題) ・SPGAと比較して，DGAは最適解発見率が高い ・サブ母集団数80のとき，最も良好な結果を示すが， これがOnemax問題の結果です。横軸を評価計算回数、縦軸を評価値としました。Onemax問題は局所解を持たないため、SPGA、DGAともに最適解を得られています。 ・SPGAと比較して，DGAは最適解発見率が高い ・サブ母集団数80のとき，最も良好な結果を示すが， 　最適解発見率は20%に満たない

最適解発見率(orb1問題・MGG) ・SPGAとDGAは最適解発見率が変わらない ・通常の世代交代モデルを使用した場合より 　かなり良好な結果が得られる

考察 理由 ・ルーレット選択と比較し，MGGのような世代交代モデル を用いることでより良好な解を得ることができた 　を用いることでより良好な解を得ることができた ・MGGをDGAに適用したが，解探索性能の向上は見られ 　なかった 理由 MGG，DGAともに個体を分割することで多様性の維持 を図っているため，DGAの効果がはっきりと表れない このように、部分だまし問題はDGAを用いても良好な結果を得ることができませんでした。この理由としては以下の2点が考えられます。１つは島数を増やすことで良好な解を得ることはできるが、島数を増やし過ぎ、1島あたりの個体数を減すと島内で有効な解探索が行えなくなってしまうこと、もう１つは進化が停滞した状態で通常の突然変異を行っても、局所探索しか行うことができず、局所解から脱出することができないことが挙げられます。 そこで、この２つの問題点を改善するために、新たな手法、リフレッシュ型分散GAを提案します。

考察 ルーレット選択の問題点 ・ルーレット選択と比較し，MGGのような世代交代モデル を用いることでより良好な解を得ることができた 　を用いることでより良好な解を得ることができた ・MGGをDGAに適用したが，解探索性能の向上は見られ 　なかった ルーレット選択の問題点 ・サブ母集団数を増やすことでより良好な解が得られるが， 　各サブ母集団の個体数を減らしすぎると 　有効な解探索が行えない このように、部分だまし問題はDGAを用いても良好な結果を得ることができませんでした。この理由としては以下の2点が考えられます。１つは島数を増やすことで良好な解を得ることはできるが、島数を増やし過ぎ、1島あたりの個体数を減すと島内で有効な解探索が行えなくなってしまうこと、もう１つは進化が停滞した状態で通常の突然変異を行っても、局所探索しか行うことができず、局所解から脱出することができないことが挙げられます。 そこで、この２つの問題点を改善するために、新たな手法、リフレッシュ型分散GAを提案します。 ルーレット選択の問題点を解決することによる DGAの解探索性能の向上 ・進化が停滞した状態では，局所解から脱出ができなく 　なってしまう

リフレッシュ型分散GAの提案 ・リフレッシュ型分散GA(DGA/R)はSPGAとDGAの ２つのグループを用いる 　２つのグループを用いる ・SPGAから定期的にDGAに良好な個体を送り， 　交叉による情報交換する(リフレッシュ交叉) ・SPGAは定期的に初期化する DGAの各島に 良好な個体を送り 交叉する リフレッシュ型分散GA、DGARはSPGAとDGAの2つのグループを用いるGAです。DGARでは、次の様にSPGAから定期的にDGAに良好な個体を送り、DGAにある個体と交叉することで情報を交換します。そして、SPGAの個体は定期的に初期化を行います。 SPGA DGA

DGA/Rによる効果 ・各サブ母集団の個体数を減らしすぎると有効な解探索が 行えない 　行えない SPGAを定期的に初期化することで局所解脱出を助けるため，サブ母集団数を必要以上に増やさずに良好な結果が得られる ・進化が停滞した状態では，局所解から脱出できない このDGARによって、次の様な効果が得られると思われます。まず、DGAでは1島あたりの個体数を減らしすぎると有効な解探索を行うことができませんでしたが、DGARではSPGAを定期的に初期化するという動作があることで局所解脱出を助けるため、島を必要以上に増やさないでも良好な結果を得ることができます。また、進化が停滞した状態では局所会から脱出できないという点は、SPGAから傾向の違う個体を定期的に送り込むことで、局所探索だけではなく個体に大きな変化を与えられると考えられます。 それでは、実際のDGARのアルゴリズムについて説明します。DGARでは初めの状態では図のようにSPGA、DGAをそれぞれ独立させて解探索を行います。 SPGAから傾向の違う個体を定期的に送り込むことで， 局所探索だけでなく個体の大きな変化を与えられる

DGA/Rのアルゴリズム SPGA DGA それでは、実際のDGARのアルゴリズムについて説明します。DGARでは初めの状態では図のようにSPGA、DGAをそれぞれ独立させて解探索を行います。

DGA/Rのアルゴリズム SPGA DGA そして、一定世代に達すると、SPGA、DGAはそれぞれで最も有効な個体をコピーし、保存します。このとき、DGAでは各島につき1個体づつ、SPGAではDGAの島数分だけの個体を保存します。

DGA/Rのアルゴリズム SPGA DGA SPGAで保存された個体をDGAに送り、DGA各島に保存された個体と複数回交叉を行います。こうすることで、SPGAの特徴をDGAに反映させることができます。

DGA/Rのアルゴリズム SPGA DGA そして、これらの交叉で生まれた中でも最も良好な個体をDGAの各島に返します。その後SPGAの個体を初期化します。この動作が終了すると、再びDGARはDGAとSPGAを独立させて解の探索を行います。これらの動作を繰り返すことで、DGARによる解探索は進められます。

実験の設定 それではDGARによる数値実験を行います。用いたパラメータについては、以上のようにしました。（5秒ほど待つ）

DGA/Rによる最適解発見率 DGA/RはDGA，SPGAと比較して高い最適解発見率を 示している

考察 代表的なジョブショップスケジューリング問題である ft10，orb1問題に対しDGA/Rを用いたところ，DGAと 同等以上の性能を得られた ft10問題に関してはMGGを用いた DGA以上の最適解発見率 初期化を行うSPGAによって作られる新たな部分解を DGAに組み込むことで良好な解を得られていると考えられる 初期個体を定期的に送り込み， リフレッシュ交叉を行うDGAとDGA/Rを比較

パラメータ

最適解発見率の比較 SPGAによる部分解を利用することで良好な結果が得られる

まとめ ・組み合わせ最適化問題に対して，DGAよりも高い 解探索性能を持つリフレッシュ型分散GA(DGA/R)を提案 ・代表的なジョブショップスケジューリング問題として　知られるft10問題，orb1問題に対してDGA/Rを適用 　したところ，MGGを採用したDGAと同等以上の性能　を得られた ・DGA/RがDGAと比較して良好な結果を示す理由 ≫初期化スキーマによる多様性の維持 ≫部分解同士を有効に組み合わせた解探索の実現 ・今後の課題 DGA/Rの有効な問題の性質の検証

質疑応答

ft10問題におけるMakespanの履歴 DGA/Rは，DGA，SPGAと比較して後半まで 解探索性能を保つことができている

orb1問題におけるMakespanの履歴 DGA/Rは，DGA，SPGAと比較して後半まで 解探索性能を保つことができている

ft10問題のMakespanの履歴

orb1問題のMakespanの履歴

GAの設定 ・コーディング法 各機械ごとの仕事列 各機械ごとに得られる仕事列を，遺伝子に変換

GAの設定 ・交叉法 Inter-Machine JOX（小野 1998） すべての 機械において 指定した仕事の 作業を子に継承する 親1,2の形質が 子1,2に継承される J1を選択

GAの設定 ・突然変異 Job-Based Shift Change（小野 1998） すべての機械で指定した仕事の作業を左 or 右に移動させる

SPGAの効果を除いたDGA/R