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

遗传算法是一种优化算法，可以用于解决旅行商问题。以下是C语言遗传算法解决旅行商问题的步骤：

1.初始化种群：生成一组随机的路径作为初始种群。
2.计算适应度：对于每个个体（路径），计算其总距离作为适应度。
3.选择操作：使用轮盘赌选择算法，根据适应度选择一些个体进行交叉互换和变异操作。
4.交叉互换：随机选择两个个体，选择一个交叉点，将两个个体在交叉点处交叉互换，生成两个新的个体。
5.变异操作：对于每个个体，以一定的概率进行变异操作，例如随机选择两个位置，将它们交换。
6.重复执行2-5步，直到达到预设的迭代次数或找到最优解。

以下是一个简单的C语言遗传算法解决旅行商问题的代码示例：

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

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

int g_Distance[CITY_NUM][CITY_NUM]; // 城市之间的距离矩阵
int g_Group[POP_SIZE][CITY_NUM]; // 种群
int g_Fitness[POP_SIZE]; // 适应度

// 计算两个城市之间的距离
int Distance(int city1, int city2) {
    return g_Distance[city1][city2];
}

// 计算一条路径的总距离
int PathDistance(int path[]) {
    int distance = 0;
    for (int i = 0; i < CITY_NUM - 1; i++) {
        distance += Distance(path[i], path[i+1]);
    }
    distance += Distance(path[CITY_NUM-1], path[0]);
    return distance;
}

// 初始化种群
void InitGroup() {
    for (int i = 0; i < POP_SIZE; i++) {
        for (int j = 0; j < CITY_NUM; j++) {
            g_Group[i][j] = j;
        }
        for (int j = 0; j < CITY_NUM; j++) {
            int k = rand() % CITY_NUM;
            int temp = g_Group[i][j];
            g_Group[i][j] = g_Group[i][k];
            g_Group[i][k] = temp;
        }
        g_Fitness[i] = PathDistance(g_Group[i]);
    }
}

// 选择操作
void Select() {
    int newGroup[POP_SIZE][CITY_NUM];
    int newFitness[POP_SIZE];
    int sumFitness = 0;
    for (int i = 0; i < POP_SIZE; i++) {
        sumFitness += g_Fitness[i];
    }
    for (int i = 0; i < POP_SIZE; i++) {
        int r = rand() % sumFitness;
        int s = 0;
        for (int j = 0; j < POP_SIZE; j++) {
            s += g_Fitness[j];
            if (s >= r) {
                for (int k = 0; k < CITY_NUM; k++) {
                    newGroup[i][k] = g_Group[j][k];
                }
                newFitness[i] = g_Fitness[j];
                break;
            }
        }
    }
    for (int i = 0; i < POP_SIZE; i++) {
        for (int j = 0; j < CITY_NUM; j++) {
            g_Group[i][j] = newGroup[i][j];
        }
        g_Fitness[i] = newFitness[i];
    }
}

// 交叉互换
void Cross() {
    for (int i = 0; i < POP_SIZE; i += 2) {
        if ((double)rand() / RAND_MAX < CROSS_RATE) {
            int sel1 = rand() % POP_SIZE;
            int sel2 = rand() % POP_SIZE;
            int pos1 = rand() % CITY_NUM;
            int pos2 = rand() % CITY_NUM;
            if (pos1 > pos2) {
                int temp = pos1;
                pos1 = pos2;
                pos2 = temp;
            }
            int child1[CITY_NUM];
            int child2[CITY_NUM];
            for (int j = 0; j < CITY_NUM; j++) {
                child1[j] = -1;
                child2[j] = -1;
            }
            for (int j = pos1; j <= pos2; j++) {
                child1[j] = g_Group[sel2][j];
                child2[j] = g_Group[sel1][j];
            }
            int k1 = pos2 + 1;
            int k2 = pos2 + 1;
            for (int j = 0; j < CITY_NUM; j++) {
                if (k1 == CITY_NUM) {
                    k1 = 0;
                }
                if (k2 == CITY_NUM) {
                    k2 = 0;
                }
                if (child1[k1] == -1) {
                    int city = g_Group[sel1][j];
                    int flag = 0;
                    for (int k = pos1; k <= pos2; k++) {
                        if (city == child1[k]) {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) {
                        child1[k1] = city;
                        k1++;
                    }
                }
                if (child2[k2] == -1) {
                    int city = g_Group[sel2][j];
                    int flag = 0;
                    for (int k = pos1; k <= pos2; k++) {
                        if (city == child2[k]) {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) {
                        child2[k2] = city;
                        k2++;
                    }
                }
            }
            for (int j = 0; j < CITY_NUM; j++) {
                g_Group[i][j] = child1[j];
                g_Group[i+1][j] = child2[j];
            }
            g_Fitness[i] = PathDistance(child1);
            g_Fitness[i+1] = PathDistance(child2);
        }
    }
}

// 变异操作
void Mutate() {
    for (int i = 0; i < POP_SIZE; i++) {
        if ((double)rand() / RAND_MAX < MUTATE_RATE) {
            int pos1 = rand() % CITY_NUM;
            int pos2 = rand() % CITY_NUM;
            int temp = g_Group[i][pos1];
            g_Group[i][pos1] = g_Group[i][pos2];
            g_Group[i][pos2] = temp;
            g_Fitness[i] = PathDistance(g_Group[i]);
        }
    }
}

// 打印最优解
void PrintBest() {
    int bestIndex = 0;
    for (int i = 1; i < POP_SIZE; i++) {
        if (g_Fitness[i] < g_Fitness[bestIndex]) {
            bestIndex = i;
        }
    }
    printf("Best path: ");
    for (int i = 0; i < CITY_NUM; i++) {
        printf("%d ", g_Group[bestIndex][i]);
    }
    printf("\nBest distance: %d\n", g_Fitness[bestIndex]);
}

int main() {
    srand((unsigned)time(NULL));
    // 初始化距离矩阵
    for (int i = 0; i < CITY_NUM; i++) {
        for (int j = 0; j < CITY_NUM; j++) {
            if (i == j) {
                g_Distance[i][j] = 0;
            } else {
                g_Distance[i][j] = rand() % 100 + 1;
            }
        }
    }
    // 初始化种群
    InitGroup();
    // 迭代
    for (int i = 0; i < ITER_NUM; i++) {
        Select();
        Cross();
        Mutate();
    }
    // 输出结果
    PrintBest();
    return 0;
}