アルゴリズムの流れとは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキング

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/18 03:28 UTC 版)

「進化戦略」の記事における「アルゴリズムの流れ」の解説

まとめると(1+1)-ES のアルゴリズムは以下のような流れで行われる。 x とσの初期値をランダムで決める。突然変異操作よりx の近傍 x' を求める（求め方は上述の概要を参照） f(x) < f(x') であるなら、x = x' とする。 1/5 ルールに従いσを更新する。適当な終了条件が満たされるまで2. 以下の操作を繰り返す。

※この「アルゴリズムの流れ」の解説は、「進化戦略」の解説の一部です。
「アルゴリズムの流れ」を含む「進化戦略」の記事については、「進化戦略」の概要を参照ください。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/18 03:28 UTC 版)

「進化戦略」の記事における「アルゴリズムの流れ」の解説

アルゴリズムの流れをまとめると(μ,λ)-ES系のアルゴリズムは以下のようになる。 μ個の個体をランダムに生成して、それぞれの個体の目的関数を評価する。いくつかの個体に対しては組み換え操作を行う。各個体を適当に選択し、その個体に突然変異操作を行った個体を新たにλ個生成する。それぞれの個体の目的関数を評価する。生き残る個体を決定する(μ,λ)-ESの場合は新たに生成したλ個の個体(λ>μ)の内上位μ個を選び、残りを削除する。 (μ+λ)-ESの場合は新たに生成したλ個の個体と生成元のμ個の個体を混ぜ合わせ上位μ個の個体を選び、残りを削除する。終了条件を満たすまで2. 以下の操作を繰り返し、最終的に最も成績の良い個体の探索ベクトルを解として出力する。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/04/13 06:46 UTC 版)

「進化的プログラミング」の記事における「アルゴリズムの流れ」の解説

上記の記述通り、進化的プログラミングは現在決まった構造を持たない。そこで、ここでは D.B.Fogel が提案した実数関数の探索アルゴリズムの流れを述べる。 N 個の個体(この場合は関数の引数)を用意して、これにランダムで初期値を設定する。個体のそれぞれのコピーをつくる。 2. で作った各コピーに正規乱数（乱数列参照）を加える。 3. の操作で作られた新しい N 個の個体と、元の個体を混ぜた 2N 個の各個体に対して評価値を求める、評価値の求め方は以下の通り。評価値を求める個体以外の個体をランダムで q 個選択する。選んだ q 個の個体のうち、対象の個体より成績が悪い個体（最大値を求める場合は、対象の個体より関数の値が小さい個体）の数をその個体の評価値とする。評価値順に個体をソートする。下位 N 個の個体を削除する。終了条件を満たすまで2. 以下の操作を繰り返す。残った中で最も成績の良い個体を「解」として出力する。上記のアルゴリズムの場合、コピーした個体に正規乱数を加える操作が突然変異の操作にあたる。特徴としては、評価値の与え方がある。この評価値は集団中で最も優れた個体の評価値は q になり、最も劣っている個体の評価値は 0 になるがそれ以外の個体の評価値は一定ではなく比較的優秀な個体の評価値の方が高くなる確率が高い確率的関数であるといえる。このような評価値を与えることを進化的プログラミングの特徴に挙げることもある。ただし、この評価値の与え方および個体の残し方は全くの拡張も変更も行わずに他の進化的アルゴリズム（遺伝的アルゴリズムや進化的戦略）に適用可能である。

※この「アルゴリズムの流れ」の解説は、「進化的プログラミング」の解説の一部です。
「アルゴリズムの流れ」を含む「進化的プログラミング」の記事については、「進化的プログラミング」の概要を参照ください。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/04 07:13 UTC 版)

「線型探索」の記事における「アルゴリズムの流れ」の解説

下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。 10 7 12 6 1 4 3 線形探索では、最初の要素である10を見る。 10は1ではないので、次の要素7を見る。 7は1ではないので、次の要素 12を見る。 12は1ではないので、次の要素6を見る。 6は1ではないので、次の要素1を見る。1を見つけることができた。最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。

※この「アルゴリズムの流れ」の解説は、「線型探索」の解説の一部です。
「アルゴリズムの流れ」を含む「線型探索」の記事については、「線型探索」の概要を参照ください。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 02:02 UTC 版)

「A*」の記事における「アルゴリズムの流れ」の解説

A* のアルゴリズムの実装を以下に示す。このOPEN リスト実装は後に述べるように遅いことを記しておく。スタートノード（ S {\displaystyle S} ）を作成する。また計算中のノードを格納しておくための優先度付きキュー OPEN リストと、計算済みのノードを格納しておくCLOSE リストを用意する。(名前は「リスト」だが、これらの実際のデータ構造は必ずしも連結リストである必要はない。) ゴールは必ずしも１つである必要はないので、ゴール条件を満たすノード集合を G {\displaystyle G} と呼ぶことにする。スタートノードをOpen リストに追加する、このとき g ( S ) {\displaystyle g(S)} = 0 {\displaystyle 0} であり f ( S ) {\displaystyle f(S)} = h ( S ) {\displaystyle h(S)} となる。また Close リストは空にする。 Open リストが空なら探索は失敗とする（スタートからゴールにたどり着くような経路が存在しなかったことになる）。 Open リストに格納されているノードの内、最小の f ( n ) {\displaystyle f(n)} を持つノード n {\displaystyle n} を1つ取り出す。同じ f ( n ) {\displaystyle f(n)} を持つノードが複数ある場合、タイブレーク手法によりどれかのノードを選択する。 n ∈ G {\displaystyle n\in G} であるなら探索を終了する。それ以外の場合は n {\displaystyle n} を Close リストに移す。 n {\displaystyle n} に隣接している全てのノード（ここでは隣接ノードを m {\displaystyle m} とおく）に対して以下の操作を行う f ′ ( m ) = g ( n ) + C O S T ( n , m ) + h ( m ) {\displaystyle f'(m)=g(n)+COST(n,m)+h(m)} を計算する、ここで C O S T ( n , m ) {\displaystyle COST(n,m)} はノード n から m へ移動するときのコストである。また g(n) は g ( n ) = f ( n ) − h ( n ) {\displaystyle g(n)=f(n)-h(n)} で求めることができる。 m の状態に応じて以下の操作を行うm が Open リストにも Close リストにも含まれていない場合 f ( m ) ← f ′ ( m ) {\displaystyle f(m)\leftarrow f'(m)} とし m を Open リストに追加する。このとき m の親を n として記録する。 m が Open リストにある場合、 f ′ ( m ) < f ( m ) {\displaystyle f'(m)<f(m)} であるなら、m をOpenから削除し、 f ( m ) ← f ′ ( m ) {\displaystyle f(m)\leftarrow f'(m)} に置き換え、再びOpenに挿入する(Openが正しくソートされていることを保証するため)。また、記録してある m の親を n に置き換える。 m が Close リストにある場合、 f ′ ( m ) < f ( m ) {\displaystyle f'(m)<f(m)} であるなら f ( m ) ← f ′ ( m ) {\displaystyle f(m)\leftarrow f'(m)} として m を Open リストに移動する。また記録してある m の親を n に置き換える。 3 以降を繰り返す。探索終了後、発見されたゴール n G {\displaystyle n_{G}} から親を順次たどっていくと S からゴール n G {\displaystyle n_{G}} までの最短経路が得られる。以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では HDA*, PBFS などの並列手法が開発され、特にHDA*は768 コア以上の大規模並列計算環境にもスケールすることが実証されている。

※この「アルゴリズムの流れ」の解説は、「A*」の解説の一部です。
「アルゴリズムの流れ」を含む「A*」の記事については、「A*」の概要を参照ください。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 03:36 UTC 版)

「タブーサーチ」の記事における「アルゴリズムの流れ」の解説

アルゴリズムの流れを以下に示す。初期状態 S0 を決定する（通常はランダム）。最良状態 Sb と現在状態 S を作成し、とりあえず S0 を両方に記録しておく。 S の近傍を複数（M 個）選び、その中で最も成績の良い近傍を S' とおく（この比較にS は入らないことに注意）状態遷移を判定（以下のどちらか）もしS' がSb より良い値ならSb =S =S' とする。このときタブーリストにS →S' になる操作が記載されている場合、その部分をタブーリストの一番新しい記載に移動する。もしS' がSb より悪い値なら、S →S' になる操作がタブーリストに記載されているかどうかを確認する。記載されていないならタブーリストにS →S' となる操作を記載して S =S' とする。このときタブーリストのサイズが上限を越えているなら、一番古い記載を削除する。終了条件が満たされるまで 3. 以下の操作を繰り返し、最終的に Sb を解として出力する。この方法は他のメタヒューリスティックと違い最良解は必ず保存することがアルゴリズム内に組み込まれている。この理由はタブーサーチにおける状態は常に遷移し続けている（タブーリストの記載方法しだいでは停滞することもあるが、それはやってはならない操作とされる）ため最終状態が最良状態である可能性が極めて低いからである。

※この「アルゴリズムの流れ」の解説は、「タブーサーチ」の解説の一部です。
「アルゴリズムの流れ」を含む「タブーサーチ」の記事については、「タブーサーチ」の概要を参照ください。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 08:04 UTC 版)

「蟻コロニー最適化」の記事における「アルゴリズムの流れ」の解説

ACO の基本的なアルゴリズムは以下の通りである。エージェント（アリ）とフェロモンの初期化終了条件を満たすまで以下の処理を繰り返す。各エージェントに対して、フェロモンとヒューリスティックな情報に基づいて確率的な解の選択を行う。各エージェントが分泌するフェロモンを計算する。フェロモン情報の更新最も良い成績のエージェントの解を出力する。解の選択は様々なものが考えられるが Marco Dorigo が巡回セールスマン問題に適用した論文では以下のような方法がとられている。今、繰り返し回数 t 時点でのエージェント k が巡回路を作成することを考える。まずスタート地点となる都市を適当に選択する。次にエージェント k はいくつかの都市を訪問し現在、都市 i にいるとする。このとき k がまだ訪問していない都市の集合を Ω で表し、Ωに属する都市 j と i に対して以下のような評価値を計算する。 a i j k ( t ) = [ τ i j ( t ) ] α [ η i j ] β ∑ l ∈ Ω [ τ i l ( t ) ] α [ η i l ] β {\displaystyle a_{ij}^{k}(t)={\frac {[\tau _{ij}(t)]^{\alpha }[\eta _{ij}]^{\beta }}{\sum _{l\in \Omega }[\tau _{il}(t)]^{\alpha }[\eta _{il}]^{\beta }}}} ここで、τij (t) は時点 t での都市 i から j への経路に蓄積されたフェロモンである。ηij は都市 i から j へヒューリスティックな情報であり、 Dorigo は距離の逆数を使用している。α、β はフェロモンとヒューリスティック情報のどちらを優先させるかという定数である。Ωの全ての都市に対して上記の評価値を計算し都市を一つ選択する。例えば都市 m が選択される確率は以下のようになる。 p i m k ( t ) = a i m k ( t ) ∑ n ∈ Ω a i n ( t ) {\displaystyle p_{im}^{k}(t)={\frac {a_{im}^{k}(t)}{\sum _{n\in \Omega }a_{in}(t)}}} この選択をΩが空集合になるまで繰り返す。各エージェントに対して以上の操作を行い時点 t における各巡回路を作成する。各巡回路が作成されたら、次にフェロモンの計算が行われる。これはエージェント k が作成した巡回路を Tk (t) としその長さを Lk (t) としたとき、エージェント k は各経路に対して以下のように分泌するフェロモンを決定する。 Δ τ i j k ( t ) = { Q / L k ( t ) , if ( i , j ) ∈ T k ( t ) 0 , e l s e {\displaystyle \Delta \tau _{ij}^{k}(t)={\begin{cases}Q/L_{k}(t),&{\mbox{if }}(i,j)\in T_{k}(t)\\0,&else\end{cases}}} ここで Q は正の定数である。この値により時点 t+1 のフェロモン情報は以下の式で更新される。 τ i j ( t + 1 ) = ρ τ i j ( t ) + ∑ k = 1 m Δ τ i j k ( t ) {\displaystyle \tau _{ij}(t+1)=\rho \tau _{ij}(t)+\sum _{k=1}^{m}\Delta \tau _{ij}^{k}(t)} ここで ρ は 0 以上 1 以下の定数であり、フェロモンの蒸発率を表している。また m はエージェントの最大数である。以上の式を定められた時点まで繰り返すことによって解を得ることができる。

※この「アルゴリズムの流れ」の解説は、「蟻コロニー最適化」の解説の一部です。
「アルゴリズムの流れ」を含む「蟻コロニー最適化」の記事については、「蟻コロニー最適化」の概要を参照ください。

アルゴリズムの流れ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/07 09:25 UTC 版)

「グローバーのアルゴリズム」の記事における「アルゴリズムの流れ」の解説

| s ⟩ {\displaystyle |s\rangle } を、全ての状態の一様な重ね合わせ | s ⟩ = 1 N ∑ x = 0 N − 1 | x ⟩ {\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle } とし、演算子 U s {\displaystyle U_{s}} を U s = 2 | s ⟩ ⟨ s | − I {\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I} とする。この演算子は、グローバーの拡散演算子と呼ばれている。グローバーのアルゴリズムの流れは以下の通りである。初期状態を以下の様に用意する： | s ⟩ = 1 N ∑ x = 1 N | x ⟩ {\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle } 次にしめす"Grover iteration"を r ( N ) {\displaystyle r(N)} 回繰返す。関数 r ( N ) {\displaystyle r(N)} は漸近的に O ( N ) {\displaystyle O({\sqrt {N}})} である関数であり、詳細は後述する。演算子 U ω {\displaystyle U_{\omega }} を適用する。演算子 U s {\displaystyle U_{s}} を適用する。状態Ωを観測する。観測の結果は、Nが十分に大きければ、1に近い確率でλωとなり、 ω {\displaystyle \omega } を得ることができる。