Switch

Welcome to My Blog

人工智能导论(1)——c语言实现进化算法

发表于 分类于 阅读次数： Valine：
本文字数： 8.9k 阅读时长 ≈ 8 分钟

一.问题描述

求该函数的最优解：

解题思路：

变量编码->生成种群->交叉->变异->选择->迭代

    对x1和x2在变量范围内的值按照给定精度计算编码成二进制码的位数；随机生成一定规模的种群，其二进制编码随机； 随机对种群内个体的编码进行交叉；随机对种群内个体的编码进行按位变异；对二进制码进行解码、求解适应度函数值、保留一定数量的精英、采用轮盘赌随机选取其余个体最终组成新的种群；迭代，重复 交叉->变异->选择 至最优适应度基本不变或迭代一定次数。

二.代码解析

1.源码

​
​ #include<stdio.h>
​ #include<stdlib.h>
​ #include<string.h>
​ #include<stdbool.h>
​ #include<math.h>
​ #include<time.h>
​
#define POPULATION_SIZE 100 //种群规模
#define RESERVE_NUM 3 //每代精英保留数
#define VARI_NUM 2 //变量个数
#define ITERATION 1000 //迭代次数
#define END_TIMES 100 //稳定终止次数
#define PC 0.6 //交叉概率
#define CROSS_LEN 8 //交叉长度
#define PM 0.1 //变异概率 

//种群结构体 
typedef struct v{
	bool encode[50];		//二进制编码 
	double value[VARI_NUM];	//解码数值 
	bool change;			//标记是否发生交叉或变异  
	double fitness;			//适应度
	double fit_rate;		//适应度占比 
}v;

double lower[VARI_NUM],upper[VARI_NUM],accur;	//x1,x2上下界和精度 
int encode_num,encode_number[VARI_NUM];			//二进制编码位数 
double real_accur[VARI_NUM];					//实际精度 
v optimization_popu;							//最优个体 

//函数声明 
v Get_Optimization(void);
void Init_Population(v* group);
void Cross(v* group);
void Mutation(v* group);
v* Select(v**group);
double Fitness(double x1,double x2); 
void Output_Result(v* optimization);
void Free_space(v** group);

//************************************************************************************************************
int main(){

	int i;
	v temp;
	
	//输入样例：-3.0 12.1 4.1 5.8 0.0001 
	printf("输入变量x1和x2的上下界和精度(x1_lower,x1_upper,x2_lower,x2_upper,accur):");
	scanf("%lf%lf%lf%lf%lf",&lower[0],&upper[0],&lower[1],&upper[1],&accur);
	
	//可以多次进行实验
	for(i=0;i<1;i++){
		temp=Get_Optimization();
		if(optimization_popu.fitness<temp.fitness)optimization_popu=temp;
	}
	Output_Result(&optimization_popu);
	
	return 0;	
}

//************************************************************************************************************
v Get_Optimization(void){
	
	srand((unsigned)time(NULL));
	int i,j;
	double temp;
	v** group=(v**)malloc(3*sizeof(v*));	//原始、交叉、变异种群
	for(i=0;i<3;i++)group[i]=(v*)malloc(sizeof(v)*POPULATION_SIZE);
	v* optimization=group[0],opt_tmep;				//最优种群 
	
	//初始化种群 
	Init_Population(group[0]);
	memcpy(group[1],group[0],sizeof(v)*POPULATION_SIZE); 
	memcpy(group[2],group[0],sizeof(v)*POPULATION_SIZE);
	
	//迭代 
	for(i=j=0;i<ITERATION;i++){
		
		//交叉
		Cross(group[1]); 
		//变异
		Mutation(group[2]);
		//选择 
		temp=optimization->fitness;
		optimization=Select(group); 
		if((optimization->fitness-temp)<accur){
			j++;
			if(j>=END_TIMES)break;		//结果保持稳定则退出 
		}
	 	
	}
	
	//输出结果
	Output_Result(optimization); 
	
	opt_tmep=*optimization;
	Free_space(group);
	return opt_tmep;
	
}

//计算变量二进制编码位数 
int Encode_Num(double lower,double upper,double accur){
	
	int num,i,j;
	num=(upper-lower)/accur+1;
	for(i=0,j=1;j<num;j*=2,i++);
	return i;
	
}

void Init_Population(v* group){
	
	int i,j;	
	
	for(i=encode_num=0;i<VARI_NUM;i++)encode_num+=(encode_number[i]=Encode_Num(lower[i],upper[i],accur));		//计算编码位数
	for(i=0;i<VARI_NUM;i++)real_accur[i]=(upper[i]-lower[i])/(pow(2,encode_number[i])-1);						//计算实际精度
	
	//初始化种群 
	for(i=0;i<POPULATION_SIZE;i++){
		//随机生成二进制编码 
		for(j=0;j<encode_num;j++){
			group[i].encode[j]=rand()%2;
//			printf("%d %d:%d\n",i,j,group[i].encode[j]);
		}
		group[i].change=true;
	}

}

//交叉lower和upper之间的编码 
void Cross(v* group){
	
	double p;
	int i,j,lower,upper;
	bool temp;
	
	//随机选取交叉片段
	lower=rand()%(encode_num-CROSS_LEN-1);
	upper=lower+CROSS_LEN; 

	for(i=0;i<POPULATION_SIZE/2-1;i++){
		p=1.0*rand()/RAND_MAX;	//***随机数*** 
		if(p<PC){ 
			//交叉 
			for(j=lower;j<upper;j++){
				temp=group[i].encode[j];
				group[i].encode[j]=group[POPULATION_SIZE-1-i].encode[j];
				group[POPULATION_SIZE-1-i].encode[j]=temp;
			}
		}
		//标记未交叉 
		else group[i].change=group[POPULATION_SIZE-1-i].change=false;
	}
	
} 

//按位变异  
void Mutation(v* group){

	double p;
	int i,j;
	for(i=0;i<POPULATION_SIZE/2;i++){
		for(j=0;j<encode_num;j++){
			p=1.0*rand()/RAND_MAX;	//***随机数*** 
			if(p<PM)group[i].encode[j]=!group[i].encode[j];
			else group[i].change=false;
		}
	}
	
}

//选择
v* Select(v**group){
	
	v* fitist[RESERVE_NUM],*group_temp=(v*)malloc(sizeof(v)*POPULATION_SIZE);
	int i,j,k,l,m,n;
	int vaild_num;	//有效个数 
	double fit_sum;	//适应度总大小
	for(i=0;i<RESERVE_NUM;i++)fitist[i]=&group[0][0]; 
		
	//解码并计算适应度函数 
	for(vaild_num=fit_sum=i=0;i<3;i++){
		for(j=0;j<POPULATION_SIZE;j++){
			if(!group[i][j].change)continue; 
			for(m=n=0;m<VARI_NUM;n+=encode_number[m],m++){
				for(k=l=0;k<encode_number[m];k++)l+=group[i][j].encode[k+n]*pow(2,k);
				//解码 
				group[i][j].value[m]=lower[m]+l*real_accur[m];
//				printf("%d %d--value[%d]:%lf\n",i,j,m,group[i][j].value[m]);
			}
			
			//计算适应度 
			group[i][j].fitness=Fitness(group[i][j].value[0],group[i][j].value[1]);
			//保存适应度大的个体
			for(k=0;k<RESERVE_NUM;k++){
				if(group[i][j].fitness>fitist[k]->fitness){
					for(l=k;l<RESERVE_NUM-1;l++)fitist[l+1]=fitist[l];
					fitist[k]=&group[i][j];
				}	
			}
			vaild_num++;fit_sum+=group[i][j].fitness;						//适应度总和计算 
//			printf("%d %d--fitness:%lf\n",i,j,group[i][j].fitness);			
		}
	} 
	
	//***保留优秀个体***
	for(i=0;i<RESERVE_NUM;i++)group_temp[i]=*fitist[i];
	
	//计算比率 
	for(i=0;i<3;i++){
		for(j=0;j<POPULATION_SIZE;j++){
			if(!group[i][j].change)continue;
			group[i][j].fit_rate=group[i][j].fitness/fit_sum;
//			printf("%d %d--fit_rate:%lf\n",i,j,group[i][j].fit_rate);	
		}
	}
	
	//轮盘赌选择
	for(i=RESERVE_NUM;i<POPULATION_SIZE;i++){
		double p=1.0*rand()/RAND_MAX;
		//寻找所处区间
		double temp;
		for(temp=0,j=0;j<3;j++){
			for(k=0;k<POPULATION_SIZE;k++){
				if(!group[j][k].change)continue;
				temp+=group[j][k].fit_rate;
				if(p<temp)break;
			}
			if(p<temp)break;
		}
		//复制 
		if(j!=3&&k!=POPULATION_SIZE)group_temp[i]=group[j][k];
		else group_temp[i]=group[j-1][k-1];
//		printf("select %3d from %3d %3d--fitness:%lf	--p:%lf\n",i,j,k,group_temp[i].fitness,p);
	} 
	 
	memcpy(group[0],group_temp,sizeof(v)*POPULATION_SIZE);
	free(group_temp);
	
	return fitist[0]; 
	
}

//适应度函数 
double Fitness(double x1,double x2){
	return 21.5+x1*sin(4*M_PI*x1)+x2*sin(20*M_PI*x2);
}

void Output_Result(v* optimization){
	int i;
	printf("最优解为:x1=%9lf x2=%9lf f(x1,x2)=%9lf 二进制编码为:",optimization->value[0],optimization->value[1],optimization->fitness); 
	for(i=0;i<encode_num;i++)printf("%d",optimization->encode[i]);
	printf("\n");
}

//释放空间 
void Free_space(v** group){
	int i;
	for(i=0;i<3;i++)free(group[i]);
	free(group);
}

2.算法关键参数

​
​ #define POPULATION_SIZE 100 //种群规模
​ #define RESERVE_NUM 3 //每代精英保留数
​ #define VARI_NUM 2 //变量个数
​ #define ITERATION 1000 //迭代次数
​ #define END_TIMES 100 //稳定终止次数
​ #define PC 0.6 //交叉概率
​ #define CROSS_LEN 8 //交叉长度
​ #define PM 0.1 //变异概率

3.定义种群结构体、相关变量及函数

​
​ //种群结构体
​ typedef struct v{
​ bool encode[50]; //二进制编码
​ double value[VARI_NUM]; //解码数值
​ bool change; //标记是否发生交叉或变异
​ double fitness; //适应度
​ double fit_rate; //适应度占比
​ }v;
​
double lower[VARI_NUM],upper[VARI_NUM],accur; //x1,x2上下界和精度
int encode_num,encode_number[VARI_NUM]; //二进制编码位数
double real_accur[VARI_NUM]; //实际精度
v optimization_popu; //最优个体 

//函数声明 
v Get_Optimization(void);
void Init_Population(v* group);
void Cross(v* group);
void Mutation(v* group);
v* Select(v**group);
double Fitness(double x1,double x2); 
void Output_Result(v* optimization);
void Free_space(v** group);

4.求解流程

​
​ v Get_Optimization(void){
​
srand((unsigned)time(NULL));
int i,j;
double temp;
v** group=(v**)malloc(3sizeof(v)); //原始、交叉、变异种群
for(i=0;i<3;i++)group[i]=(v*)malloc(sizeof(v)POPULATION_SIZE);
v optimization=group[0],opt_tmep; //最优种群

//初始化种群
Init_Population(group[0]);
memcpy(group[1],group[0],sizeof(v)*POPULATION_SIZE);
memcpy(group[2],group[0],sizeof(v)*POPULATION_SIZE);

//迭代
for(i=j=0;i<ITERATION;i++){

//交叉
Cross(group[1]);
//变异
Mutation(group[2]);
//选择
temp=optimization->fitness;
optimization=Select(group);
if((optimization->fitness-temp)<accur){
j++;
if(j>=END_TIMES)break; //结果保持稳定则退出
}

}

//输出结果
Output_Result(optimization);

opt_tmep=*optimization;
Free_space(group);
return opt_tmep;

}

三.求解结果

    改变算法关键参数会导致求解结果不同，不同的时间下的结果也不同。可以改变主函数中for循环的结束条件多次进行实验：

​
​ //可以多次进行实验
​ for(i=0;i<1;i++){
​ temp=Get_Optimization();
​ if(optimization_popu.fitness<temp.fitness)optimization_popu=temp;
​ }
​
笔者在一定的参数下得到了最优解：

​
​ 最优解为:
​ x1=11.625358
​ x2=5.725031
​ f(x1,x2)=38.850261
​ 二进制编码为:
​ 111100111111101111010110100101111
​
对于问题二，修改适应度函数：

​
​ //适应度函数
​ double Fitness(double x1,double x2){
​ // return 21.5+x1sin(4M_PIx1)+x2sin(20M_PIx2);
​ return 100pow((x2-x1x1),2)+pow((1-x1),2);
​ }
​
再输入变量范围及精度 ：

​
​ 输入样例2：-2.048 2.048 -2.048 2.048 0.0001

​
​ 最优解为:x1=-2.047875 x2=-2.037187 f(x1,x2)=3891.799899
​ 二进制编码为:01000000000000001011010100000000

四.相关思考

1.增加精度可以增加编码长度，减少交叉变异的影响，增加搜索精度，结果可能更加靠近最优解

2.增加变异概率以产生更多新的性状（变异的概率可采用自适应概率，如果最优种个体适应度值长时间未变化，可增加变异概率
），以及采用更复杂的交叉、变异算法

3.交叉、变异过于随机会使求解趋于“遍历”，并且算法的“朝最优解的驱动力”不足

本文转自 https://blog.csdn.net/qq_32971095/article/details/136715239，如有侵权，请联系删除。

> --------------- THE END -------------- <