用C语言实现蚁群算法

以下是一个简单的C语言实现蚁群算法的示例代码：

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

#define MAX_CITIES 100
#define MAX_ANTS 10
#define ALPHA 1.0
#define BETA 5.0
#define RHO 0.5
#define QVAL 100.0
#define MAX_TOURS 100
#define MAX_TIME (MAX_CITIES * MAX_TOURS)

// 城市坐标
typedef struct {
    int x, y;
} cityType;

// 蚂蚁
typedef struct {
    int curCity, nextCity;
    int path[MAX_CITIES];
    int visited[MAX_CITIES];
    double tourLength;
} antType;

// 全局变量
int numCities, numAnts;
cityType cities[MAX_CITIES];
antType ants[MAX_ANTS];
double dist[MAX_CITIES][MAX_CITIES];
double pheromone[MAX_CITIES][MAX_CITIES];
double bestTourLength;
int bestTour[MAX_CITIES];

// 初始化城市坐标
void initCities() {
    int i;
    for (i = 0; i < numCities; i++) {
        cities[i].x = rand() % 100;
        cities[i].y = rand() % 100;
    }
}

// 计算两个城市之间的距离
double distance(cityType city1, cityType city2) {
    double dx = (double)(city1.x - city2.x);
    double dy = (double)(city1.y - city2.y);
    return sqrt(dx * dx + dy * dy);
}

// 初始化距离矩阵和信息素矩阵
void initDistPhero() {
    int i, j;
    for (i = 0; i < numCities; i++) {
        for (j = 0; j < numCities; j++) {
            dist[i][j] = distance(cities[i], cities[j]);
            pheromone[i][j] = 0.1;
        }
    }
}

// 初始化蚂蚁
void initAnts() {
    int i, j, k;
    for (i = 0; i < numAnts; i++) {
        ants[i].curCity = rand() % numCities;
        for (j = 0; j < numCities; j++) {
            ants[i].visited[j] = 0;
            ants[i].path[j] = -1;
        }
        ants[i].path[0] = ants[i].curCity;
        ants[i].visited[ants[i].curCity] = 1;
        ants[i].nextCity = -1;
        ants[i].tourLength = 0.0;
    }
}

// 选择下一个城市
int selectNextCity(int ant) {
    int i, j;
    double denom = 0.0;
    for (i = 0; i < numCities; i++) {
        if (!ants[ant].visited[i]) {
            denom += pow(pheromone[ants[ant].curCity][i], ALPHA) * pow(1.0 / dist[ants[ant].curCity][i], BETA);
        }
    }
    if (denom == 0.0) {
        denom = 1.0;
    }
    for (i = 0; i < numCities; i++) {
        if (ants[ant].visited[i]) {
            continue;
        }
        double prob = pow(pheromone[ants[ant].curCity][i], ALPHA) * pow(1.0 / dist[ants[ant].curCity][i], BETA) / denom;
        double randNum = ((double)rand() / (double)RAND_MAX);
        if (randNum < prob) {
            return i;
        }
    }
    return -1;
}

// 更新信息素矩阵
void updatePheromone() {
    int i, j, ant;
    for (i = 0; i < numCities; i++) {
        for (j = 0; j < numCities; j++) {
            pheromone[i][j] *= (1.0 - RHO);
        }
    }
    for (ant = 0; ant < numAnts; ant++) {
        for (i = 0; i < numCities - 1; i++) {
            int from = ants[ant].path[i];
            int to = ants[ant].path[i + 1];
            pheromone[from][to] += (QVAL / ants[ant].tourLength);
            pheromone[to][from] = pheromone[from][to];
        }
        pheromone[ants[ant].path[numCities - 1]][ants[ant].path[0]] += (QVAL / ants[ant].tourLength);
        pheromone[ants[ant].path[0]][ants[ant].path[numCities - 1]] = pheromone[ants[ant].path[numCities - 1]][ants[ant].path[0]];
    }
}

// 运行蚁群算法
void antColonyOptimization() {
    int i, j, k;
    int curTime = 0;
    bestTourLength = 100000.0;
    while (curTime < MAX_TIME) {
        for (i = 0; i < numAnts; i++) {
            for (j = 0; j < numCities - 1; j++) {
                ants[i].nextCity = selectNextCity(i);
                ants[i].visited[ants[i].nextCity] = 1;
                ants[i].path[j + 1] = ants[i].nextCity;
                ants[i].tourLength += dist[ants[i].curCity][ants[i].nextCity];
                ants[i].curCity = ants[i].nextCity;
            }
            ants[i].tourLength += dist[ants[i].path[numCities - 1]][ants[i].path[0]];
            if (ants[i].tourLength < bestTourLength) {
                bestTourLength = ants[i].tourLength;
                for (k = 0; k < numCities; k++) {
                    bestTour[k] = ants[i].path[k];
                }
            }
            ants[i].curCity = rand() % numCities;
            for (j = 0; j < numCities; j++) {
                ants[i].visited[j] = 0;
                ants[i].path[j] = -1;
            }
            ants[i].path[0] = ants[i].curCity;
            ants[i].visited[ants[i].curCity] = 1;
            ants[i].nextCity = -1;
            ants[i].tourLength = 0.0;
        }
        updatePheromone();
        curTime++;
    }
    printf("Best tour length: %lf\n", bestTourLength);
    printf("Best tour: ");
    for (i = 0; i < numCities; i++) {
        printf("%d ", bestTour[i]);
    }
    printf("\n");
}

int main() {
    srand(time(NULL));
    numCities = 20;
    numAnts = 5;
    initCities();
    initDistPhero();
    initAnts();
    antColonyOptimization();
    return 0;
}

在这个示例中，我们通过调用 `antColonyOptimization` 函数来运行蚁群算法。在算法中，我们先定义了城市坐标、蚂蚁和全局变量等结构体，然后定义了初始化城市坐标、计算两个城市之间的距离、初始化距离矩阵和信息素矩阵、初始化蚂蚁、选择下一个城市、更新信息素矩阵等函数。在 `antColonyOptimization` 函数中，我们首先初始化全局变量，然后进行一系列迭代，在每次迭代中选择下一个城市、更新蚂蚁路径和目标函数值、更新信息素矩阵。最终，输出得到的最优解及其目标函数值。

需要注意的是，这只是一个简单的示例代码，实际应用中需要根据具体问题进行相应的修改和调整。