セルオートマトン PSO のアルゴリズム

提案手法では，次の手順で探索が行われる．

STEP1 各粒子の初期状態をランダムに決定し，繰り返し回数t= 0とする

STEP2 各粒子がルールに基づいて行動する

STEP3 t=t+ 1とし，tが設定された回数となるまでSTEP2を繰り返す

ここで，STEP2は各粒子へそれぞれ適用される．各粒子の行動は以下の通りであ

る．

STEP2-1 全粒子との距離を計算する

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

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

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

生成する

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

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

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

提案手法では，STEP2-1において，各粒子が他の粒子との距離を求めることで個々 の近傍環境との関係性を認識する．STEP2-2では，ルーレット選択によって参照相 手を決定することで，低確率で遠い粒子を参照した大域的な探索も可能としている．

STEP2-3では後述する手順で行動し，生成された次の状態の候補は，STEP2-5の

ように自身の状態が改善するなら更新を行い，そうでなければ悪化受理率に従って 更新，または更新せずにその場に留まるかどうか決定する．ここで，悪化受理とは，

行動によって評価関数値が悪化するような現在より悪い状態を新たな状態として採 用することである．個々の粒子は状態を改善することを目的に行動している．その ため，状態の悪化を受理しないことで，状態の改善に専念することができる．しか しながら，局所解へ陥った際には，状態の悪化を受理しなければそれ以上の状態改 善を行うことが困難となる．したがって，提案手法では，確率的に悪化を受理する ことで，局所解への過度な収束を防ぎながら解探索の効率化を図る．

上述のSTEP2-3において，各粒子の行動は，設計空間と行動ルールに基づいて決

定される．例えば関数最適化問題へ提案手法を適用する際，設計変数は既存のPSO と同様に各次元の変数値である．行動ルールは，参照相手との関係性に基づいて図 3.5に示す3つの移動方法の1つ，または複数を適用することで次の状態の候補を生 成する．また，粒子間の距離計算にはユークリッド距離を用いる．

x_t x_t+1 x_t+1 x_t

x_t x_t+1

(a) 接近（近づく） (b) 反発（離れる） (c) 均衡（距離を保って移動）

x_t x_t+1

x_t x_t+1 xx_t+1t+1 xx_tt

x_t x_t+1

x_t x_t+1

(a) 接近（近づく） (b) 反発（離れる） (c) 均衡（距離を保って移動）

図 3.5: 粒子の移動

n次元の変数を持つ関数へ適用する際，ある粒子Aについて，探索の繰り返し回 数がtのときの設計変数をx^t_A =⁽x^t_A1, x^t_A2, ..., x^t_An⁾ ，状態をs^t_A=x^t_Aと表すと，粒 子Bを参照した際の次の状態の候補c^t+1_A を生成するときの各移動方法の手順は以下 の通りである．

＜接近＞

STEP 1A 各次元の変数値のカウンターi= 0とする

STEP 2A 粒子AとBとの距離に基づいて算出した移動量dispと次元iにおける 変数値の差|x^t_Ai−x^t_Bi |を比較し，小さい方を移動の上限値Lとする STEP 3A [0 : 1]の一様乱数rと移動の上限値Lから次元iの移動量を∆xAi =r×L

とする STEP 4A x^t_A

i ≤x^t_B

i なら次の状態の候補の変数値をx^t+1_Ai =x^t_A

i + ∆x_Aiとし，

x^t_Ai > x^t_Biならx^t+1_Ai =x^t_Ai −∆x_Aiとする

STEP 5A i=i+ 1とし，i < nならSTEP 2Aへ戻り，候補の変数値が決定すれ ば終了する

＜反発＞

STEP 1B 各次元の変数値のカウンターi= 0とする

STEP 2B 粒子AとBとの距離に基づいて算出した移動量dispを移動の上限値L とする

STEP 3B [0 : 1]の一様乱数rと移動の上限値Lから次元iの移動量を∆x_Ai =r×L とする

STEP 4B x^t_Ai ≤x^t_Biなら次の状態の候補の変数値をx^t+1_Ai =x^t_Ai−∆xAiとし，

x^t_A

i > x^t_B

iならx^t+1_A

i =x^t_A

i + ∆x_Aiとする

STEP 5B i=i+ 1とし，i < nならSTEP 2Bへ戻り，候補の変数値が決定すれ ば終了する

＜均衡＞

STEP 1C 各次元の変数値のカウンターi= 0とする

STEP 2C 粒子AとBとの距離に基づいて算出した移動量dispと次元iにおける 変数値の差|x^t_Ai−x^t_Bi |を比較し，小さい方を移動の上限値Lとする STEP 3C [0 : 1]の一様乱数rと移動の上限値Lから次元iの移動量を∆xAi =r×L

とする

STEP 4C 接近のSTEP 4Aと反発のSTEP 4Bのどちらかをランダムに適用する ことで次の状態の候補の変数値x^t+1_Ai を決定する

STEP 5C i=i+ 1とし，i < nならSTEP 2Cへ戻り，候補の変数値が決定すれ ば終了する

ここで，粒子間の距離に基づいて決定される移動量dispと参照相手との関係性に 基づく行動ルールは提案手法の性能に大きく影響することから，3.2で述べる数値実 験において，適切なパラメータの検討を行う．また，本論文では，パラメータ設定 を容易にするために，位置や移動量，距離をすべて[0 : 1]へ正規化して扱うことと する．