分散遺伝的アルゴリズムにおけるパラメータの検討

Presentation on theme: "分散遺伝的アルゴリズムにおけるパラメータの検討"— Presentation transcript:

1 分散遺伝的アルゴリズムにおけるパラメータの検討
The examination of parameter settings for Distributed Genetic Algorithms 三木光範 同志社大学工学部 廣安知之 同志社大学大学院 上浦二郎 ○ それでは，分散遺伝的アルゴリズムにおけるパラメータの検討と題して，同志社大学の上浦から発表させて頂きます． よろしくおねがいします．

2 実験の結果を使用したパラメータチューニング 結論
発表概要 研究背景 比較するパラメータの説明 パラメータを５グループに分類した数値実験 実験の結果を使用したパラメータチューニング 結論 本発表の流れについて説明します． まず，研究背景として分散遺伝的アルゴリズムにおけるパラメータの検討の重要性について述べます． 次に，本発表で検討を行うそれぞれのパラメータについて簡単に説明を行います． これらのパラメータを5つのグループに分類し，それぞれのグループについてパラメータの傾向を知るための数値実験を行います． そして，その結果を使用して実際にパラメータチューニングを行い，良好なパラメータ設定が得られることを示します． 最後に結論を述べます．

3 研究背景：分散遺伝的アルゴリズム 分散遺伝的アルゴリズム （Tanese 1989） GAの並列化モデル
母集団を複数のサブ母集団（島）に分割 各サブ母集団（島）内で独立して遺伝的操作 移住（パラメータの増加） Population Migration では，研究背景として分散遺伝的アルゴリズムについて説明します． 分散遺伝的アルゴリズムはGAの並列化モデルの１つであり，母集団を複数の島と呼ばれるサブ母集団に分割することから島モデルとも呼ばれます． 分散GAは各島の中で独立して遺伝的操作を行いますが，各島間で探索情報を交換するために移住という操作を行います． 分散GAは単一母集団のGAと比較して良好な解を探索することができると報告されていますが，新たに移住という操作を行うために設定すべきパラメータが増加します． Distribute Subpopulations (=Islands)

4 研究背景：パラメータの検討の重要性 分散遺伝的アルゴリズムのパラメータは 数が多い（移住のパラメータの増加）
設定値が解探索効率に与える影響が大きい 最適値が単一母集団GAと異なる場合がある 各パラメータ間に相互関係がある 分散GAに特化したパラメータの検討が必要 複数のパラメータを同時に検討することが必要 さきほど述べましたように，分散GAは設定すべきパラメータが多く，その設定値は解探索効率に大きな影響を与えます． しかも，同じパラメータでも単一母集団GAとは最適な設定値が異なる場合があります． このため，分散GAに特化したパラメータの検討が必要となります． ここで，各パラメータ間には相互関係があると考えられますので，一つ一つではなく複数のパラメータを同時に検討する必要があります， 本発表では，分散GAの各遺伝的操作に注目してパラメータを分類し，同時に検討を行います． 分散遺伝的アルゴリズムの各遺伝的操作に注目してパラメータを分類して同時に検討を行う

5 個体数に関するパラメータ 母集団サイズ（個体数） 島数 探索点の総数 母集団の分割数 Population Subpopulations
次に，本発表で検討を行うパラメータについて説明します． 最初に，母集団サイズと島数について説明します． 母集団サイズ，個体数とはGAの探索点の総数のことであり， 島数とは母集団の分割数のことです． この図は個体数16，島数4の場合を示したものです． Subpopulations (=Islands) Population Size = 16 Number of Islands = 4

6 選択に関するパラメータ 選択手法 次世代の個体群の再生方法 Roulette選択（目的関数値を基に適合度を決定）
Tournament選択 Current Generation Next Generation Rank Eval Fit 1 Fit 2 1 38 32 4 2 15 9 14 8 次に選択手法について説明します． 選択手法は選択操作における次世代の個体群の再生方法です． 本発表では選択手法としてTournament選択と2つのRoulette選択を比較します． 2つのRoulette選択において異なるのは適合度の算出方法です． 一方は目的関数の関数値を基に適合度を算出し，もう一方は個体の順位を基に適合度を算出します． この図は各選択手法がどのように行われるかを示したものです． 個体群がこのような目的関数値を持つとき，目的関数値を基に適合度を決定する方法ではこのような適合度値に，個体の順位を基に適合度を決定する方法ではこのような適合度値になります．それによってこのようなルーレットが生成され，このルーレットに従った確率で次世代に再生される個体が決定します．こちらはトーナメント選択です．トーナメントサイズの個体を個体群からランダムに選び出してトーナメントの中で最も良い個体を次世代に再生します．

7 交叉に関するパラメータ 交叉手法 交叉率 交叉の方法 一点交叉 二点交叉 一様交叉 親１と親２が交叉する確率
One-point Crossover Two-point Crossover 次に交叉手法と交叉率について説明します． 交叉手法は交叉を行う方法のことです．本研究では一点交叉，二点交叉，一様交叉について検討を行います． この図はそれぞれの交叉手法を示したものです． 交叉は交叉点を境にして染色体を交換するものです． 一点交叉はこの交叉点が一つ，二点交叉は二つ，一様交叉は１以上のランダムな個数となります． 交叉率は親として選ばれた個体が交叉を行う確率です． Uniform Crossover

8 突然変異に関するパラメータ 突然変異手法 突然変異率 突然変異の方法 通常の突然変異 単一遺伝子座突然変異 シフト突然変異
各遺伝子座が突然変異する 確率（通常の突然変異） Normal Mutation Mono-bit Mutation 次に突然変異手法と突然変異率について説明します． 突然変異手法は突然変異を行う方法です． 本発表では突然変異手法として通常のビット反転による突然変異，単一遺伝子座突然変異，シフト突然変異を検討します． 突然変異率は各遺伝子座が突然変異する確率です． この図はそれぞれの突然変異手法を示したものです． 通常の突然変異は突然変異率に従って各遺伝子座が反転するかの判定を行うものです， 単一遺伝子座突然変異はランダムに選ばれた１つの遺伝子座が反転するものです． シフト突然変異はまず一つの個体について反転する遺伝子座を決定し，他の個体については反転させる遺伝子座を一つずつシフトさせるものです． Shift Mutation

9 移住に関するパラメータ（移住時期，移住頻度）
移住機会 移住をどの遺伝的操作の後に行うか 選択の後 交叉の後 突然変異の後 移住間隔 移住操作を行う世代間隔 移住率 島内の個体数に占める移住する個体の割合 次に移住時期，移住頻度に関するパラメータについて説明します． 移住時期，移住頻度に関するパラメータには移住機会，移住間隔，移住率があります． 移住機会とは移住操作をどの遺伝的操作の後に行うかです． 本発表では，選択の後，交叉の後，突然変異の後の三つについて検討を行います． 移住間隔は移住操作を行う世代間隔， 移住率は島内の個体数に占める移住する個体の割合のことです．

10 移住に関するパラメータ（移住方法） 移住トポロジ 移住個体の選択方法 移住先の選び方 Random Ring
bi-Directional Ring Ladder 移住個体の選択方法 島から移住する個体の選び方 Random を移住 Best を移住 Worst を移住 Random Ring bi-Directional Ring 次に移住方法に関するパラメータについて説明します． 移住方法に関するパラメータには移住トポロジと移住個体の選択方法があります． 移住トポロジは移住先の島の選び方であり，本発表ではRandom Ring, bi-Directional Ring, Ladder の3つについて検討を行います．この図はそれぞれの移住トポロジについて示したものです．Random Ringはランダムに一つのリングを形成します．Bi-Directional Ringは隣接する2島に移住を行います．Ladderはその名の通りハシゴ上のトポロジになっています． 移住個体の選択方法は島から移住する個体の選び方です． 本発表では，Random, Best, Worst の3種類について検討を行います． Ladder

11 数値実験 概要 分類 パラメータを各遺伝的操作に着目して分類し， 同一分類のパラメータを同時に検討する 選択・・・個体数，島数，選択手法
交叉・・・交叉手法，交叉率 突然変異・突然変異手法，突然変異率 移住頻度・移住率，移住間隔，島数 移住方法・移住トポロジ，移住個体，移住機会 ここで，パラメータの傾向を知るために数値実験を行います． 方法としては，パラメータを各遺伝的操作に着目して分類し，同一分類のパラメータのパラメータを同時に検討することにします． 分類は選択，交叉，突然変異，移住頻度，移住方法の5つです．

12 共通パラメータ 検討対象でないパラメータの設定値 個体数：４００ 島数：8 選択手法：順位から適合度値を決定するルーレット選択
交叉手法：一点交叉 交叉率：1.0 突然変異：通常の突然変異率 突然変異率：１ / 染色体長 移住トポロジ：ランダムリング 移住間隔：5 移住率：0.3 移住個体：ランダム 移住機会：選択の後 各実験において検討対象としないパラメータはこのように設定します．

13 対象問題 Rastrigin関数 Ridge関数 Schwefel関数 Griewank関数 依存関係なし，多峰性 強い依存関係あり，単峰性
中程度の依存関係， 大域的には単峰性， 局所的には多峰性 対象問題はこれらの性質の異なる4つの数学的なテスト関数を用いました． Rastrigin関数とSchwefel関数は設計変数間に依存関係のない関数であり，Ridge関数とGriewank関数は設計変数間に依存関係のある問題です． ここで各関数の2設計変数の場合の概観を示します． このようにRastrigin関数とSchwefel関数は多峰性の概観をしています． Ridge関数は単峰性の概観をしています． Griewank関数は大域的には単峰性ですが，局所的には多峰性になっています． 本研究ではそれぞれの関数について10設計変数とし，1つの設計変数を10ビットでコーディングを行いました．

14 選択に関するパラメータの実験 個体数 島数 選択手法 2，4，8，．．．，256，512，1024 1，2，4，．．．，個体数/2
Roulette（目的関数値から適合度値を求めるRoulette） Rank Roulette（順位から適合度値を求めるRoulette） Tournament 最初に選択に関するパラメータの実験を行います． 検討するパラメータはこのようになっています． ここ以降，目的関数値から適合度値を求めるRoulette選択を単にRoulette選択，順位から適合度値を求めるRoulette選択をRank Roulette選択と呼ぶことにします．

15 選択に関するパラメータの実験結果（Rastrigin）
実験結果を示します．これ以降，数値実験の結果はそれぞれ2つずつの関数について示していきます． 横軸は上側が個体数，下側は島数を示しています．例えばこの部分は128個体で，左から1島，2島，4島．．．となります．緑の線はRoulette選択，赤の線はRank Roulette選択，青の線はTournament選択を示しています．縦軸は最適解発見までにかかった評価回数の20試行の平均値を示しており，グラフの下にいくほど早く解が求められているといえます． この結果より，個体数が多すぎるとよくない，1島内の個体数が少ないときには選択手法による差が少ない．1島内の個体数は10前後がよい，ことがわかります． 個体数が多すぎるとよくない １島内の個体数が少ないときには 選択手法による差が少ない １島内の個体数は10前後がよい

16 選択に関するパラメータの実験結果（Ridge）
個体数が多すぎるとよくない １島内の個体数が少ないときには 選択手法による差が少ない １島内の個体数は10前後がよい

17 交叉に関するパラメータの実験 交叉手法 交叉率 1X （一点交叉） 2X （二点交叉） UX （一様交叉）
0.0，0.1，0.2，．．．， 0.9，1.0 One-point Crossover Two-point Crossover Uniform Crossover

18 交叉に関するパラメータの実験結果（Rastrigin）
一点交叉と二点交叉の傾向は類似している 交叉率は高いほどよい（一点交叉，二点交叉）

19 交叉に関するパラメータの実験結果（Schwefel）
一点交叉と二点交叉の傾向は類似している 交叉率は高いほどよい（一点交叉，二点交叉）

20 突然変異に関するパラメータの実験 突然変異手法 通常の突然変異 突然変異率
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

21 突然変異に関するパラメータの実験結果（Ridge）
単一遺伝子座突然変異，シフト突然変異は良好であるが，突然変異率を （1/染色体長）程度に 設定した通常の突然変異に負ける

22 突然変異に関するパラメータの実験結果（Schwefel）
単一遺伝子座突然変異，シフト突然変異は良好であるが，突然変異率を （1/染色体長）程度に 設定した通常の突然変異に負ける

23 移住頻度に関するパラメータの実験 移住間隔 移住率 島数 １，２，・・・，９，１０ 0.1， 0.２， 0.３， 0.４， 0.５
１，２，４，・・・，個体数 / 2

24 移住頻度に関するパラメータの実験結果（Rastrigin）
移住間隔は短い方がよい 移住率は高い方がよい 移住間隔が長くなると最適な島数は小さくなる

25 移住頻度に関するパラメータの実験結果（Griewank）
ある程度の移住間隔が必要 移住率は高い方がよい 島数は多い方がよい

26 移住方法に関するパラメータの実験 移住機会 移住トポロジ 移住個体 選択の後 交叉の後 突然変異の後 Random Ring
bi-Directional Ring Ladder 移住個体 Random Best Worst Random Ring bi-Directional Ring Ladder

27 移住方法に関するパラメータの実験結果（Ridge）
移住操作は選択の後に行うのがよい 移住トポロジはRandomRingがよい 移住個体がBestとRandomでは大差ない

28 移住方法に関するパラメータの実験結果（Griewank）
移住操作は選択の後に行うのがよい 移住個体としてWorstを送るRandom Ringがよい

29 数値実験のまとめ 対象問題に依存しない 対象問題に依存 島数（１島内の個体数が2～10） 交叉（交叉率1.0の一点交叉か二点交叉）
突然変異（変異率1/染色体長の通常の突然変異） 移住機会（選択の後） 移住トポロジ（RandomRing） 対象問題に依存 個体数 移住間隔 移住率 移住個体 これらの数値実験によって分かったことをここでまとめます． まず，対象問題に依存せずに決定することが可能なパラメータがあることが分かりました． つまり，島数は1島内の個体数が10以下がよい． 交叉には交叉率1.0の一点交叉か二点交叉を用いるとよい． 突然変異には突然変異率1/Lの通常のビット反転の突然変異がよい． 移住操作は選択の後に行うとよい． 移住トポロジはRandom Ringがよい． ということが分かりました． 対して，個体数，移住間隔，移住率，移住個体の4つのパラメータは対象問題によって最適値が変化することが分かりました．

30 実験計画法を用いたパラメータチューニング
目的 少ない実験で各パラメータが解探索に与える影響を 把握し，パラメータチューニングを行う （ Schwefel関数） 方法 選択，移住頻度，移住方法に関するパラメータの実験を3水準系の直交実験として扱い，分散分析を行う それぞれの分析から良好なパラメータ設定を得る ※直交実験 実験計画法の手法の１つ 少ない実験回数で，多くの因子（各パラメータやパラメータ間の相互作用）について調べることが可能 ここまでの実験で，パラメータの傾向が分かりました． ここではSchwefel関数を対象問題として実際に実験計画法を用いてパラメータのチューニングを行います． 方法としては，対象問題に依存するパラメータが含まれている選択，移住頻度，移住方法の分類に関して3水準の直交実験として扱い，分散分析を行います． この分析結果を使用して，良好なパラメータ設定を得ることを期待します． ここで，直交実験とは実験計画法の手法の一つであり，少ない実験回数で多くの因子について調べることが可能であるような実験方法です．ここでは各因子はパラメータやパラメータ間の相互作用となります．

31 分散分析結果（選択.Schwefel） F. 影響の大きさ 判定 検討した要因：水準 個体数：128,256,512 島数：8,16,32
選択手法： Roulette, Rank Roulette, Tournament A.個体数 10 有意(1%) B.島数 C.選択手法 1 A×B 4 A×C 2 B×C 選択に関するパラメータについて分散分析を行った結果を示します． この列が調べたい因子を示しています．A×BはAとBの相互関係を示しています． 分散分析を行うことによって，各因子が有意な影響を与えるかの判定を行うことができます． この実験では個体数，島数について有意に影響があることが分かりました． 個体数，島数が解探索に与える影響が大きい 選択手法の与える影響は小さい

32 島内の個体数が8，選択を Rank Roulette → 個体数256は良好
個体数のチューニング 先ほどまでの数値実験によって島内の個体数は10程度がよいことが分かっています．また，島内の個体数が10程度であるときには選択手法の影響が少ないことも分かっています．そのため，島内の個体数が8，選択手法をRank Rouletteとして個体数のチューニングを行うことができます．実験の結果，個体数は256が良好であることが分かります． 島内の個体数が8，選択を Rank Roulette →　個体数256は良好

33 分散分析結果（移住頻度.Schwefel）
判定 検討した要因：水準 移住間隔：1,5,1０ 移住率：0.1,0.3,0.5 島数：10,20,40 A.移住間隔 7 有意(1%) B.移住率 2 C.島数 3 A×B 1 A×C 5 B×C 次に移住頻度について分散分析を行います．その結果より，移住間隔が有意に影響を与えること，そして移住間隔と島数が有意に相互関係があることが分かりました． 移住間隔が解探索に与える影響が大きい 移住間隔と島数には相互関係がある

34 島内の個体数が10となる島数 → 移住間隔 １，移住率 0.5は良好
移住間隔のチューニング 対象問題によって最適なパラメータ設定の異なるパラメータである移住間隔と移住率についてチューニングを行います． さきほど移住率の影響は有意であると判定されませんでしたので，移住間隔を優先してチューニングを行います． 実験の結果，移住間隔1，移住率0.5が良好なパラメータであることが分かりました． 島内の個体数が10となる島数 →　移住間隔 １，移住率 0.5は良好

35 分散分析結果（移住方法.Schwefel）
判定 移住機会： 選択の後,交叉の後, 突然変異の後 移住トポロジ： Random Ring, bi-Directional Ring, Ladder 移住個体： Random , Best, Worst A.移住機会 130 有意(1%) B.移住トポロジ 86 C.移住個体 750 A×B 4 A×C 95 B×C 12 同様に移住方法について分散分析を行った結果，すべてのパラメータ，そして移住機会と移住トポロジを除くパラメータの組み合わせが有意であることが分かりました．特に移住個体が大きな影響を与えるようです． 移住個体が解探索に与える影響が大きい パラメータ間に相互関係

36 移住は選択の後，移住トポロジはRandom Ring → 移住個体 Best は良好
移住個体のチューニング 移住機会，移住トポロジに関しては先ほどの実験より選択の後，Random Ring と定めることができるので，ここでは検討対象を移住個体のみとすることができます．実験の結果，移住個体はBestを選択するのが良好であることが分かりました． 移住は選択の後，移住トポロジはRandom Ring →　移住個体 Best は良好

37 チューニングによって得られたパラメータは 良好なパラメータ設定である
チューニングしたパラメータの結果 ここまでのチューニングによって得られたパラメータ設定で実験を行った結果をさきほどの交叉に関する実験結果のグラフに重ると，この太い緑の線になりました． 交叉の実験でもっとも早く解が発見されていた試行と比較しても半分程度で解を発見することができています． これは，この方法によって最適なパラメータ設定である保証はないけれどもある程度良好なパラメータ設定を得ることができたことを示しています． チューニングによって得られたパラメータは 良好なパラメータ設定である

38 実験計画法を用いたパラメータチューニングのまとめ
解探索に与える影響の大きいパラメータがある 個体数 移住間隔 移住個体 同分類に入るパラメータは相互関係がある 選択（個体数，島数，選択手法） 移住頻度（移住率，移住間隔，島数） 移住方法（移住トポロジ，移住個体，移住機会） 良好なパラメータ設定を知ることが可能 実験計画法を用いたパラメータチューニングをまとめると，以下のことがいえます． まず，個体数，移住間隔，移住個体のパラメータが解探索に与える影響の大きいパラメータであることが分かりました． また，選択，移住頻度，移住方法の各分類に属するパラメータは相互関係があることがわかりました． このことはこれらの分類で実験を行ったことが適切であったことを示していると考えられます． また，この実験によってある程度良好なパラメータ設定を知ることが可能であることがわかりました．

39 結論 数値実験 実験計画法によるパラメータチューニング 島数（１島内の個体数が2～10） 交叉（交叉率1.0の一点交叉か二点交叉）
突然変異（変異率1/染色体長の通常の突然変異） 移住機会（選択の後） 移住トポロジ（RandomRing） 実験計画法によるパラメータチューニング 個体数，移住間隔，移住個体を優先すべき パラメータ間には依存関係がある場合が多い 良好なパラメータ設定を得ることが可能 最後に本発表の結論を述べます． 数値実験によって，島数，交叉率，交叉手法，突然変異，移住機会，移住トポロジについては対象問題によらずに最適なパラメータ設定が存在することがわかりました． また，実験計画法によるパラメータチューニングによって個体数，移住間隔，移住個体を優先してチューニングすべきであること，パラメータ間には依存関係がある場合が多いこと，良好なパラメータ設定を得ることが可能であることがわかりました． これによって，パラメータ設定の煩雑性を軽減することができたと考えられます． 以上です． ありがとうございました．