最適化アルゴリズムのパラメータ最適調整問題の定式化

3.2.1

最適化アルゴリズムの最適パラメータ決定問題とメタ最適化

最適化アルゴリズムを動作させるとき，様々なパラメータの設定が必要である．それら を分類すると，おもに

(1)

アルゴリズムの更新式中のパラメータ

(2)

イテレーション終了条件，探索点数等のパラメータ

(3)

初期探索点の設定に関わるパラメータ

がある．

(1)

については，推奨値として一定の値に設定されるパラメータであり，メタヒュー リスティクスはこのパラメータの設定に大きく依存することを前章においてシミュレーショ ンによって示した．

(2)

については，アルゴリズムのユーザに許容されている計算時間に依 存して決められるファンクションコール回数の上限値があり，また探索点の最適解への収 束性や最適解近傍での停留が保証されているアルゴリズムであれば，その真の最適解と探 索点との近さを表す精度を規定するパラメータがある．しかし，大域的最適解を求めるこ とを目的としていながら，その解への理論的裏づけがないメタヒューリスティクスに関し ては，イテレーション回数の上限値のみが主たる終了条件のパラメータとなり，ユーザー が使用する計算機能力や最適化問題を解かねばならない期間など，ユーザーの置かれてい る環境に依存して一意に決められ，探索点数等は経験則に基づく固定値を用いるのが一般 的である．

(3)

については多くの最適化アルゴリズムが，ユーザによって探索点そのもの の初期値が与えられるか，探索範囲を指定することでその範囲でランダムに自動的にとら れることが多い．これらのことから，パラメータを操作することによるアルゴリズムの改 良は，

(1)

を軸にして行われる．

(1)

の更新則中のパラメータをベクトル

c

で表す．この次元は，パラメータの個数である．

(2)

のパラメータでイテレーション回数の上限値パラメータを

K

，複数の探索点個数を

P

と表記し，いずれもスカラーとする．また，

(3)

のパラメータは探索点の初期座標や初期変 位量などがあるが，ここでは便宜上探索点の初期座標のみとし，それを単点型アルゴリズ

Fig. 3.1: Relations among algorithm, objective function and user.

ムでは単に

x(0)

，多点型アルゴリズムでは

x

^(p)

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

と表すことにする．メタ ヒューリスティクスも含めて多くの最適化アルゴリズム

A

がソルバーとしてブラックボッ クス化されていることを考慮すると，

Fig. 3.1

のような入出力関係の図で表すことができ る．ここで，各種のパラメータ

c

が入力として与えられたもとし，最適化アルゴリズム

A

を動作させた結果得られる探索点の状態遷移を表す時系列

x

^∗

( · )

，ないしはその時系列の 最終イテレーション

K

での解

x

^∗

(K)

が出力である．ユーザはこの時系列

x

^∗

( · )

に対する目 的関数

E

の時系列

E(x

^∗

( · ))

ないしは，その最終イテレーション

K

での値

E(x

^∗

(K))

を評 価し，各種パラメータを設定しなおすことを行う．これはまさにユーザーを通したフィー ドバック系であり，

Fig. 3.1

の破線の部分はこのことを表している．

ここで

(2)

，

(3)

のパラメータは，ユーザによってあらかじめ与えられた所与のものとし

(1)

の更新則中のパラメータであるベクトル

c

の最適化を考えるものとする．最適化アル ゴリズム

A

を動作させた結果得られる探索点の状態遷移を表す時系列を

x

^∗

( · )

とし，以下 では議論簡略化のため，

Fig. 3.1

における出力は，この時系列のうちで探索点時系列の最 終イテレーション

k = K

での最適解あるいはその近似解

x

^∗

(K)

のみを考え，時系列全体

x

^∗

(·)

を目的関数で考慮する場合は考えないことにする．具体的には，更新式中にパラメー タ

c

を含むある最適化アルゴリズム

A

を実行したもとで得られる最適解ないしはその近似 解

x

^∗

(K)

を，パラメータ

c

に対するアルゴリズム

A

による写像とみなし，

x

^∗

(K) = A(c) (3.1)

とおく．ユーザが与える探索点の初期状態や計算の終了条件のもとで，パラメータ

c

を含 む最適化アルゴリズム

A

を用いて目的関数

E(x)

を最小化するとき，得られる最適解ある いはその近似解に対する目的関数値

E(x

^∗

(K))

を最小にするようなアルゴリズムパラメー タ

c

を求める問題を，解きたい最適化問題の目的関数

E

^{とアルゴリズム}

A

^{に対する「メ}

タ最適化問題」と称し，

min

c

E (x

^∗

(K)) where x

^∗

(K) = A(c)

(3.2)

または，

x

^∗

(K)

を消去することにより，

min

c

E (A(c)) (3.3)

と定式化し，このように定式化される問題を意識して最適化アルゴリズムを設計すること を単に「メタ最適化」と称することにする．なお，アルゴリズム写像

A

で与えられる最適 化アルゴリズムの力学系を改めて記号

A

を用いて表し，さらに探索点の履歴

χ(k) = {x(0), x(1), . . . , x(k)} (3.4)

にも依存させる形で具体的に，

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

と表現すると，パラメータ

c

に対する上記の差分方程式の解の時系列

x

^∗

(·)

^{における，最} 終イテレーション

k = K

での探索点

x

^∗

(K)

に対する目的関数値

E(x

^∗

(K))

を最小にする メタ最適化問題

(3.2)

は，

min

c

E (x

^∗

(K))

where x

^∗

( · ) solution to

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

(3.6)

と定式化しなおすことができる．

このような問題を意識したり定式化したりする意義は，古典的な局所的最適化手法に関 するかぎり必ずしも大きくはないが，パラメータ依存性が強いメタヒューリスティクスの アルゴリズムに対しては大きな意義をもつ．メタヒューリスティクスを適用する際，この ようなアルゴリズムパラメータの決定問題が内在しているにも関わらず，推奨値とされる パラメータ値を用いるか，ユーザ自身の試行錯誤による決定に委ねられているのが現実で ある．しかし，パラメータの推奨値をアルゴリズムの開発者が決める作業や，解きたい問 題に適したパラメータ値をユーザ自身が試行錯誤的に決める作業自体，工学的な設計問題 の一つであり，上述のようなメタ最適化問題を暗に想定していることになる．本論文では，

メタヒューリティクスの性能を支配するアルゴリズムパラメータの値を，ユーザが解きた い問題に適応させ，かつ探索点の初期状態や計算終了条件に対応させて，最適に選択する アルゴリズム設計問題を工学的最適化問題として扱っている．とくにこのメタ最適化問題 のパラメータに関する目的関数値を「解きたい最適化問題へのアルゴリズムパラメータの 適合度」と称し，この適合度に関してパラメータ

c

を最適調整することを，「アルゴリズム 特性の進化」と称することにする．次節では，メタヒューリスティクスに対し，このメタ 最適化によるアルゴリズム特性の進化の概念をより高機能化することを考える．

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