DGAの手法の提案～DGA with SPGA～

リフレッシュ型
分散遺伝的アルゴリズム
同志社大学
同志社大学
○ 同志社大学大学院
三木光範
廣安知之
勝崎俊樹
Intelligent Systems Design Lab.
遺伝的アルゴリズム（GA）
・初期生成した個体を選択・交叉・突然変異で進化させる
ことによる解探索
長所
・傾向の異なる個体を組み合わせて解探
索を行うので，広域な探索が可能
Intelligent Systems Design Lab.
遺伝的アルゴリズム（GA）
・初期生成した個体を選択・交叉・突然変異で進化させる
ことによる解探索
短所
・個体同士の情報交換によって解探索を
行うため，世代が進むと個体の傾向
が同じになる
・一度全ての個体が同じ傾向になって
しまうと，他の傾向の個体を生み出す
ことができない
局所解から脱出できない(早熟収束)
Intelligent Systems Design Lab.
分散遺伝的アルゴリズム（DGA）
・単一母集団GA(SPGA)の短所
早熟収束によって局所解から脱出できなくなる
分散遺伝的アルゴリズム(DGA)を用いることで早熟収束の
影響を軽減できると報告されている[三木 2000]
SPGA
DGA
Intelligent Systems Design Lab.
分散遺伝的アルゴリズム（DGA）
・分散遺伝的アルゴリズム(DGA)の特徴
・個体が複数のサブ母集団(島)に分割されている
全ての個体が同じ傾向になりにくい
・サブ母集団間で個体を一定間隔ごとに交換する(移住)
異なる傾向の個体同士が交叉しやすくなる
DGAはSPGAと比較して局所解に収束しにくい
Intelligent Systems Design Lab.
テスト問題の導入
DGAを用いることで早熟収束の回避ができるかを
検証するために，以下のテスト問題を使用
• Onemax問題
局所解を持たない問題
• Harikの部分だまし問題
Onemax問題を4ビットごとに分割し，それぞれの
部分に大きな局所解を作った既存の問題
• オリジナルの部分だまし問題
Onemax問題を10ビットごとに分割し，それぞれの
部分に大きな局所解を作った自作の部分だまし問題
Intelligent Systems Design Lab.
Onemax問題
・“1”の値が得られたビットの数を評価値とする問題
・局所解を持たない問題
評価値
ビット列内に与えられたビット“1”の数が
評価値となる
Intelligent Systems Design Lab.
Harikの部分だまし問題
・Onemax問題を4ビットごとに分割し，大きな局所解を
持たせた問題
・解くことが極めて難しい問題
評価値
通常のOnemax問題では最適な部分解だが，
Harikの部分だまし問題では最大の局所解となる
Intelligent Systems Design Lab.
オリジナルの部分だまし問題
・Onemax問題を10ビットごとに分割し，大きな局所解を
持たせた問題
・解くことが極めて難しい問題
Intelligent Systems Design Lab.
実験の設定
Intelligent Systems Design Lab.
Onemax問題の結果
局所解がない問題では，DGA，SPGAともに最適解が
得られる
Intelligent Systems Design Lab.
Harikの部分だまし問題の結果
・サブ母集団数を増やすことで評価値を上げることができる
・DGAを用いても，序盤で局所解に陥ってしまう
Intelligent Systems Design Lab.
オリジナルの部分だまし問題の結果
・サブ母集団数を増やすことで評価値を上げることができる
・DGAを用いても，序盤で局所解に陥ってしまう
Intelligent Systems Design Lab.
DGAの問題点
部分だまし問題は，DGAを用いても良好な結果を
得ることができなかった
問題点
・サブ母集団数を増やすことでより良好な解が得られるが，
各サブ母集団の個体数を減らしすぎると
有効な解探索が行えない
・進化が停滞した状態で通常の突然変異を行っても，
局所探索しか行えないので，局所解から脱出できない
これらの問題点を解決するために
リフレッシュ型分散GAを提案する
Intelligent Systems Design Lab.
リフレッシュ型分散GAの概要
・リフレッシュ型分散GA(DGA/R)はSPGAとDGAの
２つのグループを用いる
・SPGAから定期的にDGAに良好な個体を送り，
交叉による情報交換する
・SPGAは定期的に初期化する
DGAの各サブ母集団に
良好な個体を送り
交叉する
SPGA
DGA
Intelligent Systems Design Lab.
DGA/Rによる効果
・各サブ母集団の個体数を減らしすぎると有効な解探索が
行えない
SPGAを定期的に初期化することで局所解脱出を助ける
ため，サブ母集団数を必要以上に増やさずに良好な結果
が得られる
・進化が停滞した状態では，局所解から脱出できない
SPGAから傾向の異なる個体を定期的に送り込むことで，
局所探索だけでなく個体の大きな変化を与えられる
Intelligent Systems Design Lab.
DGA/Rのアルゴリズム
DGA
SPGA
Intelligent Systems Design Lab.
DGA/Rのアルゴリズム
DGA
SPGA
Intelligent Systems Design Lab.
DGA/Rのアルゴリズム
DGA
SPGA
Intelligent Systems Design Lab.
DGA/Rのアルゴリズム
DGA
SPGA
Intelligent Systems Design Lab.
実験の設定
Intelligent Systems Design Lab.
DGA/Rの性能検証(Onemax)
対象問題：Onemax問題
DGA/RでもDGA，SPGAと同様に最適解を求めることが
できた
Intelligent Systems Design Lab.
DGA/Rの性能検証(Harik)
対象問題：Harikの部分だまし問題
DGA，SPGAと比較して，DGA/Rは良好な解が得られている
Intelligent Systems Design Lab.
DGA/Rの性能検証(オリジナル)
対象問題：オリジナルの部分だまし問題
DGA，SPGAと比較して，DGA/Rは良好な解が得られている
Intelligent Systems Design Lab.
解探索能力に関する考察
局所解を持つ部分だまし問題に対して，DGA/Rは有効な手法
最適解に必要な部分解を探索に組み込むことに成功している
部分だまし問題においては，ビット“0”が部分解となる
各遺伝子座のビット“0”が，全個体中で5％以上保存されている
場合，その遺伝子座は“最適解の一部となる可能性を持つ”
と判断
Intelligent Systems Design Lab.
解探索経路(Harik)
対象問題：Harikの部分だまし問題
・SPGAおよびDGAでは，序盤でビット“0”が失われている
・DGA/Rでは，ビット“0”を回復させることに成功している
Intelligent Systems Design Lab.
解探索経路(オリジナル)
対象問題：オリジナルの部分だまし問題
・SPGAおよびDGAでは，序盤でビット“0”が失われている
・DGA/Rでは，ビット“0”を回復させることに成功している
Intelligent Systems Design Lab.
他のモデルとの比較
多様性の維持について考慮された既存の世代交代モデル
であるMGGとの比較を行う
・MGGモデル[佐藤 1996]
ｰ多様性の維持を目的に使われる代表的モデル
- 他の世代交代モデルと比較し，良好な解が得られる
パラメータ
Intelligent Systems Design Lab.
MGGとの比較(Harik)
対象問題：Harikの部分だまし問題
Harikの部分だまし問題に対して，
DGA/Rは収束速度，解の精度ともにMGGを上回る
Intelligent Systems Design Lab.
MGGとの比較(オリジナル)
対象問題：オリジナルの部分だまし問題
オリジナルの部分だまし問題に対しても，
DGA/Rは収束速度，解の精度ともにMGGを上回る
Intelligent Systems Design Lab.
まとめ
早期の局所解収束を避けるために，DGAよりも
さらに局所解からの脱出に優れた手法として
リフレッシュ型分散GA(DGA/R)を提案
局所解を持つ問題に対して性能検証を行った結果，
SPGA，DGAと比較して良好な結果が得られた
多様性を考慮している世代交代モデルであるMGGと
比較し，より良好な結果を得ることができた
DGA/Rは有効な解探索手法であるといえる
Intelligent Systems Design Lab.
質疑応答
Intelligent Systems Design Lab.
DGA/RにおけるSPGAの効果
DGA/Rの解探索の要は，SPGAによる部分解の成長に
あると考えられる．
今回用いた2種類のOnemax問題に対して，
SPGAの効果を除いた初期化アルゴリズムを導入した
具体的には，
・SPGAの代わりに5個体の初期化した個体を
エリート交叉の際に使用する
・この実験はSPGAによる効果を確かめる実験なので，
改造したDGA/Rの総個体数は150とする
Intelligent Systems Design Lab.
DGA/RにおけるSPGAの効果
対象問題：Harikの部分だまし問題
Harikの部分だまし問題において，SPGAで部分解を
成長させることは重要である
Intelligent Systems Design Lab.
DGA/RにおけるSPGAの効果
対象問題：オリジナルの部分だまし問題
オリジナルの部分だまし問題において，SPGAで部分解を
成長させることは重要である
Intelligent Systems Design Lab.
マルチMGGモデル
・マルチスタートMGGモデル[渡部 1999]
ｰ MGGに初期化の概念を加えた最もシンプルなモデル
ｰ一定世代ごとにエリート個体以外の全個体を
初期化し，探索を続ける
パラメータ
Intelligent Systems Design Lab.
マルチスタートMGGとの比較(1)
対象問題：Harikの部分だまし問題
Optimum
マルチスタートMGGを用い，初期化の概念を加えても，
DGA/Rの解探索性能の方が高い
Intelligent Systems Design Lab.
マルチスタートMGGとの比較(2)
対象問題：オリジナルの部分だまし問題
Optimum
マルチスタートMGGを用い，初期化の概念を加えても，
DGA/Rの解探索性能の方が高い
Intelligent Systems Design Lab.
多様性の検証
・多様性の検証には，部分だまし問題を用いた
・ビットに，下図のように番号をつけ，
それぞれのビットが最適解へと進化できる可能性を
持っているかを調べた． (今回の場合は，“0”を持っている
割合で多様性を検証した)
ビット番号
Intelligent Systems Design Lab.
多様性の検証(SPGA)
“0”の数
“0”の数
・用いた問題は,部分だまし問題である
ビット番号
1世代目
200世代目
“0”の数
ビット番号
ビット番号
ビット番号
1000世代目
Intelligent Systems Design Lab.
“0”の数
“0”の数
多様性の検証(DGA : 20島)
ビット番号
1世代目
200世代目
“0”の数
ビット番号
ビット番号
1000世代目
Intelligent Systems Design Lab.
“0”の数
“0”の数
多様性の検証(DGA/R)
ビット番号
1世代目
200世代目
“0”の数
ビット番号
ビット番号
1000世代目
Intelligent Systems Design Lab.
“0”の数
“0”の数
多様性の検証(1000世代目)
ビット番号
SPGA
20島DGA
“0”の数
ビット番号
ビット番号
DGA/R
Intelligent Systems Design Lab.
DGAにおけるパラメータ検証
・突然変異率についてのパラメータ検証
評価値
最適解
評価計算回数
×
島数は20，交叉率は0.8を用いている
Intelligent Systems Design Lab.
DGAにおけるパラメータ検証(2)
・移住間隔についてのパラメータ検証
評価値
最適解
評価計算回数
×
島数は20，交叉率は0.8を用いている
Intelligent Systems Design Lab.
SPGAのパラメータ検証
・単一母集団GAの交叉率についてのパラメータ検証
評価値
最適解
0
2
4
8
6
評価計算回数 ×
10
4
Intelligent Systems Design Lab.
実験の設定
CCMを用いてDGA/Rと比較を行った．
対象問題：Harikの部分だまし問題
対象問題：オリジナルの部分だまし問題
Intelligent Systems Design Lab.
CCMとの比較(1)
対象問題：Harikの部分だまし問題
Optimum
DGA/RはCCMよりも良好な解探索性能を示す．
Intelligent Systems Design Lab.
CCMとの比較(2)
Optimum
DGA/RはCCMよりも良好な解探索性能を示す．
Intelligent Systems Design Lab.

Download Report