メタ最適化問題の目的関数依存性と適合目的関数

パラメータ値メタ最適化問題

: min

c

J (x

^∗

( · ))

where x

^∗

( · ) solution to

x(k + 1) = A(χ(k), c), k = 0, 1, . . . , K − 1 χ(0); given

(3.24)

パラメータ時系列メタ最適化問題

min

c(·)

J (x

^∗

( · ))

where x

^∗

( · ) solution to

x(k + 1) = A(χ(k), c(k)), k = 0, 1, . . . , K − 1 χ(0); given, c(0); given

(3.25)

フィードバック型静的調整則メタ最適化問題

: min

F(·)

J (x

^∗

( · ))

where x

^∗

(·) solution to {

x(k + 1) = A(χ(k), c(k)) c(k) = F (x(k))

k = 0, 1, . . . , K − 1 χ(0); given, c(0); given

(3.26)

フィードバック型動的調整則メタ最適化問題

:

F

min

(·,·)

J (x

^∗

(·))

where x

^∗

( · ) solution to {

x(k + 1) = A(χ(k), c(k)) c(k + 1) = F (c(k), χ(k)) k = 0, 1, . . . , K − 1 χ(0); given, c(0); given

(3.27)

と表記しなければならない．

3.3

節で定式化したメタ最適化問題の解である最適パラメー タの値，ないしはその最適時系列，あるいはそれを与える最適調整則は，いずれも解こう としている最適化問題の目的関数

E

に依存する．したがって，これらは最適化アルゴリ ズムのあるユーザが解こうとする最適化問題に適応した最適なパラメータの値，ないしは その最適時系列，さらにはそれを与える最適調整則であり，解こうとしている最適化問題 を環境とみなし，それにあるアルゴリズムを適応させた結果がメタ最適化問題の解である 最適パラメータの値，ないしはその最適時系列，あるいはそれを与える最適調整則といえ る．したがって，メタ最適化問題の考え方は，本質的にユーザが解こうとしている問題に 依存するものである．

以上のような考え方を基盤にすると，たとえば，文献

[16]

^では，

(1)

「良い解の近傍にはさらによい解がある」といういわゆる近接最適性原理

(POP)

^が成 り立つ目的関数に対して良好な計算性能を得ること

がアルゴリズムパラメータの調整指針の一つとして提唱されている．これに根拠をおくの が，探索点の挙動が発散傾向にある大域的探索と収束傾向にある局所的探索との異なる特 性，あるいは複数の探索点の分散化

(Diversification)

と集中化

(Intensification)

の特性をア ルゴリズムにもたせようとするパラメータ調整の設計指針である．

PSO

のパラメータ調整 法において大域的探索から局所的探索に一方向的に移行させるパラメータ調整や，それら の探索性能を双方方向的に移行したりするようなパラメータ調整，さらには探索点の集団 としての活性度を制御すようなパラメータ調整法がこれに相当する．

POP

が成り立つ目的 関数として，大域的な谷の構造に細かな周期的波形が重なった

Rastrigin

関数がある．しか し，

POP

自体が定性的な性質であり，

PSO

の各種のパラメータ調整法によって，

POP

が成 り立つ目的関数に対して良好な探索性能がそれらのパラメータ調整によって獲得されてい る理論的保証はなく，まして

POP

の成立が保証されていない関数に対しては，発散と収 束，ないしは分散化と集中化という設計指針は有効とは限らない．

これに対して近年では，たとえば文献

[52][63]

のように，

(2)

「変数空間に変換を施しても探索初期点に対して同じ変換を施せば，あるいは目的関 数に変換を施せば，それに対する探索性能は不変である」という計算性能の「変換 不変性」があること

が，アルゴリズムないしはそのパラメータ調整の設計指針として提唱されている．この不 変性には，具体的に

(a)

変数空間の平行移動に対し，それと同等の探索初期点の平行移動によりアルゴリズ ムの探索性能が不変

(

^{平行移動不変性}

)

(b)

変数空間の座標回転に対し，それと同等の探索初期点の回転によりアルゴリズムの 探索性能が不変

(

回転不変性

)

(c)

座標軸のスケール変換に対し，それと同等の探索初期点座標のスケール変換により アルゴリズムの探索性能が不変

(

座標スケール不変性

)

(d)

目的関数値のスケール変換に対し，アルゴリズムの探索性能が不変

(

^{目的関数値ス} ケール不変性

をあげることができる．

PSO

や

DE

の更新式は，本質的には線形演算であるため，線形演 算である平行移動や変数のスケール変換に対しては，その不変性を有するものといえる．

しかし，回転不変性については，回転演算が線形であっても，

PSO

や

DE

の更新式が変数 の成分ごとに記述されるため，変数成分間に相互干渉がない目的関数に対して良好な探索 性能を有するようパラメータ調整を行った更新式を，回転操作を施した変数座標で同じ目 的関数に対して適用してみると，回転不変性の欠如から探索性能が低下することが確認さ れる．そこで，文献

[52]

の

CMA-ES

のように，回転不変性をもたせた更新式とパラメー タ調整法を有する

ES

の開発が行われている．ただし，変数座標に対して

R(α) =

∏

N i=1

∏

N j=0

R

^i,j

(α

_ij

)

r

_k,l^i,j

(α

^q_ij

) =

 

 

 

 

 

 



 

 

 

 

 

 

cos(α

_ij

) k = i, l = i

− sin(α

_ij

) k = i, l = j sin(α

_ij

) k = j, l = i cos(α

ij

) k = j, l = j

1 k = l ̸= i, k = l ̸= j

0 otherwise

(3.29)

によって回転操作を変数に施した目的関数に対して良好な探索性能を有するようにアルゴ リズムを設計したとしても，それがユーザーが解きたい問題の目的関数に適合するアルゴ リズムである保証はない．そのため，解きたい最適化問題の目的関数に適合したパラメー タ調整法をメタ最適化の考え方によって発見することは，課題を克服するアプローチの一 つであるといえる．

以上のような，

POP

に基づく設計や変換不変性の付与による設計のほかに，

(3)

「悪条件な目的関数形状」へ適合する計算性能があること

も設計指針としてあげることができる．この悪条件の例としては，たとえばある方向には 急峻で別の方向には緩慢な細長い湾曲した形状をした谷を有する関数で，

Rosenbrock

^関数 が有名である．

本論文では，メタヒューリスティクスのアルゴリズムが適合しなければならない新たな 特徴をもつ目的関数として，またそのための設計指針として，「フラクタル的探索持続性」

を提案する．具体的には，再帰的に定義される

Fig. 3.3

のような形状のフラクタル関数

f (x) =

 

 



 

 

1

3

f (3x), if 0 ≤ x <

¹₃

−

¹₃

+

¹₃

f(3x − 1), else if

¹₃

≤ x ≤

²₃

1

3

f (3x − 2), else if

²₃

< x ≤ 1

0, otherwise

(3.30)

を用いて，

N

次元実空間で定義された目的関数

E(x) =

∑

N n=1

f (x

n

) (3.31)

0.0 0.2 0.4 0.6 0.8 1.0

−0.5

x

−0.4

−0.3

−0.2

−0.1 0.0

E (x )

Fig. 3.3: Shape of Fractal function.

を考える．ここで，あるアルゴリズムで得られる解

x

^∗に対応して

(

max

n

x

^∗_n

− 1 2

)

≤ 1 2

( 1 3

)

₋m

, n = 1 . . .

，

N (3.32)

を満たす最小の整数

m

を考えると，

x

^∗が第

m − 1

回の再帰部分の領域

(

第

m − 1

階層の 領域という

)

にあることを示す．したがって，この

Fig. 3.3

で喩えれば，

(3.31)

式の

N

次 元のフラクタル関数に適合するメタヒューリスティクスのアルゴリズムの性能として，イ テレーションが進むに従って，その探索範囲の階層数が大きくなる領域を集中して探索し ていく性能が望まれる．すなわち，最大イテレーション

K

の範囲で持続探索し続けて，第

K

イテレーション時に求まるアルゴリズムの解

x

^∗

(K)

に対応する整数の値

− m

が，最大 イテレーション回数の増加とともに大きくなることが，メタヒューリスティクスの性能と して望まれる．このような探索性能をメタヒューリスティクスの「フラクタル性」と称す ることにする．

本論文で提唱する「メタ最適化」の概念は，こうした様々な設計指針を前提としてメタ ヒューリスティクスのアルゴリズムの更新式や調整則を設計するのではなく，「ユーザが解 きたい個々の最適化問題の目的関数に適合したより良好な探索性能を獲得するよう，メタ ヒューリスティクスの更新式に対して最適な調整則を発見すること」ということができる．

そこで本論文では，本論文におけるメタ最適化問題において，アルゴリズムを進化的に適 合させる対象の目的関数として，

(a)

変数間依存を持たせるため回転変換した多峰性の

Rastrigin

^関数

(b)

変数間依存を持たせるため回転変換した多峰性で局所的最適値に差が少ない

Alpine

関数

(c)

変数間依存をさらに強くさせるため回転変換した多峰性の

Levy

関数

(d)

変数間依存を持つ悪条件の

Rosenbrock

^関数

を取り上げることにする．メタヒューリスティクスの適合対象とするこのような目的関数 をとくに「適合目的関数」と称することにする．

ドキュメント内 メタヒューリスティクスに対する遺伝的プログラミングによる創発的パラメータ調整則の自動設計(本文) (ページ 64-68)