C++ 蟻群算法求解 TSP 問題：原理、參數設置與代碼實現

TSP 問題簡介

旅行商問題：n 個城市，完全圖，邊權為距離。求訪問每城市恰好一次並回到起點的最短迴路。NP-Hard。

蟻群算法（ACO）核心思想

模擬螞蟻覓食：螞蟻釋放信息素標記路徑，傾向選擇信息素濃度高的路徑。關鍵參數：

• 信息素總量：防止過早收斂。
• 觀測範圍：局部決策。
• 出錯概率：隨機探索，避免局部最優。
• 信息素揮發速度：淘汰劣質路徑。
• 記憶：避免重複訪問城市。

應用於 TSP 的改進

• 螞蟻數 m，城市數 n。離散時間步：每步每螞蟻移動到一個未訪問城市。
• 路徑記錄 Path[m][n]。
• 信息素在邊上：Phe[i][j]。
• 更新規則（Ant-Cycle System 效果最好）：
  ΔPhe = Q / L_k（L_k 為第 k 隻螞蟻本次迴路總長），僅在經過的邊上增加。
• 揮發：Phe *= (1 - ρ)（或 Phe *= ρ，ρ<1）。
• 選擇下一城市：機率 ∝ Phe^α * (1/dist)^β，加入隨機扰動。

完整代碼示例（簡化版）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
const int MAXM = 1000;
const double Q = 100.0;
const double RHO = 0.1;      // 揮發係數
const double ALPHA = 1.0;    // 信息素重要性
const double BETA = 2.0;     // 启发式重要性
const double EPS = 1e-9;

int n, m, start;
double dist[MAXN][MAXN];
double phe[MAXN][MAXN];
int path[MAXM][MAXN];
bool visited[MAXM][MAXN];

double heuristic(int i, int j) { return 1.0 / dist[i][j]; }

int selectNext(int ant, int cur) {
    double prob[MAXN] = {0};
    double sum = 0;
    for (int j = 0; j < n; ++j) if (!visited[ant][j]) {
        prob[j] = pow(phe[cur][j], ALPHA) * pow(heuristic(cur, j), BETA);
        sum += prob[j];
    }
    double r = (double)rand() / RAND_MAX * sum;
    double acc = 0;
    for (int j = 0; j < n; ++j) if (!visited[ant][j]) {
        acc += prob[j];
        if (acc >= r) return j;
    }
    return -1;
}

int main() {
    // 讀入 n, dist, start, m...
    // 初始化 phe = 1
    for (int iter = 0; iter < 1000; ++iter) {
        // 每隻螞蟻構建路徑
        for (int ant = 0; ant < m; ++ant) {
            fill(visited[ant], visited[ant]+n, false);
            int cur = start; path[ant][0] = cur; visited[ant][cur] = true;
            for (int step = 1; step < n; ++step) {
                int nxt = selectNext(ant, cur);
                path[ant][step] = nxt; cur = nxt; visited[ant][cur] = true;
            }
        }
        // 信息素揮發
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                phe[i][j] *= (1 - RHO);
        // 信息素更新
        for (int ant = 0; ant < m; ++ant) {
            double L = 0;
            for (int i = 0; i < n-1; ++i) L += dist[path[ant][i]][path[ant][i+1]];
            L += dist[path[ant][n-1]][start];
            for (int i = 0; i < n-1; ++i) {
                int u = path[ant][i], v = path[ant][i+1];
                phe[u][v] += Q / L; phe[v][u] += Q / L;
            }
            phe[path[ant][n-1]][start] += Q / L;
        }
    }
    // 輸出最佳路徑
    return 0;
}

參數調試建議

• m ≈ n ~ 2n，iter ≈ 1000~5000。
• α=1, β=2~5, ρ=0.1~0.5, Q ≈ 平均距離 × n。
• 加入局部優化（如 2-opt）可顯著提升解質量。

局限性

參數敏感，收斂慢，難以保證最優解。實際工程常混合局部搜索或用精確算法（分支定界、動態規劃）解小規模實例。