GA.rar_遗传算法程序

//遗传算法求解f(x)=xcosx+2的最大值 //其中在尺度变换部分应用到了类似模拟退火算法部分，所有变量均使用汉语拼音很好懂 //随机初始种群 //编码方式为格雷码 //选择方法为随机遍历 //采用了精英保存策略 //采用了自适应的交叉率和变异率 //采用了与模拟退火算法相结合的尺度变换 //采用了均匀交叉法 #include <stdlib.h> #include <stdio.h> #include <math.h> #include <iostream.h> #include <iomanip.h> #include <time.h> #include <windows.h> #define IM1 2147483563 #define IM2 2147483399 #define AM (1.0/IM1) #define IMM1 (IM1-1) #define IA1 40014 #define IA2 40692 #define IQ1 53668 #define IQ2 52774 #define IR1 12211 #define IR2 3791 #define NTAB 32 #define NDIV (1+IMM1/NTAB) #define EPS 1.2e-7 #define RNMX (1.0-EPS) #define zhizhenjuli 0.005 #define PI 3.14159265358 #define T0 100000//温度要取得很高才行。 #define zhongqunshu1 200 #define zuobianjie -200 #define youbianjie 200 unsigned int seed=0; //seed 为种子，要设为全局变量 void mysrand(long int i) //初始化种子 { seed = -i; } long a[1]; //double hundun; //double c=4; //设置全局变量 struct individual { unsigned *chrom; //染色体； double geti;//变量值 double shiyingdu; //目标函数的值； double fitness; //变换后的适应度值； }; individual *zuiyougeti;//精英保存策略 int zhongqunshu; //种群大小 individual *nowpop;//当前代 individual *newpop;//新一代 double sumfitness;//当代的总适应度fitness double sumshiyingdu;//当代的总适应度shiyingdu double maxfitness;//最大适应度 double avefitness;//平均适应度 double maxshiyingdu;//最大适应度 double avgshiyingdu;//平均适应度 float pc;//交叉概率 float pm;//变异概率 int lchrom;//染色体长度 int maxgen;//最大遗传代数 int gen;//遗传代数 //函数 int flipc(double ,double );//判断是否交叉 int flipm(double );//判断是否变异 int rnd(int low,int high);//产生low与high之间的任意数 void initialize();//遗传算法初始化 void preselectfitness(); //计算sumfiness,avefitness,maxfitness void generation(); double suijibianli();//产生随机遍历指针 int fuzhi(float );//选择要复制的个体 void crossover(individual ,individual ,individual &,individual &);//交叉 void bianyi(individual &);//变异 void mubiaohanshu(individual &);//计算适应度 void chidubianhuan(individual &);//对shiyingdu进行尺度变换赋给fitness double ran1(long *);//随机数初始 void bianma(double bianliang,unsigned *p);//编码 double yima(unsigned *p); void guanjiancanshujisuan();//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness void jingyingbaoliu(); void glp(int n,int s,int *,int (*)[1],float (*)[1]);//glp生成函数 BOOL Exist(int Val, int Num, int *Array);//判断一个数在前面是否出现过 int cmpfitness(const void *p1,const void *p2) { float i=((individual *)p1)->shiyingdu;//现在是按照"适应度"排序，改成"个体"的话就是按照"个体"排序 float j=((individual *)p2)->shiyingdu; return i<j ? -1:(i==j ? 0:1);//现在是按升序牌排列，将1和-1互换后就是按降序排列 } void main() { initialize(); cout<<zuiyougeti->geti<<" "<<zuiyougeti->shiyingdu<<endl;///////////// for(gen=1;gen<maxgen;gen++) { generation(); } jingyingbaoliu(); cout<<setiosflags(ios::fixed)<<setprecision(6)<<zuiyougeti->geti<<" "<<setiosflags(ios::fixed)<<setprecision(6)<<(zuiyougeti->shiyingdu)<<endl;//////////////// delete [] newpop; delete [] nowpop; delete [] zuiyougeti; system("pause"); } void initialize() { int q[zhongqunshu1][1],s=1; float xx[zhongqunshu1][1];//生成的glp用x储存 int h[1]={1};//生成向量 zuiyougeti=new individual;//最优个体的生成 zhongqunshu=200;//种群数量 nowpop=new individual[zhongqunshu1];//当代 newpop=new individual[zhongqunshu1];//新一代 maxgen=150;//最大代数 gen=0;//起始代 lchrom=22;//基因数量的初始化 mysrand(time(0));//随机数种子 a[0]=seed;//随机数种子 //对最优个体的初始化 zuiyougeti->geti=0; zuiyougeti->fitness=0; zuiyougeti->shiyingdu=0; // glp(zhongqunshu,s,h,q,xx); //for(int i=0;i<zhongqunshu1;i++)//产生初始种群 //{ // for(int j=0;j<s;j++) // { // nowpop[i].geti=zuobianjie+(youbianjie-zuobianjie)*xx[i][j]; // } //} for(int i=0;i<zhongqunshu1;i++)//产生初始种群 { nowpop[i].geti=zuobianjie+(youbianjie-(zuobianjie))*ran1(a); } //nowpop[0].geti=999;////////////////////////// guanjiancanshujisuan(); jingyingbaoliu(); //精英保留的实现 guanjiancanshujisuan();//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness } void jingyingbaoliu() //精英保留的实现 { individual *zuiyougetiguodu; zuiyougetiguodu=new individual[zhongqunshu1];//建立一个过渡数组 for(int i=0;i<zhongqunshu;i++)//将当代个体复制到过渡数组中 zuiyougetiguodu[i]=nowpop[i]; qsort(zuiyougetiguodu,zhongqunshu1,sizeof(individual),&cmpfitness);//按fitness升序排序 // cout<<"zuiyougetiguodu适应度:"<<zuiyougetiguodu[zhongqunshu1-1].shiyingdu<<endl;/////////// // cout<<"zuiyougeti适应度:"<<zuiyougeti->shiyingdu<<endl;/////////////////// //system("pause"); if(zuiyougetiguodu[zhongqunshu-1].shiyingdu>zuiyougeti->shiyingdu) { *zuiyougeti=zuiyougetiguodu[zhongqunshu1-1];//如果最优个体的fitness比当代最大的fitness小则用当代的代替之 //cout<<"zuiyougetiguodu个体:"<<zuiyougetiguodu[zhongqunshu1-1].geti<<endl;///////////// //cout<<"zuiyougeti个体:"<<zuiyougeti->geti<<endl;///////////// } else nowpop[rnd(0,(zhongqunshu1-1))]=*zuiyougeti;//否则的话从当代中随机挑选一个用最优个体代替之 delete [] zuiyougetiguodu;//释放过渡数组 } void guanjiancanshujisuan()//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness { for(int i=0;i<zhongqunshu;i++)//计算shiyingdu mubiaohanshu(nowpop[i]); for(i=0;i<zhongqunshu;i++)//对shiyingdu进行尺度变换变成fitness chidubianhuan(nowpop[i]); preselectfitness();//根据fitness计算sumfitness，avefitness，maxfitness } void mubiaohanshu(individual &bianliang)//计算shiyingdu { bianliang.shiyingdu=(bianliang.geti*cos(bianliang.geti)+2.0);//目标函数 } void chidubianhuan(individual &bianliang)//对shiyingdu进行尺度变换变成fitness { double T;//退火温度 T=T0*(pow(0.99,(gen+1-1))); double sum=0; for(int j=0;j<zhongqunshu;j++) sum+=exp(nowpop[j].shiyingdu/T); bianliang.fitness=exp(bianliang.shiyingdu/T)/sum;//算出fitness } void preselectfitness()//根据fitness计算sumfitness，avefitness，maxfitness { int j; sumfitness=0; for(j=0;j<zhongqunshu;j++) sumfitness+=nowpop[j].fitness; individual *guodu; guodu=new individual[zhongqunshu1]; for(j=0;j<zhongqunshu;j++) guodu[j]=nowpop[j]; qsort(guodu,zhongqunshu1,sizeof(individual),&cmpfitness); maxfitness=guodu[zhongqunshu1-1].fitness; avefitness=sumfitness/zhongqunshu1; delete [] guodu; } void generation() { individual fuqin1,fuqin2,*pipeiguodu,*pipeichi; int *peiduishuzu;//用来存放产生的随机配对 pipeiguodu=new individual[zhongqunshu1]; pipeichi=new individual[zhongqunshu1]; peiduishuzu=new int[zhongqunshu1]; int member1,member2,j=0,fuzhijishu=0,i=0,temp=0,tt=0; float zhizhen; //随机遍历的实现 for(zhizhen=suijibianli();zhizhen<1;(zhizhen=zhizhen+zhizhenjuli))//设定指针1/66 { pipeichi[fuzhijishu]=nowpop[fuzhi(zhizhen)]; fuzhijishu++; } //交叉与变异的实现 //交叉 for(i=0;i<zhongqunshu1;i++) { peiduishuzu[i]=-1; } for (i=0; i<zhongqunshu1; i++) { temp =rnd(0,zhongqunshu1-1); //产生值在0-zhongqunshu1-1的随机数 while(Exist(temp, i, peiduishuzu))//判断产生的随机数是否已经产生过，如果是，则再产生一个随机数 { temp =rnd(0,zhongqunshu1-1); } //如果没有的话，则把产生的随机数放在peiduishuzu中 *(peiduishuzu+i) = temp; } for(i=0;i<zhongqunshu1-1;i=i+2) { fuqin1=pipeichi[peiduishuzu[i]]; fuqin2=pipeichi[peiduishuzu[i+1]]; crossover(fuqin1,fuqin2,newpop[i],newpop[i+1]); } for(j=0;j<zhongqunshu1;j++) { //if(newpop[j].geti<-1000) //c