作业存档

实验4 简单的遗传算法

1. 实验目的

理解和掌握遗传算法的基本方法，能够用选定的编程语言实现简单的遗传算法。

1. 实验内容和要求

1. 以函数优化问题为例，求f（x）=x2的最大值，其中x∈[0,31]；
2. 假设适应度函数为f（x），至于种群规模、选择算法、交叉概率、变异概率和计算精度等自行确定。

 

1. 函数

按照遗传算法，程序求解过程如下：

1. 编码：用到的函数：产生随机数，十进制转化成二进制，
2. 生成初始种群：用二维数组存储初始种群情况
3. 计算适应值，填入初始种群情况表
4. 选择操作：依次生成4个随机数，进行选择。用一个数组存储选择的结果。
5. 交叉：自定义交叉概率。（这个部分实现最复杂）
6. 变异
7. 得到第二代

1. 运行结果截图：

 

1. 遇到的问题：

(1)、一直得不到最大值，如下截图。原因大概是，没有变异，

 

(2)、有时候会变成4个个体染色体一样的情况：原因应该也是没有进行变异。

 

(3)、写的时候有想过要不要再选择的时候加个判断，如果被选的只有原来种群的的一两个个体，要不要重新生成一组随机数再选一次，因为担心染色体会不够丰富。但后来又看了一遍书上的介绍，以及以前学的生物进化的知识，还是觉得不应该加这个判断，而且还有变异。不过这样一来变异的概率也就决定了种群的进化快慢。

1. 源代码：

#include<stdlib.h>

#include<time.h>

#include<stdio.h>

#include<math.h>

 

//int s[10][5];

void tenToTwo(int num[],int s[10][5])

{

int i,j,k,b=0;

for(j=0;j<4;j++)       //10进制数转2进制，并存到s[][]中

{

//printf("num[j],%d\n",num[j]);

b=num[j];

//printf("b: %d\n",b);

k=4;

while(b!=0)  

{  

i=b%2;  

s[j][k]=i;  

//printf("s%d: %d   ",j,s[j][k]);

k--;  

b=b/2;      

}  

//printf("\n");

}     

for(j=0;j<4;j++)

{

printf("个体%d的染色体： ",j);

for(k=0;k<5;k++)

{

printf("%d",s[j][k]);

}

printf("\n");

}

}

void twoToTen(int x[],int s[10][5])

{

/*2进制转10进制*/

//int x[10];

int i;

for(i=0;i<4;i++)

{

x[i] = s[i][0]*16+s[i][1]*8+s[i][2]*4+s[i][3]*2+s[i][4];

}

}

int fixed(int fix[10],int num[])

{

/*计算适应度*/

int sum=0,i;

for(i=0;i<4;i++)

{

printf("%d号个体: %d",i,num[i]);

fix[i] = num[i]*num[i];

sum+=fix[i];

printf(" 个体的适应度: %d\n",fix[i]);

}

return sum;

}

void countPercent(double percent[],int fix[],double sum)

{    /*计算百分比*/

//double percent[10];

int i;

//printf("%d\n",sum);

for(i=0;i<4;i++)

{

percent[i] = double(fix[i])/double(sum);

printf("[%d]号个体的百分比: %.2lf\n",i,percent[i]);

}

}

void selectIndividual(int selected[],double percent[],int num[])

{/*依次生成4个0-1的随机数*/

int j,i;

double random[10];

srand((unsigned) time(NULL));

printf("采用轮盘赌方式选择个体，生成4个随机数：\n");

for (j=0; j<4; j++)

{

random[j] = (rand() % 100 + 1)/100.0;  //产生1-100的随机数

printf("random[%d]: %lf\n",j,random[j]);

}

/*轮盘赌选择个体*//*计算累计百分比*/

//int selected[10]; //存选中的个体

double a[10]; //存累计百分比

double cal=0.0;

a[0]=0.0;

printf("累计百分比：\n");

for(i=0;i<4;i++)

{

cal = cal+percent[i];

a[i+1] = cal;

printf("a[%d]: %f\n",i,a[i]);

}

printf("a[%d]: %f\n",i,a[i]);

int count[4]={0,0,0,0};

printf("被选上的个体：\n");

for(i=0;i<4;i++)

{

for(j=0;j<4;j++)

{

if(a[j]<=random[i]&&a[j+1]>random[i])

{

selected[i] = num[j];

count[j]++;

}

}

printf("selected[%d]: %d\n",i,selected[i]);

}

/*

//如果被踢除了两个或三个

if(count[0]>2||count[1]>2||count[2]>2||count[3]>2)

{

srand((unsigned) time(NULL));

for (j=0; j<4; j++)

{

random[j] = (rand() % 100 + 1)/100.0;  //产生1-100的随机数

printf("random[%d]: %lf\n",j,random[j]);

}

//轮盘赌选择个体  计算累计百分比

//int selected[10]; //存选中的个体

double a[10]; //存累计百分比

double cal=0.0;

a[0]=0.0;

for(i=0;i<4;i++)

{

cal = cal+percent[i];

a[i+1] = cal;

printf("a[%d]: %f\n",i,a[i]);

}

printf("a[%d]: %f\n",i,a[i]);

int count[4]={0,0,0,0}

for(i=0;i<4;i++)

{

for(j=0;j<4;j++)

{

if(a[j]<=random[i]&&a[j+1]>random[i])

{

selected[i] = num[j];

count[j]++;

printf("selected[%d]: %d\n",i,selected[i]);

}

}

}

}*/

}

void mutationoperator(int s[10][5]) //变异操作

{

int i,j;

double p;

srand((unsigned) time(NULL)); //种下随机种子

for (i=0;i<4;i++){

for(j=0;j<5;j++){

p=rand()%1000/1000.0;

if (p<0.3){

s[i][j]=(s[i][j]==0)?1:0;

}

}

}

}

 

bool IsFind(int num[])

{

int i;

for(i=0;i<4;i++)

{

if(num[i]==31)

{

printf("找到了最大值31，算法结束！");

return true;

}

}

return false;

}

int main()

{

printf("遗传算法开始，个体数是4\n");

srand((unsigned) time(NULL)); //用时间做种子，每次产生随机数不一样

int i,j=0,k=4,c=0,num[10],s[10][5];

bool flag=false; //算法终止判断

 

for(j=0;j<4;j++) //二维数组初始化，

{      

//s[10][5]是用来存储二进制编码的数组

for(i=0;i<5;i++)

{

s[j][i] = 0;

}

}

printf("***************************\n");

printf("*********第0代：***********\n");

printf("***************************\n");

 

for (j=0; j<4; j++) //产生个体

   {

     num[j] = rand() % 30 + 1;  //产生1-31的随机数

     printf("个体%d的x值: %d\n",j,num[j]);

   }

tenToTwo(num,s);  //10进制数转2进制，并存到s[][]中

int fix[10]; //存储适应值

int sum; //适应值的和

int count=1;

int f=1;

do{

printf("******计算适应度：\n");

sum= fixed(fix,num); /*计算适应度*/

double percent[10];

 

countPercent(percent,fix,sum);

/*for(i=0;i<4;i++)

{

printf("percent[%d]: %.2lf\n",i,percent[i]);

}*/

printf("******* 选择：\n");

int selected[10]; //存选中的个体

selectIndividual(selected,percent,num); /*轮盘赌选择个体*/

 

/*更新num*/

for(i=0;i<4;i++)

{

num[i] = selected[i];

}

/*生成选择后的个体的染色体*/

tenToTwo(num,s);  //10进制数转2进制，并存到s[][]中

/*交叉：交叉概率为50%*/

//随机产生交叉位，01和02交叉

printf("****** 交叉：\n");

srand((unsigned) time(NULL));

int jiaocha = rand() % 3 + 1;

printf("交叉位为：%d\n",jiaocha);

//配对交叉，得到交叉后的个体串

int index;

for(i=jiaocha;i<5;i++)

{

index = s[0][i];

s[0][i] = s[1][i];

s[1][i] = index;

}

printf("交叉后每个个体的染色体：\n");

for(j=0;j<4;j++)

{

printf("个体%d的染色体： ",j);

for(k=0;k<5;k++)

{

printf("%d",s[j][k]);

//s[j][k] = selected [j][k];

//printf("s: %d",s[j][k]);

}

printf("\n");

}

/*变异*/

printf("****** 变异操作：\n");

mutationoperator(s);

twoToTen(num,s);

printf("---------我---是---代---沟----------\n");

printf("***************************\n");

printf("*********第%d代*************\n",count);

printf("***************************\n");

count++;

for(i=0;i<4;i++)

{

printf("%d号个体：%d\n",i,num[i]);

printf("%d号个体的染色体：",i);

for(j=0;j<5;j++)

{

printf("%d",s[i][j]);

}

printf("\n");

}

//flag = IsFind(num);

for(i=0;i<4;i++)

{

if(num[i]==31)

{

printf("找到了最大值31，算法结束！");

f=0;

}

}

}while(f==1);

//flag==false||

return 0;

}