#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
#define POPSIZE 50 //最大种群数
#define CHROMLENGTH 22 //染色体长度
#define PI 3.1415926535 //PI
int maxgeneration=200; //最大代数
double pc=0.25; //交叉概率
double pm=0.01; //变异概率
double xmin=-1,xmax=2;
struct Individual
{
char chrom[CHROMLENGTH+1]; //编码串
double value; //函数值
double fitness; //适应度
};
int generation; //代数
Individual currentbest; //当前种群中的最佳个体（即函数值最大者）
Individual population[POPSIZE]; // 种群
long DecodeChromosome(char *string ,int length) //给染色体解码
{
int i;
long value=0;
for(i = 0 ;i < length ;i ++)
{
if(string[i] - '0' == 1)
value += (long)pow((double)2,i);
}
return (value);
}
void CalculateFitnessValue() //计算适应度
{
int i;
for(i=0;i<POPSIZE;i++)
{
population[i].fitness = population[i].value;
}
}
void CalculateFunctionValue() //计算函数值
{
int i;
long temp;
double x;
for (i=0; i<POPSIZE; i++)
{
temp = DecodeChromosome(population[i].chrom,CHROMLENGTH);
x = -1 + (xmax-xmin)*temp/(pow((double)2,CHROMLENGTH)-1);
population[i].value=x*sin(10*PI*x)+1.0;
}
}
void Select() //比例选择算法
{
int i,index;
double p,sum=0.0;
double cfitness[POPSIZE]; //存每个个体的概率
Individual newpopulation[POPSIZE];
for(i=0;i<POPSIZE;i++)
sum+=population[i].fitness;
for(i=0;i<POPSIZE; i++)
cfitness[i]=population[i].fitness/sum;
for(i=1;i<POPSIZE; i++) //计算累计概率
cfitness[i]=cfitness[i-1]+cfitness[i];
for (i=0;i<POPSIZE;i++)
{
p=rand()%1000/1000.0;
index=0;
while (p>cfitness[index])
index++;
newpopulation[i]=population[index];
} //轮盘赌选择
for(i=0;i<POPSIZE; i++)
population[i]=newpopulation[i];
}
void Mutate() //变异操作
{
int i,j;
double p;
for(i=0;i<POPSIZE;i++)
{
for(j=0;j<CHROMLENGTH;j++)
{
p=(rand()%1000)/1000.0;
if (p<pm)
{
population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
}
}
}
}
void Cross() //交叉算法
{
int i,j;
int index[POPSIZE];
int point,temp;
double p;
char ch;
for(i=0;i<POPSIZE;i++)
index[i]=i;
for(i=0;i<POPSIZE;i++)
{
point=rand()%(POPSIZE-i);
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}//对当前个体进行随机排序
for(i=0;i<POPSIZE-1;i+=2)
{
p=rand()%1000/1000.0;
if (p<pc)
{
point=rand()%(CHROMLENGTH-1)+1;
for (j=point; j<CHROMLENGTH;j++)
{
ch=population[index[i]].chrom[j];
population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
population[index[i+1]].chrom[j]=ch;
}
}
}
}
void FindBestIndividual() //求当前种群中的最佳个体
{
int i;
int best_index;
Individual bestIndividual=population[0];
for (i=1;i<POPSIZE; i++)
{
if (population[i].fitness>bestIndividual.fitness)
{
bestIndividual=population[i];
best_index=i;
}
}
if (generation==0)
{
currentbest=bestIndividual;
}
else
{
if(bestIndividual.fitness>=currentbest.fitness)
{
currentbest=bestIndividual;
}
}
}
void GenerateInitial( ) //种群初始化
{
int i,j;
for (i=0;i<POPSIZE; i++)
{
for(j=0;j<CHROMLENGTH;j++)
{
population[i].chrom[j]=(rand()%10<5)?'0':'1';
}
}
}
void NextGeneration() //生成下一代
{
Select();
Cross();
Mutate();
}
void EvaluatePopulation()
{
CalculateFunctionValue();
CalculateFitnessValue();
}
double CalX(char *str) //将str转成对应的x的值
{
long temp;
double x;
temp = DecodeChromosome(str,CHROMLENGTH);
x = -1 + (xmax-xmin)*temp/(pow((double)2,CHROMLENGTH)-1);
return x;
}
int main()
{
srand(time(NULL));
printf("f(x)=x*sin(10*PI*x)+1.0 (-1<=x<=2)\n");
generation=0;
GenerateInitial();
EvaluatePopulation();
while(generation<maxgeneration)
{
generation++;
NextGeneration();
EvaluatePopulation();
}
FindBestIndividual();
printf("函数最大最值等于：%f\n",currentbest.value);
printf("X的值是：%f\n",CalX(currentbest.chrom));
printf("染色体的编码是：");
for (int i=0;i<CHROMLENGTH;i++)
{
printf("%c",currentbest.chrom[i]);
}
printf("\n");
return 0;
}
