📄 佳点集算法.cpp
字号:
//用佳点集遗传算法求解函数最大值问题
// f(x)=x1^2+x2^2+x3^2 其中-5.12<=xi<=5.12
#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<iomanip.h>
#define N 50 //种群规模
#define c3length 18 // 三个编码的总编码长度
int generation; //遗传代数
double pc ; //交叉的概率(%)
double pm ; //变异的概率
typedef struct individual //定义个体的结构
{
char code[c3length+1]; //三个分量分别用6位二进制码表示
double fitness; // 适应值
float Ps,Ecount; //选择概率,期望次数
int Scount; //选中次数
}individual;
individual population[N];
long Decode(char * string,int start,int length) //解码
//表示对string字符串的从start位置开始的length个字符进行解码
{
int i;
long value=0;
int temp=1;
for (i=length+start-1 ;i>=start;i--)
{
value+=(string[i]-48)*temp;
temp*=2;
}
return value;
}
double CalculateValue(char * s) //计算函数值
{
long temp1,temp2,temp3;
double x1,x2,x3;
temp1=Decode(s,0,6);
temp2=Decode(s,6,6);
temp3=Decode(s,12,6);
x1=-5.12+(temp1*(5.12-(-5.12)))/(64-1);
x2=-5.12+(temp2*(5.12-(-5.12)))/(64-1);
x3=-5.12+(temp3*(5.12-(-5.12)))/(64-1);
return (x1*x1+x2*x2+x3*x3);
}
void InitialPopulation() //初始化种群
{
int i,j;
cout<<"产生的初始种群为:"<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<c3length;j++)
{
population[i].code[j]=((rand()%10)>5)?'1':'0';
cout<<population[i].code[j];
}
cout<<endl;
population[i].code[c3length]='\0';
}
}
void SelectCount() //对期望次数排序,求选中次数
{
int i,t;
float temp1,temp2,a[N];
int b[N];
int SHave=0;
population[0].Scount=(int)population[0].Ecount;
population[1].Scount=(int)population[1].Ecount;
population[2].Scount=(int)population[2].Ecount;
population[3].Scount=(int)population[3].Ecount;
population[4].Scount=(int)population[4].Ecount;
population[5].Scount=(int)population[5].Ecount;
population[6].Scount=(int)population[6].Ecount;
population[7].Scount=(int)population[7].Ecount;
population[8].Scount=(int)population[8].Ecount;
population[9].Scount=(int)population[9].Ecount;
for (i=0;i<N;i++)
SHave+=population[i].Scount;
for(i=0;i<N;i++)
a[i]=population[i].Ecount-population[i].Scount;
if (a[0]<a[1])
{
temp1=a[0]; a[0]=a[1];a[1]=temp1;
b[0]=1;b[1]=0;
}
else
{
b[0]=0;b[1]=1;
}
for(i=2;i<N;i++)
{
temp2=a[i];
int j=0;
while((j<i) && (a[i]<a[j]))
j++;
if(j==i)
b[i]=i;
else if(j<i)
{
for (int k=i;k>j;k--)
{
a[k]=a[k-1]; b[k]=b[k-1];
}
a[j]=temp2; b[j]=i;
}
}
for (i=1,t=0;i<=(N-SHave);i++,t++)
population[b[t]].Scount++;
}
void EvaluationIndividual() //对个体进行评价
{
int i;
double sum=0;
for(i=0;i<N;i++)
{
population[i].fitness=CalculateValue(population[i].code);
sum+=population[i].fitness;
}
for (i=0;i<N;i++)
{
population[i].Ps=(float)(population[i].fitness/sum);
population[i].Ecount=population[i].Ps*N;
}
SelectCount();
cout<<endl<<" 第"<<generation<<"代种群情况"<<endl;
cout<<"序号 种 群 适应值 选择概率(%) 期望次数 选中次数"<<endl;
for(i=0;i<N;i++)
{
cout<<setw(2)<<i+1<<" ";
for(int j=0;j<c3length;j++)
cout<<population[i].code[j];
cout<<setprecision(7);
cout<<setw(11)<<population[i].fitness<<setw(12)<<setprecision(5)<<population[i].Ps*100<<setw(14)<<setprecision(4)<<population[i].Ecount<<setw(8)<<population[i].Scount;
cout<<endl;
}
}
void SelectAlgorithm() //选择操作的算法
{
int i,j=0;
for(i=0;i<N;i++)
{
while(population[i].Scount>0)
{
for(int k=0;k<c3length;k++)
population[j].code[k]=population[i].code[k];
population[j].code[c3length]='\0';
j++;
population[i].Scount--;
}
}
}
int MinNum(int x) //求符合要求的最小素数
{
int i=2;
TAB: while(i<x)
{
if(x%i==0)
{ x++; i=2; goto TAB; }
i++;
}
return x;
}
float GetDecimal(float x) //返回小数部分
{
int y=(int)x;
return (x-y);
}
char GetChromosomeCode(float x) //获得交叉后产生的n个后代中的第k个染色体
{
char ch;
if (x>0.5)
ch='0';
else
ch='1';
return ch;
}
void CrossAlgorithm() //交叉操作
{
int Randpc; //产生随机交叉概率看是否执行交叉
char s[N]; //保存是否交叉状态Y or N
int i,j;
int c[N]; //记录与之交叉的个体
for(i=0;i<N;i++)
s[i]='N';
//保存交叉前的个体,便于输出
individual p[N];
for(i=0;i<N;i++)
{
for(j=0;j<c3length;j++)
p[i].code[j]=population[i].code[j];
p[i].code[c3length]='\0';
}
//执行交叉
for(i=0;i<N;i++)
{
Randpc=rand()%100;
if ((Randpc<pc) && (s[i]=='N') )
{
int cross;
// char ch;
s[i]='Y';
char codes[c3length+1]; //二个个体对应位置值相同用原码值,不同记为'*'
individual B[2];
int t=0; //记录二个交叉个体不同分量的个数,从而方便求素数p
int p; //最小素数
int k1,k2,k3=1;
float tp,t1;
do
{
cross=rand()%N;
}while((s[cross]=='Y') || (cross==i));
s[cross]='Y';
c[i]=cross;
c[cross]=i;
for (int k=0;k<c3length;k++)
{
if (population[i].code[k]==population[cross].code[k])
codes[k]=population[i].code[k];
else
{
codes[k]='*';
++t;
}
}
p=MinNum(2*t+3);
for(k1=0;k1<2;k1++)
for(k2=0;k2<c3length;k2++)
{
if (codes[k2]=='*')
{
t1=(float)(2*cos((2*3.14*k3)/p));
tp=GetDecimal(t1);
B[k1].code[k2]=GetChromosomeCode(tp);
++k3;
}
else
B[k1].code[k2]=codes[k2];
}
for(k2=0;k2<c3length;k2++)
population[i].code[k2]=B[0].code[k2];
for(k2=0;k2<c3length;k2++)
population[cross].code[k2]=B[0].code[k2];
}
}
for (i=0;i<N;i++)
population[i].fitness=CalculateValue(population[i].code);
cout<<endl<<" 第"<<generation<<"代种群交叉情况"<<endl;
cout<<"序号 种 群 交叉否 交叉 子 代 适应值"<<endl;
for(i=0;i<N;i++)
{
cout<<setw(2)<<i+1<<" ";
for (j=0;j<c3length;j++)
cout<<p[i].code[j];
cout<<" "<<s[i];
cout<<" "<<setw(2)<<c[i]+1<<" ";
for (j=0;j<c3length;j++)
cout<<population[i].code[j];
cout<<" "<<setw(9)<<setprecision(6)<<population[i].fitness;
cout<<endl;
}
}
void MutationAlgorithm() //变异算法.这里默认只有一个个体变异
{
int i,j;
int MutationLocate=rand()%c3length; //变异的位置
int MutationIndividual=rand()%N; //变异的个体
char yesno[N];
if ((rand()%100)>pm)
goto T;
for (i=0;i<N;i++)
{
if (i==MutationIndividual)
yesno[i]='Y';
else
yesno[i]='N';
} //保存变异前的个体,便于输出
individual p[N];
for(i=0;i<N;i++)
{
for(j=0;j<c3length;j++)
p[i].code[j]=population[i].code[j];
p[i].code[c3length]='\0';
}
//执行变异过程
population[MutationIndividual].code[MutationLocate]=(population[MutationIndividual].code[MutationLocate]=='0')?'1':'0';
population[MutationIndividual].fitness=CalculateValue(population[MutationIndividual].code);
cout<<endl<<" 第"<<generation<<"代种群变异情况"<<endl;
cout<<"序号 种 群 是否变异 变异位 新种群 适应值"<<endl;
for (i=0;i<N;i++)
{
cout<<setw(3)<<i+1<<" ";
for(j=0;j<c3length;j++)
cout<<p[i].code[j];
cout<<" "<<yesno[i];
if (yesno[i]=='Y')
cout<<setw(10)<<setprecision(2)<<MutationLocate;
else
cout<<setw(10)<<" ";
cout<<" ";
for(j=0;j<c3length;j++)
cout<<population[i].code[j];
cout<<setw(12)<<setprecision(6)<<population[i].fitness;
cout<<endl;
}
T: ;
}
void output() //输出最后结果
{
int i;
double max=population[0].fitness;
int temp=0;
for(i=1;i<N;i++)
if (population[i].fitness>max)
{
max=population[i].fitness;
temp=i;
}
cout<<endl<<endl<<" 最 后 结 果 为: "<<endl;
cout<<"x1染色体编码为:";
for(i=0;i<6;i++)
cout<<population[temp].code[i];
cout<<endl<<"x2染色体编码为:";
for(i=6;i<12;i++)
cout<<population[temp].code[i];
cout<<endl<<"x3染色体编码为:";
for(i=12;i<c3length;i++)
cout<<population[temp].code[i];
cout<<endl<<"f(x)取得最大值:"<<population[temp].fitness<<endl;
}
void main()
{
cout<<"本程序用佳点集遗传算法求解函数最大值问题 "<<endl;
cout<<" f(x)=x1^2+x2^2+x3^2 -5.12<=xi<=5.12"<<endl;
generation =0;
int gene;
cout<<"请输入操作参数 :";
cout<<endl<<" 请输入最大遗传代数（100-500）:";
cin>>gene;
cout<<endl<<" 请输入交叉概率(40-99):";
cin>>pc;
cout<<endl<<" 请输入变异概率(1-50):";
cin>>pm;
cout<<endl<<endl;
srand((unsigned) time (NULL));
InitialPopulation();
while(generation<gene)
{
EvaluationIndividual();
SelectAlgorithm();
CrossAlgorithm();
MutationAlgorithm();
generation++;
}
output();
int jixu;
cout<<"是否继续（1/0）：";
cin>>jixu;
if (jixu==1) {main();}
else exit(0);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -