c语言遗传算法商旅问题

遗传算法是一种基于自然选择和遗传学原理的优化算法，可以用于解决许多实际问题，其中商旅问题是其中一个经典的问题。商旅问题是指在给定的一组城市和每对城市之间的距离的情况下，找到一条经过每个城市一次且总距离最短的路径。以下是使用遗传算法解决商旅问题的C语言代码：

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

#define CITY_NUM 10 // 城市数量
#define POP_SIZE 100 // 种群数量
#define GENERATION_NUM 500 // 迭代次数
#define CROSSOVER_RATE 0.8 // 交叉概率
#define MUTATION_RATE 0.1 // 变异概率

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

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

// 初始化城市坐标
void init_cities(City cities[]) {
    srand((unsigned)time(NULL));
    for (int i = 0; i < CITY_NUM; i++) {
        cities[i].x = rand() % 100;
        cities[i].y = rand() % 100;
    }
}

// 计算两个城市之间的距离
double distance(City city1, City city2) {
    return sqrt(pow(city1.x - city2.x, 2) + pow(city1.y - city2.y, 2));
}

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

// 初始化种群
void init_population(Individual population[]) {
    srand((unsigned)time(NULL));
    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 / path_length(population[i].path);
    }
}

// 选择操作
void selection(Individual population[], Individual parents[]) {
    double fitness_sum = 0;
    for (int i = 0; i < POP_SIZE; i++) {
        fitness_sum += population[i].fitness;
    }
    for (int i = 0; i < POP_SIZE; i++) {
        double p = (double)rand() / RAND_MAX * fitness_sum;
        double sum = 0;
        for (int j = 0; j < POP_SIZE; j++) {
            sum += population[j].fitness;
            if (sum >= p) {
                parents[i] = population[j];
                break;
            }
        }
    }
}

// 交叉操作
void crossover(Individual parents[], Individual offspring[]) {
    for (int i = 0; i < POP_SIZE; i += 2) {
        if ((double)rand() / RAND_MAX < CROSSOVER_RATE) {
            int point1 = rand() % CITY_NUM;
            int point2 = rand() % CITY_NUM;
            if (point1 > point2) {
                int temp = point1;
                point1 = point2;
                point2 = temp;
            }
            int k = 0;
            int temp[CITY_NUM];
            for (int j = point1; j <= point2; j++) {
                temp[k++] = parents[i].path[j];
            }
            for (int j = 0; j < CITY_NUM; j++) {
                if (j < point1 || j > point2) {
                    for (int l = 0; l < k; l++) {
                        if (parents[i+1].path[j] == temp[l]) {
                            goto end;
                        }
                    }
                    offspring[i].path[j] = parents[i+1].path[j];
                } else {
                    offspring[i].path[j] = temp[j-point1];
                }
                end:;
            }
            k = 0;
            for (int j = point1; j <= point2; j++) {
                temp[k++] = parents[i+1].path[j];
            }
            for (int j = 0; j < CITY_NUM; j++) {
                if (j < point1 || j > point2) {
                    for (int l = 0; l < k; l++) {
                        if (parents[i].path[j] == temp[l]) {
                            goto end2;
                        }
                    }
                    offspring[i+1].path[j] = parents[i].path[j];
                } else {
                    offspring[i+1].path[j] = temp[j-point1];
                }
                end2:;
            }
        } else {
            offspring[i] = parents[i];
            offspring[i+1] = parents[i+1];
        }
        offspring[i].fitness = 1 / path_length(offspring[i].path);
        offspring[i+1].fitness = 1 / path_length(offspring[i+1].path);
    }
}

// 变异操作
void mutation(Individual offspring[]) {
    for (int i = 0; i < POP_SIZE; i++) {
        if ((double)rand() / RAND_MAX < MUTATION_RATE) {
            int point1 = rand() % CITY_NUM;
            int point2 = rand() % CITY_NUM;            int temp = offspring[i].path[point1];
            offspring[i].path[point1] = offspring[i].path[point2];
            offspring[i].path[point2] = temp;
            offspring[i].fitness = 1 / path_length(offspring[i].path);
        }
    }
}

// 寻找最优解
void find_best_solution(Individual population[], Individual *best_solution) {
    *best_solution = population[0];
    for (int i = 1; i < POP_SIZE; i++) {
        if (population[i].fitness > best_solution->fitness) {
            *best_solution = population[i];
        }
    }
}

int main() {
    City cities[CITY_NUM];
    init_cities(cities);
    Individual population[POP_SIZE];
    init_population(population);
    Individual parents[POP_SIZE];
    Individual offspring[POP_SIZE];
    Individual best_solution;
    for (int i = 0; i < GENERATION_NUM; i++) {
        selection(population, parents);
        crossover(parents, offspring);
        mutation(offspring);
        find_best_solution(offspring, &best_solution);
        printf("Generation %d: %lf\n", i+1, best_solution.fitness);
        for (int j = 0; j < POP_SIZE; j++) {
            population[j] = offspring[j];
        }
    }
    printf("Best solution: ");
    for (int i = 0; i < CITY_NUM; i++) {
        printf("%d ", best_solution.path[i]);
    }
    printf("\n");
    return 0;
}