数理解析研究所講究録
第 1864 巻 2013 年 20-30

20

巣形成と役割分担を用いた最適化手法に関する一考察
阪井

広島修道大学商学部

節子 (Setsuko Sakai)

Faculty of Commercial Sciences, Hiroshima Shudo University
広島市立大学大学院情報科学研究科 高濱 徹行 (Tetsuyuki Takahama)
Graduate School of Information Sciences, Hiroshima City University

1

はじめに

進化的アルゴリズム (Evolutionary Algorithm, $EA$ ) は，生物進化の過程をモデル化した最適化アルゴリ
ズムの総称であり，遺伝的アルゴリズム (Genetic Algorithm, $GA$ ), 進化戦略 (Evolution Strategy, $ES$ ), 差$EA$
分進化 (Differential Evolution, $DE$ )[1, 2] など多くのアルゴリズムが提案されている．
は，最適化の対象である目的関数の値だけを利用して解を求めることができる直接探索法であり，アルゴリズムの実装が容易であることから，様々な最適化問題を解くために利用されている．
$EA$ は確率的な多点探索を行うため，比較的局所解に陥りにくいが，関数評価回数が多くなりがしかし，ちである．近年，最適化問題が大規模化し，目的関数の評価コストが増大してきているため，目的関数の評
価回数の削減は大きな課題となってきている．

本研究では，蟻の巣形成と役割分担に着目した最適化アルゴリズムを提案する．探索点から近接グラフを構成し目的関数の概形を把握する [3,4,5]. 谷点およびその近傍の探索点が存在する領域は有望な探索領域である考えられるため，この領域を巣と見なす．谷点を女王蟻，谷近傍点を雄蟻とし，これらの蟻の近傍に新しい蟻，すなわち新しい探索点を生成する．それ以外の蟻は，採餌行動を行っている働き蟻とし，通常の探索により良い餌場を探して移動する．ただし，山点に到達した蟻は餌場の探索に失敗したと考え，帰巣本$EA$ を効率化し，広い範囲の問題に対して，能により巣に帰る行動をとる．このようなアイデアに基づき，少ない関数評価回数で精度の高い解の探索を実現することが本研究の目的である．

2

最適化問題
本研究では，決定変数の上下限制約のみを有する次のような最適化問題 (P) を扱う．
$(P)$

(1)

minimize $f(x)$subject to$l_{i}\leq x_{i}\leq u_{i},$

ここで，

は $n$

$x=(x_{1}, \cdots, x_{n})$の実数値関数である．

$l_{i},$$u_{i}$$i=1,$$\ldots,$$n$次元決定変数ベクトル，$f(x)$ は目的関数であり， は線形あるいは非線形$f$はそれぞれ， 個の決定変数$n$$x_{i}$の下限値，上限値である．さらに，以下では全ての上下限制約を満足する領域を探索空間 $(S)$ と呼ぶことにする．

3

近接グラフ

3.1

定義

頂点集合 $V$ と辺集合 $E$ からなるグラフ $G$ を $G(V, E)$ で表現する．近接グラフ (proximity graph) は，頂点集合 $V$ の近傍構造を表現するグラフであり，最近傍グラフ (Nearest Neighborhood Graph), Gabriel グ
ラフ (Gabriel Graph, GG)[6],相対近傍グラフ (Relative Neighborhood Graph, RNG) $[7],$競合ヘブ則によるグラフ [9] などが提案されている．近接グラフでは，任意の 2 頂点
$vj$ ) $\in E$ となる．
を満足するときのみ辺価，Gabriel グラフでは， と$v_{i}$$v_{j}$$v_{i},$$\beta$skeleton[8],$vj\in V$ が近傍条件を結ぶ線分を直径とする超球内に他の頂点が含まれていなければ， と$v_{i}$$v_{j}$が近傍条件を満足する．Gabriel グラフ $GG(V, E)$ は，以下のように定義できる．
$(v_{i}, v_{j}) \in E\Leftrightarrow HS(\frac{v_{i}+v_{j}}{2}, \frac{||v_{i}-v_{j}||}{2})nV=\phi$

(2)

21
$HS(v, r)$ は頂点
ここで，

$v$

を中心とする半径$r$の超球内の領域，すなわち(3)$HS(v, r)=\{x|||x-v||<r\}$である．

この様子を図 1 に示す．任意の頂点$v_{k}$

が超球内に存在しない場合にのみ頂点を接続し，そうでない場合

は接続しない．

::$::\ldots\ldots\cdots=:..\ldots\ldots.:$$=.. \cdots$$=.$$\bullet \mathcal{V}_{k}\cdots\cdots$.... ...

$.$$.$$v_{i}$.. ..

$\bullet$$\bullet_{:}$.

$v_{j}$.:の$:\cdot:^{:^{=}}.:^{=}$$:::::$..

..

$i:::$

図 2: 相対近傍グラフにおける辺の判定

相対近傍グラフでは，頂点$v_{i}$および吻を中心とする半径 $||v_{i}-vj||$ の 2 つの超球の共通集合内に他の頂点が含まれていなければ近傍条件を満足する．相対近傍グラフは Gabriel グラフの部分グラフである．相対近傍グラフ $RNG(V, E)$ は以下のように定義できる．
$(v_{i}, v_{j})\in E\Leftrightarrow HS(v_{i}, ||v_{i}-v_{j}||)\cap HS(v_{j}, ||v_{i}-v_{j}||)\cap V=\phi$(4)

この様子を図 2 に示す．

3.2

近接グラフのアルゴリズム

近接グラフを決定するアルゴリズムは以下のようになる．

1. 全ての頂点対について，vi, 吻間の距離 $d(v_{i}, vj),$ $j=1,2,$$i,$$\cdots,$ $n$を求める．

2. 全ての頂点対 $v_{ij}v$ について，(a) ある頂点 $v_{k}(k\neq i, k\neq j)$ に対して，$d(v_{i}, v_{k})^{2}+d(v, v)^{2}<d(v_{i}, v_{j})^{2}$
Gabriel グラフの場合は，$v_{ij}v$ は近傍関係にない．
ならば，$d(v_{i}, v_{k})<d(v_{i}, vj)$ かつ $d(v, v)<d(v_{i}, vj)$ ならば，vi,
相対近傍グラフの場合は，
吻は近傍関

係にない．

(b) 上記を満たす妬が存在しなければ，辺 $(v_{i,j}v)$ を生成する．
$O(|V|^{3})$ である．
なお，アルゴリズムの計算量は，

4巣形成と役割分担に基づく最適化アルゴリズム
本研究では，Differential Evolution ( $DE$ ) に巣形成と役割分担の考えを導入した最適化アルゴリズムである NRDE(Differential Evolution with Nest-building and Role-sharing) を提案する．

22
Differential Evolution

4.1

Differential evolution ( $DE$ ) は，Storn and Price[1, 2] によって提案された進化的アルゴリズム (Evolu$DE$ は解集団を用いた多点探索を行う確率的直接探索法であり，非線形
tionary Algorithm) の 1 つである．
問題，微分不可能な問題，非凸問題，多峰性問題など，様々な最適化問題に適用されてきており，高速で頑健なアルゴリズムであることが示されている．
$DE$ では，探索空間中にランダムに初期個体を生成し，初期集団を構成する．各個体は決定ベクトルに対応
し， 個の決定変数を遺伝子として持つ．各世代において，全ての個体を親として選択する．各親に対して，
次のような処理が行われる．突然変異のために，選択された親を除く個体群から互いに異なる 1 2 $num$
個の個体を選択する．最初の個体が基本ベクトル (base vector) となり，残りの個体対が $num$ 個の差分ベクトル (difference vector) となる．差分ベクトルはスケーリングファクタ $F$ (scaling factor) が乗算され基
本ベクトルに加算され，変異ベクトル (mutant vector) が得られる．変異ベクトルと親が交叉し，交叉率
$n$

$+$

$CR$

(crossover rate) により指定された確率で親の遺伝子をベクトルの要素で置換することにより，子のベク

トル (trial vector) が生成される．最後に，生存者選択として，子が親よりも良ければ，親を子で置換する．

$DE/best/1/bin$ や $DE/rand/1/\exp$ などがよく知られていには幾つかの形式が提案されており，$DE/base/num/cross$ という記法で表現される．“base” は基本ベクトルとなる親の選択
る．これらは，$DE$ /rand/num/cros
は基本ベクトルのための親を集団からランダムに選択し，方法を指定する．例えば，$DE$ /best $/num/$$oss$ は集団の最良個体を選択する．$num$ は基本ベクトルを変異させるための差分ベクトル$DE$ /base/num/binの個数を指定する．“cross” は子を生成するために使用する交叉方法を指定する．例えば，$DE$ /base/num/exp は，指数関数的には一定の確率で遺伝子を交換する交叉 (binomial crossover) を用い，
$DE$

$s$

”

減少する確率で遺伝子を交換する交叉 (exponential crossover) を用いる．

本研究では，差分ベクトル数を 1 $(num=1)$ とした $DE/rand/1/\exp$ を用いる．以下に $DE/rand/1/\exp$の擬似コードを示す．

$DE/rand/1/\exp^{()}\{$//

Initialize a populationindividuals generated randomly in $S$ ;

;

$P=N$

for $(t=1;FE\leq FE_{\max};t++)$ {for $(i=1;i\leq N;i++)$ {// $DE$ operation$x^{p1}=$
Randomly selected from $P(p1\neq i)$ ;$x^{p2}=$
Randomly selected from $P(p2\not\in\{i,p1\})$ ;$x^{p3}=$
Randomly selected from $P$$(p3\not\in\{i,p1,p2\})$

4.2$\ovalbox{\tt\small REJECT}_{\}}\}^{P\{z^{i},i=1,2,\cdot N\};}e1sez^{i}=x^{i};/Su_{if(f(x^{chi1d})\leq f(x^{i}))z^{i}=x^{chi1d};}rvivorse1ection\}_{=}^{FE=FE+1;}x^{chi1d}=tria1.vectorisgeneratedfromx’=x^{p1}+F(x^{p2}.-,x^{p3});x^{i}andx’by\exp\circ nentia1cross\circ ver$;

山谷構造の推定と山谷判定

に対して山度 xi. ん沼と谷度 .valley を付与する．近傍
本研究では，山と谷を判定するために，各点グラフの全ての辺について，その辺を構成する 2 点のうち，評価値の良い点の谷度を 1 増加させ，評価値の悪い点の山度を 1 増加させる．
$x_{i}$$x_{i}$

本研究では，各点の谷度と山度を用いて，3 種類の点，谷点，山点，谷近傍点を定義し，各点$x_{i}$の山谷判定を行う．

谷点近傍により悪い点が一つ以上存在し，より良い点が存在しない点である．すなわち，谷点はかつ.hill $=0$ の点である．

$x_{i}$.valley $>0$

$x_{i}$

山点近傍により良い点が一つ以上存在し，より悪い点が存在しない点である．すなわち， .hill $>0$ かつ.valley $=0$ の点である．
$x_{i}$$x_{i}$

谷近傍点谷点に隣接する点，すなわち 1 つの辺を共有する点でかつ，山点でない点である．

23
4.3

アルゴリズム以下にアルゴリズムの概要を示す．

1. 初期化
探索領域内に点をランダムに生成し，初期探索点集合を構成する．

2. 近傍グラフの構成
点間の距離を求める．近傍関係を求め，近傍グラフを構成する．
3. 山谷判定
各点に山度と谷度を付与し，山谷判定を行う．
4. 探索点の生成
女王蟻 (谷点) および雄蟻 (谷近傍点) は局所探索を行うため，局所的な $DE$ 操作を行う．谷点を中心とする探索を行うために，スケーリングファクタ に小さな値，交叉率 $CR$ に大きな値を設定する．
山点では，標準的な探索をあきらめ，最良の谷点へ向かって移動する．すなわち帰巣行動 (中域探索)$F$$CR$ は [0,1] の乱数で値を設定する．それ以外の点については，を行う．このために， に大きな値，$F$

標準的な探索を続行，すなわち通常のパラメータ値 $F$ と $CR$ による $DE$ 操作を行う．
5. 生存者選択
元の点が生成された探索点より良好でなければ，探索点と置換する．2. に戻る．

4.4

探索点の生成本研究では，山谷判定による各親ベクトル$x_{i}$の属性に応じて，以下のように基本ベクトルの選択戦略およびスケーリングファクター $F$ と交叉率 $CR$ の制御ルールを採用することにより，近傍探索，中域探索と大域探索を実現する．
谷点の場合
谷点

$x_{i}$の周辺で局所探索を行うため，基本ベクトルを谷点$x_{i}$$F=0.3,$ $CR=1.0$ とする．とし，谷近傍点の場合

谷点の場合と同様に，谷点の周辺で局所探索を行うため，基本ベクトルを近傍の谷点と$F=0.4,$
し，$CR=1- \frac{1}{n}$$x_{i}$

の中点と

とする．

山点の場合

山点である蟻は，標準的な探索をあきらめ帰巣行動をとる．そのため，基本ベクトルを集団内の最良$CR$ は区間 [0,1] 上の一様乱数とする．

解 (最良の谷点) とし，$F=0.9,$

それ以外の場合

標準的探索を続行する．そのため，基本ベクトルは$x_{i}$

を除く集団からランダムに選択し， と $CR$

は通常の $DE$ で標準的に用いられる (0.7,0.9) とする．

4.5

擬似コード

以下に $DE/rand/1/\exp$ の擬似コードを参考に，NRDE の擬似コードを示す．

$F$

24
NGDE

switch ($()$$x_{i}$の種類){

case 谷点 :$\{$Generate $N$ individuals$N$ ;$i=1,2,$
Evaluate$P=$$x_{i},$

break;
case 谷近傍点 :$\cdots,${

for $(t=1;t<T_{\max};t++)$// 距離などの初期化
for $(i=1;i\leq N;i++)$. num . valley$p_{1}=i_{valley};F’=0.4;CR’=1-1/n$ ;{. hill$=x_{i}$$=x_{i}$$x_{i}$$p_{1}=i;F’=0.3;CR’=1$ ;randomly;$\{x_{i}\}$CurrentToQueen$=1$ ;$=0$break;
case 山点 :;for $(j=i+1;j\leq N;j++)$$d_{ij}=d_{ji}=x_{i}$;$F’=0.9;CR’=[O, 1]$ の乱数 ;と $Xj$ 間の距離 $d(X_{i}, Xj)$ ;$p_{1}=best$

$\}$

//

break;

近傍グラフの構成
for $(i=1;i\leq N;i++)$ {for $(j=i+1;j\leq N;j++)$default:
select randomly in 1,$F’=F;CR’=CR$ ;{for $(k=i;k\leq N;k++)$ {$p_{1}=$

if $(k!=i$ && $k!=j$ &&

$)$

&&

$N]\backslash \{i\}$//$d_{jk}<d_{ij}//$

RNG

探索点の生成$p_{2}=$

break;$p_{3}=$

select randomly in 1,
select randomly in 1,$x_{i}^{new}=x_{i}\in P$$\}$

if $(k>N)\{$// 山谷判定: 辺 $(x_{i}, Xj)$ の生成

$j=$

$[$

$N]\backslash \{i, p_{1}\}$$[$$N]\backslash \{i, p_{1},p_{2}\}$;

select randomly from 1, $n]$ ;$[$$k=1,\cdot$

do {if $(f(x_{i})<f(x_{j}))\{,$$x_{i}.valley++;Xj\cdot hil1++$ ;$x_{ij}^{new}=x_{p_{1},j}+F’(x_{p_{2},j}-x_{p_{3},j})$;if (CurrentToQueen)$\}$else if $(f(x_{i})>f(Xj))${$x_{ij}^{new}+=0.5(x_{i,j}-x_{p_{1},j})$j (j$Xj\cdot valley++ix_{i}.hill++$ ;

$=$

$k++$

$\}$

$\}$

$\}$

$+$

;

l)%n;

;

while $(k\leq n \ \ u(O, 1)<CR’)$ ;// 生存者選択$\}$

if $(f(x^{new})\leq f(x_{i}))x_{i}=x^{new}$ ;$\}$全ての個体について山谷判定を行う;

for $(i=1;i\leq N;i++)$CurrentToQueen$=0$ ;ただし， .hill,$x_{i}$$x_{i}$$\}${.valley はそれぞれ点

$\}$

$\}$

$x_{i}$

より良い近傍頂点数，悪い近傍頂点数であり，$x_{i_{。}}$

。lley

は

$x_{i}$の隣接谷点，Xbest は集団内の最良点である．

5

実験

5.1

テスト問題

;

$\}$

$d_{ik}^{2}+d_{jk}^{2}<d_{ij}^{2}//GG$$d_{ik}<d_{ij}$$[$

本実験では，変数間依存性，悪スケール性，および大谷構造を有する問題を用いる [10]. 変数間依存性の強い問題として，稜構造を有する問題を用いる．悪スケール性のある問題として，稜構造でかつ変数によりスケールが異なる問題を用いる．大谷構造とは，微視的に見れば局所解となる多数の小さな谷が存在する
が，巨視的に見れば大きな谷が一つだけ存在し，その谷が最適解となっている構造であり，Rastrigin 関数
がその典型例である．

以下に，関数とその初期化領域を示す．なお， は次元数を表している．
$n$

25

.

$fi$

:Sphere 関数$f(x)= \sum_{i=1}^{n}x_{i}^{2}, -5.12\leq x_{i}\leq 5.12$.

単峰性の関数で，点 $(0,0, \cdots, 0)$ で最小値
$f_{2}$$O$をとる．

:Rosenbrock 関数$f(x)= \sum_{i=2}^{n}\{100(x_{1}-x_{i}^{2})^{2}+(x_{i}-1)^{2}\}, -2.048\leq x_{i}\leq 2.048$.

単峰性の稜構造を有する関数で，点 $(1,1, \cdots, 1)$ で最小値
$f_{3}$$O$: ill-scaled Rosenbrock 関数

単峰性の稜構造を有する関数で，点$f_{4}$(6)をとる．

$f(x)= \sum_{i=2}^{n}\{100(x_{1}-(ix_{i})^{2})^{2}+(ix_{i}-1)^{2}\}, -2.048/i\leq x_{i}\leq 2.048/i$.

(5)$(1, \frac{1}{2}, \cdots , \frac{1}{n})$

で最小値

$0$

(7)

をとる．

:Rastrigin 関数$f(x)=10n+ \sum_{i=1}^{n}\{x_{i}^{2}-10\cos(2\pi x_{i})\}, -5.12\leq x_{i}\leq 5.12$(8)

多峰性の大谷構造を有する関数で，点 $(0,0, \cdots, 0)$ で最小値 0 をとる．
図 5 に $n=2$ のときの関数 $fi,$$f_{2},$$f_{4}$のグラフを示す．また，表 1 に各関数の特徴を示した [10].

図 5: 関数$f_{1},f_{2},f_{4}$のグラフ

表 1: テスト問題の特徴

関数変数間依存性 悪ケ$fi$$f_{2}$$f_{3}$$f_{4}$

5.2

ール性 大谷構造

なし

なし

なし

強い

なし

なし

強い
なし

あり

なし

なし

あり

実験条件

の関数を最適化する．rand 戦略を用いる標準の $DE$ , 近接グラフとして相対近傍グラフ (RNG) あるいは Gabriel グラフ (GG) を利用した NRDE の 3 つのアルゴリズムの性
次元数 $n=30$ に設定し，$fi$ から$f_{4}$

26$DE$ の設定は，個体数 $N=50,$
能を比較する．

試行を行い，結果を考察する．個体数は

$2n$

$F$

と $CR$ の組合せを (0.7, 0.9) とし，各関数について 30 回のから $10n$ 程度が良いとされているが，効率性を重視し少し小さい値とした．なお，試行打ち切り条件は，文献 [10] と同様に，(1) 評価値が探索打ち切り評価回数が $fi$ およびの条件を満足する場合とした．

5.3$f_{2}$

は $2n\cross 10^{5},$$f_{3}$

は $5n\cross 10^{5},$$f_{4}$$1.0\cross 10^{-7}$以下に達した，(2)は $3n\cross 10^{5}$ に達した，のいずれか

実験結果

実験結果を表 2 に示す．許容精度を満足した回数を差を eval,$<1e-7$ ”, 実際に関数を評価した回数とその標準偏そのうち子ベクトルが良かった回数を succ, 悪かった回数を fail, 成功率を rate に示した．
表 2: 実験結果については，NRDE(GG) が最も効率よく近似解を探索できており，次に NRDE(RNG) の効率が優については，NRDE(RNG) が最も効率よく近似解を探索できている．次に NRDE(GG)
れている．
$fi$

$f_{2},$ $f_{3}$の効率が良いが， では 28 回の試行， では 20 試行で近似解の発見に失敗しているため，実質的には$DE$ (rand) の方が NRDE(GG) より効率が優れていると考えられる． については，NRDE(RNG) が最も効率よく近似解を探索できており，次に $DE$ (rand) の効率が優れている．NRDE(GG) では 7 試行で近似解$f_{3}$$f_{2}$$f_{4}$の発見に失敗している．以上のことから，安定的な探索の観点からは，NRDE(RNG) がもつとも優れており，次に $DE$ (rand) となる．NRDE(GG) は問題に依存した不安定さがある．また，近似解の発見までに要について$fi$ については約 44%,
する関数評価回数について NRDE(RNG) と $DE$ (rand) を比較すると，については約 18% の削減に成功している．以上のことから，探索効率については約 85%,は約 82%,の点からも NRDE(RNG) が最も優れている．
各問題における最良個体の関数値について，その平均値の変化を図 6 から図 9 に示す．横軸は世代数，縦$f_{2}$$f_{4}$$f_{3}$

軸が関数値である．

については，NRDE(GG) が最も効率的に探索を行っており，NRDE(RNG) がほぼ同程度の効率である．
$DE$ (rand) は探索がについては，NRDE(RNG) が非常に効率的に探索し，(rand) はかなり遅い．

$fi$

$DE$

$f_{2},$$f_{3}$

遅く，NRDE(GG) は最大評価回数までに満足できる解を探索できなかった． についても，NRDE(RNG)$DE$ (rand) がやや劣った効率である．NRDE(GG) は満足できる解を発が最も効率的に探索を行っており，$f_{4}$

見できない場合があった．

27

$0$

500

1000
$G$

図 6:

$f_{i}$

1500
eneration

2000

2500

3000

$0$

500

$s$

図 7:

における関数値の変化$f_{2}$

1000

1500
2000
Generat ons

2500

30

における関数値の変化$0 500 1000 1500 2000 2500 3000 0 500 1000 1500 2000 2500 300$
Generations

図 8:$f_{3}$

Generations

図 9:における関数値の変化$f_{4}$

における関数値の変化

谷 (valley), 谷近傍 (near valley), 山 (hill) の点の数の変化 (左軸参照) と最良値 (best, 右軸参照) の変化について，NRDE(RNG) の場合を図 10 から図 13 に，NRDE(GG) の場合を図 14 から図 17 に示す．
$fi$ については，谷点は定常的に約 2 個であり，谷近傍点は定常的に 7 個から 8NRDE(RNG) において，個程度の間で増減を繰り返している．山点は定常的に 30 個程度である．すなわち，巣の近傍での近傍探索
は 10 個体程度，巣への帰巣行動は 30 個体程度，通常の $DE$ による大域探索を 10 個体程度が定常的に行っていると考えられる． については，初期は谷点が 3$f_{2}$$\sim$

5 個体まで減少し，その後増加し，中盤以降は定常

的に 10 個体程度となっている。 谷近傍点も 5 8 個体程度まで減少し，その後は谷点と同様の変化を見せている．山点は初期に 30 個体程度まで増加し，その後減少し，再度やや増加し，中盤以降は定常的に 25 個体$\sim$

程度となっている．最良値の変化とあわせると，探索の中盤までは，谷点として局所解である $(0,0, \cdots, 0)$
しか発見できておらず，その後最適解である $(1,1, \cdots, 1)$ も発見して，その結果谷点及び谷近傍点が増加したと考えられる．最良値の最適値への収束もこの変化に同期していることが分かる．

については，初期は谷点が 6 9 個体，谷近傍が 9 11 個程度で，その後増加し，中盤以降は定常的にそれぞれ 14 個，11 個体程度となっている。 山点は初期に $18$ $20$ 個であるが，その後定常的に 20 個体程度$\sim$$f_{3}$$\sim$〜となっている．最良値の変化とあわせると， と同様に，一度 $(0,0, \cdots, 0)$ 付近に収束し，そこから狭小な$f_{2}$

谷を通って$(1, \frac{1}{2}, \cdots, \frac{1}{n})$に向かって移動するという探索方法がとられていると考えられる． については，$f_{4}$

序盤は谷点が 4 から 14 個，谷近傍点が 8 から 18 個へ増加し，山点は 24 から 10 個へ減少している．中盤
は定常的に谷点が 13 個程度，谷近傍点が 19 個程度，山点 8 個程度である．終盤には谷点は 3 個程度，谷近傍点は 7 個程度まで減少し，谷点は 30 個程度まで増加増加している．最良値の変化とあわせると， は$f_{4}$

28

Generat ons

Generatlons

図 11:

図 10: $fi$ における山谷判定 (NRDE/RNG)$f_{2}$

Generat ons
図 12:$f_{3}$

における山谷判定 $(NRDE/RNG)$

Generations
図 13:における山谷判定 $(NRDE/RNG)$$f_{4}$

における山谷判定 $(NRDE/RNG)$

巨視的には谷がただ一つだけ存在するため，序盤は探索空間内にランダムに生成した探索点は大域的最適の多数の小さな谷にとらえられるため谷点および谷近傍点が増加する．
探索が大域的最適解の周辺まで進むと，大域的最適解である谷点の周辺は局所的には $fi$ と同様な単峰性あるため，終盤では谷点と谷近傍点が再度減少し，最良値が急速に最適値に収束している．
からに共通した特徴として，NRDE(RNG) に比して谷近傍点の個数が多いことがNRDE(GG) のあげられる．RNG は GG の部分グラフであるため，GG は RNG に比して完全グラフに近いグラフである．
したがって 1 個の頂点に連結する辺の数が多くなり，谷点に連結する点である谷近傍点が多くなっている．

値方向へ探索が行われる．中盤は$f_{1}$$fi$$f_{4}$$f_{4}$

については，谷点は定常的に約 2 個であり，谷近傍点は定常的に 20 個から 27 個程度の間で増減を繰り返している．山点は定常的に 4 個程度である．すなわち，巣の近傍での近傍探索は 30 個体程度，巣への帰巣行動は 4 個体程度，通常の $DE$ による大域探索を 15 個体程度が定常的に行っていると考えられる． お$f_{2}$よび$f_{3}$

については，谷点が十分に減少していない． については，谷点が定常的に 1 個程度となっている．
$f_{4}$

最良値が最適値に収束していないことから，局所解に完全に収束してしまっていると考えられる．このよう$fi$ のような単峰性関数に対に探索に失敗した原因は，GG が完全グラフに近い密なグラフであるために，しては探索性能を有するが，変数依存性や悪スケール性を有する関数ゐやゐ，大谷構造を有する血では谷を十分とらえられなかったためと考えられる．

29

2000

$1\infty 0$

$0$

3000

1000

$0$

図 14: $fi$ における山谷判定 $(NRDE/GG)$

2000
Generations$Generat|ons$

図 15:$f_{2}$

における山谷判定 $(NRDE/GG)$$0 1000 2000 3000 0 1000 2000 3000$
Generations

Generations

図 16:

6

$f_{3}$

における山谷判定 $(NRDE/GG)$

図 17:$f_{4}$

における山谷判定 $(NRDE/GG)$

おわりに

本研究では，集団的最適化アルゴリズムにおいて，探索効率を向上する方法として，巣形成と役割分担に基づく最適化アルゴリズムを提案した．提案した巣形成と役割分担に基づく最適化アルゴリズムは，探索点による近接グラフに基づく山谷構造の推定と山谷判定を行い，探索点の近傍における山谷構造に基づいて探索モードを変更することで，探索効率を向上する方法である．山谷構造の推定では近接グラフとしてガブリエルグラフと相対近傍グラフを用い，探索点を谷点，山点，谷近傍点，その他の点の 4 種類に分類した．巣形成と役割分担としては，谷点 (女王蟻) と隣接する谷近傍点 (雄蟻) が巣を形成し近傍探索を行い，山点は最良の巣へ帰巣する中域探索を行い，その他の点は通常の大域探索を行うこととした．本研
究では探索アルゴリズムとして $DE$ を採用した巣形成と役割分担に基づく最適化アルゴリズム NRDE を提案し，ガブリエルグラフによる NRDE(NRDE(GG)), 相対近傍グラフによる NRDE(NRDE(RNG)) 及
び標準的 $DE$ ( $DE$ /rand) を比較することにより，単峰性関数に対しては NRDE(GG) が，稜構造および多峰性関数については NRDE(RNG) が他の方法と比較して，効率性の高い方法であることを示した．特に，NRDE(RNG) はいずれの問題に対しても安定的最適化アルゴリズムであることが示された．これにより，NRDE を利用して探索性能を向上できることを示した．

30
今後は，近接グラフとして競合ヘブ則によるグラフを用いること，局所探索と大域探索の実現方法を検討$PSO$ などの集団的最適すること，self-adaptive のようにパラメータを動的に制御する手法と比較を行う，
化アルゴリズムに適用することなどを予定している．

謝辞

この研究の一部は，日本学術振興会科学研究費補助金基盤研究 (c) (No. 22510166, 24500177) および広島市立大学特定研究費く一般研究)の援助を受けた．

参考文献[1] R. Stom and K. Price: “Minimizing the real functions of the ICEC’96 contest by differential evolution”, Proc. of the Intemational Conference on Evolutionary Computation, pp. 842-844 (1996).

[2] R. Stom and K. Price: “Differential evolution– simple and efficient heuristic for global optimization over continuous spaces”, Joumal of Global optimization, 11, pp. 341-359 (1997).
$A$[3] 阪井，高濱:“多次元空間における近傍構造を利用した最適化アルゴリズムに関する一検討”, 不確実
不確定性下での意思決定過程，数理解析研究所講究録 1682, pp. 184-192 (2010).

[4] 高濱，阪井 :“競合ヘブ則によるグラフ生成に基づく種分化型 diffferential evolution の提案”, 第 22 回インテリジェントシステムシンポジウム講演論文集．

[5] T. Takahama and S. Sakai: “Differential evolution with graph-based speciation by competitive hebbian rules”, Proc. of the Sixth Intemational Conference on Genetic and Evolutionary Computing(ICGEC2012), pp. 445-448 (2012).

[6] K. R. Gabriel and R. R. Sokal: “ new statistical approach to geographic variation analysis”,
Systematic Zoology, $1S$ , pp. 259-270 (1969).
$A$[7] G. T. Toussaint: “The relative neighborhood graph of a finite planar set”, Pattern Recognition, 12,4, pp. 261-268 (1980).
[8] D. G. Kirkpatrick and J. D. Radke: “ framework for computational morphology”, Computational
geometry (Ed. by G. Toussaint), North-Holland, pp. 217-248 (1985).
$A$[9] T. Martinetz and K. Schulten: “Topology representing networks”, Neural Networks, 7, 3, pp. 507522 (1994).
[10] 田中，土谷，佐久間，小野，小林 :“Saving MGG: 実数値 $GA/MGG$ における適応度評価回数の削減”,
人工知能学会論文誌，21, 6, pp. 547-555 (2006).