SimE

外国人名読み方字典

Sime

名前 サイム； シーム

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/13 02:05 UTC 版)

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

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

アルゴリズム

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

1. 初期化：ランダムで解を一つ生成する。
2. 評価処理：解を構成する各要素に評価値を与える。
3. 選択処理：解の構成要素を次の世代に残すものと、変化させるものの二つの集合に分ける。残す方の集合を P_r、変化させる方の集合を P _s と表す。
4. 割り当て処理： P _s の各要素の状態を変化させ、P _r と融合させ新たな解を生成する。
5. 終了条件を満たすまで 2.以下を繰り返す

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

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

${\displaystyle g_{i}={\frac {O_{i}}{C_{i}}}}$

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集