蚁群算法路径规划的c++实现

蚁群算法是一种基于模拟蚂蚁觅食行为的启发式算法，常用于解决路径规划问题。下面是一个简单的蚁群算法路径规划的C++实现：

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

const int MAXN = 100; // 最大城市数
const int MAXM = 10000; // 最大迭代次数
const double ALPHA = 1.0; // 信息素重要程度因子
const double BETA = 2.0; // 启发函数重要程度因子
const double RHO = 0.5; // 信息素挥发因子
const double Q = 100.0; // 常系数
const double MAX_T = 100.0; // 最大初始信息素浓度
const double MIN_T = 0.1; // 最小初始信息素浓度

int n; // 城市数
double dist[MAXN][MAXN]; // 城市间距离
double tau[MAXN][MAXN]; // 信息素浓度
int ant_num; // 蚂蚁数量
int ant_path[MAXM][MAXN]; // 蚂蚁路径
double ant_dist[MAXM]; // 蚂蚁路径长度
double best_dist; // 最短路径长度
int best_path[MAXN]; // 最短路径

double rand_double() {
    return rand() / (RAND_MAX + 1.0);
}

void init() {
    // 初始化距离和信息素浓度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0.0;
                tau[i][j] = 0.0;
            } else {
                dist[i][j] = rand_double();
                tau[i][j] = MAX_T;
            }
        }
    }
    // 初始化最短路径长度和路径
    best_dist = 1e9;
    for (int i = 0; i < n; i++) {
        best_path[i] = i;
    }
}

void ant_move(int k) {
    int cur_city = rand() % n; // 随机选择起点城市
    ant_path[k][0] = cur_city;
    for (int i = 1; i < n; i++) {
        double sum_prob = 0.0;
        double prob[MAXN];
        for (int j = 0; j < n; j++) {
            if (j == cur_city) {
                prob[j] = 0.0;
            } else {
                prob[j] = pow(tau[cur_city][j], ALPHA) * pow(1.0 / dist[cur_city][j], BETA);
                sum_prob += prob[j];
            }
        }
        double r = rand_double() * sum_prob;
        double tmp_sum_prob = 0.0;
        int next_city;
        for (int j = 0; j < n; j++) {
            if (j == cur_city) {
                continue;
            }
            tmp_sum_prob += prob[j];
            if (tmp_sum_prob >= r) {
                next_city = j;
                break;
            }
        }
        ant_path[k][i] = next_city;
        ant_dist[k] += dist[cur_city][next_city];
        cur_city = next_city;
    }
    ant_dist[k] += dist[ant_path[k][n - 1]][ant_path[k][0]];
}

void update_tau() {
    // 信息素挥发
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tau[i][j] *= (1.0 - RHO);
        }
    }
    // 信息素更新
    for (int k = 0; k < ant_num; k++) {
        double delta_tau = Q / ant_dist[k];
        for (int i = 0; i < n; i++) {
            int cur_city = ant_path[k][i];
            int next_city = ant_path[k][(i + 1) % n];
            tau[cur_city][next_city] += delta_tau;
        }
    }
}

void solve() {
    for (int i = 0; i < MAXM; i++) {
        // 蚂蚁移动
        for (int k = 0; k < ant_num; k++) {
            ant_move(k);
            if (ant_dist[k] < best_dist) {
                best_dist = ant_dist[k];
                for (int j = 0; j < n; j++) {
                    best_path[j] = ant_path[k][j];
                }
            }
        }
        // 更新信息素
        update_tau();
    }
}

int main() {
    srand(time(NULL));
    n = 10;
    ant_num = 50;
    init();
    solve();
    cout << "最短路径长度：" << best_dist << endl;
    cout << "最短路径：";
    for (int i = 0; i < n; i++) {
        cout << best_path[i] << " ";
    }
    cout << endl;
    return 0;
}