この記事は機械翻訳されたものです。
テストの実行
蟻コロニー最適化 (機械翻訳)
今月のコラムでは巡回セールスマン問題 (TSP) を解決するために蟻コロニー最適化 (ACO) アルゴリズムを実装する c# コードを紹介します。 ACO アルゴリズムはアリのフェロモン レイアウト動作に基づいて、人工知能技術です。 グラフを最適パスを求める極めて複雑な問題の解決策を見つけるために使用できます。 どこに向かっているを参照する最良の方法でスクリーン ショットを見ている図 1。 この例では、デモ、TSP のインスタンスをそれぞれ 60 の都市の 1 回の訪問の最短経路を見つけることを目標と解決です。 デモ プログラム 4 アリを使用; それぞれのアリは、潜在的なソリューションを表します。 ACO は後で説明します、フェロモン蒸発係数 （ロー） は、フェロモンの影響要因 (アルファ) などのいくつかのパラメーターの指定が必要です。 4 つのアリは、60 の都市のランダムな小道に初期化されます; 初期化後は、最高の ant の最短の道長 245.0 台です。 キー ACO の模擬のフェロモンより良いコースをグラフにアリを集めるの使用勧めします。 メインの処理ループを代替間現在フェロモン値に基づいての蟻道を更新し、新しい ant トレイルに基づくフェロモンを更新します。 最大数 (1,000) 回メイン処理ループを実行した後、プログラムが最高の歩道とその対応する長さ (61.0 単位) が表示されます。
60 都市グラフ人為的これはすべての都市はすべて他の都市に接続されていると、2 つの都市間の距離が 1.0 と 8.0 任意単位 （マイル、km やなど) の間のランダムな値に構成されています。 TSP を解決するは簡単ではありません。 任意都市と前方または後方に移動を始めることができるし、すべての都市が接続されていることを仮定して、60 の都市では、合計の (60-1)! ・ 2 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 可能な解決策を =。 1 秒あたり 10億可能なソリューションを評価する場合、それ約 2.2 ※ 1063 年彼らのすべてを確認するには、宇宙の推定年齢よりも数倍の時間がかかるでしょう。
ACO は型メタは、特定のグラフのパスの問題を解決するために、特定のアルゴリズムを作成するために使用することができます一般的なフレームワークです。 ACO は M 1991 博士論文で提案されたが。 Dorigo、アルゴリズムの最初の詳細な説明は、通常 1996年フォロー アップ紙に M 原因です。 Dorigo、V。 Maniezzo と A Colorni。 以来、ACO が広く研究され変更しますが、少し不思議なことに、非常にほとんどの完全なと正しい実装をご利用いただけません。
この列は、中級-上級プログラミングのスキルがあると仮定します。 C# を使用して、ACO プログラムを実装するが、あまりにも多くのトラブルを JavaScript などの別の言語コードをリファクタリングしてはなりません。 できるだけ明確のアルゴリズムのアイデアを維持するオブジェクト指向プログラミング (OOP) のすべての使用を回避することを決めた。 スペースの制限のため、私はすべてを実行しているコードの存在することはできません図 1。 私は、トリッキーな部分に行き、完全なコードをダウンロードすることができます archive.msdn.microsoft.com/mag201202TestRun。 ACO コードを直接使用することは可能性がありますが、その技術は、ルーレット ホイール選択などの多くの面白いことができ、技術的なスキルに便利な追加機能を設定します。
.png)
図 1 アント コロニー最適化行動
プログラムの構造
私は、1 つの c# コンソール アプリケーションとして、ACO のデモ プログラムを実装しました。 削除、ほとんどの WriteLine ステートメントはプログラムの全体構造で表示されます図 2。 いくつかの部分が難しいが、プログラムが複雑なことはない図 2 多くの方法の短いヘルパー メソッドであるために提案します。
図 2 蟻コロニー最適化プログラム構造
using System;
namespace AntColony
{
class AntColonyProgram
{
static Random random = new Random(0);
static int alpha = 3;
static int beta = 2;
static double rho = 0.01;
static double Q = 2.0;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
int numCities = 60;
int numAnts = 4;
int maxTime = 1000;
int[][] dists = MakeGraphDistances(numCities);
int[][] ants = InitAnts(numAnts, numCities);
int[] bestTrail = BestTrail(ants, dists);
double bestLength = Length(bestTrail, dists);
double[][] pheromones = InitPheromones(numCities);
int time = 0;
while (time < maxTime)
{
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = BestTrail(ants, dists);
double currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength)
{
bestLength = currBestLength;
bestTrail = currBestTrail;
}
++time;
}
Console.WriteLine("\nBest trail found:");
Display(bestTrail);
Console.WriteLine("\nLength of best trail found: " +
bestLength.ToString("F1"));
Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
static int[][] InitAnts(int numAnts, int numCities) { .
.
}
static int[] RandomTrail(int start, int numCities) { .
.
}
static int IndexOfTarget(int[] trail, int target) { .
.
}
static double Length(int[] trail, int[][] dists) { .
.
}
static int[] BestTrail(int[][] ants, int[][] dists) { .
.
}
static double[][] InitPheromones(int numCities) { .
.
}
static void UpdateAnts(int[][] ants, double[][] pheromones,
int[][] dists) { .
.
}
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists) { .
.
}
static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones,
int[][] dists) { .
.
}
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists) { .
.
}
static void UpdatePheromones(double[][] pheromones, int[][] ants,
int[][] dists) { .
.
}
static bool EdgeInTrail(int nodeX, int nodeY, int[] trail) { .
.
}
static int[][] MakeGraphDistances(int numCities) { .
.
}
static double Distance(int cityX, int cityY, int[][] dists) { .
.
}
static void Display(int[] trail) { .
.
}
static void ShowAnts(int[][] ants, int[][] dists) { .
.
}
static void Display(double[][] pheromones) { .
.
}
}
}
私は Visual Studio の AntColony という名前のコンソール アプリケーションを作成するのにために使用。 [ソリューション エクスプ ローラー] ウィンドウでは、既定 Program.cs ファイル AntColonyProgram.cs を自動変更切、1 つのクラスは、プロジェクトの名前を変更します。 私はすべて、テンプレートによって生成された削除ステートメント、システム名前空間を除く — ACO 通常多くのライブラリのサポート必要はないです。 2 つのキーのメソッドは、UpdateAnts と UpdatePheromones です。 ヘルパー BuildTrail は、NextCity は、MoveProbs を呼び出す呼び出しメソッド UpdateAnts を呼び出します。 ヘルパー EdgeInTrail は、IndexOfTarget を呼び出すメソッド UpdatePheromones を呼び出します。
私はクラス スコープ ランダム オブジェクトをというランダム宣言。 後ほど説明しますが、ACO アルゴリズムは確率論的です。 クラス スコープ変数アルファ、ベータ、rho と Q ACO アルゴリズムの動作を制御します。 ACO の元の説明に使用されたのでこれらの変数の名前を使用します。
問題の設定
私は、人工のグラフを設定するメソッド MakeGraphDistances を使用しました。
static int[][] MakeGraphDistances(int numCities)
{
int[][] dists = new int[numCities][];
for (int i = 0; i < dists.Length; ++i)
dists[i] = new int[numCities];
for (int i = 0; i < numCities; ++i)
for (int j = i + 1; j < numCities; ++j) {
int d = random.Next(1, 9); // [1,8]
dists[i][j] = d; dists[j][i] = d;
}
return dists;
}
実際のグラフの問題についてはおそらくグラフ - 読むだろう隣接ノードとノードの間の距離データをテキスト ファイルにある種のデータ構造から。 ここで私は市には都市から、列インデックス j を表す行のインデックスを表す配列の配列を作成することによって、グラフをシミュレートしました。 すべての都市が接続されていることの通知、距離対称あり自体には、都市からの距離は 0 です。
かつて私は、距離のデータ構造がある距離法が使えます。
static double Distance(int cityX, int cityY, int[][] dists)
{
return dists[cityX][cityY];
}
表示コード量を最小限にするには、通常のエラー チェック、cityX および cityY パラメーターが有効であることを確かめるなどを省略しました。
アリと、フェロモンを開始
このオブジェクト指向の実装では、アリは単に、最初の都市を介してすべての他の都市から、トレイル、またはパスを表す int 型の値の配列です。 アリのコレクションは配列の最初のインデックス、ant を示す配列です。
static int[][] InitAnts(int numAnts, int numCities)
{
int[][] ants = new int[numAnts][];
for (int k = 0; k < numAnts; ++k) {
int start = random.Next(0, numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}
初期化メソッドは、行は、それぞれのアリを割り当てます、ランダム スタート市のおすすめし、ヘルパー メソッド RandomTrail を呼び出します。
static int[] RandomTrail(int start, int numCities)
{
int[] trail = new int[numCities];
for (int i = 0; i < numCities; ++i) { trail[i] = i; }
for (int i = 0; i < numCities; ++i) {
int r = random.Next(i, numCities);
int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
}
int idx = IndexOfTarget(trail, start);
int temp = trail[0]; trail[0] = trail[idx]; trail[idx] = temp;
return trail;
}
RandomTrail ヘルパー歩道を割り当てます、それは 0、1、2 に初期化します. numCities-1。 次に、メソッドが、フィッシャー Yates シャッフル アルゴリズムを使用して、歩道に都市の順序をランダムに。 指定した開始都市です [あり位置記録 [0] にスワップします。
フェロモン化学アリ場所の道である; 彼らは他のアリを誘致します。 個のアリに短い歩道、食料源に旅行する — とより多くのフェロモンを預金 — よりも長いトレイル。 フェロモンは、ゆっくりと時間をかけて蒸発します。 ここの方法 InitPheromones
static double[][] InitPheromones(int numCities)
{
double[][] pheromones = new double[numCities][];
for (int i = 0; i < numCities; ++i)
pheromones[i] = new double[numCities];
for (int i = 0; i < pheromones.Length; ++i)
for (int j = 0; j < pheromones[i].Length; ++j)
pheromones[i][j] = 0.01;
return pheromones;
}
フェロモン情報は、配列の配列形式対称行列では行はインデックス列インデックス j に市の都市からであり。 すべての値は、ジャンプに、任意の小さな値 (0.01) を当初設定されます UpdateAnts UpdatePheromones サイクルを開始します。
アリを更新
ACO アルゴリズムの鍵を構築によって各 ant と記録を更新するプロセスです-私たちより良い希望 — 歩道のフェロモンと距離情報に基づきます。 見て図 3。 我々 は 5 つの都市の小さなグラフがあるとします。 図 3 、ant の新しい道は工事中です。 歩道都市で 1 日を開始 3 年の都市に行くし、更新アルゴリズム次の都市を決定することです。 今、フェロモンの距離と情報は、図のように。 次の都市を決定するには、まず配列の構築 (ギリシャ文字タウと eta の研究論文の使用するため) は「taueta」と呼ばれてきた。 Taueta 値をアルファ、ベータ乗距離値を 1 つの回発生したエッジのフェロモンの値です。 アルファおよびベータ版を指定する必要がありますグローバル定数であることを思い出してください。 ここで私はアルファは 3 ベータ 2 だと仮定します。 彼らはすでに、現在の歩道のため taueta 市 1 市 3 値が計算されていません。 フェロモンの値を大きく taueta、増加が、taueta より大きい距離を減少に注意してください。
.png)
図 3 更新 Ant 情報
Taueta のすべての値が計算された後は、次のステップ確率にこれらの値を変換し、それらの場所には、配列では probs ラベルを付けた。 アルゴリズムは、この例では、82.26 を取得、taueta の値の合計し、各 taueta 値で合計を分けます。 この時点で、都市 0 のように選択されて 0.09 の確率があります。 次に、アルゴリズム、計算の確率に基づく次の都市を選択する必要があります。 前述したように、私はこの記事で提示 ACO アルゴリズム ルーレット ホイール選択と呼ばれるきちんとした方法を使用します。 Cumul は、累積的な確率を保持と呼ばれる拡張配列を構築します。 拡張配列のサイズは、probs 配列よりも大きいもの、セル [0] を 0.0 シードです。 Cumul 内の各セルの確率の累積合計です。 Cumul 配列が作成された後は、0.0 と 1.0 の間のランダムな数 p が生成されます。 P と 0.538 よう =。 その p 値 [2] 値と [3] つまり、cumul 配列の滝 [2]、または市 2 が、次の都市として選択されています。
更新用の最上位のメソッドは、UpdateAnts という名前です。
static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
for (int k = 0; k < ants.Length; ++k) {
int start = random.Next(0, numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}
それぞれのアリ、新しい、ランダムな開始市割り当てられていることはなく、古いを維持開始都市に注意してください。 実際の作業のほとんどは実行されますヘルパーによる BuildTrail に示すように図 4。
図 4 BuildTrail メソッド
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists)
{
int numCities = pheromones.Length;
int[] trail = new int[numCities];
bool[] visited = new bool[numCities];
trail[0] = start;
visited[start] = true;
for (int i = 0; i < numCities - 1; ++i) {
int cityX = trail[i];
int next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}
作成記録が重複する都市が含まれていないので、ブール値の配列を訪問、BuildTrail を維持します。 記録 [0] の値は開始都市で、シード、各都市でのヘルパー メソッド NextCity、追加した図 5。
図 5 NextCity メソッド
static int NextCity(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.Length + 1];
for (int i = 0; i < probs.Length; ++i)
cumul[i + 1] = cumul[i] + probs[i];
double p = random.NextDouble();
for (int i = 0; i < cumul.Length - 1; ++i)
if (p >= cumul[i] && p < cumul[i + 1])
return i;
throw new Exception("Failure to return valid city in NextCity");
}
NextCity メソッドは、ルーレット ホイール選択アルゴリズムを実装します。Cumul 配列の最後の値が （おそらくのために丸め誤差)、1.00 より大きい場合に、常に cumul [cumul。 設定するロジックを追加する必要があります、アルゴリズムが失敗することに注意してください。長さ-1] 1.00。 NextCity 確率でヘルパー メソッド MoveProbs、生産の配列が必要です図 6。
図 6 MoveProbs メソッド
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
double[] taueta = new double[numCities];
double sum = 0.0;
for (int i = 0; i < taueta.Length; ++i) {
if (i == cityX)
taueta[i] = 0.0; // Prob of moving to self is zero
else if (visited[i] == true)
taueta[i] = 0.0; // Prob of moving to a visited node is zero
else {
taueta[i] = Math.Pow(pheromones[cityX][i], alpha) *
Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
if (taueta[i] < 0.0001)
taueta[i] = 0.0001;
else if (taueta[i] > (double.MaxValue / (numCities * 100)))
taueta[i] = double.MaxValue / (numCities * 100);
}
sum += taueta[i];
}
double[] probs = new double[numCities];
for (int i = 0; i < probs.Length; ++i)
probs[i] = taueta[i] / sum;
return probs;
}
(距離値が非常に大きい場合) に、taueta 値がきわめて小さいことまたは非常に大規模な (フェロモン値大きいはかどうか) は、アルゴリズムの難しさを生成することができます。 これに対処するには、私は、taueta の値をチェックし、任意の最小値と最大値を課します。
フェロモンを更新
フェロモン情報の更新は、ant の追跡情報を更新するよりもはるかに簡単です。 UpdatePhermones メソッドのコードのキー行です。
double length = Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k]) == true)
increase = (Q / length);
pheromones[i][j] = decrease + increase;
各フェロモン値、蒸発、シミュレーションし増加、フェロモンの預金をシミュレートするアリ歩道上で減少します。 減少効果は、グローバル パラメーター rho の依存 1.0 未満の倍フェロモンの現在の値を乗算することによって生成されます。 大きいローは、フェロモン値の減少が大きいです。 増加の効果は、現在の ant の合計の歩道の長さ、割合が Q グローバル パラメーターによって決まりますの割合を追加することによって生成されます。 Q の値を大きく追加フェロモンの量を増やします。 メソッドの UpdatePheromones 呼び出しヘルパーはセグメントと 2 つの都市間を決定 EdgeInTrail、ant の現在歩道です。 詳細については、この資料のコードのダウンロードを調べることができます (archive.msdn.microsoft.com/mag201202TestRun)。
まとめ
ACO の多くのバリエーションがあることを強調しておきます。 ここで紹介したバージョンを 1 つだけ多くの可能なアプローチです。 ACO の擁護者、アルゴリズム組合せ最適化問題の広い範囲に適用します。 その他組合せオプティmization アルゴリズム自然なシステムの動作に基づいてにはシミュレート焼鈍 (これについては先月説明 SA) が含まれます (msdn.microsoft.com/magazine/hh708758) と模擬蜂コロニー （私は私の 2011 年 4 月のコラムで説明 SBC)、(msdn.microsoft.com/magazine/gg983491)。 各アプローチには、長所と短所があります。 私の意見では、ACO SA と SBC スケジューリングより一般的な組合せ最適化問題のより良いが、密接に巡回セールスマン問題のような問題に適しています。
ACO、他メタヒューリスティクスの自然のシステム上ではお好みの無料グローバル パラメーターにかなり敏感-アルファ、ベータで。 ACO パラメーターに関する研究のビットをかなりされているが、一般的なコンセンサスは、パフォーマンスおよびソリューション品質の最高の組み合わせを取得する無料のパラメーターと実験のビットする必要があることです。
Dr.James McCaffrey作品は Volt Information Sciences Inc.、ここで彼は、Microsoft レドモンド、ワシントン州で、キャンパス働くソフトウェア エンジニアの技術トレーニングを管理します。彼は、Internet Explorer、MSN サーチなど複数のマイクロソフト製品に働いています。McCaffrey の著者である」。NET Test Automation Recipes」』 (Apress、2006年）、jmccaffrey@volt.com または jammc@microsoft.com に行くことができます。
この記事のレビュー、次のマイクロソフト技術専門家に感謝： Dan Liebling とAnne Loomis Thompson