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

以下是使用遗传算法求解旅行商问题的C语言实现代码：

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

#define N 4   // 城市数量
#define POP_SIZE 100  // 种群数量
#define MAX_GEN 1000  // 最大进化代数
#define CROSS_RATE 0.9  // 交叉概率
#define MUT_RATE 0.1  // 变异概率

int dist[N][N] = {  // 城市之间的距离
    { 0, 2, 9, 10 },
    { 1, 0, 6, 4 },
    { 15, 7, 0, 8 },
    { 6, 3, 12, 0 }
};

int pop[POP_SIZE][N];  // 种群
int fitness[POP_SIZE];  // 适应度
int best_path[N+1];  // 记录最优路径
int best_cost = INT_MAX;  // 记录最优路径的长度

// 计算路径长度
int get_path_len(int path[]) {
    int len = 0;
    for(int i=0; i<N-1; i++) {
        len += dist[path[i]][path[i+1]];
    }
    len += dist[path[N-1]][path[0]];
    return len;
}

// 初始化种群
void init_pop() {
    for(int i=0; i<POP_SIZE; i++) {
        for(int j=0; j<N; j++) {
            pop[i][j] = j;
        }
        for(int j=0; j<N; j++) {
            int k = rand() % N;
            int tmp = pop[i][j];
            pop[i][j] = pop[i][k];
            pop[i][k] = tmp;
        }
        fitness[i] = get_path_len(pop[i]);
    }
}

// 选择操作
void select() {
    int new_pop[POP_SIZE][N];
    int new_fitness[POP_SIZE];
    int sum_fitness = 0;
    for(int i=0; i<POP_SIZE; i++) {
        sum_fitness += fitness[i];
    }
    for(int i=0; i<POP_SIZE; i++) {
        int r = rand() % sum_fitness;
        int s = 0;
        for(int j=0; j<POP_SIZE; j++) {
            s += fitness[j];
            if(s >= r) {
                memcpy(new_pop[i], pop[j], N*sizeof(int));
                new_fitness[i] = fitness[j];
                break;
            }
        }
    }
    memcpy(pop, new_pop, POP_SIZE*N*sizeof(int));
    memcpy(fitness, new_fitness, POP_SIZE*sizeof(int));
}

// 交叉操作
void crossover() {
    for(int i=0; i<POP_SIZE; i+=2) {
        if((double)rand() / RAND_MAX < CROSS_RATE) {
            int j = rand() % N;
            int k = rand() % N;
            if(j > k) {
                int tmp = j;
                j = k;
                k = tmp;
            }
            int child1[N] = { 0 };
            int child2[N] = { 0 };
            for(int m=j; m<=k; m++) {
                child1[m] = pop[i+1][m];
                child2[m] = pop[i][m];
            }
            int idx1 = 0;
            int idx2 = 0;
            for(int m=0; m<N; m++) {
                if(idx1 == j) {
                    idx1 = k + 1;
                }
                if(idx2 == j) {
                    idx2 = k + 1;
                }
                if(!child1[m]) {
                    while(idx1 <= k && memchr(child1, pop[i][idx1], N)) {
                        idx1++;
                    }
                    child1[m] = pop[i][idx1];
                    idx1++;
                }
                if(!child2[m]) {
                    while(idx2 <= k && memchr(child2, pop[i+1][idx2], N)) {
                        idx2++;
                    }
                    child2[m] = pop[i+1][idx2];
                    idx2++;
                }
            }
            memcpy(pop[i], child1, N*sizeof(int));
            memcpy(pop[i+1], child2, N*sizeof(int));
        }
    }
}

// 变异操作
void mutate() {
    for(int i=0; i<POP_SIZE; i++) {
        if((double)rand() / RAND_MAX < MUT_RATE) {
            int j = rand() % N;
            int k = rand() % N;
            int tmp = pop[i][j];
            pop[i][j] = pop[i][k];
            pop[i][k] = tmp;
            fitness[i] = get_path_len(pop[i]);
        }
    }
}

// 更新最优路径
void update_best_path() {
    for(int i=0; i<POP_SIZE; i++) {
        if(fitness[i] < best_cost) {
            best_cost = fitness[i];
            memcpy(best_path, pop[i], N*sizeof(int));
        }
    }
}

int main() {
    srand(time(NULL));
    init_pop();
    update_best_path();
    for(int gen=0; gen<MAX_GEN; gen++) {
        select();
        crossover();
        mutate();
        update_best_path();
    }
    printf("Best path: ");
    for(int i=0; i<N; i++) {
        printf("%d ", best_path[i]);
    }
    printf("%d\n", best_path[0]);
    printf("Best cost: %d\n", best_cost);
    return 0;
}

其中，`dist`数组存储了城市之间的距离，`pop`数组存储了种群，`fitness`数组存储了每个个体的适应度，`best_path`数组记录最优路径，`best_cost`记录最优路径的长度。

在`init_pop`函数中，首先将每个个体初始化为一个随机的排列。然后对每个个体计算适应度。

在`select`函数中，使用轮盘赌选择算法选择下一代个体。

在`crossover`函数中，对于每一对父代，如果随机数小于交叉概率，就进行交叉操作。将父代中随机选择的一段基因复制到子代中，然后根据子代中已有的基因确定子代中缺失的基因。这里使用了一个技巧，即先将子代中交叉段的基因初始化为父代2中的相应基因，然后根据子代中已有的基因从父代1中补充缺失的基因。

在`mutate`函数中，对于每个个体，如果随机数小于变异概率，就进行变异操作。随机选择两个基因交换。

在`update_best_path`函数中，更新最优路径和最优路径长度。

在`main`函数中，初始化种群，然后进行迭代。每次迭代都进行选择、交叉、变异操作，然后更新最优路径。迭代结束后，输出最优路径和最优路径长度。

需要注意的是，遗传算法的性能和结果质量受到许多因素的影响，如种群数量、交叉概率、变异概率、选择算法等等。在实际应用中需要结合具体情况选择合适的参数和算法。