C语言实现用遗传算法解旅行商问题

下面是一个简单的C语言实现，用遗传算法解决旅行商问题。代码实现中采用了两种常用的选择方法：轮盘赌选择和锦标赛选择。具体实现步骤如下：

1. 初始化种群：随机生成多个个体，每个个体表示一条可能的路径。

2. 评估适应度：根据路径长度计算每个个体的适应度，路径长度越短适应度越高。

3. 选择父代：根据适应度选择优秀的个体作为父代，可以采用轮盘赌选择、锦标赛选择等方法。

4. 交叉繁殖：对选出的父代进行交叉操作，生成新的子代个体。

5. 变异操作：对新生成的子代进行变异操作，保持种群的多样性。

6. 更新种群：将新生成的子代加入到种群中，取代部分不适应的个体。

7. 终止条件：当达到预设的迭代次数或者找到一条满意的路径时，终止算法。

以下是代码实现，仅供参考：

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

#define CITY_NUM 10   // 城市数量
#define POP_SIZE 50   // 种群大小
#define MAX_GENERATION 500   // 最大迭代次数
#define MUTATION_RATE 0.01   // 变异率
#define TOURNAMENT_SIZE 3    // 锦标赛选择的选择个体数量

// 城市坐标结构体
struct City {
    int x;
    int y;
};

// 种群个体结构体
struct Individual {
    int path[CITY_NUM];   // 路径
    double fitness;       // 适应度
};

// 计算欧几里得距离
double calcDistance(struct City city1, struct City city2) {
    return sqrt(pow(city1.x - city2.x, 2) + pow(city1.y - city2.y, 2));
}

// 计算路径长度
double calcPathLength(int path[]) {
    double length = 0.0;
    for (int i = 0; i < CITY_NUM - 1; i++) {
        length += calcDistance(cities[path[i]], cities[path[i + 1]]);
    }
    length += calcDistance(cities[path[CITY_NUM - 1]], cities[path[0]]);
    return length;
}

// 初始化种群
void initPopulation(struct Individual population[]) {
    for (int i = 0; i < POP_SIZE; i++) {
        for (int j = 0; j < CITY_NUM; j++) {
            population[i].path[j] = j;
        }
        for (int j = 0; j < CITY_NUM; j++) {
            int k = rand() % CITY_NUM;
            int temp = population[i].path[j];
            population[i].path[j] = population[i].path[k];
            population[i].path[k] = temp;
        }
        population[i].fitness = 1.0 / calcPathLength(population[i].path);
    }
}

// 轮盘赌选择
int rouletteWheelSelection(struct Individual population[]) {
    double totalFitness = 0.0;
    for (int i = 0; i < POP_SIZE; i++) {
        totalFitness += population[i].fitness;
    }
    double randNum = (double)rand() / RAND_MAX * totalFitness;
    double sum = 0.0;
    for (int i = 0; i < POP_SIZE; i++) {
        sum += population[i].fitness;
        if (sum > randNum) {
            return i;
        }
    }
    return POP_SIZE - 1;
}

// 锦标赛选择
int tournamentSelection(struct Individual population[]) {
    int bestIndex = rand() % POP_SIZE;
    double bestFitness = population[bestIndex].fitness;
    for (int i = 1; i < TOURNAMENT_SIZE; i++) {
        int index = rand() % POP_SIZE;
        if (population[index].fitness > bestFitness) {
            bestIndex = index;
            bestFitness = population[index].fitness;
        }
    }
    return bestIndex;
}

// 交叉操作
void crossover(int parent1[], int parent2[], int child[]) {
    int startPos = rand() % CITY_NUM;
    int endPos = rand() % CITY_NUM;
    if (startPos > endPos) {
        int temp = startPos;
        startPos = endPos;
        endPos = temp;
    }
    for (int i = 0; i < CITY_NUM; i++) {
        child[i] = -1;
    }
    for (int i = startPos; i <= endPos; i++) {
        child[i] = parent1[i];
    }
    int curIndex = endPos + 1;
    for (int i = 0; i < CITY_NUM; i++) {
        if (curIndex == CITY_NUM) {
            curIndex = 0;
        }
        int city = parent2[i];
        if (child[curIndex] == -1) {
            while (1) {
                int j;
                for (j = startPos; j <= endPos; j++) {
                    if (city == child[j]) {
                        break;
                    }
                }
                if (j == endPos + 1) {
                    break;
                }
                city = parent2[++i];
            }
            child[curIndex++] = city;
        }
    }
}

// 变异操作
void mutate(int path[]) {
    for (int i = 0; i < CITY_NUM; i++) {
        if ((double)rand() / RAND_MAX < MUTATION_RATE) {
            int j = rand() % CITY_NUM;
            int temp = path[i];
            path[i] = path[j];
            path[j] = temp;
        }
    }
}

// 更新种群
void updatePopulation(struct Individual population[], struct Individual newPopulation[]) {
    for (int i = 0; i < POP_SIZE; i++) {
        population[i] = newPopulation[i];
    }
}

// 遗传算法求解旅行商问题
void solveTSP() {
    // 初始化城市坐标
    struct City cities[CITY_NUM] = {
        {1304, 2312}, {3639, 1315}, {4177, 2244}, {3712, 1399}, {3488, 1535},
        {3326, 1556}, {3238, 1229}, {4196, 1004}, {4312, 790}, {4386, 570}
    };

    // 初始化种群
    struct Individual population[POP_SIZE];
    initPopulation(population);

    // 迭代计算
    for (int generation = 0; generation < MAX_GENERATION; generation++) {
        struct Individual newPopulation[POP_SIZE];
        for (int i = 0; i < POP_SIZE; i++) {
            int parent1 = rouletteWheelSelection(population);
            int parent2 = tournamentSelection(population);
            crossover(population[parent1].path, population[parent2].path, newPopulation[i].path);
            mutate(newPopulation[i].path);
            newPopulation[i].fitness = 1.0 / calcPathLength(newPopulation[i].path);
        }
        updatePopulation(population, newPopulation);
    }

    // 输出结果
    int bestIndex = 0;
    for (int i = 1; i < POP_SIZE; i++) {
        if (population[i].fitness > population[bestIndex].fitness) {
            bestIndex = i;
        }
    }
    printf("Best path length: %.2f\n", 1.0 / population[bestIndex].fitness);
    printf("Best path: ");
    for (int i = 0; i < CITY_NUM; i++) {
        printf("%d ", population[bestIndex].path[i]);
    }
    printf("\n");
}

int main() {
    srand((unsigned int)time(NULL));
    solveTSP();
    return 0;
}