6 適応化のフレームワーク に基づく メタヒューリスティクス
本章では，7章で適応化のフレームワークに基づき適応型メタヒューリスティクスを開 発することを踏まえ，適応化設計論に基づく新たなメタヒューリスティクスを設計する。
高い適応能力を有するように設計したメタヒューリスティクスを適応化すれば，優れた適 応能力・探索性能を有する適応型メタヒューリスティクスの構築が期待できる。
第6章 適応化のフレームワークに基づくメタヒューリスティクス 92
vi(k)=
xˆi(k)−xi(k), f (ˆxi(k)) < f (xi(k))
0, otherwise (6.2)
xi(k+1)=xi(k)+vi(k) (6.3)
ただし，α, β≥ 0はパラメータ，ubetter = xbetter,i(k)−xi(k)，urandom =xr−xi，xbetter,iは 式(2.17)で定義されるbetter，r, iは整数値一様分布UZ(1,m)に従う乱数，R,ϕ∈RN×N は対角行列であり，Rの対角要素は実数値一様分布UR(0,1)に従う乱数，ϕの対角要素は 実数値一様分布UR(−0.5,0.5)に従う乱数である。
図6.1に，提案手法の近傍生成について示す。式(6.1)で表されるように，提案手法では，
ˆ
xi−xiiが，探索点xiからランダムの探索点xrに向かう差分ベクトルurandomと，探索点xi からbetterxbetter,iに向かう差分ベクトルubetterの線形結合で表され，近傍解xˆiは基底ベク トルの係数の乱数R,ϕによる摂動に基づく近傍内に生成される。提案手法は改善移動で あるため，探索点xiは目的関数値が改善した場合，近傍解xˆiへ移動する。
この探索構造は，4.3節のADMの説明で述べた「優れた探索構造となる必要条件」に 基づいて構成されている。探索点間の差分ベクトルubetter，urandomを用いることで，良い 解を活用しながら，特定の領域・方向に対する指向性を促進することが可能となる。そし て，基底ベクトルの係数に一様乱数を用いることで，摂動・探索点分布の縮小が可能とな る。また，一様乱数ϕの区間を[−0.5,0.5]とすることで，urandomとは逆の方向にも摂動を 生じさせ，一定以上の摂動の拡大が可能となる。さらに，これらの操作は探索過程で多様 化・集中化に対する影響が変化するため，有効な探索戦略が実現可能な構造である。以上 から，提案手法は，3章の解析に基づく優れた探索構造を有しているため，高い適応能力・
探索性能が期待できる。
以下に，本論文で提案した適応化のフレームワークに基づくメタヒューリスティクス（提 案手法）のアルゴリズムを示す。アルゴリズムの終了条件をk =kmaxとする。評価回数は T =m(kmax+1)となる。探索点の初期位置を初期配置領域IS = [a, c]N ⊂RN内に与える。
【提案手法のアルゴリズム】
Step 0:［準備］
探索点数m，パラメータα, β ≥ 0，最大反復回数kmaxを定め，反復回数をk = 1と する。
第6章 適応化のフレームワークに基づくメタヒューリスティクス 93
Step 1:［初期化］
探索点の初期位置xi(k)（i= 1,2,· · · ,m）を初期配置領域IS内にランダムに与える。
Step 2:［近傍の生成］
各探索点xi(k)について，優良探索点群Betteri，近傍解xˆi(k)を
Betteri = {xℓ(k)| f (xℓ(k))< f (xi(k)); ℓ =1,· · · ,m}
ˆ
xi(k) =
xi(k)+αRubetter +βϕurandom, Betteri ,∅
xi(k)+βϕurandom, otherwise
より，生成する。
ただし，ubetter =xi,better(k)−xi(k)，urandom= xr(k)−xi(k)，xi,better(k)∈Betteriは 優良探索点群Betteriからランダムに選ばれた探索点，∅は空集合，rは整数値一 様分布UZ(1,m)に従う乱数，R,ϕ∈RN×Nは対角行列であり，Rの対角要素は実数 値一様分布UR(0,1)に従う乱数，ϕの対角要素は実数値一様分布UR(−0.5,0.5)に従 う乱数である。
Step 3:［探索点の更新］
各探索点xi(k)について，
vi(k)=
xˆi(k)−xi(k), f (ˆxi(k))< f (xi(k))
0, otherwise
xi(k+1)=xi(k)+vi(k)
より，更新する。
Step 4:［終了判定］
k=kmaxならば，探索を終了する。さもなければ，k :=k+1とし，Step 2へ戻る。
第6章 適応化のフレームワークに基づくメタヒューリスティクス 94
図6.1： 提案手法の近傍の生成