41st MPS

分散遺伝的アルゴリズムによる
離散的最適化問題の新解法
水田伯典, 三木光範, 廣安知之
同志社大学工学部
知的システムデザイン研究室
第9回 MPS シンポジウム
2003. 1.16
発表の概要
離散的最適化問題に対する
新たな分散GAモデルの提案と有効性の検証
• 離散的最適化問題に対する分散GAの性能検証
• 新たな分散GAのモデル GCDGA の提案
• 数値実験によるGCDGAの有効性検証と考察
• まとめ
Intelligent Systems Design Lab. Doshisha Univ.
遺伝的アルゴリズム (GA)
GA(Genetic Algorithm)は
生物の進化を模倣したアルゴリズム
初期化
選択
交叉
突然変異
遺伝的操作
反復計算を行うため負荷が高い
評価
終了条件
GAの並列化
探索終了
• 島モデルの分散GA
• 近傍モデル etc...
Intelligent Systems Design Lab. Doshisha Univ.
分散GA (Distributed GA: DGA)
• 母集団を複数のサブ母集団(島)に分割
• サブ母集団ごとに独立して探索を行う
• 一定周期ごとに移住を行い情報交換を行う
Intelligent Systems Design Lab. Doshisha Univ.
分散GAの操作
初期化
サブ母集団数の母集団を生成
評価
終了条件
Yes
探索終了
No
選択
移住間隔
Yes
移住
No
移住間隔ごとに移住を実行
移住する個体数は
移住率によって決定される
交叉
突然変異
分散GAには上記3つの
新たなパラメータが存在する
Intelligent Systems Design Lab. Doshisha Univ.
研究背景
分散GAの性能
• 連続最適化問題
単一母集団GAよりも高い性能を示す [三木00]
• 離散的最適化問題
対象問題によっては報告がされているが、
TSPやJSPにおける報告は少ない
JSPを対象として分散GAの性能検証
・・・
分散GAの性能は高くない
分散GAの性能を向上させる新手法の提案と評価
Intelligent Systems Design Lab. Doshisha Univ.
Job-shop Scheduling Problem (JSP)
複数の独立な仕事を行うために
仕事を処理する機械の時間的な割当てを決定する問題
• 仕事は定められた順序で機械に処理されなければならない
• 一つの機械は同時に二つ以上の仕事を処理できない
総作業時間(Makespan)を最小化する問題
Intelligent Systems Design Lab. Doshisha Univ.
GAの設定
本研究で用いた実験の設定
コーディング法
交叉
突然変異
世代交代モデル
個体修正
各機械ごとの仕事列
Inter-Machine JOX
Job-based Shift Change
CCM
GT法
Intelligent Systems Design Lab. Doshisha Univ.
GAの設定
本研究で用いた実験の設定
コーディング法
交叉
突然変異
世代交代モデル
個体修正
各機械ごとの仕事列
Inter-Machine JOX
Job-based Shift Change
CCM
GT法
Intelligent Systems Design Lab. Doshisha Univ.
GAの設定
本研究で用いた実験の設定
コーディング法
交叉
突然変異
すべての
世代交代モデル
機械において
指定した仕事の
個体修正
作業を子に継承する
各機械ごとの仕事列
Inter-Machine JOX [小野98]
Job-based Shift Change
CCM
J1,J4
GT法を選択
親1,2の形質が
子1,2に継承される
Intelligent Systems Design Lab. Doshisha Univ.
GAの設定
本研究で用いた実験の設定
コーディング法
交叉
突然変異
世代交代モデル
個体修正
各機械ごとの仕事列
Inter-Machine JOX
Job-based Shift Change
CCM
GT法
すべての機械で
指定した仕事の
作業を左 or 右に
移動させる
Intelligent Systems Design Lab. Doshisha Univ.
GAの設定
本研究で用いた実験の設定
コーディング法
交叉
突然変異
世代交代モデル
個体修正
各機械ごとの仕事列
Inter-Machine JOX
Job-based Shift Change
CCM [Ono 98]
GT法
Intelligent Systems Design Lab. Doshisha Univ.
GAのパラメータ
単一母集団GAと分散GAの性能比較
母集団サイズ
交叉率
突然変異率
CCM生成個体数
評価計算回数
800
1.0
0.1
10
6
10 回
移住に関するパラメータは以下の12通りを採用
移住間隔 2, 5, 10, 20世代
0.1, 0.2, 0.5
移住率
100回試行
最適解取得率を比較する
Intelligent Systems Design Lab. Doshisha Univ.
単一母集団GAと分散GAの性能比較(2)
FT10問題
移住パラメータ
Sub Interval Rate
4
2世代
0.2
10
5世代
0.5
20
10世代
0.5
40
2世代
0.5
80
2世代
0.5
(SPGA)
移住パラメータの調節により、分散GAの性能が向上
移住を多く行うほうが高い性能を示す
Intelligent Systems Design Lab. Doshisha Univ.
分散GAの性能と考察
分散GAの性能
• サブ母集団数の少ない分散GAは
単一母集団GAよりもやや高い性能を示す
• 移住を多く行うことで性能が上がる
サブ母集団数を増やしても性能が向上しない
移住による情報交換がうまく機能していない
離散的最適化問題
従来の分散GAでは性能が向上しない
Intelligent Systems Design Lab. Doshisha Univ.
分散GAの問題点
離散的最適化問題
移住による情報交換がうまく行われていない
各サブ母集団で成長している部分解を集め、
それらをつなぎ合わせて最適解を得る
対象問題の性質
特殊なコーディングを用いることが多い
離散的最適化問題では大きな部分解が存在しないことが多い
移住では部分解を集めることができない
移住個体が移住先のサブ母集団で有効利用されにくい
Intelligent Systems Design Lab. Doshisha Univ.
新たなサブ母集団間情報交換スキームの提案
分散GAにおける問題点を解消する新手法
GCDGA(Global Crossover based DGA)の提案
従来の移住では性能が向上しない
移住に変わる新たな操作を導入する
・情報交換は交叉の連続によって行う
・各サブ母集団内で成長した個体を用いる
大域的交叉 (Global Crossover: GC)
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの操作
初期化
評価
終了条件
Yes
探索終了
No
選択
GC間隔
Yes
No
移住がGCに置き換わっている
GC
交叉
突然変異
他の部分は移住を行わない
分散GAと同じ操作
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの操作(2)
初期化
評価
終了条件
Yes
探索終了
No
選択
GC間隔
GC
No
GC個体群選択
Yes
GC
交叉対象個体選択
交叉
突然変異
多段交叉
No
GC終了
Yes
Intelligent Systems Design Lab. Doshisha Univ.
GC中の操作(1)
GC個体群選択
GC実行の個体候補選択
交叉対象個体選択
多段交叉
各サブ母集団からエリート個体を含む
半数の個体を選択
サブ母集団内での独自性が維持される
GC終了
GC個体群の選択は
1回のＧＣ中で
1度しか実行されない
Intelligent Systems Design Lab. Doshisha Univ.
GC中の操作(2)
GC個体群選択
交叉対象個体選択
多段交叉
多段交叉の対象とする個体の選択
• 各サブ母集団のGC個体群から
2個体ずつを交叉対象個体とする
• 高い確率でエリートを選択
GC終了
交叉対象個体のみ
多段交叉が適用される
残りの個体はそのまま
Intelligent Systems Design Lab. Doshisha Univ.
GC中の操作(3)
GC個体群選択
交叉対象個体選択
多段交叉
交叉対象個体を用いた複数回の交叉
• 親個体は必ず異なるサブ母集団
からの個体とする
• 各ペアで複数回の交叉を行う
GC終了
多段交叉回数に至るまで
親個体の組み替えを行って
再度交叉を行う
Intelligent Systems Design Lab. Doshisha Univ.
GC中の操作(4)
GC個体群選択
交叉対象個体選択
GC終了条件を満たすまで
交叉個体の選択・多段交叉を繰り返す
多段交叉
GC終了
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの特徴
エリート個体を重視した連続交叉による情報交換
• エリート個体は各サブ母集団の有力な情報を持った個体
• 最適解を構成する微少な部分解が含まれる可能性が高い
交叉によって部分解が組合わされ最適解に近づく
GCでの交叉対象は一部の個体のみ
• 交叉が行われなかった個体は各サブ母集団の性質を維持する
移住を行わない分散GA
• 各サブ母集団の独立した進化が探索の終盤まで行われる
GCDGAは多様性を失うことなく探索を続けられる
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの設定
GCDGAと単一母集団GA・分散GAの性能比較
GCDGA独自の設定
GC開始
10世代目
GC適用間隔
5世代
GC終了条件
8万回評価
多段交叉回数
2
エリート選択率
0.5
他のパラメータは先の実験と同じとする
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能
FT10問題
• GCDGAの性能は分散GAよりも高い
• GCDGAはサブ母集団数を増やすと性能が向上する
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能(2)
ORB1問題
サブ母集団数を増やすとGCDGAの性能が向上する
Intelligent Systems Design Lab. Doshisha Univ.
GCDGA性能の考察
GCDGAの性能
• サブ母集団数が多い場合には分散GAよりも高い性能
多様な個体を多段交叉に用いる方が性能が上がる
• 解探索の履歴
の検証
• 部分解の成長
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能考察
FT10問題適合度の履歴 (100試行平均)
水色は
GC適用部分
• GCによる解の改善は分散GA(移住)よりも大きい
• サブ母集団数が多いGCDGAは探索後半でも解探索能力が高い
Intelligent Systems Design Lab. Doshisha Univ.
JSPに対する新たな指標
JSPには多くの最適解が存在する
最適解中のクリティカルパスは一致している
クリティカルパスの連続を調査する
赤線を引いているジョブは
クリティカルパス上のジョブ
Intelligent Systems Design Lab. Doshisha Univ.
JSPに対する新たな指標
最適解中のクリティカルパスの2つの連続
最適クリティカルパスペア(OCP)
一致するOCPの数＝部分解の数
赤線を引いているジョブは
クリティカルパス上のジョブ
Intelligent Systems Design Lab. Doshisha Univ.
OCP数の推移
GCDGAと従来手法でのOCP数の比較
FT10問題
最大OCP=16
水色は
GC適用部分
探索中盤以降のGCによりOCP数が大きく増加
GCDGAの性能が向上した要因
Intelligent Systems Design Lab. Doshisha Univ.
OCP数の推移
GCDGAにおけるサブ母集団数ごとの比較
FT10問題
水色は
GC適用部分
全エリート個体中のOCP数に差がある
探索後半の成長に差が出た原因
Intelligent Systems Design Lab. Doshisha Univ.
OCP数の推移(2)
ORB1問題
最大OCP=23
水色は
GC適用部分
GCによってOCP数が大きく増加している
Intelligent Systems Design Lab. Doshisha Univ.
GCDGA性能の考察
GCDGAの性能
• サブ母集団数が多い場合には分散GAよりも高い性能
GCDGAによる多様性の維持
多様な個体を多段交叉に用いることで性能向上
個体が各サブ母集団に
分散していることが有効活用されている
• GCは移住よりも高い効果を持つ
GCは移住に変わる新たな分散GAのオペレータ
Intelligent Systems Design Lab. Doshisha Univ.
まとめ
GCDGAの提案
• 離散的最適化問題において
分散GAの移住では大きな性能向上は見られない
• サブ母集団間の効率的な情報交換に着目
GCDGAの性能
• 分散GAよりも高い解探索性能を持つ
• サブ母集団数の多くすることで性能が向上する
• 多くの部分解を集めれば高い性能を得られる
Intelligent Systems Design Lab. Doshisha Univ.
Intelligent Systems Design Lab. Doshisha Univ.
分散GAの性能と考察
分散GAの性能
• サブ母集団数の少ない分散GAでは
単一母集団GAよりもやや高い性能を示す
• 移住を多く行うことで性能が上がる
サブ母集団数を増やしても性能が向上しない
Intelligent Systems Design Lab. Doshisha Univ.
性能の考察
分散GAの性能はサブ母集団数を増やすと悪化した
サブ母集団内の個体数が減少した
・・・
4島・・・ 200個体
80島・・・ 10個体
サブ母集団内の多様性の低下
移住によって解決可能
移住間隔 10世代
0.1
移住率
前の実験におけるパラメータでは不十分
Intelligent Systems Design Lab. Doshisha Univ.
単一母集団GAと分散GAの性能比較
FT10問題
(SPGA)
• 最高の性能を示したのはサブ母集団数4の分散GA
•サブ母集団数を増やすと性能が低下
Intelligent Systems Design Lab. Doshisha Univ.
連続最適化問題における分散GAの性能
10次元Rastrigin関数
サブ母集団数を増やした方が分散GAの性能は高い
Intelligent Systems Design Lab. Doshisha Univ.
移住について (Random-Ring)
移住実行のたびに移住先を形成するリングが変わる方式
移住1
移住2
Intelligent Systems Design Lab. Doshisha Univ.
単一母集団GAと分散GAの性能比較
FT10問題
(SPGA)
• 最高の性能を示したのはサブ母集団数4の分散GA
• サブ母集団数を増やすと性能が低下
Intelligent Systems Design Lab. Doshisha Univ.
単一母集団GAと分散GAの性能比較(2)
移住パラメータ
Sub Interval Rate
4
2世代
0.2
10
5世代
0.5
20
10世代
0.5
40
2世代
0.5
80
2世代
0.5
(SPGA)
移住パラメータの調節により、分散GAの性能が向上
移住を多く行うほうが高い性能を示す
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能(FT10)
FT10問題
• GCDGAの性能は分散GAよりも高い
• GCDGAは島数を増やすと性能が向上する
Intelligent Systems Design Lab. Doshisha Univ.
ORB1問題
ORB1問題の最適解(一例)
最適解におけるクリティカルパスは一致している
OCP数による解探索性能調査
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能(2)
ORB1問題
水色は
GC適用部分
ORB1に対してはGCDGAが有効
探索の後半まで解の改善が続いている
Intelligent Systems Design Lab. Doshisha Univ.
OCP数の推移(2)
ORB1問題
最大OCP=23
水色は
GC適用部分
探索中盤以降の性能に差が出た原因
サブ母集団数が少ないと
各サブ母集団中のエリートにおけるOCP数が減少する
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能(LA19)
LA19問題
GCDGAの性能は分散GAと差がない
島数が少ないと性能が劣っている
Intelligent Systems Design Lab. Doshisha Univ.
GCDGAの性能(TSP)
eil101問題
40 Trials
TSPに対してもGCDGAは高い性能を示す
Intelligent Systems Design Lab. Doshisha Univ.

Download Report