pdf, 3p, 163Kb - 知的システムデザイン研究室

月例発表会 Vol. 25(1999 年 12 月)
知的システムデザイン研究室
探索領域分割型遺伝的アルゴリズム
Divided Searching-Area Genetic Algorithm
赤塚浩太（知的システムデザイン研究室）
Kouta AKATSUKA (Intelligent Systems Design Laboratory)
Abstract
In this paper, new model for Island GA is proposed. This model can improve
performance if desigin variables are independent. This model examines dependency of desigin
variables.
It devides chromosome at every dependent variables, and target variables are
determined by island.
1 はじめに
遺伝的アルゴリズム (Genetic Algorithm: GA) は生
物の進化を模倣した手法であり，探索領域が連続な問題
や離散的な問題に対応できる優れた最適化手法の１つで
ある．分散ＧＡ (Distributed GA: DGA) は，単一母集
団ＧＡと比較して解の品質が向上すると報告されている
図 1: 全体の流れ
[1]．しかし，ＤＧＡでは，新たに島数と移住というパラ
メータが増加する．未知の問題を解く際，パラメータを
2.3
最適な値に設定することは難しく，パラメータは少ない
依存関係のない問題へのアプローチ
ほうが良い．そこで，本研究では島数と移住のパラメー
すべての設計変数間に依存関係のない問題では，先に
タ設定を不要にしたあらたなＧＡである探索領域分割型
も述べたように設計変数の数だけ島を用意し，各島で 1
ＧＡ (DSAGA) を提案する．
つの設計変数を解く．これにより，たとえば 10bit10 設
2
が簡単に求まると考えられる．また，各島は移住を行わ
計の rastrigin 関数は 10bit1 設計の問題となり，より解
探索領域分割型ＧＡの基本アルゴリズム
2.1
ず解き終わった後に各設計変数を集め解を求める．これ
により，移住の必要がなくなる．
概要
2.4
島数と移住のパラメータはいずれも対象問題における
依存関係のある問題へのアプローチ
設計変数間の依存関係に大きく影響していると考えられ
すべての設計変数間に依存関係のある問題では，各島
ている [2]．そこで，DSAGA では，まずはじめに対象
ですべての設計変数を対象にする．つまり，通常の DGA
問題の解析を行い，設計変数間の依存関係を調べる．そ
において，移住を行わない場合と同じである．
の結果を元に，依存関係のある設計変数を１つの塊とし
2.5
て扱い，依存関係のない設計変数同士は別の塊として扱
ローチ
う．この塊を各島で解く．このままでは，塊の数が総島
依存関係が一部の設計変数間に限られる場合，依存関
数となり，島数が一定にならないが，実際には，塊内の
係のある設計変数同士を塊とし，その塊を各島で解く．
設計変数の数だけ島を用意するため，総島数は常に設計
つまり，依存関係がある設計変数の塊内では，移住を行
変数の数となる．一連の流れを図 1 に示す．
2.2
依存関係が一部の設計変数間にある問題へのアプ
わない DGA を適用するのと同じであり，また，塊と塊
の間には依存関係が無くなるため，依存関係がない問題
設計変数間の依存関係の評価
と同じアルゴリズムを用いる．したがって，10 設計変
数の問題で，依存関係が 1-3,4-6,7-10 の設計変数にある
設計変数間の依存関係を調査するのに，統計的な手法
がうまく応用できなかったため，今回は解平面にサンプ
場合，島 1 は設計変数 1-3 を解き，島 2,3 も同様である．
ル点を取り依存関係を評価する方法で代用した．
また，島 4 は設計変数 4-6 を解く．
1
2.6
移住，島数のパラメータ
表 1: Rastrigin ＆ Schwefel
いずれの場合においても，各島は対象とする設計変数
を解くのみで，他の島の情報を必要としない．このため，
Rastrigin
DSAGA では，移住を行わない．また，島数は設計変数
世代
評価計算
世代
評価計算
DSAGA
13
7873
12
7151
DGA-Mig(0.0)
734
441000
789
474000
DGA-Mig(0.3)
347
208500
353
212520
DGA-Mig(0.6)
289
173820
334
200700
の数と決定しているため，島数のパラメータを設定する
必要もない．
3
数値実験
Schewefel
今回の手法を次の関数で実験し，通常の分散ＧＡと比
較した．
fRastrigin
=
Xf
N
10N +
Xf
( 5:12
fSchwefel
N
=
i=1
Xf
xi 5:12)
i=1
N
=
i=2
100(x2i 1
X
fGriewank
N
=
1+
i=1
( 512
(2)
x22i )2 + (x2i
xi )2 + (xi
100(x1
( 2:048
(1)
xi jg
Xf
( 5:12
fRosenbrock
pj
xi 512)
N=2
=
10 cos(2xi )
xi 5:12)
xi sin
( 512
fOriginal
i=1
表 2: Original Function
g
x2i
1)
1)
2
Yf
N
4000
i=1
xi 512)
世代
評価計算
0.00
159
95258
DGA-Mig(0.0)
0.45
898
560820
DGA-Mig(0.3)
0.08
969
582000
DGA-Mig(0.6)
0.13
911
547020
g
で定義される関数を定義し，DGA と DSAGA で解を求
(3)
めた．この関数は，設計変数 1-2，3-4，5-6 と，前また
g
xi 2:048)
x2i
2
最適解
DSAGA
は後の設計変数のみと依存関係がある関数で，DSAGA
では 2 設計変数ずつ島に分割して解を求める．表 2 に各
(4)
GA での結果を掲載する．解が求まったのは，DSAGA
xi
cos( p )g
i
のみで DGA では 1000 世代では解を求めることができ
なかった．また DSAGA では 150 世代ほどで求まって
(5)
おり，1000 世代でも解の出なかった DGA より大幅に性
能の向上を実現したと言える．
なお，DGA での島数は 10 島，移住率は 0，0.3，0.6，
3.3
移住間隔は 5 世代とした．また，関数はすべて 10bit10
設計変数であり，染色体長は 100bit となる．その他の両
Rosenbrock, Griewank
Rosenbrock や Griewank 関数では，すべての設計変数
者共通のパラメータは，総個体数 600，交叉率 1.0，突
間に依存関係が有るため，DSAGA は通常の DGA にお
然変異率 1/L を用い，試行回数は 10 回とした．
いて移住を行わない場合と同等となる．結果を表 3 に示
3.1
す．なお，すべての設定において 1000 世代では解が出な
Rastrigin,Schwefel
Rastrigin 関数及び Schwefel
かったため，1000 世代での解のみを示した．Rosenbrock
関数では，設計変数間に
関数では，DGA における移住の最適パラメータが移住
依存関係が無いため，DSAGA では各島は１つの設計変
を行わない場合のため，DSAGA は最も良い結果を得
数を対象に解探索を行う．表 1 に Rastrigin，Schwefel
ることができた．しかし，Griewank 関数では，適度に
関数での結果を示す．なお，両関数とも 1000 世代では
移住を行う方が良い結果となるため，移住を行わない
十分に最適解を発見できたので，最適解発見世代と必要
DSAGA ではあまり良い結果は得られなかった．
評価計算回数だけを示す．DSAGA では，両関数とも 15
世代ほどで解が出ており飛躍的に性能が向上している．
4
また，評価計算回数においても圧倒的に優れているとい
最初に述べたように，未知の問題にＧＡを適用するに
は，パラメータ設定が大きな問題となる．移住に関して
も同じ事が言え，ある関数で最適な移住パラメータでも
他の関数で最適かどうかは不明である．図 2 に，移住に
関するパラメータを７種類設定し，各関数を解いた場合
の性能を示した．設定した移住パラメータは，移住率が
0,0.3,0.6 の３種，移住間隔が 2,5,10 である．なお，グラ
える．
3.2
移住パラメータに関して
Original Function
今回の DSAGA では，依存関係が一部の設計変数間に
ある場合も，性能の向上が期待できる．そこで，式（ 3 ）
2
表 3: Original function
Rosenbrock
Griewank
DSAGA(DGA-Mig(0.0))
0.051
0.110
DGA-Mig(0.3)
1.025
0.091
DGA-Mig(0.6)
0.814
0.067
フ化するにあたって，以下の操作を行った．そのため，
いずれも 1.0 に近い方が性能が良い．
Rastrigin,Schwefel では解がすべてもとまったため，解発見世代を元
に，1000 世代∼0 世代を 0.0∼1.0 に変換したものを用いた．
その他の関数では，解がもとまらなかったため 1000 世代での解の値を
1.0 から引いたものを用いた．
DGA においては，Rastrigin,Schwefel
図 2: DSAGA と移住パラメータを変えた DGA
では移住間隔 2，
移住率 0.6 が最も良い結果となった．また，Original で
は移住間隔 5，移住率 0.3 が最も良い結果となり，Rosen-
ある場合はその大小にかかわらず移住を行わないため，
brock では移住無しが，Griewank では移住間隔 2，移住
Griewank など，依存関係が中程度の問題では移住を行
率 0.3 が最も良い結果となった．また，Rastrigin で最
う DSA より性能が悪化する．したがって，中程度の依
も良かったパラメータは Rosenbrock,Griewank で最も
存関係を持つ問題に対しては，移住率・移住間隔をラン
悪くなるなど，関数によって最適なパラメータが異なる
ダムにした DGA を用いる [3] 等，性能を悪化させない
ばかりではなく，他の関数では，最も悪い結果になる可
必要がある．また，最適な島数に関して，今回は設計変
能性もある．一方で，DSAGA では Griewank を除いて
数の数だけ島を用意するアルゴリズムを提案したが，個
最も良い結果となり，Griwank での結果も比較的良好で
体数が極端に多い場合や少ない場合は，性能の低下が懸
あるといえる．したがって，未知の問題を対象とする場
念される．そこで，総個体数と島数の関連を調べ，それ
合 DSAGA は，DGA より有効な手段であるといえる．
を生かすアルゴリズムを考案する必要がある．
5
7 まとめ
設計変数数，染色体長の増加に対して
これまで行ってきた実験はすべて，100bit の問題で
問題の性質が未知である場合，GA はそのパラメータ
あった．そこで，15bit20 設計変数 300bit の Rastrigin
設定の難しさが問題となっている．特に DGA では島数
関数を DSAGA と DGA で比較した．DGA では移住パ
と移住のパラメータが増えるため，その問題はより大き
ラメータとしてもっとも性能の良かった移住間隔 2，移
くなる．そこで今回提案した手法である DSAGA を用
住率 0.6 を使用した．DSAGA の結果は，平均 36 世代
いることにより，設計変数間に依存関係がない場合や一
で最適解が求まった．一方 DGA では，986 世代で最適
部の設計変数間のみに依存関係がある場合には，DGA
解が求まった．100bit の場合 DSAGA では平均 13 世代，
よりも性能を向上した上で，移住と島数のパラメータを
DGA では 279 世代であったため，必要な世代数はそれぞ
自動化することに成功した．また，依存関係がある問題
れ 2.7 倍，3.5 倍になったといえる．この結果，DSAGA
でも，最適な移住パラメータ設定の GA には及ばないも
では設計変数数や染色体長が変化しても十分 DGA より
のの，ある程度の品質の解を求めることに成功した．こ
良い性能を得られると考えられる．
れにより，未知の問題を対象にする場合や依存関係が無
いとわかっている問題を対象にする場合，今回の手法は
6
有効であるといえる．
今後の課題
現在依存関係の評価に用いているアルゴリズムは独自
参考文献
の手法であり現在の実用上問題は無いが，数学・統計学
上証明されたものでは無い．したがって，必ずしも正確
[1] 三木，畠中：”並列分散ＧＡによる計算時間の短縮と解の高品質化 ”, 第 3
回最適化シンポジウム講演論文集，pp59,1998
な依存関係の評価ができるとは言えず，今後は統計学を
[2] 畠中:"分割母集団 GA における移住間隔の最適化", 日本機械学会,1999
用いた手法で依存関係を評価する方法を実装しなければ
[3] 根上:"並列分散遺伝的アルゴリズムの移住率のランダム化 ", 同志社大学
理工学研究報告 Vol.40, pp.25-34 ,1999
ならない．また，現在のアルゴリズムでは，依存関係が
3

Download Report