c语言蚁群算法解决TSP问题代码

下面是基于C语言实现的蚁群算法解决TSP问题的示例代码：

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

#define NUM_CITIES 10
#define NUM_ANTS 10
#define ALPHA 1.0
#define BETA 5.0
#define RHO 0.1
#define Q 1.0
#define NUM_ITERATIONS 100

double cities[NUM_CITIES][2];
double distances[NUM_CITIES][NUM_CITIES];
double pheromones[NUM_CITIES][NUM_CITIES];

double get_distance(int city1, int city2) {
    double dx = cities[city1][0] - cities[city2][0];
    double dy = cities[city1][1] - cities[city2][1];
    return sqrt(dx * dx + dy * dy);
}

void init_distances() {
    for (int i = 0; i < NUM_CITIES; i++) {
        for (int j = 0; j < NUM_CITIES; j++) {
            distances[i][j] = get_distance(i, j);
        }
    }
}

void init_pheromones() {
    for (int i = 0; i < NUM_CITIES; i++) {
        for (int j = 0; j < NUM_CITIES; j++) {
            pheromones[i][j] = 1.0;
        }
    }
}

void init_cities() {
    srand(time(NULL));
    for (int i = 0; i < NUM_CITIES; i++) {
        cities[i][0] = rand() % 100;
        cities[i][1] = rand() % 100;
    }
}

void update_pheromones(int best_ant_position[]) {
    double delta_pheromones[NUM_CITIES][NUM_CITIES] = {0};
    for (int i = 0; i < NUM_ANTS; i++) {
        double path_distance = 0;
        for (int j = 0; j < NUM_CITIES - 1; j++) {
            int current_city = best_ant_position[i * NUM_CITIES + j];
            int next_city = best_ant_position[i * NUM_CITIES + j + 1];
            path_distance += distances[current_city][next_city];
        }
        delta_pheromones[NUM_CITIES - 1][best_ant_position[i * NUM_CITIES]] += Q / path_distance;
        for (int j = 0; j < NUM_CITIES - 1; j++) {
            int current_city = best_ant_position[i * NUM_CITIES + j];
            int next_city = best_ant_position[i * NUM_CITIES + j + 1];
            delta_pheromones[current_city][next_city] += Q / path_distance;
        }
    }
    for (int i = 0; i < NUM_CITIES; i++) {
        for (int j = 0; j < NUM_CITIES; j++) {
            pheromones[i][j] = (1 - RHO) * pheromones[i][j] + delta_pheromones[i][j];
        }
    }
}

int select_next_city(int ant_position[], int num_visited_cities) {
    double probabilities[NUM_CITIES] = {0};
    double total_probability = 0;
    int current_city = ant_position[num_visited_cities - 1];
    for (int i = 0; i < NUM_CITIES; i++) {
        if (!ant_position[i]) {
            double pheromone = pow(pheromones[current_city][i], ALPHA);
            double distance = pow(1.0 / distances[current_city][i], BETA);
            probabilities[i] = pheromone * distance;
            total_probability += probabilities[i];
        }
    }
    if (total_probability == 0) {
        for (int i = 0; i < NUM_CITIES; i++) {
            if (!ant_position[i]) {
                return i;
            }
        }
    }
    double r = (double)rand() / RAND_MAX;
    double sum = 0;
    for (int i = 0; i < NUM_CITIES; i++) {
        if (!ant_position[i]) {
            sum += probabilities[i] / total_probability;
            if (r <= sum) {
                return i;
            }
        }
    }
    return -1;
}

void search(int best_ant_position[]) {
    for (int iteration = 0; iteration < NUM_ITERATIONS; iteration++) {
        int ant_positions[NUM_ANTS][NUM_CITIES] = {0};
        for (int i = 0; i < NUM_ANTS; i++) {
            ant_positions[i][0] = rand() % NUM_CITIES;
        }
        for (int i = 0; i < NUM_ANTS; i++) {
            for (int j = 1; j < NUM_CITIES; j++) {
                int next_city = select_next_city(ant_positions[i], j);
                ant_positions[i][j] = next_city;
            }
        }
        double best_distance = -1;
        for (int i = 0; i < NUM_ANTS; i++) {
            double path_distance = 0;
            for (int j = 0; j < NUM_CITIES - 1; j++) {
                int current_city = ant_positions[i][j];
                int next_city = ant_positions[i][j + 1];
                path_distance += distances[current_city][next_city];
            }
            int last_city = ant_positions[i][NUM_CITIES - 1];
            int first_city = ant_positions[i][0];
            path_distance += distances[last_city][first_city];
            if (best_distance == -1 || path_distance < best_distance) {
                best_distance = path_distance;
                for (int j = 0; j < NUM_CITIES; j++) {
                    best_ant_position[i * NUM_CITIES + j] = ant_positions[i][j];
                }
            }
        }
        update_pheromones(best_ant_position);
    }
}

int main() {
    init_cities();
    init_distances();
    init_pheromones();
    int best_ant_position[NUM_ANTS * NUM_CITIES] = {0};
    search(best_ant_position);
    double best_distance = -1;
    for (int i = 0; i < NUM_ANTS; i++) {
        double path_distance = 0;
        for (int j = 0; j < NUM_CITIES - 1; j++) {
            int current_city = best_ant_position[i * NUM_CITIES + j];
            int next_city = best_ant_position[i * NUM_CITIES + j + 1];
            path_distance += distances[current_city][next_city];
        }
        int last_city = best_ant_position[i * NUM_CITIES + NUM_CITIES - 1];
        int first_city = best_ant_position[i * NUM_CITIES];
        path_distance += distances[last_city][first_city];
        if (best_distance == -1 || path_distance < best_distance) {
            best_distance = path_distance;
        }
    }
    printf("Best distance: %f\n", best_distance);
    return 0;
}

这段代码中，我们使用了二维数组来存储城市坐标、距离以及信息素，使用了随机数生成城市坐标。在搜索过程中，我们使用了二维数组来存储每只蚂蚁的位置，使用了选择下一个城市的函数来确定每只蚂蚁的行动。在更新信息素矩阵时，我们使用了二维数组来存储每只蚂蚁的路径，并计算出每只蚂蚁路径上的信息素增量。最后，我们输出最优路径和最优距离。