計算時間の短縮

状態が改善された粒子の数が少ないというように，局所的な探索性能が低下してい たと考えられる．本項における行動ルールは，自身より悪い相手を参照する際に，相 手の位置情報ではなくpbestの位置情報のみの参照や局所探索を行う．これは，個々 の粒子の行動における状態改善の確率を高めることを目的としている．

GAが確率的な方法を用いた多点探索最適化法と呼ばれる[1]ように，多くのメタ ヒューリスティクス手法による解探索性能は，確率論の視点から解析することもで

きる[2]．例えば，GAにおける解探索は，交叉と突然変異，自然淘汰のような遺伝

操作に加えて，適用問題の設計空間の構造に基づいて求められる解の精度が決定さ れる．まず，適用問題の設計空間におけるPOPの恩恵を受けやすい交叉方法を開発 することで，今の世代より優れた子どもを生成する確率が高くなる．次に，自然淘 汰においてエリート選択を用いることで，優れた個体の生存確率と次の世代におい てより良い子どもを生成する確率を高めることができる．ただし，エリートを保存 する割合を大きくすることで個体群の収束も早まるため，適切な割合を設定する必 要がある．また，突然変異による遺伝操作は，解探索の初期収束を防ぐ効果がある．

しかしながら，エリートの割合と同様に，過度な突然変異は優れた子どもの生成を 妨げるため，適切な値の設定が求められる．

本項におけるCAPSOの行動ルールは，上述のGAの遺伝操作のように，個々の 粒子の状態改善確率に着目した改良を行っている．さらに，個々の粒子の行動の改 善は，粒子間の相互作用にも強く影響を与えることから，粒子群全体の解探索能力 の向上につながると考えられる．

ができ，手法の適用しやすさを損なう可能性もある．したがって，本項では，参照 相手の候補の選択を行うことで，CAPSOの探索性能を損なうことなく距離計算の 対象を減らすことによる計算時間の短縮を試みる．3.1.4で述べた各粒子の行動手順 において，計算時間を短縮するよう改良した行動は以下の通りである．

STEP2-0 t= 0のときのみ，各粒子をK個のクラスタへランダムに割り振る

STEP2-1 K平均法に基づいて各粒子をクラスタリングする

STEP2-2 K個の各クラスタからランダムに1体ずつ粒子を選択する

STEP2-3 選択されたK個の粒子との距離を計算する

STEP2-4 K個の粒子に対して距離の近い順に順位付けし，ルーレット選択によっ

て参照相手とする粒子を決定する

STEP2-5 参照相手との関係性に基づいて選択した行動によって次の状態の候補を

生成する

STEP2-6 生成した次の状態の候補を評価する

STEP2-7 次の状態の候補から最良の状態を選択し，今以上の状態であれば更新を

行い，そうでなければ悪化受理率に従って確率的に更新するかどうか決 定する

この手順において，STEP2-0，および2-1は，各粒子ではなく，全体の処理として 実行される．粒子群の位置関係の把握と距離計算の短縮を行うために，本論文では K平均法[3]による粒子のクラスタリングを行う．そして，K個に割り振られた粒子 のクラスタからそれぞれ1体ずつ代表を選択して距離計算を行うことで，1体の粒 子が行う距離計算の回数をK回に削減できる．K平均法のアルゴリズムは以下の通 りである．

1. n体の粒子に対してランダムにクラスタを割り振る．

2. 割り振った粒子を基に各クラスタの中心V_jを計算する．計算はクラスタjに 割り振られた粒子の各要素の平均値を求める．

3. 各粒子x_iと各V_j との距離を求め，x_iを最も近い中心のクラスタに割り当て 直す．

4. すべてのxiのクラスタが変化しなかったときにアルゴリズムを終了する．そ うでなければ，新しく割り振られたクラスタを用いて2.を行う．

ここで，粒子xi(i= 1, ..., n)の位置は，最適化に用いる設計変数ではなく，クラス タリングのためのベクトルを用いる．Kはクラスタ数を表しており，割り振られた 粒子のベクトルに基づいてクラスタの中心V_jを求め，各粒子x_iのベクトルとクラ スタの中心v_jとの距離を計算することで適切なクラスタを決定する．なお，K平均 法で用いるベクトル，および距離の計算方法は，最適化に用いる設計変数と粒子間 の距離計算をそのまま用いることも可能である．例えば，関数最適化問題における ベクトルは各次元の変数値，距離計算はユークリッド距離を最適化と同じようにク ラスタリングに用いる．

クラスタ1 クラスタ2

クラスタ3

クラスタ4

距離計算を行う粒子 選択されなかった粒子 選択された粒子

クラスタ1 クラスタ2

クラスタ3

クラスタ4

距離計算を行う粒子 選択されなかった粒子 選択された粒子

図 4.5: クラスタリングと距離計算対象の選択

K平均法では，粒子間の位置関係からベクトルを生成してクラスタリングが行わ れる．そして，各クラスタからそれぞれランダムに選ばれたK体の粒子に対しての み距離計算が行われることになる．これにより，図4.5に示すように，クラスタリ ングによって距離の近い粒子が同じクラスタに割り振られることで，各粒子が参照 相手として選ばれる確率は全粒子を対象にルーレット選択したものと同等のになる と考えられる．CAPSOにおいて，距離計算された参照相手の候補は，距離の近い 順に適応度が与えられる．そのため，位置関係に基づいてクラスタリングとそれら の代表を対象としたルーレット選択を行うことで各粒子が選択される確率は，それ ぞれの粒子の位置関係に基づいていることから，全粒子を対象にルーレット選択し たものと同程度の確率であると予想される．また，K平均法においても距離計算や クラスタリングのための計算時間が必要となる．しかしながら，繰り返し回数t = 0 のとき以降は，前回の結果を用いて再度クラスタリングを行われる．このとき，1回

の探索における各粒子の位置の変化は小さいことから，再度クラスタリングを行う 際の計算時間は短くなると予想される．したがって，全粒子との距離計算と比較し て，この改良案は計算時間を短縮できると考えられる．