蚁群算法c++

蚁群算法（Ant Colony Optimization，ACO）是一种模拟蚂蚁觅食行为的优化算法，可用于求解各种优化问题，如最短路径问题、旅行商问题等。

以下是一个简单的蚁群算法的C++实现：

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;

const int MAXN = 100; // 最大城市数
const int MAXM = 10000; // 最大迭代次数
const double ALPHA = 1.0; // 信息素重要程度因子
const double BETA = 5.0; // 启发式因子
const double RHO = 0.5; // 信息素的挥发速度
const double Q = 100.0; // 常量

struct Ant {
    vector<int> path; // 蚂蚁走过的路径
    double length; // 蚂蚁走过的总距离
};

double dist[MAXN][MAXN]; // 城市之间的距离
double pheromone[MAXN][MAXN]; // 城市之间的信息素浓度
int n, m; // 城市数和迭代次数
vector<Ant> ants; // 蚂蚁群

// 初始化
void init() {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0.0;
            } else {
                dist[i][j] = dist[j][i] = rand() % 100 + 1; // 随机生成城市之间的距离
            }
            pheromone[i][j] = 0.1; // 初始化信息素浓度
        }
    }
}

// 选择下一个城市
int selectNextCity(int curCity, vector<bool>& visited) {
    double sum = 0.0;
    double p[MAXN]; // 选择每个城市的概率
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            p[i] = pow(pheromone[curCity][i], ALPHA) * pow(1.0 / dist[curCity][i], BETA);
            sum += p[i];
        } else {
            p[i] = 0.0;
        }
    }
    double randNum = (double)rand() / RAND_MAX;
    double curSum = 0.0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            curSum += p[i] / sum;
            if (randNum <= curSum) {
                return i;
            }
        }
    }
    return -1;
}

// 蚂蚁走一遍路径
void antGo(Ant& ant) {
    vector<bool> visited(n, false); // 标记城市是否已经被访问过
    ant.path.push_back(rand() % n); // 随机选择起点
    visited[ant.path.back()] = true;
    while (ant.path.size() < n) {
        int curCity = ant.path.back();
        int nextCity = selectNextCity(curCity, visited);
        if (nextCity >= 0) {
            ant.path.push_back(nextCity);
            visited[nextCity] = true;
            ant.length += dist[curCity][nextCity];
        } else {
            break;
        }
    }
    ant.length += dist[ant.path.back()][ant.path.front()]; // 回到起点
}

// 更新信息素浓度
void updatePheromone() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pheromone[i][j] *= (1.0 - RHO); // 挥发
        }
    }
    for (int i = 0; i < ants.size(); i++) {
        double delta = Q / ants[i].length;
        for (int j = 0; j < ants[i].path.size() - 1; j++) {
            int from = ants[i].path[j];
            int to = ants[i].path[j + 1];
            pheromone[from][to] += delta;
            pheromone[to][from] += delta;
        }
        pheromone[ants[i].path.back()][ants[i].path.front()] += delta;
        pheromone[ants[i].path.front()][ants[i].path.back()] += delta;
    }
}

// 主函数
int main() {
    n = 10;
    m = 100;
    init();
    Ant bestAnt;
    bestAnt.length = 1e9;
    for (int t = 0; t < m; t++) {
        ants.clear();
        ants.resize(n);
        for (int i = 0; i < n; i++) {
            antGo(ants[i]);
            if (ants[i].length < bestAnt.length) {
                bestAnt = ants[i];
            }
            ants[i].path.clear();
            ants[i].length = 0.0;
        }
        updatePheromone();
    }
    cout << "Best path: ";
    for (int i = 0; i < n; i++) {
        cout << bestAnt.path[i] << " ";
    }
    cout << endl;
    cout << "Best length: " << bestAnt.length << endl;
    return 0;
}

该程序用蚂蚁群算法求解了一个10个城市的旅行商问题，输出了最优路径和长度。