アリコロニー最適化アルゴリズム

「知能」はもはや中央集権的なものではなく、あらゆる微小な物体に遍在するようになったため、新たな概念が必要とされている。人間中心の概念は、データ処理、制御ユニット、計算能力が中央集権化されたITシステムを生み出すことに繋がってきた。これらの中央集権型ユニットは性能を絶えず向上させ、人間の脳に匹敵するようになった。脳のモデルは、コンピュータの究極のビジョンとなった。しかし、インテリジェントな物体のアンビエントネットワーク、そして遅かれ早かれ、さらに拡散しナノテクノロジーに基づいた新世代の情報システムは、この概念を根本的に変えるだろう。昆虫に匹敵する小型デバイスは、それ自体では高度な知能を持たない。実際、その知能はかなり限定的であると言える。例えば、あらゆる種類の数学的問題を解決できる高性能計算機を、人体に埋め込まれるバイオチップや、商品追跡用に設計されたインテリジェントタグに統合することは不可能である。しかし、これらの物体が相互接続されると、アリやミツバチのコロニーに匹敵する知能を発達させる。特定の問題の場合、この種の知能は脳に似た中央集権的なシステムの推論よりも優れている可能性がある。^{[ 11 ]}

自然界には、微小な生物が共通の基本ルールに従うことで、巨視的なレベルで集合知を形成する例が数多く存在する。社会性昆虫のコロニーは、人間の社会とは大きく異なるこのモデルを完璧に体現している。このモデルは、単純で予測不可能な行動をとる独立した個体の協力に基づいている。^{[ 12 ]}それらは特定のタスクを実行するために周囲を移動し、そのための情報はごく限られている。例えば、アリのコロニーは、周囲の物体のネットワークにも適用できる多くの特性を備えている。アリのコロニーは、環境の変化に適応する能力が非常に高く、個体が特定のタスクを実行できない場合にも対処できる力も非常に強い。このような柔軟性は、絶えず進化し続ける物体のモバイルネットワークにも非常に役立つだろう。コンピュータからデジタルオブジェクトに移動する情報の束は、アリと同じように振る舞う。それらはネットワークを移動し、最終目的地にできるだけ早く到達することを目的として、あるノードから次のノードへと移動する。^{[ 13 ]}

フェロモンを用いたコミュニケーションは、自然界で広く見られる最も効果的なコミュニケーション方法の一つです。フェロモンは、ミツバチ、アリ、シロアリなどの社会性昆虫によって、個体間および個体群間のコミュニケーションに利用されています。その実現可能性から、人工フェロモンはマルチロボットシステムや群ロボットシステムに採用されています。フェロモンを用いたコミュニケーションは、化学的^{[ 14 ] [ 15 ] [ 16 ]}や物理的(RFIDタグ^{[ 17 ]}、光[ ^{18 ] [ 19] [ 20 ] [ 21 ]、}音^{[ 22 ] )など、さまざまな方法で実現されてきました。しかし、これらの実装では、}自然界で見られるフェロモンのすべての側面を再現することはできませんでした。

投影光の使用は、マイクロ自律ロボットとのフェロモンベースの通信を研究するための実験装置として、2007 年の IEEE 論文で Garnier、Simon らによって発表されました。^{[ 23 ]}別の研究では、ロボットが移動する水平 LCD スクリーンを介してフェロモンを実装し、ロボットが下向きの光センサーを備えてその下のパターンを登録するシステムが発表されました。^{[ 24 ] [ 25 ]}

各アリはグラフ内を移動するための解を構築する必要があります。アリは、ツアーの次のエッジを選択するために、現在の位置から利用可能な各エッジの長さと、対応するフェロモンレベルを考慮します。アルゴリズムの各ステップで、各アリはある状態から移動します。${\displaystyle x}$述べる${\displaystyle y}$より完全な中間解に対応する。したがって、各アリは${\displaystyle k}$セットを計算する${\displaystyle A_{k}(x)}$各反復において、現在の状態への実行可能な拡張の候補を抽出し、確率的にこれらのうちの1つに移動します。${\displaystyle k}$確率${\displaystyle p_{xy}^{k}}$州から移動する${\displaystyle x}$述べる${\displaystyle y}$2つの値の組み合わせに依存します。魅力$\displaystyle \eta _{xy}}$その移動の事前の望ましさとトレイルレベルを示す何らかのヒューリスティックによって計算された移動の評価$\displaystyle \tau _{xy}}$その動きの熟練度は、過去にその動きをどれだけうまく実行できたかを示します。トレイルレベルは、その動きの望ましさを事後的に示す指標です。

一般的に、${\displaystyle k}$アリが州から移動する${\displaystyle x}$述べる${\displaystyle y}$確率で

${\displaystyle p_{xy}^{k}={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum _{z\in \mathrm {許可} _{x}}(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}}}$

どこ$\displaystyle \tau _{xy}}$状態遷移のために沈着したフェロモンの量${\displaystyle x}$に${\displaystyle y}$、${\displaystyle \alpha }$≥ 0 は、影響を制御するためのパラメータです。$\displaystyle \tau _{xy}}$、$\displaystyle \eta _{xy}}$状態遷移の望ましさ${\displaystyle xy}$（先験的知識、典型的には）$1/d_{xy}}$、 どこ${\displaystyle d}$距離は、${\displaystyle \beta }$≥ 1 は、影響を制御するためのパラメータです。$\displaystyle \eta _{xy}}$そして$\displaystyle \mathrm {allowed} _{x}}$これは、州から許可されている目的地の集合です。${\displaystyle x}$。$\displaystyle \tau _{xz}}$そして$\displaystyle \eta _{xz}}$他の可能な状態遷移におけるトレイルレベルと魅力度を表す。

トレイルは通常、すべてのアリが解決策を完了したときに更新され、「良い」解決策または「悪い」解決策の一部であった移動に対応するトレイルのレベルがそれぞれ増減されます。グローバルフェロモン更新ルールの例は次のとおりです。

${\displaystyle \tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k}^{m}\Delta \tau _{xy}^{k}}$

どこ${\displaystyle \tau _{xy}}$状態遷移のために沈着したフェロモンの量${\displaystyle xy}$、${\displaystyle \rho }$はフェロモン蒸発係数です。${\displaystyle m}$はアリの数であり、${\displaystyle \Delta \tau _{xy}^{k}}$は、${\displaystyle k}$アリは、通常、TSP問題（グラフの弧に対応する移動）に対して与えられます。

${\displaystyle \Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{if ant }}k{\mbox{ uses curve }}xy{\mbox{ in its tour}}\\0&{\mbox{otherwise}}\end{cases}}}$

どこ${\displaystyle L_{k}}$コストは${\displaystyle k}$アリのツアー（通常は長さ）と${\displaystyle Q}$定数です。

アリシステムは最初のACOアルゴリズムです。このアルゴリズムは、上記で紹介したものに相当します。これはDorigoによって開発されました。^{[ 26 ]}

アリコロニーシステムアルゴリズムでは、元のアリシステムが3つの点で変更されました。

1. エッジの選択は、利用（つまり、フェロモンの量が多い最短のエッジを選択する確率を優先する）に偏っている。
2. アリは解を構築する際に、局所的なフェロモン更新ルールを適用することで、選択するエッジのフェロモンレベルを変化させる。
3. 各反復の最後に、最も優れたアリのみが、修正されたグローバルフェロモン更新ルールを適用してトレイルを更新することが許可されます。^{[ 27 ]}

このアルゴリズムでは、グローバル最適解は、他のすべてのアリとともに、各反復処理後に（たとえその経路が再訪されていなくても）自身の経路にフェロモンを付着させます。エリート戦略の目的は、すべてのアリの探索を誘導し、現在の最適経路のリンクを含む解を構築することです。

このアルゴリズムは、各トレイル上のフェロモン量の最大値と最小値を制御します。フェロモンをトレイルに追加できるのは、グローバルベストツアーまたはイテレーションベストツアーのみです。探索アルゴリズムの停滞を避けるため、各トレイル上の可能なフェロモン量の範囲は区間[τ _max ,τ _{min ]に制限されます。すべてのエッジはτ max}に初期化され、より多くの解を探索するように強制されます。停滞に近づくと、トレイルはτ _{maxに再初期化されます。} ^{[ 28 ]}

すべての解は、その長さに基づいてランク付けされます。この反復処理において、最も優れたアリのうち、一定数のアリのみが試行を更新できます。各解に対して、フェロモンの放出量が重み付けされ、経路が短い解ほど、経路が長い解よりも多くのフェロモンが放出されます。

コミュニケーション戦略を備えたアリコロニーシステム（ACS）が開発されました。人工アリはいくつかのグループに分割されます。ACS内のグループ間でフェロモンレベルを更新するための7つのコミュニケーション方法が提案され、巡回セールスマン問題で機能します。 ^{[ 29 ]}

COACのフェロモン堆積メカニズムは、アリが協力して効果的に解決策を探索できるようにするものです。直交設計法を用いることで、実行可能領域内のアリは、グローバル探索能力と精度が向上し、選択した領域を迅速かつ効率的に探索できます。直交設計法と適応半径調整法は、他の最適化アルゴリズムにも拡張でき、実用的な問題を解決する上でより幅広い利点をもたらします。^{[ 30 ]}

これは、探索領域全体を複数のサブドメインに分割し、これらのサブドメインで目的関数を解く再帰的なアリシステムです。^{[ 31 ]}すべてのサブドメインの結果が比較され、そのうちの上位数個が次のレベルに昇格されます。選択された結果に対応するサブドメインはさらに細分化され、所望の精度の出力が得られるまでこのプロセスが繰り返されます。この方法は、不適切な地球物理学的逆問題でテストされており、うまく機能します。^{[ 32 ]}

• 順序付け問題(SOP) ^{[ 34 ]}
• ジョブショップスケジューリング問題（JSP）^{[ 35 ]}
• オープンショップスケジューリング問題 (OSP) ^{[ 36 ] [ 37 ]}
• 順列フローショップ問題（PFSP）^{[ 38 ]}
• 単一機械の総遅延問題 (SMTTP) ^{[ 39 ]}
• 単一機械の総加重遅延問題 (SMTWTP) ^{[ 40 ] [ 41 ] [ 42 ]}
• リソース制約付きプロジェクトスケジューリング問題（RCPSP）^{[ 43 ]}
• グループショップスケジューリング問題（GSP）^{[ 44 ]}
• 順序依存のセットアップ時間を持つ単一機械の総遅延問題（SMTTPDST）^{[ 45 ]}
• 順序依存のセットアップ/切り替え時間を持つ多段階フローショップスケジューリング問題（MFSP）^{[ 46 ]}
• アセンブリ順序計画（ASP）問題^{[ 47 ]}

• 容量制約付き車両経路問題 (CVRP) ^{[ 48 ] [ 49 ] [ 50 ]}
• 複数拠点車両経路問題（MDVRP）^{[ 51 ]}
• 周期車両経路問題（PVRP）^{[ 52 ]}
• 分割配送車両経路問題（SDVRP）^{[ 53 ]}
• 確率的車両経路問題 (SVRP) ^{[ 54 ]}
• 集荷と配送を伴う車両経路問題 (VRPPD) ^{[ 55 ] [ 56 ]}
• 時間枠付き車両経路問題 (VRPTW) ^{[ 57 ] [ 58 ] [ 59 ] [ 60 ]}
• 時間依存型車両経路問題（TDVRPTW）^{[ 61 ]}
• 時間枠と複数のサービス作業員を考慮した車両経路問題（VRPTWMS）

• 二次割り当て問題(QAP) ^{[ 62 ]}
• 一般化割り当て問題(GAP) ^{[ 63 ] [ 64 ]}
• 周波数割り当て問題（FAP）^{[ 65 ]}
• 冗長性割り当て問題（RAP）^{[ 66 ]}

• 集合被覆問題(SCP) ^{[ 67 ] [ 68 ]}
• 分割問題（SPP）^{[ 69 ]}
• 重み制約付きグラフツリー分割問題（WCGTPP）^{[ 70 ]}
• 弧重み付きl-カーディナリティツリー問題（AWlCTP）^{[ 71 ]}
• 多重ナップサック問題（MKP）^{[ 72 ]}
• 最大独立集合問題 (MIS) ^{[ 73 ]}

• アリコロニー最適化（ACO）に基づく45nm  CMOSベースのセンスアンプ回路の最適化は、非常に短い時間で最適な解に収束する可能性がある。^{[ 74 ]}
• アリコロニー最適化（ACO）に基づく可逆回路合成は、効率を大幅に向上させることができる。^{[ 75 ]}

アンテナの形状を最適化するために、アリコロニーアルゴリズムを使用できます。例として、アリコロニーアルゴリズム (ACO) に基づく RFID タグのアンテナ^{[ 77 ]} 、ループバックおよびアンループバックバイブレータ 10×10 ^{[ 76 ]が考えられます。}

ACOアルゴリズムは、画像処理において画像のエッジ検出やエッジ連結に使用されます。^{[ 78 ] [ 79 ]}

• エッジ検出:

このグラフは2次元画像であり、アリはフェロモンを塗布しながらあるピクセル間を移動します。アリがピクセル間を移動する方向は、画像の輝度値の局所的な変化によって決まります。この動きによって、フェロモンの密度が最も高くなるのは画像の端の部分です。

ACO を使用したエッジ検出の手順は次のとおりです。^{[ 80 ] [ 81 ] [ 82 ]}

ステップ1：初期化。ランダムに配置する${\displaystyle K}$画像上のアリ${\displaystyle I_{M_{1}M_{2}}}$どこ${\displaystyle K=(M_{1}*M_{2})^{\tfrac {1}{2}}}$フェロモンマトリックス${\displaystyle \tau _{(i,j)}}$はランダムな値で初期化されます。初期化プロセスにおける主な課題は、ヒューリスティック行列を決定することです。

ヒューリスティック行列を決定する方法はいくつかあります。以下の例では、ヒューリスティック行列は局所統計情報、つまりピクセル位置における局所統計情報に基づいて計算されました。${\displaystyle (i,j)}$。

${\displaystyle \eta _{(i,j)}={\tfrac {1}{Z}}*Vc*I_{(i,j)},}$

どこ${\displaystyle I}$サイズの画像です${\displaystyle M_{1}*M_{2}}$、

${\displaystyle Z=\sum _{i=1:M_{1}}\sum _{j=1:M_{2}}Vc(I_{i,j})}$

は正規化係数であり、

${\displaystyle {\begin{aligned}Vc(I_{i,j})=&f\left(\left\vert I_{(i-2,j-1)}-I_{(i+2,j+1)}\right\vert +\left\vert I_{(i-2,j+1)}-I_{(i+2,j-1)}\right\vert \right.\\&+\left\vert I_{(i-1,j-2)}-I_{(i+1,j+2)}\right\vert +\left\vert I_{(i-1,j-1)}-I_{(i+1,j+1)}\right\vert \\&+\left\vert I_{(i-1,j)}-I_{(i+1,j)}\right\vert +\left\vert I_{(i-1,j+1)}-I_{(i-1,j-1)}\right\vert \\&+\left.\left\vert I_{(i-1,j+2)}-I_{(i-1,j-2)}\right\vert +\left\vert I_{(i,j-1)}-I_{(i,j+1)}\right\vert \right)\end{aligned}}}$

${\displaystyle f(\cdot )}$以下の関数を使用して計算できます。

${\displaystyle f(x)=\lambda x,\quad {\text{for x ≥ 0; (1)}}}$

${\displaystyle f(x)=\lambda x^{2},\quad {\text{for x ≥ 0; (2)}}}$

${\displaystyle f(x)={\begin{cases}\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (3)}}\\0,&{\text{else}}\end{cases}}}$

${\displaystyle f(x)={\begin{cases}\pi x\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (4)}}\\0,&{\text{else}}\end{cases}}}$

パラメータ${\displaystyle \lambda }$上記の各関数は、それぞれの関数の形状を調整します。

ステップ2：構築プロセス。アリの動きは、4つの連結ピクセルまたは8つの連結ピクセルに基づいています。アリが移動する確率は、確率方程式によって与えられます。${\displaystyle P_{x,y}}$

ステップ 3 とステップ 5: 更新プロセス。フェロモンマトリックスは 2 回更新されます。ステップ 3 ではアリの軌跡 (以下で与えられる)${\displaystyle \tau _{(x,y)}}$）が更新される一方、ステップ5では、トレイルの蒸発速度が更新され、それは次のように表されます。

${\displaystyle \tau _{new}\leftarrow (1-\psi )\tau _{old}+\psi \tau _{0}}$、

どこ${\displaystyle \psi }$フェロモンの減衰係数${\displaystyle 0<\tau <1}$

ステップ 7: 決定プロセス。K匹のアリが N 回繰り返して一定距離 L 移動したら、それがエッジであるかどうかの決定は、フェロモン行列 τ 上の閾値 T に基づいて行われます。以下の例の閾値は、大津の方法に基づいて計算されます。

ACOを使用して検出された画像のエッジ：以下の画像は、式(1)～(4)で示される異なる関数を使用して生成されています。^{[ 83 ]}

• エッジリンキング: ^{[ 84 ]} ACOはエッジリンキングアルゴリズムでも効果的であることが証明されています。

• 倒産予測^{[ 85 ]}
• 分類^{[ 35 ]}
• 露天掘り鉱山の長期生産計画^{[ 86 ]}
• コネクション指向型ネットワークルーティング^{[ 87 ]}
• コネクションレス型ネットワークルーティング^{[ 88 ] [ 89 ]}
• データマイニング^{[ 35 ] [ 90 ] [ 91 ] [ 92 ]}
• プロジェクトスケジューリングにおける割引キャッシュフロー^{[ 93 ]}
• 分散情報検索^{[ 94 ] [ 95 ]}
• エネルギーおよび電力ネットワーク設計^{[ 96 ]}
• グリッドワークフロースケジューリング問題^{[ 97 ]}
• タンパク質間相互作用に対する阻害ペプチド設計^{[ 98 ]}
• インテリジェントテストシステム^{[ 99 ]}
• パワーエレクトロニクス回路設計^{[ 100 ]}
• タンパク質の折り畳み^{[ 101 ] [ 102 ] [ 103 ]}
• システム同定^{[ 104 ] [ 105 ]}