Javaの例によるアリコロニー最適化

投稿日: 2019-10-19 2022-11-10
タグ: Algorithms

1. 序章

このシリーズの目的は、遺伝的アルゴリズムの概念を説明し、最もよく知られている実装を示すことです。

このチュートリアルでは、アリコロニー最適化（ACO）の概念を説明し、その後にコード例を示します。

2. ACOの仕組み

ACOは、アリの自然な行動に触発された遺伝的アルゴリズムです。 ACOアルゴリズムを完全に理解するには、その基本的な概念に精通する必要があります。

アリはフェロモンを使用して、家と食料源の間の最短経路を見つけます
フェロモンはすぐに蒸発します
アリはより密度の高いフェロモンでより短い経路を使用することを好みます

巡回セールスマン問題で使用されるACOの簡単な例を示しましょう。次の場合、グラフ内のすべてのノード間の最短経路を見つける必要があります。

自然な行動に続いて、アリは探索中に新しい道を探索し始めます。濃い青色は他の経路よりも頻繁に使用される経路を示し、緑色は現在見つかっている最短経路を示します。

その結果、すべてのノード間の最短パスを実現します。

ACOテスト用の優れたGUIベースのツールは、ここにあります。

3. Javaの実装

3.1. ACOパラメータ

AntColonyOptimizationクラスで宣言されたACOアルゴリズムの主なパラメーターについて説明しましょう。

private double c = 1.0;
private double alpha = 1;
private double beta = 5;
private double evaporation = 0.5;
private double Q = 500;
private double antFactor = 0.8;
private double randomFactor = 0.01;

パラメータcは、シミュレーション開始時の元のトレイル数を示します。さらに、 alpha はフェロモンの重要性を制御し、betaは距離の優先度を制御します。 通常、最良の結果を得るには、ベータパラメータをアルファより大きくする必要があります。

次に、 evaporation 変数は、すべての反復でフェロモンが蒸発している量のパーセントを示しますが、 Q は、各Antによってトレイルに残っているフェロモンの総量に関する情報を提供します、および antFactor は、都市ごとに使用するアリの数を示します。

最後に、シミュレーションで少しランダムにする必要があります。これはrandomFactorでカバーされています。

3.2. アリを作成する

各Antは、特定の都市を訪問し、訪問したすべての都市を記憶し、トレイルの長さを追跡することができます。

public void visitCity(int currentIndex, int city) {
    trail[currentIndex + 1] = city;
    visited[city] = true;
}

public boolean visited(int i) {
    return visited[i];
}

public double trailLength(double graph[][]) {
    double length = graph[trail[trailSize - 1]][trail[0]];
    for (int i = 0; i < trailSize - 1; i++) {
        length += graph[trail[i]][trail[i + 1]];
    }
    return length;
}

3.3. アリの設定

最初に、トレイルとアリの行列を提供して、ACOコードの実装を初期化する必要があります。

graph = generateRandomMatrix(noOfCities);
numberOfCities = graph.length;
numberOfAnts = (int) (numberOfCities * antFactor);

trails = new double[numberOfCities][numberOfCities];
probabilities = new double[numberOfCities];
ants = new Ant[numberOfAnts];
IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

次に、ランダムな都市から開始するために、アリマトリックスを設定する必要があります。

public void setupAnts() {
    IntStream.range(0, numberOfAnts)
      .forEach(i -> {
          ants.forEach(ant -> {
              ant.clear();
              ant.visitCity(-1, random.nextInt(numberOfCities));
          });
      });
    currentIndex = 0;
}

ループの反復ごとに、次の操作を実行します。

IntStream.range(0, maxIterations).forEach(i -> {
    moveAnts();
    updateTrails();
    updateBest();
});

3.4. アリを動かす

moveAnts（）メソッドから始めましょう。 すべてのアリの次の都市を選択する必要があります。各アリが他のアリの軌跡をたどろうとしていることを思い出してください。

public void moveAnts() {
    IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> {
        ants.forEach(ant -> {
            ant.visitCity(currentIndex, selectNextCity(ant));
        });
        currentIndex++;
    });
}

最も重要な部分は、訪問する次の都市を適切に選択することです。確率論理に基づいて次の町を選択する必要があります。まず、Antがランダムな都市を訪問する必要があるかどうかを確認できます。

int t = random.nextInt(numberOfCities - currentIndex);
if (random.nextDouble() < randomFactor) {
    OptionalInt cityIndex = IntStream.range(0, numberOfCities)
      .filter(i -> i == t && !ant.visited(i))
      .findFirst();
    if (cityIndex.isPresent()) {
        return cityIndex.getAsInt();
    }
}

ランダムな都市を選択しなかった場合、アリはより強く短い道をたどることを好むことを思い出して、次の都市を選択する確率を計算する必要があります。これを行うには、各都市に移動する確率を配列に格納します。

public void calculateProbabilities(Ant ant) {
    int i = ant.trail[currentIndex];
    double pheromone = 0.0;
    for (int l = 0; l < numberOfCities; l++) {
        if (!ant.visited(l)){
            pheromone
              += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta);
        }
    }
    for (int j = 0; j < numberOfCities; j++) {
        if (ant.visited(j)) {
            probabilities[j] = 0.0;
        } else {
            double numerator
              = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta);
            probabilities[j] = numerator / pheromone;
        }
    }
}

確率を計算した後、次を使用してどの都市に行くかを決定できます。

double r = random.nextDouble();
double total = 0;
for (int i = 0; i < numberOfCities; i++) {
    total += probabilities[i];
    if (total >= r) {
        return i;
    }
}

3.5. トレイルの更新

このステップでは、トレイルと左フェロモンを更新する必要があります。

public void updateTrails() {
    for (int i = 0; i < numberOfCities; i++) {
        for (int j = 0; j < numberOfCities; j++) {
            trails[i][j] *= evaporation;
        }
    }
    for (Ant a : ants) {
        double contribution = Q / a.trailLength(graph);
        for (int i = 0; i < numberOfCities - 1; i++) {
            trails[a.trail[i]][a.trail[i + 1]] += contribution;
        }
        trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution;
    }
}

3.6. 最良のソリューションを更新する

これは、各反復の最後のステップです。それへの参照を維持するために、最良のソリューションを更新する必要があります。

private void updateBest() {
    if (bestTourOrder == null) {
        bestTourOrder = ants[0].trail;
        bestTourLength = ants[0].trailLength(graph);
    }
    for (Ant a : ants) {
        if (a.trailLength(graph) < bestTourLength) {
            bestTourLength = a.trailLength(graph);
            bestTourOrder = a.trail.clone();
        }
    }
}

すべての反復の後、最終結果はACOによって検出された最適なパスを示します。都市の数を増やすと、最短経路を見つける確率が低くなることに注意してください。

4. 結論

このチュートリアルでは、アリコロニー最適化アルゴリズムを紹介します。この分野の予備知識がなくても遺伝的アルゴリズムについて学ぶことができ、基本的なコンピュータープログラミングスキルしかありません。

このチュートリアルのコードスニペットの完全なソースコードは、GitHubプロジェクトで利用できます。

遺伝的アルゴリズムの他の例を含むシリーズのすべての記事については、次のリンクを確認してください。

getdocs

13036