遗传算法C语言实现以及思路详解简单易懂
目录前言实例代码解释1.初始化参数以及变量设置2.定义环境（定义目标函数）3.DNA解码（计算x，y）4.初始化种群（初始化解，考虑定义域）5.计算适应度（计算误差，考虑定义域）6.适者生存（挑选误差较小的答案）7.生殖、变异（更改部分二进制位，取反部分二进制位，可能生成误差更小的答案）8.copy函数（将选择的selected_animal赋值回animal以便迭代遗传进化）9.遗传进化以及结果
·
目录
前言
前几天刚用python实现了遗传算法用于求解函数最值，详见遗传算法详解python代码实现以及实例分析然后我又用c语言写了一遍，因为当时老师说只能用c语言，但是他发的实验报告里又说能用python、matlab了，挺奇怪的，没事，写都写完了，分享一下吧。
首先讲一下用c语言和python写这题的一些区别，由于c语言相对于python来说比较底层，所以涉及到的复杂的操作会比较少，但是由于c比python快不止一倍两倍，基本就不用咋考虑性能了，怎么好理解我就怎么写了。
python用一个numpy矩阵就可以表示一个种群了，c语言我是用一个animal结构体数组来表示种群；
python在进行优胜劣汰的时候，是根据适应度转换为对应被抽取的概率然后用numpy.random.choice根据概率进行对应抽取形成新的种群，而c语言里我是通过计算出适应度概率之后计算ceil(适应度概率 * 种群数量)，然后以此作为此animal被留下的数量。
主要是一些细节的不同，整体思路是完全一致的。
实例代码解释
1.初始化参数以及变量设置
#include<bits/stdc++.h>
using namespace std;
# define Int_bit 3 // 整数占的bit位
# define DNA_bit 16 // 一个DNA的二进制位数,(第一维表示符号位)
# define DNA_num 2 // DNA的个数
# define animal_num 200 // 开始种群的数量
# define cross_rate 0.8 // 生殖交叉概率
# define variation_rate 0.005 // 变异的概率
# define generator_n 100 // 种群演变的次数
int limit_area[2] = {0, 10}; // 值域
struct animals{//存储x, y两个二进制表示
int DNA[DNA_bit * DNA_num];
}animal[animal_num], selected_animal[animal_num];
struct DNA_results{//二进制转化为十进制的结果存储
double translated_result[DNA_num];
}DNA_result[animal_num];
struct fitnesses{//每个animal的适应度计算
double p;
int id;
}fitness[animal_num];
参数设置和python那篇是一样的。
2.定义环境（定义目标函数）
double f(double x, double y){
return (6.452 * (x+0.125*y) * pow(cos(x)-cos(2*y), 2)) / (pow(0.8+pow(x-4.2, 2) + 2*pow(y-7, 2), 0.5))+ 3.226*y;
}
3.DNA解码（计算x，y）
void DNA2to10(int n){//将二进制解码为十进制
for(int i=0; i<DNA_num; i++){
double sum = 0;
int base = i * DNA_bit;
double sign = animal[n].DNA[base];
double flag;
if(sign == 0)flag = -1;
else flag = 1;
for(int j=base+1; j<=base+Int_bit; j++){
if(animal[n].DNA[j] == 1)sum += pow(2, Int_bit+base-j);
}
for(int j=base+Int_bit+1; j<DNA_bit+base; j++){
if(animal[n].DNA[j] == 1)sum += pow(2, Int_bit+base-j);
}
DNA_result[n].translated_result[i] = sum * flag;
}
}
4.初始化种群（初始化解，考虑定义域）
srand((unsigned)time(NULL));//时间随机
for(int i=0; i<animal_num; i++){//初始化种群
for(int j=0; j<DNA_bit * DNA_num; j++){
animal[i].DNA[j] = rand()%2;
}
}
for(int i=0; i<animal_num; i++){//如果有不符合定义域的就再生成一遍
for(int j=0; j<DNA_bit * DNA_num; j++){
animal[i].DNA[j] = rand()%2;
}
if(flag_limit_area(limit_area, i) != 1)i-=1;
}
5.计算适应度（计算误差，考虑定义域）
//适应度排序的方法（带着id然后按适应度排序
int cmp(fitnesses f1, fitnesses f2){
return f1.p < f2.p;
}
void get_fitness(){//计算每个animal的适应度
double fitness_score[animal_num];
double fit_flag[animal_num];
for(int i=0; i<animal_num; i++){
DNA2to10(i);
fitness_score[i] = f(DNA_result[i].translated_result[0], DNA_result[i].translated_result[1]);
fit_flag[i] = flag_limit_area(limit_area, i);
}
double minn=8888888;
for(int i=0; i<animal_num; i++)minn = min(minn, fitness_score[i]);
for(int i=0; i<animal_num; i++){
fitness_score[i] = fitness_score[i] - minn + 1e-5;
}
double sum = 0;
for(int i=0; i<animal_num; i++){
fitness_score[i] = fitness_score[i] * fit_flag[i];
sum += fitness_score[i];
};
for(int i=0; i<animal_num; i++){
fitness[i].p = fitness_score[i] / sum;
fitness[i].id = i;
}
}
6.适者生存（挑选误差较小的答案）
void select(){//根据适应度选择animal
int n = 0;
for(int i=animal_num; i>=0; i--){
int num = ceil(fitness[i].p * animal_num);
for(int j=0; j<num; j++){
for(int k=0; k<DNA_bit * DNA_num; k++){
selected_animal[n].DNA[k] = animal[fitness[i].id].DNA[k];
}
n++;
if(n == animal_num)break;
}
if(n == animal_num)break;
}
}
7.生殖、变异（更改部分二进制位，取反部分二进制位，可能生成误差更小的答案）
void crossover_and_variation(){//生殖交叉、变异
for(int k=0; k<animal_num; k++){
int father[DNA_bit * DNA_num];
int mother[DNA_bit * DNA_num];
int child[DNA_bit * DNA_num];
int father_id = rand() % 200;
int mother_id = rand() % 200;
for(int i=0; i<DNA_bit * DNA_num; i++){
father[i] = animal[father_id].DNA[i];
mother[i] = animal[mother_id].DNA[i];
}
if((rand()%100)/100.0 < cross_rate){
int cross_pos = rand() % (DNA_bit * DNA_num);
for(int i=0; i<cross_pos; i++)child[i] = father[i];
for(int i=cross_pos; i<DNA_bit * DNA_num; i++)child[i] = mother[i];
}
if((rand()%100)/100.0 < variation_rate){
int variation_pos = rand() % (DNA_bit * DNA_num);
child[variation_pos] = 1 - child[variation_pos];
}
for(int j=0; j<DNA_bit * DNA_num; j++){
selected_animal[k].DNA[j] = child[j];
}
}
}
8.copy函数（将选择的selected_animal赋值回animal以便迭代遗传进化）
void copy(){//将新的结果copy回animal以便进行下一轮迭代
for(int i=0; i<animal_num; i++){
for(int j=0; j<DNA_bit * DNA_num; j++){
animal[i].DNA[j] = selected_animal[i].DNA[j];
}
}
}
9.遗传进化以及结果选择
for(int i=0; i<generator_n; i++){//遗传进化
get_fitness();//适应度计算
sort(fitness, fitness+animal_num, cmp);//排序，方便挑选
select();//挑选种群
copy();//将挑选好的复制回原来的种群
crossover_and_variation();//交配、变异
copy();//将生成的子种群复制回原来的种群
}
//得出最终的最优结果
get_fitness();
sort(fitness, fitness+animal_num, cmp);
int id = fitness[animal_num-1].id;
double x = DNA_result[id].translated_result[0];
double y = DNA_result[id].translated_result[1];
cout<<"最优结果："<<endl;
cout<<"x: "<<x<<" "<<"y: "<<y<<endl;
cout<<f(x, y);
10.完整代码
#include<bits/stdc++.h>
using namespace std;
# define Int_bit 3 // 整数占的bit位
# define DNA_bit 16 // 一个DNA的二进制位数,(第一维表示符号位)
# define DNA_num 2 // DNA的个数
# define animal_num 200 // 开始种群的数量
# define cross_rate 0.8 // 生殖交叉概率
# define variation_rate 0.005 // 变异的概率
# define generator_n 100 // 种群演变的次数
int limit_area[2] = {0, 10}; // 值域
struct animals{//存储x, y两个二进制表示
int DNA[DNA_bit * DNA_num];
}animal[animal_num], selected_animal[animal_num];
struct DNA_results{//二进制转化为十进制的结果存储
double translated_result[DNA_num];
}DNA_result[animal_num];
struct fitnesses{//每个animal的适应度计算
double p;
int id;
}fitness[animal_num];
int cmp(fitnesses f1, fitnesses f2){
return f1.p < f2.p;
}
double f(double x, double y){
return (6.452 * (x+0.125*y) * pow(cos(x)-cos(2*y), 2)) / (pow(0.8+pow(x-4.2, 2) + 2*pow(y-7, 2), 0.5))+ 3.226*y;
}
void DNA2to10(int n){//将二进制解码为十进制
for(int i=0; i<DNA_num; i++){
double sum = 0;
int base = i * DNA_bit;
double sign = animal[n].DNA[base];
double flag;
if(sign == 0)flag = -1;
else flag = 1;
for(int j=base+1; j<=base+Int_bit; j++){
if(animal[n].DNA[j] == 1)sum += pow(2, Int_bit+base-j);
}
for(int j=base+Int_bit+1; j<DNA_bit+base; j++){
if(animal[n].DNA[j] == 1)sum += pow(2, Int_bit+base-j);
}
DNA_result[n].translated_result[i] = sum * flag;
}
}
int flag_limit_area(int limit_area[], int i){//检测是否超过定义域
DNA2to10(i);
if(DNA_result[i].translated_result[0] >= limit_area[0]
&& DNA_result[i].translated_result[0] <= limit_area[1]
&& DNA_result[i].translated_result[1] >= limit_area[0]
&& DNA_result[i].translated_result[1] <= limit_area[1])
return 1;
else return 0;
}
void get_fitness(){//计算每个animal的适应度
double fitness_score[animal_num];
double fit_flag[animal_num];
for(int i=0; i<animal_num; i++){
DNA2to10(i);
fitness_score[i] = f(DNA_result[i].translated_result[0], DNA_result[i].translated_result[1]);
fit_flag[i] = flag_limit_area(limit_area, i);
}
double minn=8888888;
for(int i=0; i<animal_num; i++)minn = min(minn, fitness_score[i]);
for(int i=0; i<animal_num; i++){
fitness_score[i] = fitness_score[i] - minn + 1e-5;
}
double sum = 0;
for(int i=0; i<animal_num; i++){
fitness_score[i] = fitness_score[i] * fit_flag[i];
sum += fitness_score[i];
};
for(int i=0; i<animal_num; i++){
fitness[i].p = fitness_score[i] / sum;
fitness[i].id = i;
}
}
void select(){//根据适应度选择animal
int n = 0;
for(int i=animal_num; i>=0; i--){
int num = ceil(fitness[i].p * animal_num);
for(int j=0; j<num; j++){
for(int k=0; k<DNA_bit * DNA_num; k++){
selected_animal[n].DNA[k] = animal[fitness[i].id].DNA[k];
}
n++;
if(n == animal_num)break;
}
if(n == animal_num)break;
}
}
void crossover_and_variation(){//生殖交叉、变异
for(int k=0; k<animal_num; k++){
int father[DNA_bit * DNA_num];
int mother[DNA_bit * DNA_num];
int child[DNA_bit * DNA_num];
int father_id = rand() % 200;
int mother_id = rand() % 200;
for(int i=0; i<DNA_bit * DNA_num; i++){
father[i] = animal[father_id].DNA[i];
mother[i] = animal[mother_id].DNA[i];
}
if((rand()%100)/100.0 < cross_rate){
int cross_pos = rand() % (DNA_bit * DNA_num);
for(int i=0; i<cross_pos; i++)child[i] = father[i];
for(int i=cross_pos; i<DNA_bit * DNA_num; i++)child[i] = mother[i];
}
if((rand()%100)/100.0 < variation_rate){
int variation_pos = rand() % (DNA_bit * DNA_num);
child[variation_pos] = 1 - child[variation_pos];
}
for(int j=0; j<DNA_bit * DNA_num; j++){
selected_animal[k].DNA[j] = child[j];
}
}
}
void copy(){//将新的结果copy回animal以便进行下一轮迭代
for(int i=0; i<animal_num; i++){
for(int j=0; j<DNA_bit * DNA_num; j++){
animal[i].DNA[j] = selected_animal[i].DNA[j];
}
}
}
int main(){
srand((unsigned)time(NULL));//时间随机
for(int i=0; i<animal_num; i++){//初始化种群
for(int j=0; j<DNA_bit * DNA_num; j++){
animal[i].DNA[j] = rand()%2;
}
}
for(int i=0; i<animal_num; i++){//如果有不符合定义域的就再生成一遍
for(int j=0; j<DNA_bit * DNA_num; j++){
animal[i].DNA[j] = rand()%2;
}
if(flag_limit_area(limit_area, i) != 1)i-=1;
}
for(int i=0; i<generator_n; i++){//遗传进化
get_fitness();//适应度计算
sort(fitness, fitness+animal_num, cmp);//排序，方便挑选
select();//挑选种群
copy();//将挑选好的复制回原来的种群
crossover_and_variation();//交配、变异
copy();//将生成的子种群复制回原来的种群
}
//得出最终的最优结果
get_fitness();
sort(fitness, fitness+animal_num, cmp);
int id = fitness[animal_num-1].id;
double x = DNA_result[id].translated_result[0];
double y = DNA_result[id].translated_result[1];
cout<<"最优结果："<<endl;
cout<<"x: "<<x<<" "<<"y: "<<y<<endl;
cout<<f(x, y);
return 0;
}
运行结果：
看得出和python运行出的结果是差不多的。
总结
通过先前python语言的遗传算法实现以及现在c语言遗传算法的实现，我感觉能够比较好的理解遗传算法的思路了，如果认真看完我这两篇博客，一个也能够比较好的理解遗传算法了吧，但是主要还是需要自己敲敲代码，懂得会比较快。
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
16
0- 0
已为社区贡献11条内容
所有评论(0)