シミュレーティド・エボリューション
SimE のアルゴリズムは通常以下のような順序で行われる。
初期化:ランダムで解を一つ生成する。
評価処理:解を構成する各要素に評価値を与える。
選択処理:解の構成要素を次の世代に残すものと、変化させるものの二つの集合に分ける。残す方の集合を Pr、変化させる方の集合を P s と表す。
割り当て処理: P s の各要素の状態を変化させ、 P r と融合させ新たな解を生成する。
終了条件を満たすまで 2.以下を繰り返す
SimE では解は複数の要素による集合と考え、その要素毎に評価値を設定する。例として巡回セールスマン問題を挙げると、この場合は解は各都市の集合である。
評価処理は各要素の評価値の更新を行う。評価値の与え方は以下のような方法で求める
g i = O i C i {\displaystyle g_{i}={\frac {O_{i}}{C_{i}}}}
ここで Oi は集合の要素 i が取りうる理論上の最適値、Ci は現在の値である。例えば巡回セールスマン問題の場合を考えると今、都市 i は都市jと都市 k に繋がっているとする。この時、i と j の距離を dij、 i と k の距離を dik とし、 i と最も近い都市との距離を di、2番目に近い都市との距離を di とすると、都市 i の評価値は以下のようになる。
g i = d i 1 + d i 2 d i j + d i k {\displaystyle g_{i}={\frac {d_{i}^{1}+d_{i}^{2}}{d_{ij}+d_{ik}}}}