分散遺伝的アルゴリズムにおけ
るパラメータの検討
The examination of parameter settings for Distributed Genetic Algorithms
同志社大学工学部
廣安知之
同志社大学工学部
三木光範
同志社大学大学院
○ 上浦二郎
発表概要





研究背景
比較するパラメータの説明
パラメータを5グループに分類した数値実験
実験の結果を使用したパラメータチューニン
グ
結論
研究背景:分散遺伝的アルゴリズム

分散遺伝的アルゴリズム (Tanese 1989)




GAの並列化モデル
母集団を複数のサブ母集団(島)に分割
各サブ母集団(島)内で独立して遺伝的操作
移住(パラメータの増加)
Population
Migration
Subpopulations
(=Islands)
Distribute
研究背景:パラメータの検討の重要性

分散遺伝的アルゴリズムのパラメータは



数が多い(移住のパラメータの増加)
設定値が解探索効率に与える影響が大きい
最適値が単一母集団GAと異なる場合がある
分散GAに特化したパラメータの検討が必要

各パラメータ間に相互関係がある
複数のパラメータを同時に検討することが必
要
分散遺伝的アルゴリズムの各遺伝的操作に注
目してパラメータを分類して同時に検討を行
う
個体数に関するパラメータ

母集団サイズ(個体数)


探索点の総数
島数

母集団の分割数
Population
Subpopulations
(=Islands)
Population Size = 16
Number of Islands = 4
選択に関するパラメータ

選択手法

次世代の個体群の再生方法
– Roulette選択(目的関数値を基に適合度を決定)
– Roulette選択(個体の順位を基に適合度を決定)
– Tournament選択
Rank
Eval
Fit 1
Fit 2
1
38
32
4
2
15
9
2
2
15
9
2
4
14
8
1
Current
Generation
Next
Generation
交叉に関するパラメータ

交叉手法


交叉の方法
– 一点交叉
– 二点交叉
– 一様交叉
One-point Crossover
交叉率

親1と親2が交叉する確
率
Two-point Crossover
Uniform Crossover
突然変異に関するパラメータ

突然変異手法


突然変異の方法
– 通常の突然変異
– 単一遺伝子座突然変異
– シフト突然変異
突然変異率

Normal Mutation
Mono-bit Mutation
各遺伝子座が突然変異する
確率(通常の突然変異)
Shift Mutation
移住に関するパラメータ(移住時期,移住頻
度)

移住機会


移住間隔


移住をどの遺伝的操作の後に行うか
– 選択の後
– 交叉の後
– 突然変異の後
移住操作を行う世代間隔
移住率

島内の個体数に占める移住する個体の割合
移住に関するパラメータ(移住方法)

移住トポロジ


移住先の選び方
– Random Ring
– bi-Directional Ring
– Ladder
Random Ring
移住個体の選択方法

島から移住する個体の選び方
– Random を移住
– Best を移住
– Worst を移住
bi-Directional Ring
Ladder
数値実験

概要


パラメータを各遺伝的操作に着目して分類し,
同一分類のパラメータを同時に検討する
分類





選択・・・個体数,島数,選択手法
交叉・・・交叉手法,交叉率
突然変異・突然変異手法,突然変異率
移住頻度・移住率,移住間隔,島数
移住方法・移住トポロジ,移住個体,移住機会
共通パラメータ

検討対象でないパラメータの設定値












個体数:400
島数:8
選択手法:順位から適合度値を決定するルーレット選
択
交叉手法:一点交叉
交叉率:1.0
突然変異:通常の突然変異率
突然変異率:1 / 染色体長
移住トポロジ:ランダムリング
移住間隔:5
移住率:0.3
移住個体:ランダム
移住機会:選択の後
対象問題

Rastrigin関数


Ridge関数


強い依存関係あり,単峰性
Schwefel関数


依存関係なし,多峰性
依存関係なし,多峰性
Griewank関数

中程度の依存関係,
大域的には単峰性,
局所的には多峰性
選択に関するパラメータの実験

個体数


島数


2,4,8,...,256,512,1024
1,2,4,...,個体数/2
選択手法



Roulette(目的関数値から適合度値を求める
Roulette)
Rank Roulette(順位から適合度値を求める
Roulette)
Tournament
選択に関するパラメータの実験結果
(Rastrigin)



個体数が多すぎるとよくない
1島内の個体数が少ないときには
選択手法による差が少ない
1島内の個体数は10前後がよい
選択に関するパラメータの実験結果(Ridge)



個体数が多すぎるとよくない
1島内の個体数が少ないときには
選択手法による差が少ない
1島内の個体数は10前後がよい
交叉に関するパラメータの実験

交叉手法




1X (一点交叉)
2X (二点交叉)
UX (一様交叉)
One-point Crossover
交叉率

0.0,0.1,0.2,...,
0.9,1.0
Two-point Crossover
Uniform Crossover
交叉に関するパラメータの実験結果
(Rastrigin)


一点交叉と二点交叉の傾向は類似している
交叉率は高いほどよい(一点交叉,二点交叉)
交叉に関するパラメータの実験結果
(Schwefel)


一点交叉と二点交叉の傾向は類似している
交叉率は高いほどよい(一点交叉,二点交叉)
突然変異に関するパラメータの実験

突然変異手法


通常の突然変異
突然変異率
– 0.00,0.002,0.004,
0.006,0.008,0.01,
0.012,0.014,0.016,
0.018,0.02,0.03,
0.04,0.05,

単一遺伝子座突然変異

シフト突然変異
Normal Mutation
Mono-bit Mutation
Shift Mutation
突然変異に関するパラメータの実験結果
(Ridge)

単一遺伝子座突然変異,
シフト突然変異は良好で
あるが,突然変異率を
(1/染色体長)程度に
設定した通常の突然変異
に負ける
突然変異に関するパラメータの実験結果
(Schwefel)

単一遺伝子座突然変異,
シフト突然変異は良好で
あるが,突然変異率を
(1/染色体長)程度に
設定した通常の突然変異
に負ける
移住頻度に関するパラメータの実験

移住間隔


移住率


1,2,・・・,9,10
0.1, 0.2, 0.3, 0.4, 0.5
島数

1,2,4,・・・,個体数 / 2
移住頻度に関するパラメータの実験結果
(Rastrigin)



移住間隔は短い方がよい
移住率は高い方がよい
移住間隔が長くなると最適な島数は小さくなる
移住頻度に関するパラメータの実験結果
(Griewank)



ある程度の移住間隔が必要
移住率は高い方がよい
島数は多い方がよい
移住方法に関するパラメータの実験

移住機会




Random Ring
移住トポロジ




選択の後
交叉の後
突然変異の後
Random Ring
bi-Directional Ring
Ladder
bi-Directional Ring
移住個体



Random
Best
Worst
Ladder
移住方法に関するパラメータの実験結果(Ridge)



移住操作は選択の後に行うのがよい
移住トポロジはRandomRingがよい
移住個体がBestとRandomでは大差ない
移住方法に関するパラメータの実験結果
(Griewank)


移住操作は選択の後に行うのがよい
移住個体としてWorstを送るRandom Ringがよい
数値実験のまとめ

対象問題に依存しない






島数(1島内の個体数が2~10)
交叉(交叉率1.0の一点交叉か二点交叉)
突然変異(変異率1/染色体長の通常の突然変異)
移住機会(選択の後)
移住トポロジ(RandomRing)
対象問題に依存




個体数
移住間隔
移住率
移住個体
実験計画法を用いたパラメータチューニング

目的


少ない実験で各パラメータが解探索に与える影響を
把握し,パラメータチューニングを行う
( Schwefel関数)
方法
選択,移住頻度,移住方法に関するパラメータの実
験を3水準系の直交実験として扱い,分散分析を行う
 それぞれの分析から良好なパラメータ設定を得る
※直交実験
 実験計画法の手法の1つ
 少ない実験回数で,多くの因子(各パラメータやパ
ラメータ間の相互作用)について調べることが可能

分散分析結果(選択.Schwefel)
A.個体数
B.島数
C.選択手法
A×B
A×C
B×C
F. 影響の 判定
大きさ
10 有意
10 有意
1
4 有意
2
0
検討した要因:水準
個体数:128,256,512
島数:8,16,32
選択手法:
Roulette,
Rank Roulette,
Tournament
• 個体数,島数が解探索に与える影響が大きい
• 選択手法の与える影響は小さい
個体数のチューニング

島内の個体数が8,選択を Rank Roulette
→ 個体数256は良好
分散分析結果(移住頻度.Schwefel)
F. 影響の 判定
大きさ
A.移住間隔
7 有意


B.移住率
C.島数
A×B
2
3
1
A×C
B×C
5 有意
1
検討した要因:水準
移住間隔:1,5,10
移住率:0.1,0.3,0.5
島数:10,20,40
移住間隔が解探索に与える影響が大きい
移住間隔と島数には相互関係がある
移住間隔のチューニング

島内の個体数が10となる島数
→ 移住間隔 1,移住率 0.5は良好
分散分析結果(移住方法.Schwefel)
A.移住機会
B.移住トポロ
C.移住個体
A×B
A×C
B×C


F. 影響の 判定
大きさ
130 有意(1%)
86 有意(1%)
750 有意(1%)
4 有意(1%)
95 有意(1%)
12 有意(1%)
移住機会:
選択の後,交叉の後,
突然変異の後
移住トポロジ:
Random Ring,
bi-Directional Ring,
Ladder
移住個体:
Random , Best, Worst
移住個体が解探索に与える影響が大きい
パラメータ間に相互関係
移住個体のチューニング

移住は選択の後,移住トポロジはRandom Ring
→ 移住個体 Best は良好
チューニングしたパラメータの結果

チューニングによって得られたパラメータは
良好なパラメータ設定である
実験計画法を用いたパラメータチューニングのまと
め

解探索に与える影響の大きいパラメータがある




同分類に入るパラメータは相互関係がある




個体数
移住間隔
移住個体
選択(個体数,島数,選択手法)
移住頻度(移住率,移住間隔,島数)
移住方法(移住トポロジ,移住個体,移住機会)
良好なパラメータ設定を知ることが可能
結論

数値実験






島数(1島内の個体数が2~10)
交叉(交叉率1.0の一点交叉か二点交叉)
突然変異(変異率1/染色体長の通常の突然変異)
移住機会(選択の後)
移住トポロジ(RandomRing)
実験計画法によるパラメータチューニング



個体数,移住間隔,移住個体を優先すべき
パラメータ間には依存関係がある場合が多い
良好なパラメータ設定を得ることが可能
ダウンロード

PowerPoint プレゼンテーション