メタヒューリスティクスのパラメータ最適調整問題とメタ最適化

PSO

の改良手法である

IWA-PSO

は，調整パラメータ

c

として慣性係数

c

0のみを選び，

その時系列

c

₀

(k) = c

_start

− (c

_start

− c

_end

) k

K (3.11)

を，最適か否かは別としてある種のメタ最適化問題の解とみなしているものといえる．

3.2

節で定式化したメタ最適化問題においては，パラメータ

c

を一定としているが，時系列

c(·)

が一定の値を取り続けるものとすれば，一定のパラメータの推奨値を決める問題

(3.6)

もパラメータ時系列を求めるメタ最適化問題

(3.10)

の特殊な場合とみなすことができる．

こうして，パラメータを時系列化することで，たとえば，

IWA-PSO

のように大域的な探 索から局所的探索へ移行させるなど，探索過程中に探索点の挙動に変化を与えることで，

メタ最適化の機能を高めることが可能である．

また，探索性能を評価する目的関数が，計算終了時のイテレーションの上限での探索点 座標の目的関数値

E(x

^∗

(K))

ではなく，探索点群の群れとしての挙動特性を示す指標，た とえば探索点群の活性度を指標とし，その変動の目標時系列に追従するようなパラメータ 調整を行う活性度調整型

PSO

に対して，その最適調整則を与えるメタ最適化問題を定式 化すると，

min

c(·)

∑

K k=1

| I (x

^∗

(k)) − I

_R

(k) | = J(x

^∗

( · )) where x

^∗

( · ) solution to

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

(3.12)

となる．ここで，

J(x

^∗

( · ))

は探索点時系列

x

^∗

( · )

の挙動を評価する指標であり，パラメー タ時系列

c( · )

に対する最適化アルゴリズムによる探索点時系列

x

^∗

( · )

に関する評価指標の 時系列

I (x

^∗

( · ))

とその目標時系列

I

_R

( · )

との偏差を最小にするように，パラメータ時系列

c(·)

^{を求める問題である．}

一方，

PSO

の

NDT-PSO

や

ES

および

DE

におけるパラメータ調整則は，探索点の挙動

状態に応じながらパラメータの値を変動させるものである．この場合もパラメータは時系 列となるが，この場合のパラメータ

c

の引数は，イテレーション回数

k

だけでなく，探索 点の挙動状態を表す探索点座標

x

も引数とする関数

F

を用いて，

c = F (k, x) (3.13)

とみなすことができる．イテレーション回数

k

を引数にしない場合でも，探索点座標

x

が 時系列であるため，パラメータ

c

は結果的に

c(k) = F (x(k)), k = 0, 1, . . . , K (3.14)

と時系列になる．この場合，最適化アルゴリズム

A

を実行して得られる最終イテレーショ ン

k = K

での最適解ないしはその近似解

x

^∗

(K)

は，直接パラメータ時系列に依存するの ではなく，関数

F (·)

に依存するため，これを引数として，

x

^∗

(K) = A(F (·)) (3.15)

とおくことができる．したがって，メタ最適化問題は目的関数値

E(x

^∗

(K))

を最小にする ような関数

F ( · )

を決定する問題となり，

min

F(·)

E (x

^∗

(K))

where x

^∗

(K) = A(F ( · ))

(3.16)

または，

min

F(·)

E (A(F ( · ))) (3.17)

と定式化される．これらの定式化において，

F ( · )

の表記を

F (x)

と記述しないのは，前者 は変数

x

の空間上で定義された関数自体を変数とする関数空間での最適化問題であるのに 対して，後者では変数

x

のある値に対する関数

F (x)

の値で最小化するという意味と解釈 されるためである．この問題をメタ最適化問題

(3.10)

に対応づけて定式化すると，

min

F(·)

E (x

^∗

(K))

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.18)

となる．

ところで，関数

F

^{はすべての探索点座標}

x

^{をパラメータの値}

c

^{に対応づけるベクトル} 関数で，これを改めて

c = F (x)

と表現すると，探索点座標

x

を入力とし，それに応じて パラメータ

c

の値が出力として決まる入出力関係である．したがって，パラメータ

c

の空 間の値を入力とし，

x

の空間の値を出力するような入出力関係

x = A(c)

とは，その入出 力関係が逆の関係であることがわかる．そこで，このようにパラメータ

c

を

x

の関数と して与える問題を「フィードバック型メタ最適化問題」と称することにする．このような フィードバックの関係を図示すると，

Fig. 3.2

のようになる．最適化アルゴリズムの写像

A

から生成される変数

x

の力学系に対して，関数

F

により

x

から

c

を生成する逆関数に よってフィードバック系を構成することは，最適化アルゴリズムの写像

A( · )

の力学系が有 する動的特性に対して，写像

A( · )

と関数

F ( · )

の合成写像

A(F ( · ))

による新たな力学系を 構成していることになり，本来のアルゴリズムの力学系の特性に対して本質的な変更を与 えることに相当し，より高機能なアルゴリズムパラメータの調整を行っていることになる．

このような例としては，

NDT-PSO

における調整則があげられ，たとえば

(2.18c)

^式におい て，

g-best

^座標

x

^(g−best)を定数とみなし，かつ探索点番号の上付き添字

(p)

^{を省略すると}

F (x) = 1 − d

1

+ d

1

d

0

exp(− ||x − x

^(g−best)

||

d

2

d

0

) (3.19)

とみなすことができる．

Fig. 3.2: Relations among algorithm, objective function and parameter tuning rule.

一方，

ES

における正規乱数の標準偏差に相当するパラメータ

σ(k)

^{の調整則である}

(2.24)

^，

(2.25)

式は，

σ(k + 1) = F (σ(k), p

_s

(k)) (3.20)

と一般化することができる．ここで

p

s

(k)

は，現在のイテレーション

k

から遡った一定のイテ レーション期間で突然変異が成功した頻度であり，この遡る一定のイテレーション期間を

l

と すると，

p

_s

(k)

は

x(k)

だけでなく，過去に

l

期遡った時系列

{ x(k − l), x(k − l+1), . . . , x(k) }

やその目的関数値を関数

F

の引数にしていることになり，それを示しているのが破線の部 分である．

(

試験点との目的関数値の比較にもよるので試験点の時系列を引数にする関数 ともみなせるが，これについては議論簡略化のため省略する

)

．また，関数

F

の引数に現 イテレーションのパラメータ

σ(k)

も含まれていることから，関数

F

による関数にも離散 系のダイナミクスをもたせていることがわかる．これらのことを一般化すると，パラメー タの更新則は離散力学系として

c(k + 1) = F (c(k), χ(k)), k = 0, 1, . . . , K − 1 (3.21)

と一般化することができる．このような一般化された調整則の離散力学系を与える関数

F

を用いて，計算終了時のイテレーションの上限

k = K

^{での探索点}

x

^∗

(K)

^{に対する目的関}

数値

E (x

^∗

(K))

を最小にするようパラメータ調整則を求めるメタ最適化問題は，

min

F(·,·)

E(x

^∗

(K))

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.22)

とさらに一般化して定式化することができる．この問題を「最適化アルゴリズム

A

に対す るパラメータの最適調整則

F

を与えるメタ最適化問題」と称することにする．なお，問題

(3.12)

に対応する形で，パラメータ時系列

c( · )

に対する最適化アルゴリズムによる探索点

の時系列

x

^∗

(·)

に関する評価指標の時系列

I(x

^∗

(·))

^{とその目標時系列}

I

R

(·)

^{との偏差を目} 的関数として導入すると，これを最小にするようなパラメータ時系列

c( · )

を与えるフィー トバック調整則

F ( · , · )

を求める，いわば問題

(3.22)

に対応するメタ最適化問題は，

min

F(·,·)

∑

K k=1

| I(x

^∗

(k)) − I

_R

(k) | 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.23)

となる

.

問題

(3.18)

や問題

(3.22)

のように，最適パラメータ時系列を与える調節則を与える関数

F

を求めるメタ最適化問題を「フィートバック型メタ最適化問題」ということにし，こ れに対して問題

(3.10)

のような最適なパラメータ時系列を直接求める「フィードフォワー ド型メタ最適化問題」からは区別する．とくにフィードバック型問題は，関数

F

による フィードバック関数が静的な問題

(3.18)

のタイプと，パラメータ調整にダイナミクスをも たせて動的にフィードバックを行う問題

(3.22)

のタイプを考えることができる．問題

(3.18)

を「フィードバック型静的調整則決定メタ最適化問題」，問題

(3.22)

を「フィードバック 型動的調整則メタ最適化問題」と称することにする．

なお，目的関数

E(x

^∗

(K))

や

∑

_K

k=1

| I (x

^∗

(k)) − I

_R

(k) |

は，最適化アルゴリズムの時系 列

x

^∗

( · )

が決まるとそれに対応して実数スカラー値が決まる汎関数であるため，以降では 便宜上のこの汎関数を

J (x

^∗

( · ))

と統一的に表すことが可能である．この汎関数の表記を用 い，以上において定式化したメタ最適化問題をまとめると以下のようになる．

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

: 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)

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