メタヒューリスティクスのパラメータ調整変数の種類

(c)

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

Levy

関数

(d)

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

Rosenbrock

^関数

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

以上のパラメータ調整に使われる情報の分類において，使われる情報によってはアルゴ リズムの不変性に影響を与える．例えば

(1)

の複数探索点群の状態として探索点の位置情 報を用いてパラメータ調整を行うことは，使い方によってはアルゴリズムの回転不変性は 担保することができるが，スケール不変性は損なわれてしまう．例として変位ベクトルの 大きさ

||v(k)||

^に

2

乗ノルムを用いた調整則

c(k + 1) = F (c(k), || v(k) || ), k = 0, 1, . . . , K − 1 (3.34)

を考える．座標のアフィン変換を考え，変換行列を

M

とすると，上式は

c(k + 1) = F (c(k), || M v(k) || ), k = 0, 1, . . . , K − 1 (3.35)

と書き換えられる．

M

が回転行列であれば，

|| M v(k) || = || v(k) ||

^{となり，影響は与えな} いが，

M

が回転行列でなければ，

|| M v(k) || ̸ = || v(k) ||

となり，パラメータ調整則

F

が座 標系に依存することとなる．このため，パラメータ調整則

F

は座標の変換に対してロバ ストでなくなり，与えられた問題の座標系に応じて．アルゴリズムの性能が変化する．ま た，同様の議論で変位ベクトルの大きさに

1

乗ノルムを使用した場合，回転に対する不変 性も満たさず，フラクタルな関数に対しても，大域的な探索と局所的な探索においてノル ムが変化するため，フラクタル性も満たさない．

さらに，

(4)

において目的関数値そのものを用いる調整則も目的関数値に対する不変性 を損なう．メタヒューリスティクスは一般的に，目的関数値の大小関係をもとに駆動し，

大小関係が同じであれば同じ解を得る．単調増加の変換

h

を考えた際に，目的関数値に依 存するパラメータ調整則

c(k + 1) = F (c(k), E(x(k))), k = 0, 1, . . . , K − 1 (3.36)

を，変換関数

h

を用いて目的関数のスケールを変換した場合

c(k + 1) = F (c(k), h(E(x(k)))), k = 0, 1, . . . , K − 1 (3.37)

となるが，一般的に

E(x(k)) ̸ = h(E(x(k)))

であるため，目的関数値のスケールに対する 不変性が損なわれる．そのため，順位等の序数情報に変換する必要がある．

このように，

(1)

^と

(4)

は解きたい最適化問題の変換に対してロバストでない場合があり，

アルゴリズムの性能が問題に依存する．一方で，

(2)

^と

(3)

による調整ルールは，アルゴリ ズムの内部状態

(

^{イテレーションの経過}

t(k)

^{や，探索点の更新確率}

p

s

(k))

^{に依存し，解き} たい最適化問題の変換によって陰に影響は受けるが

(

例えば問題の変換により，

p

s

(k)

に影 響が及び，結果として問題に対する性能が変化する

)

，

(1)

と

(4)

の様に施す変換から陽に 影響は受けない．言い換えれば

(2)

と

(3)

の調整ルールによる性能変化はアルゴリズム内 の問題であり，アルゴリズム内の調整則によって補償されるため，解きたい問題に依存せ ず，より問題に対してロバストであると考えられる．

以上により，本論文では，

(2)

^と

(3)

で用いられる変数や情報，そして少なくとも回転に 対する不変性が保存される

(1)

の

2

乗ノルムを用いた場合をパラメータ調整の基本と考え る．まず，

(1)

に相当する探索点の群れとしての情報として，それらの集中・分散度の指標 になるものとして，探索点の位置情報ではなく変位情報を探索点群で集約した

(a)

第

k

イテレーションでの探索点の変位の大きさ

|| v

^(p)

(k) ||

の探索点群全体での平均

|| v(k) || = 1 P √

N

∑

P p=1

|| v

^(p)

(k) || (3.38)

と，探索点と

g-best

座標の距離の探索点群全体での平均

∆

g

(k) = 1 P √

N

∑

P p=1

|| x

^(g−best)

(k) − x

^(p)

(k) || (3.39)

を変数とすることを提案する．これらは文献

[49][50]

^{などにおいて，}

PSO

^{における探索} 点群の集中・分散度を示す指標として，また探索点の大域的探索と局所的探索性能を調整 するための有力な指標として提案されたもので，手法間での公平な比較のために他のメタ ヒューリスティクスにも導入する．なお，探索点位置情報を調整則に用いることは，アル ゴリズムのスケール不変性を損なう恐れがあるが，探索点群での最良の探索点との位置関 係は，パラメータ調整にとって重要な情報であると考え，探索点群からの各探索点の群れ としての平均距離も併せて変数に採用する．

また，

(2)

の情報を用いた調整則として，

(b)

あらかじめ設定された最大イテレーション回数

K

対する第

k

イテレーション時の経 過割合

t(k) = k/K (3.40)

を，調整則のための重要な変数の一つとして設定する．文献

[44]

^において

PSO

^にも導入 されている調整則であるが，アルゴリズムの更新経過とともに大域的探索から局所的探索 へとその探索の様相を変化させるのに重要な変数と捉え，他のメタヒューリスティクスに も導入する．

パラメータ調整のための第三の変数として，

(3)

の情報を用いた調整則変数として，個々 の探索点が目的関数を改善した情報を群れとして集約するために，

(c)

^第

k

イテレーションから遡った一定イテレーション間で，目的関数値を改善させる ことに成功したイテレーション数の割合

p

^(p)s

(k), p = 1, . . . , P

^{の探索点群全体での} 平均

p

s

(k) = 1 P

∑

P p=1

p

^(p)_s

(k) (3.41)

を採用する．探索点を多点化した多点型

ES

アルゴリズムにおいて，この変数を用いた調 整則を本論文の

2

章で用いたが，公平な比較のためにも

PSO

^，

DE

^，

FA

^{等の異種のアルゴ} リズムに対し，これを変数に用いた調整則の設計を試みる．

以上により，本論文では，メタヒューリスティクスのアルゴリズムの共通のパラメータ 調整則として，これらを変数とした

3

種類の調整則を取り上げ，その有効性を以下の章に おいて確認する．具体的には，パラメータ調整を行いたいメタヒューリスティクスアルゴ リズム

A

のパラメータを

c

，このパラメータをイテレーションの経過と伴に再帰的に調整 する関数を

F

^{とすると，}

(a)

探索点変位および最良点との距離による調整則

c(k + 1) = F (c(k), ||v(k)||, ∆

g

(k)) (3.42)

(b)

イテレーション経過割合による調整則

c(k + 1) = F (c(k), t(k)) (3.43)

(c)

目的関数改善割合による調整則

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

_s

(k)) (3.44)

の

3

種類のフィードバック型動的調整則である．本論文では，与えられた解くべき最適化 問題と，それに適用したいアルゴリズムにとって，そのアルコリズム中のパラメータをイ テレーション経過とともに調整するための調整則を

GP

により進化的に獲得した結果を次 章で示す．

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