蚁群算法c语言源代码

以下是一个基于蚁群算法的TSP问题求解的C语言源代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define MAX_CITY_NUM 100 // 最大城市数量
#define ANTS_NUM 50 // 蚂蚁数量
#define ALPHA 1.0 // 信息素重要程度因子
#define BETA 2.0 // 启发式因子
#define RHO 0.5 // 信息素挥发因子
#define Q 100 // 增加信息素的常数
#define MAX_GEN 200 // 最大迭代次数

int g_city_num; // 城市数量
double g_distance[MAX_CITY_NUM][MAX_CITY_NUM]; // 城市之间的距离
double g_tau[MAX_CITY_NUM][MAX_CITY_NUM]; // 城市之间的信息素
int g_best_tour[MAX_CITY_NUM]; // 最优路径
double g_best_length = 1e9; // 最优路径长度

struct Ant {
    int cur_city; // 当前所在城市
    int tabu[MAX_CITY_NUM]; // 禁忌表
    int tabu_len; // 禁忌表长度
    int tour[MAX_CITY_NUM]; // 路径
    double tour_length; // 路径长度
};

struct Ant ants[ANTS_NUM];

double rand_01() {
    return (double)rand() / RAND_MAX;
}

void init() {
    // 初始化信息素
    for (int i = 0; i < g_city_num; ++i) {
        for (int j = 0; j < g_city_num; ++j) {
            g_tau[i][j] = 1.0;
        }
    }

    // 初始化蚂蚁
    for (int i = 0; i < ANTS_NUM; ++i) {
        ants[i].cur_city = rand() % g_city_num;
        ants[i].tabu[0] = ants[i].cur_city;
        ants[i].tabu_len = 1;
        for (int j = 0; j < g_city_num; ++j) {
            ants[i].tour[j] = -1;
        }
        ants[i].tour[0] = ants[i].cur_city;
        ants[i].tour_length = 0.0;
    }
}

double distance(int city1, int city2) {
    double x1 = 0.0, y1 = 0.0, x2 = 0.0, y2 = 0.0;
    x1 = rand_01();
    y1 = rand_01();
    x2 = rand_01();
    y2 = rand_01();
    return sqrt(pow(x1 - x2, 2.0) + pow(y1 - y2, 2.0));
}

void update_ant(struct Ant* ant) {
    while (ant->tabu_len < g_city_num) {
        int i = ant->cur_city;
        double p[MAX_CITY_NUM] = { 0.0 };
        double p_sum = 0.0;
        for (int j = 0; j < g_city_num; ++j) {
            if (j == i || ant->tabu[j] != -1) {
                continue;
            }
            p[j] = pow(g_tau[i][j], ALPHA) * pow(1.0 / g_distance[i][j], BETA);
            p_sum += p[j];
        }
        double rand_num = p_sum * rand_01();
        int j = -1;
        while (rand_num > 0.0) {
            ++j;
            if (j == g_city_num) {
                j = 0;
            }
            if (ant->tabu[j] == -1) {
                rand_num -= p[j];
            }
        }
        ant->cur_city = j;
        ant->tabu[ant->tabu_len++] = j;
        ant->tour[ant->tabu_len - 1] = j;
        ant->tour_length += g_distance[i][j];
    }
    ant->tour_length += g_distance[ant->tour[g_city_num - 1]][ant->tour[0]];
}

void update_tau() {
    double delta_tau[MAX_CITY_NUM][MAX_CITY_NUM] = { 0.0 };
    for (int i = 0; i < ANTS_NUM; ++i) {
        for (int j = 0; j < g_city_num; ++j) {
            delta_tau[ants[i].tour[j]][ants[i].tour[(j + 1) % g_city_num]] += Q / ants[i].tour_length;
        }
    }
    for (int i = 0; i < g_city_num; ++i) {
        for (int j = 0; j < g_city_num; ++j) {
            g_tau[i][j] = (1.0 - RHO) * g_tau[i][j] + delta_tau[i][j];
        }
    }
}

void search() {
    for (int i = 0; i < MAX_GEN; ++i) {
        for (int j = 0; j < ANTS_NUM; ++j) {
            update_ant(&ants[j]);
            if (ants[j].tour_length < g_best_length) {
                g_best_length = ants[j].tour_length;
                for (int k = 0; k < g_city_num; ++k) {
                    g_best_tour[k] = ants[j].tour[k];
                }
            }
        }
        update_tau();
        for (int j = 0; j < ANTS_NUM; ++j) {
            ants[j].cur_city = rand() % g_city_num;
            ants[j].tabu[0] = ants[j].cur_city;
            ants[j].tabu_len = 1;
            ants[j].tour[0] = ants[j].cur_city;
            ants[j].tour_length = 0.0;
            for (int k = 1; k < g_city_num; ++k) {
                ants[j].tabu[k] = -1;
                ants[j].tour[k] = -1;
            }
        }
    }
}

void print_result() {
    printf("Best tour:\n");
    for (int i = 0; i < g_city_num; ++i) {
        printf("%d ", g_best_tour[i]);
    }
    printf("\nBest tour length: %.2lf\n", g_best_length);
}

int main() {
    srand((unsigned)time(NULL));
    scanf("%d", &g_city_num);
    for (int i = 0; i < g_city_num; ++i) {
        for (int j = 0; j < g_city_num; ++j) {
            g_distance[i][j] = distance(i, j);
        }
    }
    init();
    search();
    print_result();
    return 0;
}

需要注意的是，以上代码中的距离计算函数 `distance` 只是一个示例，实际应用中应根据具体问题进行修改。同时，为了简化代码，禁忌表的实现使用了一个数组，而不是通常所用的哈希表等数据结构。