c遗传算法解决旅行商问题

遗传算法是一种基于生物进化原理的优化算法，可以用于解决旅行商问题。其基本思想是通过模拟生物进化过程，不断地从种群中筛选出适应度高的个体，并通过交叉、变异等操作产生新的个体，最终得到最优解。

以下是使用C语言实现遗传算法解决旅行商问题的基本步骤：

1. 初始化种群：随机生成一定数量的个体，每个个体表示一条路径，即旅行商要依次经过的城市序列。

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

3. 选择操作：根据适应度大小选择一定数量的个体作为下一代的父代。

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

5. 变异操作：对新的个体进行变异操作，引入新的基因。

6. 更新种群：将新的个体加入种群中，替换掉适应度较低的个体。

7. 判断终止条件：当达到预设的迭代次数或者找到最优解时，停止算法。

以下是一个简单的C语言程序，用遗传算法解决旅行商问题：

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

#define CITY_NUM 10 // 城市数量
#define POP_SIZE 100 // 种群大小
#define MAX_GEN 1000 // 最大迭代次数
#define CROSS_RATE 0.8 // 交叉概率
#define MUTATE_RATE 0.1 // 变异概率

// 城市坐标
int city[CITY_NUM][2] = {
    {1304, 2312}, {3639, 1315}, {4177, 2244}, {3712, 1399}, {3488, 1535},
    {3326, 1556}, {3238, 1229}, {4196, 1004}, {4312, 790}, {4386, 570}
};

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

// 种群结构体
typedef struct {
    Individual pop[POP_SIZE]; // 个体数组
    Individual best; // 最优个体
} Population;

// 计算两个城市之间的距离
double distance(int city1[], int city2[]) {
    return sqrt(pow(city1[0] - city2[0], 2) + pow(city1[1] - city2[1], 2));
}

// 计算个体的路径长度和适应度
void calc_fitness(Individual *ind) {
    double len = 0;
    for (int i = 0; i < CITY_NUM - 1; i++) {
        len += distance(city[ind->path[i]], city[ind->path[i+1]]);
    }
    len += distance(city[ind->path[CITY_NUM-1]], city[ind->path[0]]);
    ind->fitness = 1 / len;
}

// 初始化个体
void init_individual(Individual *ind) {
    for (int i = 0; i < CITY_NUM; i++) {
        ind->path[i] = i;
    }
    for (int i = 0; i < CITY_NUM; i++) {
        int j = rand() % CITY_NUM;
        int temp = ind->path[i];
        ind->path[i] = ind->path[j];
        ind->path[j] = temp;
    }
    calc_fitness(ind);
}

// 初始化种群
void init_population(Population *pop) {
    for (int i = 0; i < POP_SIZE; i++) {
        init_individual(&pop->pop[i]);
        if (i == 0 || pop->pop[i].fitness > pop->best.fitness) {
            pop->best = pop->pop[i];
        }
    }
}

// 选择操作
void selection(Population *pop, Individual *parent1, Individual *parent2) {
    int i, j;
    i = rand() % POP_SIZE;
    j = rand() % POP_SIZE;
    *parent1 = pop->pop[i].fitness > pop->pop[j].fitness ? pop->pop[i] : pop->pop[j];
    i = rand() % POP_SIZE;
    j = rand() % POP_SIZE;
    *parent2 = pop->pop[i].fitness > pop->pop[j].fitness ? pop->pop[i] : pop->pop[j];
}

// 交叉操作
void crossover(Individual *parent1, Individual *parent2, Individual *child1, Individual *child2) {
    int i, j, k;
    i = rand() % CITY_NUM;
    j = rand() % CITY_NUM;
    if (i > j) {
        k = i;
        i = j;
        j = k;
    }
    for (int m = 0; m < CITY_NUM; m++) {
        child1->path[m] = -1;
        child2->path[m] = -1;
    }
    for (int m = i; m <= j; m++) {
        child1->path[m] = parent1->path[m];
        child2->path[m] = parent2->path[m];
    }
    int c1 = j + 1;
    int c2 = j + 1;
    for (int m = j + 1; m < CITY_NUM + j + 1; m++) {
        int n = m % CITY_NUM;
        if (child1->path[n] == -1) {
            while (parent2->path[c1 % CITY_NUM] == child1->path[c1 % CITY_NUM]) {
                c1++;
            }
            child1->path[n] = parent2->path[c1 % CITY_NUM];
            c1++;
        }
        if (child2->path[n] == -1) {
            while (parent1->path[c2 % CITY_NUM] == child2->path[c2 % CITY_NUM]) {
                c2++;
            }
            child2->path[n] = parent1->path[c2 % CITY_NUM];
            c2++;
        }
    }
    calc_fitness(child1);
    calc_fitness(child2);
}

// 变异操作
void mutation(Individual *ind) {
    int i, j;
    i = rand() % CITY_NUM;
    j = rand() % CITY_NUM;
    int temp = ind->path[i];
    ind->path[i] = ind->path[j];
    ind->path[j] = temp;
    calc_fitness(ind);
}

// 更新种群
void update_population(Population *pop, Individual *child1, Individual *child2) {
    int worst = 0;
    for (int i = 0; i < POP_SIZE; i++) {
        if (pop->pop[i].fitness < pop->pop[worst].fitness) {
            worst = i;
        }
    }
    if (child1->fitness > child2->fitness) {
        if (child1->fitness > pop->pop[worst].fitness) {
            pop->pop[worst] = *child1;
        }
        if (child1->fitness > pop->best.fitness) {
            pop->best = *child1;
        }
    } else {
        if (child2->fitness > pop->pop[worst].fitness) {
            pop->pop[worst] = *child2;
        }
        if (child2->fitness > pop->best.fitness) {
            pop->best = *child2;
        }
    }
}

// 遗传算法求解旅行商问题
void tsp_ga() {
    srand((unsigned)time(NULL));
    Population pop;
    Individual parent1, parent2, child1, child2;
    init_population(&pop);
    for (int i = 0; i < MAX_GEN; i++) {
        for (int j = 0; j < POP_SIZE / 2; j++) {
            selection(&pop, &parent1, &parent2);
            if ((double)rand() / RAND_MAX < CROSS_RATE) {
                crossover(&parent1, &parent2, &child1, &child2);
            } else {
                child1 = parent1;
                child2 = parent2;
            }
            if ((double)rand() / RAND_MAX < MUTATE_RATE) {
                mutation(&child1);
            }
            if ((double)rand() / RAND_MAX < MUTATE_RATE) {
                mutation(&child2);
            }
            update_population(&pop, &child1, &child2);
        }
        printf("Generation %d: %lf\n", i+1, pop.best.fitness);
    }
    printf("Best path: ");
    for (int i = 0; i < CITY_NUM; i++) {
        printf("%d ", pop.best.path[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    tsp_ga();
    return 0;
}