[C++知识库]遗传算法C语言实现以及思路详解简单易懂

前言

前几天刚用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语言遗传算法的实现，我感觉能够比较好的理解遗传算法的思路了，如果认真看完我这两篇博客，一个也能够比较好的理解遗传算法了吧，但是主要还是需要自己敲敲代码，懂得会比较快。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖