シミュレーティド・エボリューション

シミュレーティド・エボリューション(Simulated Evolution，SE，SimEと略記)は大域的最適化問題への汎用の確率的メタアルゴリズムである．遺伝的アルゴリズムと同様に，生物学的進化の過程における自然淘汰原理に基づいている．1987年、当時イリノイ大学で修士課程を学んでいたラルフ・クリングの論文によって発表された。遺伝的アルゴリズムでは一つの個体が一つの問題に対する解を表していたのに対し、シミュレーティド・エボリューションは一つの問題に対する部分要素を一つの個体と見なし良い部分要素を取り込むことで探索を進める。

クリングはシミュレーティド・エボリューションに対する論文は全て設計自動化学会と設計自動化論文誌で発表したため、他の研究者達によるシミュレーティド・エボリューションの研究にはVLSI回路の配線を対象とした設計自動化問題を解くためのものが多い。

アルゴリズム

SimE のアルゴリズムは通常以下のような順序で行われる。

(一)初期化‥ランダムで解を一つ生成する。

(二)評価処理‥解を構成する各要素に評価値を与える。

(三)選択処理‥解の構成要素を次の世代に残すものと、変化させるものの二つの集合に分ける。残す方の集合を　P_r、変化させる方の集合を P_sと表す。

(四)割り当て処理‥ P_sの各要素の状態を変化させ、 P_rと融合させ新たな解を生成する。

(五)終了条件を満たすまで 2.以下を繰り返す

SimE では解は複数の要素による集合と考え、その要素毎に評価値を設定する。例として巡回セールスマン問題を挙げると、この場合は解は各都市の集合である。

評価処理は各要素の評価値の更新を行う。評価値の与え方は以下のような方法で求める

$g_{i}={\frac {O_{i}}{C_{i}}}$$g_{i}={\frac {O_{i}}{C_{i}}}$
ここで O_iは集合の要素iが取りうる理論上の最適値、C_i は現在の値である。例えば巡回セールスマン問題の場合を考えると今、都市iは都市jと都市kに繋がっているとする。この時、i　とjの距離を d_ij、iとkの距離を d_ikとし、iと最も近い都市との距離を d¹_i、2番目に近い都市との距離を d²_iとすると、都市iの評価値は以下のようになる。

$g_{i}={\frac {d_{i}^{1}+d_{i}^{2}}{d_{ij}+d_{ik}}}$$g_{i}={\frac {d_{i}^{1}+d_{i}^{2}}{d_{ij}+d_{ik}}}$
このような評価値を各要素で求めた後に選択処理を行う。選択処理では解を P_rと P_sの二つの集合に分割する。評価値の高いものを P_rに含めるべきだが、あまり評価値のみを重視すると貪欲法による解法とほとんど変わらない結果しか得られない。このため分割はなるべく評価値が高いものが生き残る可能性があるような確率的な方法で決定する。通常以下のような擬似コードで表される処理が行われる。

function Selection(i)
  if Random < 1 -  g[i] then
    Insert(Ps, i)
  else
    Insert(Pr, i)

ここで Random は 0 から1までの乱数を返すものとする。上記の処理は評価値が1なら P_rに選ばれ、0 なら P_sに選ばれるがそれ以外の値の場合︵ほとんどの要素はそうなる︶は評価値が高ければ P_rに組み込まれる可能性が高いが、外れる可能性も 0 ではない。このようにして残す要素に揺らぎを持たせることで、局所解に陥ることを防いでいる。

二つに分割したら割り当て処理を行う。割り当て処理は解の制約条件を満たす範囲で P_sの要素に変化を与え新たな解を生成する方法である。変化の与え方は問題によって異なるがそれぞれの要素に変化を与える操作を何度も試行して、その良さに従って新たな解に取り込んでいくことが行われる。割り当て処理は SimE における解の改善に最も直接的な影響を与えるが、あまり貪欲にならず前の世代の改善を行うことを目標にするように設定することが好ましいとされる。

特徴

利点として，常に一つの解を対象としているため，処理時間や所要メモリ量が遺伝的アルゴリズムより少なくてすむということが挙げられる．また，適応度という概念を導入し，解の要素レベルでの評価値を利用している．完全な解の評価値をもとに交叉を行うのに比べて貪欲的であることから，高速に最適に近い解へと収束することも特徴として挙げられる．

参考文献

• Kling, R.M. and Banerjee, P. (1987). "A Placement Algorithm for Execution on Distributed Processors", Proceedings of the IEEE International Conference on Computer-Aided Design, pp.354-357.
• Kling, R.M. and Banerjee, P. (1990). "Optimization by Simulated Evolution with Applications to Standard Cell Placement", Proceedings of 27th Design Automation Conference, pp.20-25.
• Sadiq M.Sait、Habib Youssef、『組合せ最適化アルゴリズムの最新手法 基礎から工学応用まで』、白石洋一訳、丸善、2002年、ISBN 4-621-04998-4

関連項目

• 最適化問題
• マルコフ連鎖
• 組合せ最適化
• 遺伝的アルゴリズム
• 確率的進化手法