数理解析研究所講究録
第 1559 巻 2007 年 22-33

22

比較推定による最適化アルゴリズムの効率性向上
広島修道大学商学部

阪井

節子 (Setsuko Sakai)

Faculty of Commercial Science, Hiroshima Shudo University
広島市立大学情報科学部 高濱 徹行 (Tetsuyuki Takahama)
Faculty of Information Sciences, Hiroshima City University

1

はじめに

最適化アルゴリズムは, 与えられた領域において最小値 (最大値) をとる解を探索するためのアルゴリズ
ムである. 近年, 最適化アルゴリズムとして, 集団的降下法に基づくアルゴリズムが注目されている. 集団的降下法とは, 複数の解の集合により集団を形成し, 集団から得られる情報に基き, 集団の各要素に対して順次新しい解を生成し, 新しい解が良ければ古い解と置換するという方法である.
集団的降下法の代表として, Differential Evolution (DE) と Particle Swarm Optimization (PSO) があ

DE では, 個体により集団を形成し. 各個体から交叉と突然変異により新しい個体を生成し, 新しい個体が良ければ古い個体と置換する [1, 2, 3, 4]. PSO では, 解に対応する位置の情報を持つエージェントにより集団を形成し, 各エージェントの現在位置とエージェントの最良位置と集団の最良位置により新しい位置を生成し, その位置が最良位置より良ければ古い最良位置と置換する [5, 6, 7, 8, 9, 10, 11]. これらの方法は, 集団の各要素が降下法により個別に最適化されるため, 集団が急速に特定の解に集中することが少な
く, 網羅性の高い探索が行われる. また, 各要素が新しい解を生成する際に集団の情報を利用できるため,一つの点による降下法と比較すると局所解に陥りにくい効率の良い探索が行われる.
しかしながら, 最適化問題が大規模化してきており, 目的関数の評価コストが増大してきている. このような問題の例としては, 構造設計最適化 (structural design optimization) 問題がある. 計算流体力学 (computational fluid dynamic8, CFD) シミュレーションを要する空力設計最適化 (aerodynamic design
optimization) では, CFD シミ レーションのために 1 回の計算に数 10 時間かかる場合もある. このため,目的関数の評価回数を抑えるべく, さらに効率的な最適化アルゴリズムの開発が期待されている $[12, 13]$ .
これに対して, 我々は, 集団的降下法の効率をさらに向上させるために, 低精度の近似モデルを有効に利用して評価回数を削減する比較推定法を提案した [14]. 比較推定法は, 近似モデルにより解の良さを推定
し. 生成された新しい解が古い解より良いと推定された場合にのみ新しい解を評価し, 新しい解が古い解より良ければ置換することにより, 臼的関数の評価回数を抑える方法である. 学習が不要な低精度の近似モデ
ルを利用することにより, アルゴリズムの速度を大きく低下させることなく効率的な最適化が可能となる.
比較推定法の適用例として, 集団的降下法としては DE を, 低精度の近似モデルとしては, ポテンシャル
エネルギーに基づく学習不要のモデルを採用したポテンシャル法を提案し, 評価回数がかなり削減できることを示した. ところが. 滑らかな関数では評価回数を大きく削減できたが, 急峻な構造を持っ関数では,
やや評価回数の削減が少ないという傾向が見られた. この理由としては, ポテンシャルが関数値を滑らかに近似することが考えられる. 滑らかな関数では近似精度が高くなり, 解の比較が適切に行われる. しかし,急激に変化する関数では, 近似精度が不十分になり, 本来受け入れるべき重要な解を拒否したため, 最適解る.

$\iota$に近づくのが遅れたと考えられる.
本研究では, 近似精度が不十分と推定される場合に重要な解を拒否しないように, ポテンシャルに基づく
混雑度 (混雑ポテンシャル) を利用することを提案する. ポテンシャル法に混雑度を用いた方法を, ポテン
シャル法およびオリジナルの DE と比較し, 混雑度を用いることにより, 急峻な構造を持つ問題において,
関数評価回数をさらに削減でき, 効率性が向上することを数値実験により示す.

本論文は次のように構成されている. 2. で最適化問題を定義し, 比較推定法について説明する. 3. でボ
4. でポテンシャル法を DE に組み込んだ potential DE 法を脱明し, その改良方法を提案する. 5. で実験結果を示す. 6. はまとめである.
テンシャル法を説明する.

23
2

比較推定法

2.1

最適化問題

一般的な最適化問題 (P) は, 不等式制約, 等式制約, 上下限制約を有しており, 以下のように定義できる.
$(P)$

minimize $f(x)$subject to $g_{j}(x)\leq 0,$ $j=1,$$h_{j}(x)=0,$ $j=q+1,$$\ldots,$$l_{i}\leq x_{i}\leq u_{i},$ここで.

$x=(x_{1}, \cdots, x_{n})$$i=1,$(1)$q$$\ldots,$$\ldots,$

$m$

$n$

は $n$ 次元決定変数ベクトル, $f(x)$ は目的関数,$h_{j}(x)=0$ は $m-q$ 個の等式制約であり,$g_{j}(x)\leq 0$は$q$個の不等式制約,$f,$は線形あるいは非線形の実数値関数である.
:は個の決定変数の下限値, 上限値である.
目的関数および制約条件がともに線形の場合が線形計画問題, その他の場合が非線形計画問題である. 本
研究では, 不等式制約および等式制約のない非線形計画問題を対象とする.

それぞれ.

2.2

$n$

$g_{j},$$h_{j}$$l_{:},$$u$$x_{i}$

集団的降下法DE や PSO などのように解集団による最適化の際に降下法を利用した最適化法である集団的降下法について説明する. 集団的降下法は一般に以下のように記述できる.
まず,

1. 初期化: 集団に属する解をランダムに発生する
2. 評価: 全ての解を評価する

3. 終了判定: 終了条件を満足すれば終了する
4. 各解に対して,(a) 生成: 各解と集団の情報に基づき新しい解を生成する(b) 評価: 新しい解を評価する(c) 更新: 新しい解が古い解より良ければ, 古い解を新しい解で置換する

5.3. へ戻る(4C) が各解による降下法の部分である.

2.3

比較推定法

比較推定法は, 関数評価回数を削減する手法であるが, できる限り汎用的な手法とするために, 導入が容易であり, それぞれのアルゴリズムの特徴を生かすことに配慮した方法である. このため, 上記 (4b) および (4c) の部分のみを変更し, 以下のように, 新しい解を評価する前に, 近似モデルに基づき, 古い解より良いと推定された解だけを評価するように変更する.

1. if 新しい解が古い解より良いと推定された then(b) 評価: 新しい解を評価する(c) 更新: 新しい解が古い解より良ければ, 古い解を新しい解で置換する

2. endif
比較推定法の特徴をまとめると, 以下のようになる.

24近似モデルに基づき, 新しい解と古い解の良さを推定する. このとき, 解の良さは目的関数値を求めずに決める必要がある.

$\bullet$.

新しい解が良いと推定されれば評価更新を行否する.

3$A\searrow$

そうでなければ, 新しい解は評価することなく拒

ポテンシヤル法
ポテンシャル法は, 比較推定法において, ポテンシャルエネルギーに基づく近似モデルを採用する方法でここでは. ポテンシャルに基づく近似モデルについて簡単に説明する.

ある.

3.1

ポテンシヤル

ポテンシャルエネルギーとは, 物体がある位置に存在することで物体に蓄えられる位置エネルギーである. 例えば, 質量 $m$ の物体が存在すれば, その周りには重カポテンシャル砺が発生し, その物体から距離$r$

離れた質量 $m’$ の物体には引力$E_{g}$が働く.

$U_{g}=-G \frac{m}{r}$

距離

$G$

$q$

$q’$

ここで,

$\epsilon_{0}$$U_{e}$が発生し, その電荷から$E_{*}$$U_{e}=- \frac{1}{4\pi\epsilon_{0}}\frac{q}{r}$

3.2

(2)

$E_{g}=G \frac{mm’}{r^{2}}$は万有引力定数である. また, 電荷 をおくと, 静電ポテンシャルが働く.
離れた電荷 にはクーロンカ

ここで,
$r$

,

,

(3)

$E_{e}= \frac{1}{4\pi\epsilon_{0}}\frac{qq’}{r^{2}}$は真空中の誘電率である.

ポテンシャルに基づく近似モデル

本研究では. ある解 が存在することにより, その解から 離れた位置に, 目的ポテンシャル $U_{o}(potentia1$
for objective) と混雑ポテンシャル ( $potentia1$ for congestion) 力境生すると仮定する.
$x$

$r$

$U_{c}$$U_{o}$$=$$\frac{f(x)}{r^{p}}$$U_{c}$$=$$\frac{1}{r^{p}}$ここでは, 簡単のため, 比例係数を 1 とした.

(4)
(5)

また, 距離のべ*乗数 $P>0$ は整数値であり通常 1 あるいは 2 とする.

解集合 $X=\{x_{1}, x_{2}, \cdots, x_{N}\}$ が存在し, 関数値 $f(x_{t}),$ $i=1,2,$
けるポテンシャルを, 以下のように定義する.

$\cdots$$U_{o}(y)$$=$$\sum_{:}\frac{f(x_{1})}{d(x_{1},y)^{p}}$$U_{c}(y)$$=$$\sum_{:}\frac{1}{d(x_{1},y)^{p}}$, $N$ が既知であるとき, ある点

$y$

にお

(6)
(7)

ただし, $d(x, y)$ は点 $x$ と点 $y$ 間の距離である.

はある点における関数値の大きさの傾向を示しており,は近傍にどの程度他の点が存在し混雑しているかを示している. 点 における関数の推定値
は, これらの商で与えられる.
このとき,$U_{o}$$U_{c}$$\hat{f}(y)$$y$$\hat{f}(y)=\frac{U_{o}(y)}{U_{c}(y)}$

(8)

25
集団的降下法では, 関数値が既知の解集合 $X$ に属する古い解亀から新しい解
それぞれの点における推定値 $f(x_{i})$ および$f(x_{\mathfrak{i}}’)$は, 以下のように古い解$x_{i}$$x_{i}’$

を生成する. このとき,を除いた解集合 $X$ によるポテンシャルで求めることができる.
$U_{o}(x_{i})$(9)$= \cdot\sum_{j\neq i}\frac{f(x_{j})}{d(x_{j},x_{i})^{p}}$$U_{c}(x_{i})$$=$$\hat{f}(x_{i})$

$=$

(10)

$\sum_{j\neq i}\frac{1}{d(x_{j},x_{\dot{*}})^{p}}$(11)$\frac{U_{o}(x_{i})}{U_{c}(X_{1}\cdot)}$’$U_{o}(X_{1}\cdot)$$=$’$U$ $(x_{1})$

$=$

。

(12)

$\sum_{j\neq i}\frac{f(x_{j})}{d(x_{j},x_{i}’)^{p}}$(13)$\sum_{j\neq i}\frac{1}{d(X_{j},l_{1}’\cdot)^{p}}$’$\hat{f}(x_{i})$

$=$

(14)

$\frac{U_{o}(x_{i}’)}{U_{c}(x_{*}’\cdot)}$

potential DE

4Differential Evolution にポテンシャル法を適用したアルゴリズムである potential DE を説明し, 改良方法を提案する.

Differential Evolution

4.1

Differential evolution (DE) は進化的戦略 (evolution strategy) の一つであり, Storn and $Prioe[1,2]$ によって提案された. DE は確率的な直接探索法であり, 解集団を用いた多点探索を行う. DE は非線形問題,
微分不可能な問題, 非凸問題, 多峰性問題などの様々な最適化問題に適用されてきており, これらの問題に対して高速で頑健なアルゴリズムであることが示されてきている.
DE の重要な特徴として, 進化的戦略ではガウス突然変異のステップ幅を制御する必要があるが, DE ではこのような制御が不要となる単純な数学的演算を用いていることが挙げられる. 一般に, ガウス突然変異における理想的なステップ幅は, 遺伝子あるいは各次元毎に異なり, また進化の状態によっても異なるため, 何らかの方法でステップ幅を適応的に調整する必要がある. これに対し, DE はガウス突然変異の代わりに, 基本ベクトル (base vector) と差分ベクトル (difference vectors) との重み付き和を突然変異として採用している. 集団から選択された 1 個体が基本ベクトルとなり, 集団からランダムに選択された個体対の差
解集団が探索空間内で収縮したり拡張したりすることにより,が差分ベクトルとなる. 世代を経るに従$A\backslash$

差分ベクトルが変化し, 差分ベクトルとして与えられる各次元におけるステップ幅が自動的に調整されるのである.
DE には幾つかの形式が提案されており, $DE/best/1/bin$ や $DE/rand/1/\exp$ などがよく知られてい’ は基本ベクトルとなる親の選択
る. これらは, $DE/ba\epsilon e/num/cross$ という記法で表現される.
方法を指定する. 例えば. $DE/rand/num/cross$ は基本ベクトルのための親を集団からランダムに選択し,$DE/best/num/cross$ は集団の最良個体を選択する. $num$ ’ は基本ベクトルを変異させるための差分ベクトルの個数を指定する. “cross” は子を生成するために使用する交叉方法を指定する. 例えば, $DE/base/num/bin$は一定の確率で遺伝子を交換する交叉 (binomial crossover) を用い, $DE/base/num/\exp$ は, 指数関数的に減少する確率で遺伝子を交換する交叉 (exponential crossover) を用いる.
$ba\epsilon e$

DE では, 探索空間内にランダムに初期個体を生成し, 初期集団を構成する. 各個体は決定ベクトルに対応個の決定変数を遺伝子として持つ. 各世代において, 全ての個体を親として選択する. 各親に対して,
次のような処理が行われる. 突然変異のために, 選択された親を除く個体群から互いに異なる 1+2 num
し,

$n$

26
個の個体を選択する. 最初の個体が基本ベクトルとなり, 残りの個体対が差分ベクトルとなる. 差分ベク
トルは $F$ (scaling factor) が乗算され基本ベクトルに加えられる.

その結果得られたベクトルと親が交叉し,(crossover factor) により指定された確率で親の遺伝子をベクトルの要素で置換することにより, 子のベ
クトル (trial vector) が生成される. 最後に, 生存者選択として, 子が親よりも良ければ, 親を子で置換する.

$CR$

本研究では, 差分ベクトル数を 1 $(num=1)$ とした $DE/rand/1/\exp$ を用いる.

4.2

potential DE のアルゴリズム

potential $DE/rand/1/\exp$ のアルゴリズムは以下のように記述できる $[3, 4]$ .

Step0 初期化.

$N$個の初期個体$x_{i}$

を初期探索点として生成し, 初期集団 $\{x_{i}, i=1,2, \cdots, N\}$ を構成する. 全ての個体を評価する.

Stepl 終了判定. 終了条件を満足すれば, アルゴリズムは終了する. 終了条件としては, 最大の繰り返し
回数や関数評価回数を用いることが多い.
Step2 突然変異. 各個体に対して, 3 個体 $x_{p1},$ $x_{p2},$
ムに選択する. 新しいベクトル $x’$ を基本ベクトル$x_{i}$

を$x_{p3}$$x_{p1}$$x_{t}$

および互いに重複しないようにランダおよび差分ベクトル $x_{p2}-x_{p3}$ から以下のよ

うに生成する.

(15)$x’=x_{p1}+F(x_{p2}-x_{p3})$

ここで,

$F$

はスケーリングパラメータである.

Step3 交叉. ベクトル $x’$ を親と交叉し, 子ベクトルを生成する. 交差点 を全ての次元 $[1, n]$のからランダムに選択する. 子ベクトル
番目の要素を $x’$ の 番目の要素から継承する. それ以降の次元は, 交叉パラメータ $CR$ によって指数関数的に減少する確率で, $x’$ の要素から継承する. 残りの部分は, 親から継承する. 実際の処理では, Step2 と Step3 はーまとまりの処理で実現される.
$X_{1}^{ncw}$$x_{i}$$j$$i$$x_{j}^{n\epsilon w}$$i$$x_{i}$

Step4 ポテンシャル法. もし, 子ベクトルが親ベクトルよりも良いと推定されれば, Step5 に進む. そう
でなければ, Step6 に進む.
Step5 生存者選択. 子ベクトルを評価する. 子ベクトル
生存者とな呪 親を子ベクトルで置換する.

$x_{1}^{now}$が親ベクトルよりも良ければ子ベクトルがStep6 Stepl に戻る.
以下に擬似コードを示す.
potential $DB/rand/1/\exp()$$\{$$P=GenerateN$ individuals
randomly;$N$ ;Evaluate $x:$ , $i=1,2,$
for ( $t=1$ ; 終了条件が満たされない ; $t++$ )for (isl; $i\leq N_{j}i++$ )$(P_{1},P_{2},P_{3})=\epsilon elect$
randomly from 1, .
$\{x_{1}\}$$\cdots,$

$\{$

$\{$

$\{$

$x^{new}:=x_{i}\in P$$j$:-seloct randomly from

$k=1$

do

$\{$

1,

;
$\{$

$x_{jj}^{new}=x_{p_{1},j}+F(x_{p_{2},j}-x_{ps,j})$$j-(j+l)\% n;$ .
$k++$

;

;

$\cdot$..,$N\}_{j}$$\cdot$.,$N\}\backslash \{i\}$.

8. $t$ $Pj\neq p_{k}(j, k=1,2,3,j\neq k)$:

27while ( $k\leq n$ &&u(O, $1)<CR$ );if $(Better_{Potentia1}(x^{new}, x))$;
Evaluate

$\}$

$\{$

$x^{11ew}$

if $(f(x_{i}^{new})<f(x_{i}))x_{i}=x_{i}^{new}$ ;
$\}$

$\}$

$\}$

$\}$

ここで, $u(O, 1)$ は区問 $[0,1]$ の一様乱数生成関数, $Better_{P}$は, ポテンシャル法に基づき, 解の良さを比較する関数である. この関数値が常に真ならば, すなわち, $Better_{Potentia1}(\cdot, \cdot)=1$ ならば, 常に関数値の評価が行われることになるため, 通常の $DE/rand/1/\exp$ と一致する.
$t\epsilon ntial(\cdot, \cdot)$。

4.3近似モデルによる比較

比較推定法 [14] では, 低精度の近似モデルを使用するため, 推定誤差を考慮し, ある程度の余裕を与えを使用した.
た次の関数 $Better_{P}$$t$$nti\cdot 1$
。
。

(16)

$Better_{P\circ tentia1}(x_{1}’, x:)\Leftarrow\frac{\hat{f}(x_{1}’)-\hat{f}(x_{i})}{|\hat{f}(x_{1})|}\leq\delta$

ここで、 (16) は、 右辺の不等式が成立するとき,いる。 また,$\delta\geq 0$が真であるということを意味しては誤差の余裕を決めるパラメータであり. 推定値を決めるための解集合 $X$ は, 各世代$Better_{P}$ 。。ntial $(X’\cdot, X;)$$t$

における集団 $P$ とした.
が の場合は, 推定値に基づく比較となり, 多数のベクトルを拒否するため, 良いベクトルも拒否してを大きくすると, 推定値が少し悪いベクトルも受け入れるため, 良いベクトル
しまう可能性が高くなる.
は適当な大きさにとる必要を拒否する可能性は低くなるが. 逆に. 拒否する数が減少する. したがって,$\delta$$0$$\delta$$\delta$があり, 通常 $\delta=0.001$ とする.

さらに, 本研究では, 式 (16) による条件に加えて. 重要なベクトルを拒否しないように, 混雑ポテンシャ

ルを用いて受け入れる条件を与えることを提案する. 混雑度が高い解は近くに解が存在するため近似精度が高く, 混雑度が低い解は近くに解が存在しないため近似精度が低いと考えられる. したがって, 重要な解を拒否しないためには, 混雑度が低い解を受け入れた方が良いと考えられる. また, 混雑度が低い解は, これまでに探索してこなかった領域の解であるため, 網羅性の向上にも有効であると期待できる. このため,混雑度を用いて解を, 確率的に受け入れる以下の条件を追加した.
$Better_{Pot\epsilon ntla1}(x_{1}’, x_{t})\Leftarrow\frac{U(x_{i}’}{U_{\text{。}}(x_{i}}\}\leq\lambda$

ただし,$\lambda(0\leq\lambda\leq 1)$

w.p.

(17)

$P_{\epsilon}$は解を受け入れる混雑ポテンシャルの比を指定するパラメータであり,$P_{c}$

は条件を満足したときに受け入れる確率を指定するパラメータである.
$\lambda$

を大きくすると, 重要なベクトルを拒否する可能性は低くなるが, 逆に悪いベクトルを受け入れるようになる.

を小さくすると, 悪いベクトルを受け入れる可能性は低くなるが, 重要なベクトルを拒否してしまうようになる. したがって,は適当な大きさにとる必要がある. 受け入れ確率瓦は, 混雑度の条件を$\lambda$$\lambda$

満足したときに実際に解を受け入れる確率であり,の場合は, 推定値のみによる判定となり従来のを大きポテンシャル法と一致する, P』が 1 の場合は混雑度による判定を完全に受け入れることになる.
くすると重要なベクトルを拒否する可能性が下がるが, 逆に悪いベクトルを受け入れる可能性が高くなる.
さらに, 次元毎のスケールの差に対応するために, 各世代において集団に存在する解の次元毎の幅, すな
わち最大値と最小値の差により正規化した距離を導入する.
$P_{c}$

が$0$$P_{c}$(18)
なお, 距離のべ \neq 乗数は, 最も計算量が少なくなる $p=2$ に設定した.

28
5

実験

5.1

テスト問題

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

がその典型例である.
以下に, 関数とその初期化領域を示す. なお,

.

$fi$

$n$

は次元数を表している.

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

単峰性の関数で, 点 $(0,0, \cdots,0)$ で最小値

$0$,$-5.12\leq x:\leq 5.12$

(19)

をとる.

$f_{1}$.

図 1: $n=2$ のときの関数 $fi$ のグラフ

$f_{2}:$

Rosenbrock NM$f(x)= \sum_{:=2}^{n}:+(x_{i}-1)^{2}\}$ ,単峰性の稜構造を有する関数で, 点 $(1, 1, \cdots, 1)$ で最小値$\bullet$$f_{S}$$0$

単峰性の稜構造を有する関数で, 点$f_{4}$

(20)

をとる.

: ill-scaled $R_{08}enbrock$ 関数$f(x)= \sum_{=;2}^{n}\{100(x_{1}-(ix_{i})^{2})^{2}+(ix_{i}-1)^{2}\}$.

$-2.048\leq x_{i}\leq 2.048$$(1, \frac{1}{2}, \cdots, \frac{1}{n})$

で最小値

,

$-2.048/i\leq x_{i}\leq 2.048/i$

$0$

をとる.

,

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

多峰性の大谷構造を有する関数で, 点 $(0,0, \cdots, 0)$ で最小値

$0$

をとる.

(22)

29

図 2: $n=2$ のときの関数ゐのグラフ

図 3: $n=2$ のときの関数ゐのグラフ
また, 表 1 に各関数の特徴を示す.
表 1: テスト問題の特徴

関数 変数 $Mff$ 存

悪スケール性大谷構造

$fi$

なし

なし

なし

$f_{2}$

強い

なし

なし

強い
なし

あり

なし

なし

あり

$f_{3}$$f_{4}$

52$\dagger*$

実験結果

表 2 に余裕 $\delta=0.001$ , 混雑度比 $\lambda=0.5$ としたときの 20 回の試行の結果を示す. IFNinc. は目的関数,
は受け入れ確率である。 $P_{c}=0$ の場合が, 従来のポテンシャル法に対応する. 実際に関数を評価した回数
を eval, そのうち子ベクトルが良かった回数を $8UCC$ , 悪かった回数を fail, 成功率を rate に示している. ま$P_{c}$

30
た、 obj-succ は, 拒否されたベクトルが親ベクトルよりも悪かった回数, obj-fail は, 拒否されたベクトルが良かった回数, rate は拒否したベクトルが実際に悪かった確率を示している.

さらに、 acc-succ は, 混雑度により受け入れたベクトルが親ベクトルよりも良かった回数, acc-fail は, 受け入れたベクトルが悪かった回数, rate は受け入れたが実際に良かった確率を示している.
関数の評価回数は, 単純な関数である $fi$ においては従来のポテンシャル法である $P_{c}=0$ の場合が最も良
いが, より現実的で困難な問題である
では $P_{c}=0.75,$
では $P_{c}=0.75,$
では $P_{c}=0.25$ が最も優れた結果となっている. 特に,およびたにおいては, 受け入れ成功確率が 1%程度にもかかわらず, 評
価回数を大きく削減しており, 重要な解を拒否しないことに成功したと考えられる. したがって, 現実的な問題においては混雑度による解の受け入れは有効であるといえる.
$f_{2}$$f_{3}$$f_{4}$$f_{2}$

表 2: 混雑度を利用したポテンシャル法の実験結果

混雑度を導入した potential DE を評価するために, 安定した結果を残した $P_{c}=0.5$ の場合と従来のポテンシャル法およびオリジナルの DE を比較した結果を表 3 に示す.
表 3: potential DE と DE の評価回数の比較

混雑度を導入した場合, DE と比較すると, $fi$ では半分以上,
では約半分,
では約 23%, んでは約20% 削減することに成功している. 混雑度を利用しない potential DE と比較すると, $f1$ は 3%増加しているが,は同程度であり,は約 9%,
は約 7%評価回数を削減することに成功している. したがって,
混雑度を導入した potential DE は, 特に急激な変化を伴う関数に対してさらに探索効率を向上させることに成功した, 非常に効率性の高いアルゴリズムであるといえる.
DE, potential DE
および混雑度を導入した potential DE( $P$ $=0.5$ ) を比較するために, 2 つの方法について各問題における関数値の変化を図 4, 6, 8 および 10 にそれぞれ示し、 成功率の変化を図 5,$f_{4}$$f_{4}$$f_{2}$$(P_{\text{。}}=0)$$f_{2}$$f_{3}$。

31
7, 9 および 11 にそれぞれ示した. 横軸は関数評価回数, 縦軸は関数値および成功率である. なお, グラフ
は 20 回の実験の平均値を示しているため, グラフの終末付近では探索を打ち切った試行が多くなり, デー

タ数が減少し平均値に乱れが出ている.

0.8

0.6

0.4

$0\ell$$0$$0$

図 4: $fi$ における関数値の変化

10000

20000

図 5:

$fi$

30000

$4\infty\infty$

SOOOO

60000

における成功率の変化

図 6: ゐにおける関数値

図 7: ゐにおける成功率の変化

図 8: $fa$ における関数値

図 9:たにおける成功率の変化

70000

$K$

32

図 10:

$f_{4}$

図 11: みにおける成功率の変化における関数値

全ての問題において potential DE および混雑度を導入した potential DE が DE よりも常に高速に関数値を減少させており, 成功率についても, potential DE の方が常に高い値を示している. さらに, 急峻な構造を持つ問題 $(f_{2}, f_{3})$ においては, 混雑度を導入した potential DE が potential DE より高速に関数値を減少させていることが分かる. また, ポテンシャル法による推定の成功率 (obj-rate) についてもほとんどの場
合に 90% を超えており, かなり精度が高いことが分かる.

6

おわりに

本研究では, 集団的降下法において, 関数評価回数を削減し効率性を向上する方法として. ポテンシャル法について説明した. ポテンシャル法は, 関数値の近似のために解のポテンシャルを用
近似値に基づき解を比較し, 不必要な解の評価をできる限り行わないようにすることで, 関数評価回数を削減する方法である. しかし, ポテンシャル法は近似精度の低いポテンシャルに基づく近似モデルを使用するため, 急激な変化を伴う関数において, 重要な解を拒否してしま
探索効率が低下する場合があった. 本研究では,混雑度を導入することにより, 重要な解を受け入れる方法を提案した. 混雑度を導入した potential DE を,
$Aa$

$Aa$

potential DE およびオリジナルの DE と比較することにより, 混雑度を導入した方法が他の方法と比較して効率性の高い方法であることを示した. 現在のところ, 混雑度に関するパラメータである およびに関する調査がまだ十分ではないため, さらに検討を進める必要がある.
今後は, ポテンシャル法を PSO などの他の集団的降下法へ適用すること, 近似値に基づく比較に Simulated
Annealing のような確率的な比較を取り入れることを予定している.
$\lambda$$P_{c}$

謝辞
この研究の一部は,もとで行われた.

日本学術振興会科学研究費補助金基盤研究 (c) (No. 16500083,17510139) の援助の参考文献
[1] R. Storn and K. Price: “Minimizing the real functions of the $ICEC’ 96$ contest by differential evolution”, Proc. of the International Conference on Evolutionary Computation, pp. 842-844 (1996).
[2] R. Storn and K. Price: :evolution-a simple and efficient heuristic for global optimization
over continuous spaces”, Journal of Global Optimization, 11, pp. $341-arrow 359(1997)$ .

33[3] T. Takahama, S. Sakai and N. Iwane: “Solving nonlinear constrained optimization problems by
the constrained differential evolution”, Proc. of the 2006 IEEE Conference on Systems, Man, andCybernetics, pp. 2322-2327 (2006).
$\epsilon$[4] T. Takahama and S. Sakai: :‘Constrained optimization by the constrained differential evolution withgradient-based mutation and feasible elites”, Proc. of the 2006 World Congress on Computational
Intelligence, pp. 308-315 (2006).
$\epsilon$[5] J. Kennedy and R. C. Eberhart: “Particle swarm optimization”, Proceedings of IEEE International
Conference on Neural Networks, Vol. 1498 of Lecture Notes in Computer Science, Perth, Australia,
IEEE Press, pp. 1942-1948 (1995). vol.IV.
[6] J. Kennedy and R. C. Eberhart: “Swarm Intelligence”, Morgan Kaufmann, San Francisco (2001).

[7] T. Takahama and S. Sakai: “Constrained optimization by combining the constrained method withparticle swarm optimization”, Proc. of Joint 2nd Intemational Conference on Soft Computing andIntelligent Systems and 5th International Symposium on Advanced Intelligent Systems (2004).
$\alpha$[8] T. Takahama and S. Sakai: “Constrained optimization by theconstrained particle swarm optimizer”, Journal of Advanced Computational Intelligence and Intelligent Informatics, 9, 3, pp.
282-289 (2005).
$\alpha$[9] T. Takahama and S. Sakai: uConstrained optimization by constrained particle swarm optimizer
with -level control”, Proc. of the 4th IEEE International Workshop on Soft Computing as Transdisciplinary Science and Technology (WSTST’05), pp. 1019-1029 (2005).
$\epsilon$$\epsilon$[10] T. Takahama, S. Sakai and N. Iwane: “Constrained optimization by the constrained hybrid algorithm of particle swarm optimization and genetic algorithm”, Proc. of the 18th Australian Joint
Conference on Artificial Intelligence, pp. $38k400$ (2005). Lecture Notes in Computer Science 3809.
$\epsilon$[11] T. Takahama and S. Sakai: “Solving constrained optimization problems by the constrained particle swarm optimizer with adaptive velocity limit control”, Proc. of the 2nd IEEE International
Conferenoe on Cybernetics&Intelligent Systems, pp. 683-689 (2006).
$\epsilon$[12] Y. Jin: “A comprehensive survey of fltness approximation in evolutionary computation”, Soft Computing, 9, pp. 3-12 (2005).

[13] Y.-S. Ong, Z. Zhou and D. Lim: “Curse and blessing of uncertainty in evolutionary algorithm using
approximation”, 2006 IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, pp.
9833-9840 (2006).

[14] 阪井, 高濱 :“最適化手法に蓄ける関数評価回数の削減手法一ポテンシャルモデルに基づく比較推定法の提案一,,, 京都大学数理解析研究所講究録 (印刷中).
[15] 田中, 土谷, 佐久間, 小野, 小林 :“Saving MGG: 実数値 $GA/MGG$ における適応度評価回数の削減”,
人工知能学会論文誌, 21, 6, pp. 547-555 (2006).