蟻コロニー最適化とは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > 最適化 > 蟻コロニー最適化の意味・解説 

蟻コロニー最適化

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

蟻コロニー最適化の概念図

蟻コロニー最適化(ありコロニーさいてきか、Ant Colony OptimizationACO)とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー(=群れ)から食物までの経路を見つける際の挙動からヒントを得たものである。

概要

実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。

しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発するよりも早く補強されるため、フェロモン濃度は高いまま保たれる。

従って、あるアリがコロニーから食料源までの良い(すなわち短い)経路を見つけると、他のアリもその経路を辿る可能性が高くなり、正のフィードバック効果によって結局すべてのアリが1つの経路を辿ることになる。蟻コロニー最適化アルゴリズムの考え方は、解決すべき問題を表しているグラフを歩き回る「シミュレーションされたアリ」によってこの行動を真似ることである。

蟻コロニー最適化アルゴリズムは、巡回セールスマン問題に近似最適解を生み出すために用いられた。この手法はグラフが動的に変化する場合に焼きなまし法遺伝的アルゴリズムよりも有効である。蟻コロニー最適化アルゴリズムは継続的に実行されるので、リアルタイムで変化に適応することができる。このことから、ネットワークルーティングや都市交通システムでの応用が考えられる。

アルゴリズムの流れ

ACO の基本的なアルゴリズムは以下の通りである。

  1. エージェント(アリ)とフェロモンの初期化
  2. 終了条件を満たすまで以下の処理を繰り返す。
    1. 各エージェントに対して、フェロモンとヒューリスティックな情報に基づいて確率的な解の選択を行う。
    2. 各エージェントが分泌するフェロモンを計算する。
    3. フェロモン情報の更新
  3. 最も良い成績のエージェントの解を出力する。

解の選択は様々なものが考えられるが Marco Dorigo が巡回セールスマン問題に適用した論文では以下のような方法がとられている。

今、繰り返し回数 t 時点でのエージェント k が巡回路を作成することを考える。まずスタート地点となる都市を適当に選択する。 次にエージェント k はいくつかの都市を訪問し現在、都市 i にいるとする。このとき k がまだ訪問していない都市の集合を Ω で表し、Ωに属する都市 ji に対して以下のような評価値を計算する。

Optimization computes maxima and minima.
非線形(制約付き)
凸最適化
組合せ最適化
メタヒューリスティクス

蟻コロニー最適化

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/18 16:06 UTC 版)

群知能」の記事における「蟻コロニー最適化」の解説

蟻コロニー最適化(ACO)は難しい組合わせ最適化問題近似解探索するのに使われるメタヒューリスティック最適化アルゴリズムである。ACOでは、現実真似た人工問題グラフ上を移動することで解を構築しようとする。このとき、グラフ上に人工フェロモンを置くことでその後人工よりよい解を探索できるようにする。ACO多数最適化問題効力発揮してきた。

※この「蟻コロニー最適化」の解説は、「群知能」の解説の一部です。
「蟻コロニー最適化」を含む「群知能」の記事については、「群知能」の概要を参照ください。

ウィキペディア小見出し辞書の「蟻コロニー最適化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



蟻コロニー最適化と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「蟻コロニー最適化」の関連用語

蟻コロニー最適化のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



蟻コロニー最適化のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの蟻コロニー最適化 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの群知能 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS