遗传算法（C语言实现）

#include "my_ga.h" #include <stdio.h> #include <stdlib.h> #include <time.h> static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code); static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2); static void gene_generator(double *gene1, double *gene2); static void init(GA *ga); static unsigned int select(GA *ga); static void fit(GA *ga); static void create_roulette(GA *ga); static unsigned int select(GA *ga); static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother); static void cross(GA *ga, unsigned int *one, unsigned int *another); static void mutate(unsigned int *gene_code); static void evolve(GA *ga); /* 创建遗传算法器 */ GA *create_ga(double (*get_fitness)(double, double), unsigned int population_num) { GA *ga = (GA *)calloc(1, sizeof(GA)); ga->population_num = population_num; ga->gene = (Gene *)calloc(population_num, sizeof(Gene)); ga->gene_code = (unsigned int *)calloc(population_num, sizeof(unsigned int)); ga->fitness = (double *)calloc(population_num, sizeof(double)); ga->roulette = (double *)calloc(population_num, sizeof(double)); ga->get_fitness = get_fitness; ga->init = init; ga->evolve = evolve; return ga; } /* 销毁遗传算法器 */ void delete_ga(GA *ga) { free(ga->gene); free(ga->gene_code); free(ga->fitness); free(ga->roulette); free(ga); } /* 初始化遗传算法器 ga 遗传算法器指针 */ static void init(GA *ga) { /* 1.初始化随机数发生器(以时间作为种子) */ srand((unsigned int)time(NULL)); /* 2.根据种群个数产生初始种群的基因并编码 */ for (int num = 0; num < ga->population_num; num++) { gene_generator(&ga->gene[num].gene1, &ga->gene[num].gene2); if (!gene_encode(ga->gene[num].gene1, ga->gene[num].gene2, &ga->gene_code[num])) { printf("gene_encode error!\n"); return; } } /* 3.首次计算适应度 */ fit(ga); /* 4.首次创建赌盘 */ create_roulette(ga); // 打印生成的初始种群 //printf("初始种群:\n"); //for (int num = 0; num < ga->population_num; num++) // printf("%3d : gene1 = %f gene2 = %f\n", num, ga->gene[num].gene1, ga->gene[num].gene2); // 打印编码后的初始种群 //printf("编码后的初始种群:\n"); //for (int num = 0; num < ga->population_num; num++) // printf("%3d : gene_code = %u\n", num, ga->gene_code[num]); // 测试解码 //printf("解码误差:\n"); //for (int num = 0; num < ga->population_num; num++) //{ // double tmp1, tmp2; // // gene_decode(ga->gene_code[num], &tmp1, &tmp2); // printf("%3d : delta gene1 = %f delta gene2 = %f\n", num, tmp1 - ga->gene[num].gene1, tmp2 - ga->gene[num].gene2); // } // 打印适应度 // printf("适应度:\n"); // for (int num = 0; num < ga->population_num; num++) // printf("%3d : fitness = %f\n", num, ga->fitness[num]); // printf("best fitness = %f\n", ga->fitness[ga->best_individual]); // printf("sum fitness = %f\n", ga->sum_fitness); // 打印赌盘 // printf("赌盘:\n"); // for (int num = 0; num < ga->population_num; num++) // printf("%3d : roulette = %f\n", num, ga->roulette[num]); } /* 计算种群中各个个体的适应度函数 ga 遗传算法器指针 说明：在计算适应度的同时会寻找适应度最大的个体并计算总和适应度 */ static void fit(GA *ga) { unsigned int index = 0; double sum_fitness = 0; for (int num = 0; num < ga->population_num; num++) { ga->fitness[num] = ga->get_fitness(ga->gene[num].gene1, ga->gene[num].gene2); index = (ga->fitness[num] > ga->fitness[index]) ? num : index; sum_fitness += ga->fitness[num]; } ga->best_individual = index; ga->sum_fitness = sum_fitness; } /* 创建赌盘 ga 遗传算法器指针 */ static void create_roulette(GA *ga) { /* 计算赌盘中的概率 */ ga->roulette[0] = ga->fitness[0] / ga->sum_fitness; for (int num = 1; num < ga->population_num - 1; num++) { ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness; } ga->roulette[ga->population_num - 1] = 1.0; } /* 基因选择函数 ga 遗传算法器指针 返回值：返回使用轮盘赌的方式选出的个体(编号) 说明：选择策略为轮盘赌+随机竞争 */ static unsigned int select(GA *ga) { unsigned int index1 = 0, index2 = 0; /* 产生一个[0.0, 1.0]之间的浮点数 */ double selector1 = rand() * 1.0 / RAND_MAX; double selector2 = rand() * 1.0 / RAND_MAX; /* 找出被选中的个体的索引 */ for (; selector1 > ga->roulette[index1]; index1++); for (; selector2 > ga->roulette[index2]; index2++); return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2); } /* 繁殖函数 ga 遗传算法器指针 father 从种群中选出的父体 mother 从种群中选出的母体 返回值：适应度最高的子代的基因编码 说明： 1.一对父体与母体将繁殖出一对子代 2.选择出适应性更好的子代返回 */ static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother) { unsigned int son1 = ga->gene_code[father]; unsigned int son2 = ga->gene_code[mother]; /* 1.交叉 */ //unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1; //unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1; //unsigned char min_pos = min(pos1, pos2); //unsigned char max_pos = max(pos1, pos2); //unsigned int father_gene_seg = get_bits(ga->gene_code[father], min_pos, max_pos) << (min_pos - 1); //unsigned int mother_gene_seg = get_bits(ga->gene_code[mother], min_pos, max_pos) << (min_pos - 1); //unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1)); //son1 = (ga->gene_code[father] & mask) | mother_gene_seg; //son2 = (ga->gene_code[mother] & mask) | father_gene_seg; cross(ga, &son1, &son2); /* 2.变异 */ mutate(&son1); mutate(&son2); /* 3.子代竞争 */ double son1_gene1, son1_gene2, son2_gene1, son2_gene2; gene_decode(son1, &son1_gene1, &son1_gene2); gene_decode(son2, &son2_gene1, &son2_gene2); return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2; } /* 交叉函数 ga 遗传算法器指针 one 输出型参数，待交叉基因 another 输出型参数，待交叉基因 说明： 1.对传入的基因编码执行两点交叉操作 */ static void cross(GA *ga, unsigned int *one, unsigned int *another) { /* 1.随机产生两个交叉点的位置 */ unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1; unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1; unsigned char min_pos = min(pos1, pos2); unsigned char max_pos = max(pos1, pos2); /* 2.截出需要交换的基因段 */ unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1); unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1); unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1)); /* 3.执行交叉操作 */ *one = (*one & mask) | another_gene_seg; *another = (*another & mask) | one_gene_seg; } /* 变异函数 gene_code 输入型参数 说明： 1.对传入的基因编码执行变异操作 2.随机选择基因编码中的一位做反转操作 */ static void mutate(unsigned int *gene_code) { unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH); *gene_code ^= mutate_bit; } /* 进化函数 ga 遗传算法器指针 */ static void evolve(GA *ga) { /* 申请暂存子代基因编码的内存 */ unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int)); /* 精英保留(将上一代中适应度最高的个体的基因编码保留) */ descendants[0] = ga->gene_code[ga->best_individual]; /* 1.�