シミュレーティド・エボリューション("Simulated Evolution"，SE，SimEと略記)は大域的最適化問題への汎用の確率的メタアルゴリズムである．遺伝的アルゴリズムと同様に，生物学的進化の過程における自然淘汰原理に基づいている．1987年、当時イリノイ大学で修士課程を学んでいたラルフ・クリングの論文によって発表された。遺伝的アルゴリズムでは一つの個体が一つの問題に対する解を表していたのに対し、シミュレーティド・エボリューションは一つの問題に対する部分要素を一つの個体と見なし良い部分要素を取り込むことで探索を進める。クリングはシミュレーティド・エボリューションに対する論文は全て設計自動化学会と設計自動化論文誌で発表したため、他の研究者達によるシミュレーティド・エボリューションの研究にはVLSI回路の配線を対象とした設計自動化問題を解くためのものが多い。SimE のアルゴリズムは通常以下のような順序で行われる。SimE では解は複数の要素による集合と考え、その要素毎に評価値を設定する。例として巡回セールスマン問題を挙げると、この場合は解は各都市の集合である。評価処理は各要素の評価値の更新を行う。評価値の与え方は以下のような方法で求めるここで "O" は集合の要素 i が取りうる理論上の最適値、"C" は現在の値である。例えば巡回セールスマン問題の場合を考えると今、都市 i は都市jと都市 k に繋がっているとする。この時、i　と j の距離を "d"、 i と k の距離を "d" とし、 i と最も近い都市との距離を "d"、2番目に近い都市との距離を "d" とすると、都市 i の評価値は以下のようになる。このような評価値を各要素で求めた後に選択処理を行う。選択処理では解を "P" と "P " の二つの集合に分割する。評価値の高いものを "P" に含めるべきだが、あまり評価値のみを重視すると貪欲法による解法とほとんど変わらない結果しか得られない。このため分割はなるべく評価値が高いものが生き残る可能性があるような確率的な方法で決定する。通常以下のような擬似コードで表される処理が行われる。ここで "Random" は 0 から 1までの乱数を返すものとする。上記の処理は評価値が 1 なら "P" に選ばれ、0 なら "P " に選ばれるがそれ以外の値の場合（ほとんどの要素はそうなる）は評価値が高ければ "P" に組み込まれる可能性が高いが、外れる可能性も 0 ではない。このようにして残す要素に揺らぎを持たせることで、局所解に陥ることを防いでいる。二つに分割したら割り当て処理を行う。割り当て処理は解の制約条件を満たす範囲で "P " の要素に変化を与え新たな解を生成する方法である。変化の与え方は問題によって異なるがそれぞれの要素に変化を与える操作を何度も試行して、その良さに従って新たな解に取り込んでいくことが行われる。割り当て処理は SimE における解の改善に最も直接的な影響を与えるが、あまり貪欲にならず前の世代の改善を行うことを目標にするように設定することが好ましいとされる。利点として，常に一つの解を対象としているため，処理時間や所要メモリ量が遺伝的アルゴリズムより少なくてすむということが挙げられる．また，適応度という概念を導入し，解の要素レベルでの評価値を利用している．完全な解の評価値をもとに交叉を行うのに比べて貪欲的であることから，高速に最適に近い解へと収束することも特徴として挙げられる．

出典:wikipedia