3.8.1 近傍の生成方法
3.6節まで行った解析を基に，メタヒューリスティクスの探索構造，特に近傍の生成のパ ターンを分類し，考察する。
まず，近傍の生成方法について着目する。近傍は，探索点xを基準とした，更新式に含ま れる乱数に基づく摂動によって生成される。この摂動は，移動ベクトルvの終点となる近傍 解xˆが生成される範囲となる。すなわち，近傍は更新される場合の移動ベクトルv =xˆ−x の生成方法に依存する。v= xˆ−xの生成方法は，(a)基底ベクトルの線形結合で生成する 場合（PSO，FA），(b)探索点同士の組み合わせで生成する場合（DE，ABC），(c)特定の 確率分布に従うランダムウォークで生成する場合（CS），の三つに分かれる。
第3章 メタヒューリスティクスの探索構造の解析 56
(a)基底ベクトルの線形結合
(a)の場合，図3.2，図3.3で示されるように，近傍解xˆは，基底ベクトルの線形結合によ り張られる空間内に生成される。近傍は，基底ベクトルの係数や要素として使用する，乱 数に基づく摂動によって得る空間となる。このため，近傍の偏りは，基底ベクトルの方向 や摂動のスケールによって調整される。
(b)解同士の組み合わせ
(b)の場合，図3.4，図3.5で示されるように，近傍解xˆは，解同士の組み合わせによっ て生成される可能性がある空間内に生成される。近傍は，「解の中で組み合わせる要素の選 択」や「要素の組み合わせ」において使用する，乱数に基づく摂動によって得る空間とな る。このため，近傍の偏りは，解同士の要素の組み合わせ方，摂動のスケール，組み合わ せる解同士の距離によって調整される。
(c)特定の確率分布に従うランダムウォーク
(c)の場合，図3.6で示されるように，近傍解xˆは，参照点を始点とする乱数ベクトルs によって生成される。近傍は，乱数ベクトルsの要素として使用する，乱数に基づく摂動 によって得る空間となる。このため，近傍の偏りは，参照点の選び方や，摂動のスケール
（確率分布の種類や形状）によって調整される。(a)や(b)の場合に比べて，摂動によって 得る近傍が広い。
3.8.2 ベクトルの種類
v = xˆ−xの生成において，活用されるベクトルは，(a)差分ベクトルu（PSO，FA，DE， ABC）と，(b)乱数ベクトルs（FA，CS），の二つに分かれる。
(a)差分ベクトルu
(a)の場合，差分ベクトルuが活用される箇所は，3.8.1項の(a)（PSO，FA），DE，ABC で分けられる。3.8.1項の(a)では，基底ベクトルとして差分ベクトルuを使用する。DE
第3章 メタヒューリスティクスの探索構造の解析 57
では，解同士の組み合わせで用いる解を生成するときに差分ベクトルuを使用する。ABC では，解同士の組み合わせが行われる要素における摂動として差分ベクトルuを使用する。
差分ベクトルuの使用は，3.7節で定義した多様化・集中化の実現状態へ影響を与える ことが考えられる。差分ベクトルuを使用する場合，その終点として特殊な解・探索点を 設定する。PSOでは，探索点から式(2.12)で定義されるp-bestまでの差分ベクトルup−best と，探索点から式(2.13)で定義されるg-bestまでの差分ベクトルug−bestを使用する。FA では，探索点から式(2.17)で定義されるbetterまでの差分ベクトルubetterを使用する。DE では，ランダムに選ばれた探索点間の差分ベクトルubetweenを使用する。ABCでは，探索 点からランダムに選ばれた探索点までの差分ベクトルurandomを使用する。
差分ベクトルの活用は，基本的に探索点分布を縮小する操作となるため，探索過程で徐々 に特定の領域へ近傍が狭まる。しかし，終点として設定する解の種類によって，多様化・
集中化の実現状態に対する影響の強さは異なる。例えば，g-bestやbetterなどの良い解ま での差分ベクトルの活用は，特定の領域に対する指向性を促進する操作となる。探索点間 の差分ベクトルの活用は，探索序盤では探索点分布が広いため，特定の領域・方向に対す る指向性を抑制する操作となり，探索終盤では探索点分布が狭いため，特定の領域・方向 に対する指向性を促進する操作となる。したがって，差分ベクトルの活用は，多様化・集 中化の実現状態へ影響を与える上に，探索過程でその状態を調整する効果を持つことから，
3.7節で述べた探索戦略の実現へ貢献することが考えられる。しかし，終点として設定する 解が探索過程で同一の場合，その領域に対する指向性が促進され，短期的に探索点分布が 縮小する傾向がある。このため，探索過程で適切な多様化・集中化を実現するために，差 分ベクトル以外のベクトルの活用や，差分ベクトルのスケールの調整が重要である。
(b)乱数ベクトルs
(b)の場合，乱数ベクトルsが活用される箇所は，3.8.1項の(a)あるいは(b)（FA），3.8.1 項の(c)（CS）で分けられる。3.8.1項の(a)あるいは(b)では，基底ベクトルの線形結合や 解同士の組み合わせにおいて，乱数ベクトルsを使用する。例として，FAでは，基底ベク トルとして一様乱数ベクトルεを使用する。3.8.1項の(c)では，ランダムウォークにおい て，乱数ベクトルsを使用する。例として，CSでは，L´evy乱数ベクトルL(β)を使用する。
乱数ベクトルはスケールや方向が確率的に決定されるため，ベクトルの終点を任意に設
第3章 メタヒューリスティクスの探索構造の解析 58
定できず，特定の領域・方向への指向性が存在しない。乱数ベクトルの活用は，探索点分 布の状態に関わらず，一定以上の広がりを有する近傍を生成するため，摂動・分布を拡大 する操作となる。一方で，乱数ベクトルを活用しても，探索過程で摂動・分布の拡大・縮 小を自律的に調整することはできない。このため，乱数ベクトルの活用は，多様化・集中 化の実現状態の調整に対する貢献度が低いことが考えられる。
しかし，乱数が従う分布やステップサイズのスケールは，3.7節で定義した多様化・集中 化の実現状態へ影響を与えることが考えられる。CSでは，ヘヴィーテイル型のL´evy分布 を使用している。式(1.12)で定義される実数値一様分布UNを使用した場合，確率分布に 偏りがないため，多様化・集中化の実現状態へ影響を与えることができない。これに対し
て，式(1.14)で定義される正規分布Nや，ヘヴィーテイル型の確率分布は，参照点から距
離が近い位置の確率が高く，参照点から距離が離れた位置の確率が低い形状となるため，
特定の領域に対する指向性を促進する効果を生み出す。特に，ヘヴィーテイル型の分布で は，距離が離れた位置の確率がある程度残るため，探索点分布・摂動を拡大する，特定の 領域に対する指向性を抑制する効果も生み出す。さらに，乱数が従う分布やステップサイ ズのスケールを変更することで，摂動の傾向をある程度調整することが可能である。この ため，探索過程で摂動の傾向を動的に変更することで，多様化・集中化を調整する効果を 生み出すことが考えられる。
3.8.3 乱数の使用箇所
数理計画法とは異なり，連続値最適化問題を対象としたメタヒューリスティクスは乱数 を使用する。乱数はvの生成において使用される。乱数が使用される箇所は，(a)ベクトル の係数（PSO，ABC），(b)ベクトルの要素（乱数ベクトル）（FA，CS），(c)解の組み合わ せ（DE，ABC），の三つに分かれる。
(a)ベクトルの係数
(a)の場合，ベクトルの係数における乱数は多様化・集中化の実現に対して様々な効果を 生み出す。ベクトルの係数が定数のみである場合，ベクトルの終点は一意に決定されるた め，乱数に基づく摂動を生み出すことができない。特定の領域・方向に対する指向性を促
第3章 メタヒューリスティクスの探索構造の解析 59
進する操作となる。これに対して，基底ベクトルや差分ベクトルの係数に乱数を含む場合，
ベクトルの終点は一定以上の摂動の中で生成されるため，係数が定数である場合に比べて，
多様な近傍を生み出すことができる。これは，摂動を拡大する操作，特定の領域・方向に 対する指向性を抑制する操作となる。
また，ベクトルの係数として使用する乱数は，式(1.12)の実数値一様分布UR，式(1.14) の正規分布N，式(1.15)のL´evy分布Lなどの確率分布に従う。一様乱数の区間のサイズ が1以下の場合（PSOやFA）や，乱数の大きさが小さな値である確率が高い（CS）場合，
探索点分布よりも小さなスケールで摂動が起こる可能性が高い。これは，探索点分布を縮 小する操作となる。これに対して，一様乱数の区間のサイズが1以上であり，負の値もと る場合（ABC）は，探索点分布よりも小さなスケールで摂動が起こる可能性もあれば，大 きなスケールで摂動が起こる可能性もある。これは，摂動・探索点分布を拡大・縮小する 操作となる。
さらに，ベクトルの係数に含まれる乱数の影響は探索過程で変化する。探索序盤では，
使用するベクトルのノルムが大きいため，摂動が大きい。探索過程で，徐々にベクトルの ノルムが小さくなるため，乱数の影響が軽減された結果，探索終盤では特定の領域に探索 点分布が縮小する。したがって，ベクトルの係数における乱数の活用は，多様化・集中化 の実現状態へ影響を与える上に，探索過程でその状態を調整する効果を持つことから，3.7 節で述べた探索戦略の実現へ貢献することが考えられる。
(b)ベクトルの要素（乱数ベクトル）
(b)の場合，参照点から直接摂動を与え，参照点を中心とした近傍を生成する。ベクトル の要素として乱数を使用した場合，探索点分布の状態に関わらず，一定以上の広がりを有 する近傍を生成するため，摂動・分布を拡大させる操作となる。
しかし，3.8.2項の(b)で述べたように，近傍解xˆへの方向を設定することができないた
め，特定の領域・方向に対する指向性が存在しない。また，乱数の種類により，近傍内で 近傍解xˆが生成される確率に偏りが生じる。このため，乱数ベクトルの活用は，多様化・
集中化の実現状態の調整に対する貢献度が低いことが考えられる。
一方，乱数が従う分布やステップサイズのスケールを変更することで，近傍をある程度 調整することが可能であることから，探索過程で摂動の傾向を動的に変更することで，多