|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
シミュレーティド・エボリューション(''Simulated Evolution''，SE，SimEと略記)は大域的最適化問題への汎用の確率的メタアルゴリズムである．遺伝的アルゴリズムと同様に，生物学的進化の過程における自然淘汰原理に基づいている．1987年、当時イリノイ大学で修士課程を学んでいたラルフ・クリングの論文によって発表された。遺伝的アルゴリズムでは一つの個体が一つの問題に対する解を表していたのに対し、シミュレーティド・エボリューションは一つの問題に対する部分要素を一つの個体と見なし良い部分要素を取り込むことで探索を進める。 クリングはシミュレーティド・エボリューションに対する論文は全て設計自動化学会と設計自動化論文誌で発表したため、他の研究者達によるシミュレーティド・エボリューションの研究にはVLSI回路の配線を対象とした設計自動化問題を解くためのものが多い。 == アルゴリズム == SimE のアルゴリズムは通常以下のような順序で行われる。 # 初期化：ランダムで解を一つ生成する。 # 評価処理：解を構成する各要素に評価値を与える。 # 選択処理：解の構成要素を次の世代に残すものと、変化させるものの二つの集合に分ける。残す方の集合を ''Pr''、変化させる方の集合を ''P s'' と表す。 # 割り当て処理： ''P s'' の各要素の状態を変化させ、 ''P r'' と融合させ新たな解を生成する。 # 終了条件を満たすまで 2.以下を繰り返す SimE では解は複数の要素による集合と考え、その要素毎に評価値を設定する。例として巡回セールスマン問題を挙げると、この場合は解は各都市の集合である。 評価処理は各要素の評価値の更新を行う。評価値の与え方は以下のような方法で求める : ここで ''Oi'' は集合の要素 i が取りうる理論上の最適値、''Ci'' は現在の値である。例えば巡回セールスマン問題の場合を考えると今、都市 i は都市jと都市 k に繋がっているとする。この時、i と j の距離を ''dij''、 i と k の距離を ''dik'' とし、 i と最も近い都市との距離を ''d1i''、2番目に近い都市との距離を ''d2i'' とすると、都市 i の評価値は以下のようになる。 : このような評価値を各要素で求めた後に選択処理を行う。選択処理では解を ''Pr'' と ''P s'' の二つの集合に分割する。評価値の高いものを ''Pr'' に含めるべきだが、あまり評価値のみを重視すると貪欲法による解法とほとんど変わらない結果しか得られない。このため分割はなるべく評価値が高いものが生き残る可能性があるような確率的な方法で決定する。通常以下のような擬似コードで表される処理が行われる。 function Selection(i) if ''Random'' < 1 - g then Insert(Ps, i) else Insert(Pr, i) ここで ''Random'' は 0 から 1までの乱数を返すものとする。上記の処理は評価値が 1 なら ''Pr'' に選ばれ、0 なら ''P s'' に選ばれるがそれ以外の値の場合（ほとんどの要素はそうなる）は評価値が高ければ ''Pr'' に組み込まれる可能性が高いが、外れる可能性も 0 ではない。このようにして残す要素に揺らぎを持たせることで、局所解に陥ることを防いでいる。 二つに分割したら割り当て処理を行う。割り当て処理は解の制約条件を満たす範囲で ''P s'' の要素に変化を与え新たな解を生成する方法である。変化の与え方は問題によって異なるがそれぞれの要素に変化を与える操作を何度も試行して、その良さに従って新たな解に取り込んでいくことが行われる。割り当て処理は SimE における解の改善に最も直接的な影響を与えるが、あまり貪欲にならず前の世代の改善を行うことを目標にするように設定することが好ましいとされる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「シミュレーティド・エボリューション」の詳細全文を読む スポンサード リンク
|