当前位置:首页 > AI > 西电人工智能大作业(遗传算法求函数最大值)

西电人工智能大作业(遗传算法求函数最大值)

一叶知秋2024-05-11 17:55:25AI7

西电人工智能大作业(遗传算法求函数最大值)

一、问题描述

在这里插入图片描述

二、算法分析

step1:确定种群规模N,交叉概率pc,变异概率pm。随机生成N个个体作为初始种群P。
step2:计算种群P中每个个体的适应度值。
step3:
1)从P中依据轮盘赌选择出N/2对父代;
2)对选择的N/2对父代,依概率pc进行交叉,生成的子代个体记为 P_s;
3)对集合O1中的个体依概率pm进行变异,生成的子代个体记为P_m;
4))从P、P_s、P_m中依据l轮盘赌选出N个个体组成下一代种群P。
step4:更新最大值,重复step2。

三、具体实现

1.种群编码实现

求maxf(x),其中x的取值范围是[a,b],精度要求不小于10^(-k),那么二进制位数m应该满足pow(2,m-1) - 1 < (b - a) < pow(2,m)
因此根据以上公式可以求出x1和x2的编码长度为len1 = 18,len2 = 15,总编码长度为len = 33。

#define x1min -3.0
#define x1max 12.1
#define x2min 4.1
#define x2max 5.8
#define len1 18
#define len2 15
#define len 33
typedef struct //个体结构体
{
	char code[len+1];
	double x1;
	double x2;
	double fitness;
	double fit_p;
	double fit_p_c;
}Individual;
//种群初始化
void InitPopu(Individual *P,int N)
{	
	int i,k,n;
	for(i = 0;i < N;i ++)
	{
		for(k = 0;k < len;k ++)
		{
			n = rand()%100;
			if(n<50)
				P[i].code[k] = '0';
			else
				P[i].code[k] = '1';
		}
		P[i].code[len] = '\0';
	}
}

2.种群解码实现

容易想到解码的方法可以采用比值的映射。
在这里插入图片描述

即:
(x - 0)/ (pow(2,m)-1-0) = (y - a) / (b - a)
所以y = a + (b - a) * x / (pow(2,m) - 1)
注意这里需要将二进制字符串转为十进制整型。
代码实现如下:

long long int binaryToDecimal(char *binaryString) 
{
    int i;
	long long int decimal = 0;
    int length = strlen(binaryString);
    for (i = 0; i < length; i++) 
        if (binaryString[i] == '1') 
            decimal += 1 << (length - i - 1);
    return decimal;
}
void decode(Individual *P,int N)
{
	int i,j;
	char code1[len1+1];
	char code2[len2+1];
	for(i = 0;i < N;i ++)
	{
		for(j = 0;j < len1;j ++)
			code1[j] = P[i].code[j];
		code1[len1] = '\0';
		for(j = 0;j < len2;j ++)
			code2[j] = P[i].code[j+len1];
		code2[len2] = '\0';
		long long int code1num = pow(2,len1);
		long long int code2num = pow(2,len2);
		long long int num1 = binaryToDecimal(code1);
		long long int num2 = binaryToDecimal(code2);
		P[i].x1 = x1min + (x1max - x1min) * num1 / (code1num - 1);
		P[i].x2 = x2min + (x2max - x2min) * num2 / (code2num - 1);
	}	
}

3.适应度计算实现

非常简单,直接上代码:

void CulFitness(Individual *P,int N)
{
	int i;
	for(i = 0;i < N;i ++)
		P[i].fitness = 21.5 + P[i].x1 * sin(4 * pi * P[i].x1) + P[i].x2 * sin(20 * pi * P[i].x2);
}

4.轮盘赌实现

思路:
为群体中每个个体指定饼图中一个小块。块的大小与个体的适应度成比例,适应度愈高,它在饼图中对应的小块所占面积也愈大。为了选取一个个体,要做的就是旋转这个轮子,直到轮盘停止时,看指针停止在
哪一块上,就选中与它对应的那个个体。
具体方案如图所示:
在这里插入图片描述
代码实现如下:

void Roulette(Individual *P,Individual *P_t,int N,int M)
{
	//计算P_t中N个个体适应度比值以及适应度比值前缀和
	int i,j;
	double sum = 0;
	for(i = 0;i < N;i ++)
	{
		sum += P_t[i].fitness;
		P_t[i].fit_p_c = sum;
	}	
	for(i = 0;i < N;i ++)
	{
		P_t[i].fit_p = P_t[i].fitness / sum;
		P_t[i].fit_p_c /= sum;
	}	
	double n;
	//从P_t中选出M个个体,存入P中
	for(i = 0;i < M;i ++)
	{
		n = (double)rand() / RAND_MAX;
		for(j = 0;j < N;j ++)
		{
			if(n<P[j].fit_p_c)
			{
				memcpy(&P[i],&P_t[j],sizeof(P[j]));
				break;
			}
		}
	}
}

5.交叉产生后代P_s实现

将P中的个体两两组队,依据交叉概率pc,若生成的随机数大于pc,则再生成两个随机数代表交叉点位,进行交叉后产生后代P_s。
具体代码如下:

int ProduceSon(Individual *P,Individual *P_s,int N)
{
	int i,j,k = 0;
	double n;
	int a,b;
	for(i = 0;i < N / 2;i ++)
	{
		n = (double)rand() / RAND_MAX;
		if(n > pc)
		{
			a = rand() % len;
			b = rand() % len;
			if(b < a)
			{
				int temp = a;
				a = b;
				b = temp;
			}
			for(j = 0;j < a;j ++)
			{
				P_s[k].code[j] = P[2*i].code[j];
				P_s[k+1].code[j] = P[2*i+1].code[j];
			}	
			for(j = a;j < b;j ++)
			{
				P_s[k].code[j] = P[2*i+1].code[j];
				P_s[k+1].code[j] = P[2*i].code[j];
			}	
			for(j = b;j < len;j ++)
			{
				P_s[k].code[j] = P[2*i].code[j];
				P_s[k+1].code[j] = P[2*i+1].code[j];
			}
			P_s[k].code[len] = '\0';
			P_s[k+1].code[len] = '\0';
			k += 2;
		}
	}
	return k;//返回值是P_s中的个体数量
}

6.交叉产生后代P_m实现

在P_s的每个个体中依据变异概率pm,当生成的随机数小于pm,则相应的二进制编码取反。
具体代码如下:

int Mutation(Individual *P_s,Individual *P_m,int N)
{
	int i,j,k = 0,flag;
	double n;
	for(i = 0;i < N;i ++)
	{
		flag = 0;
		for(j = 0;j < len;j ++)
		{
			n = (double)rand() / RAND_MAX;
			if(n <= pm)
			{
				if(flag == 0)
				{
					memcpy(&P_m[k],&P_s[i],sizeof(P_s[i]));
					flag = 1;
				}
				if(P_s[i].code[j] == '0')
					P_m[k].code[j] = '1';
				else if(P_s[i].code[j] == '1')
					P_m[k].code[j] = '0';
			}
		}
		if(flag == 1)
			k++;
	}
	return k;//返回值是P_m中个体数量
} 

7.保留精英、产生下一代P实现

将P、P_s、P_m进行整合并且根据适应度排序,将前两名保留至下一代种群,然后将剩余个体进行轮盘赌产生N-2个个体保留至下一代。
具体代码如下:

int compare(const void *a, const void *b) 
{
    Individual *structA = (Individual *)a;
    Individual *structB = (Individual *)b;
    if (structA->fitness > structB->fitness) return -1;
    if (structA->fitness < structB->fitness) return 1;
    return 0;
}
//整合到P_n中并排序
void NewPopu(Individual *P,Individual *P_s,Individual *P_m,Individual *P_n,int N,int M,int K)
{
	int i,k = 0;
	for(i = 0;i < N;i ++)
		memcpy(&P_n[k++],&P[i],sizeof(P[i]));
	for(i = 0;i < M;i ++)
		memcpy(&P_n[k++],&P_s[i],sizeof(P_s[i]));
	for(i = 0;i < K;i ++)
		memcpy(&P_n[k++],&P_m[i],sizeof(P_n[i]));
	qsort(P_n,N+M+K,sizeof(Individual),compare);
}
//下面的内容放到了main函数里
	Individual P_two[2];
	memcpy(&P_two[0],&P_new[0],sizeof(P_new[0]));
	memcpy(&P_two[1],&P_new[1],sizeof(P_new[1]));	
	Individual P_remain[N+son_num+m_num-2];
	for(i = 0;i < N+son_num+m_num-2;i ++)
		memcpy(&P_remain[i],&P_new[i+2],sizeof(P_new[i+2]));
	Individual P_t[N-2];
	Roulette(P_t,P_remain,N+son_num+m_num-2,N-2);
	for(i = 0;i < 2;i ++)
		memcpy(&Popu[i],&P_two[i],sizeof(P_two[i]));
	for(i = 2;i < N;i ++)
		memcpy(&Popu[i],&P_t[i-2],sizeof(P_t[i-2]));		

四、总体代码

进化代数:1000
因收敛不稳定故执行了5遍取最大值,结果稳定。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#define pi 3.141593
#define x1min -3.0
#define x1max 12.1
#define x2min 4.1
#define x2max 5.8
#define len1 18
#define len2 15
#define len 33
#define pc 0.6
#define pm 0.1

typedef struct
{
	char code[len+1];
	double x1;
	double x2;
	double fitness;
	double fit_p;
	double fit_p_c;
}Individual;

long long int binaryToDecimal(char *binaryString) 
{
    int i;
	long long int decimal = 0;
    int length = strlen(binaryString);
    for (i = 0; i < length; i++) 
        if (binaryString[i] == '1') 
            decimal += 1 << (length - i - 1);
    return decimal;
}

void InitPopu(Individual *P,int N)
{	
	int i,k,n;
	for(i = 0;i < N;i ++)
	{
		for(k = 0;k < len;k ++)
		{
			n = rand()%100;
			if(n<50)
				P[i].code[k] = '0';
			else
				P[i].code[k] = '1';
		}
		P[i].code[len] = '\0';
	}
}

void decode(Individual *P,int N)
{
	int i,j;
	char code1[len1+1];
	char code2[len2+1];
	for(i = 0;i < N;i ++)
	{
		for(j = 0;j < len1;j ++)
			code1[j] = P[i].code[j];
		code1[len1] = '\0';
		for(j = 0;j < len2;j ++)
			code2[j] = P[i].code[j+len1];
		code2[len2] = '\0';
		long long int code1num = pow(2,len1);
		long long int code2num = pow(2,len2);
		long long int num1 = binaryToDecimal(code1);
		long long int num2 = binaryToDecimal(code2);
		P[i].x1 = x1min + (x1max - x1min) * num1 / (code1num - 1);
		P[i].x2 = x2min + (x2max - x2min) * num2 / (code2num - 1);
	}	
}

void CulFitness(Individual *P,int N)
{
	int i;
	for(i = 0;i < N;i ++)
		P[i].fitness = 21.5 + P[i].x1 * sin(4 * pi * P[i].x1) + P[i].x2 * sin(20 * pi * P[i].x2);
}

void Roulette(Individual *P,Individual *P_t,int N,int M)
{
	int i,j;
	double sum = 0;
	for(i = 0;i < N;i ++)
	{
		sum += P_t[i].fitness;
		P_t[i].fit_p_c = sum;
	}	
	for(i = 0;i < N;i ++)
	{
		P_t[i].fit_p = P_t[i].fitness / sum;
		P_t[i].fit_p_c /= sum;
	}	
	double n;
	for(i = 0;i < M;i ++)
	{
		n = (double)rand() / RAND_MAX;
		for(j = 0;j < N;j ++)
		{
			if(n<P[j].fit_p_c)
			{
				memcpy(&P[i],&P_t[j],sizeof(P[j]));
				break;
			}
		}
	}
}

int ProduceSon(Individual *P,Individual *P_s,int N)
{
	int i,j,k = 0;
	double n;
	int a,b;
	for(i = 0;i < N / 2;i ++)
	{
		n = (double)rand() / RAND_MAX;
		if(n > pc)
		{
			a = rand() % len;
			b = rand() % len;
			if(b < a)
			{
				int temp = a;
				a = b;
				b = temp;
			}
			for(j = 0;j < a;j ++)
			{
				P_s[k].code[j] = P[2*i].code[j];
				P_s[k+1].code[j] = P[2*i+1].code[j];
			}	
			for(j = a;j < b;j ++)
			{
				P_s[k].code[j] = P[2*i+1].code[j];
				P_s[k+1].code[j] = P[2*i].code[j];
			}	
			for(j = b;j < len;j ++)
			{
				P_s[k].code[j] = P[2*i].code[j];
				P_s[k+1].code[j] = P[2*i+1].code[j];
			}
			P_s[k].code[len] = '\0';
			P_s[k+1].code[len] = '\0';
			k += 2;
		}
	}
	return k;
}

int Mutation(Individual *P_s,Individual *P_m,int N)
{
	int i,j,k = 0,flag;
	double n;
	for(i = 0;i < N;i ++)
	{
		flag = 0;
		for(j = 0;j < len;j ++)
		{
			n = (double)rand() / RAND_MAX;
			if(n <= pm)
			{
				if(flag == 0)
				{
					memcpy(&P_m[k],&P_s[i],sizeof(P_s[i]));
					flag = 1;
				}
				if(P_s[i].code[j] == '0')
					P_m[k].code[j] = '1';
				else if(P_s[i].code[j] == '1')
					P_m[k].code[j] = '0';
			}
		}
		if(flag == 1)
			k++;
	}
	return k;
} 

int compare(const void *a, const void *b) 
{
    Individual *structA = (Individual *)a;
    Individual *structB = (Individual *)b;
    if (structA->fitness > structB->fitness) return -1;
    if (structA->fitness < structB->fitness) return 1;
    return 0;
}

void NewPopu(Individual *P,Individual *P_s,Individual *P_m,Individual *P_n,int N,int M,int K)
{
	int i,k = 0;
	for(i = 0;i < N;i ++)
		memcpy(&P_n[k++],&P[i],sizeof(P[i]));
	for(i = 0;i < M;i ++)
		memcpy(&P_n[k++],&P_s[i],sizeof(P_s[i]));
	for(i = 0;i < K;i ++)
		memcpy(&P_n[k++],&P_m[i],sizeof(P_n[i]));
	qsort(P_n,N+M+K,sizeof(Individual),compare);
}

int main()
{
	srand((unsigned int)time(NULL));
	int N = 100;
	int i,j,k,t;
	Individual Popu[N],P_temp[N],P_son[N],P_m[N];
	Individual max;
	for(t = 0;t < 5;t ++)
	{
		InitPopu(Popu,N);
		decode(Popu,N);
		CulFitness(Popu,N);
		for(k = 0;k < 1000;k ++)
		{
			memcpy(P_temp,Popu,sizeof(Popu));
			Roulette(Popu,P_temp,N,N);	
			int son_num = ProduceSon(Popu,P_son,N);
			decode(P_son,son_num);
			CulFitness(P_son,son_num);		
			int m_num = Mutation(P_son,P_m,son_num);
			decode(P_m,m_num);
			CulFitness(P_m,m_num);		
			Individual P_new[N+son_num+m_num];
			NewPopu(Popu,P_son,P_m,P_new,N,son_num,m_num);	
			Individual P_two[2];
			memcpy(&P_two[0],&P_new[0],sizeof(P_new[0]));
			memcpy(&P_two[1],&P_new[1],sizeof(P_new[1]));	
			Individual P_remain[N+son_num+m_num-2];
			for(i = 0;i < N+son_num+m_num-2;i ++)
				memcpy(&P_remain[i],&P_new[i+2],sizeof(P_new[i+2]));
			Individual P_t[N-2];
			Roulette(P_t,P_remain,N+son_num+m_num-2,N-2);
			for(i = 0;i < 2;i ++)
				memcpy(&Popu[i],&P_two[i],sizeof(P_two[i]));
			for(i = 2;i < N;i ++)
				memcpy(&Popu[i],&P_t[i-2],sizeof(P_t[i-2]));		
			for(i = 0;i < N;i ++)
				if(max.fitness < Popu[i].fitness)
					memcpy(&max,&Popu[i],sizeof(Popu[i]));
		}
	}
	printf("%s %.4f %.4f %.4f\n",max.code,max.fitness,max.x1,max.x2);
	return 0;
} 

五、运行结果

在这里插入图片描述

六、问题2解决

在这里插入图片描述
只需改变相应的参数以及适应度求解函数即可:

#define x1min -2.048
#define x1max 2.048
#define x2min -2.048
#define x2max 2.048
#define len1 16
#define len2 16
#define len 32
void CulFitness(Individual *P,int N)
{
	int i;
	for(i = 0;i < N;i ++)
		P[i].fitness = 100 * pow((P[i].x2 - pow(P[i].x1,2)),2) + pow((1 - P[i].x1),2);
}

运行结果如下:
在这里插入图片描述

扫描二维码推送至手机访问。

版权声明:本站部分文章来自互联网采集,请查看免责申明

本文链接:https://www.yyzq.team/post/338232.html

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。