本篇文章根据教材《人工智能技术导论》（第三版 廉师友）习题编写
遗传算法注重随机性和概率性
在模拟选择，复制，交叉，变异过程中务必凸显随机
#include<iostream>#include<ctime>#include<cstring>using namespace std;/**遗传算法求解y=x^2在[0,31]区间上的最大值*/int max(int a,int b,int c,int d){if(a>b)swap(a,b);if(b>c)swap(b,c);if(c>d)swap(c,d);return d;}int min(int a,int b,int c,int d){if(a<b)swap(a,b);if(b<c)swap(b,c);if(c<d)swap(c,d);return d;}void init(int &s1,int &s2,int &s3,int &s4){//生成初始染色体srand(time(NULL));s1=rand()%31;s2=rand()%31;s3=rand()%31;s4=rand()%31;while(s2==s1)s2=rand()%31;while(s3==s1||s3==s2)s3=rand()%31;while(s4==s1||s4==s2||s4==s3)s4=rand()%31;}void show(int x){int a[6];memset(a,0,sizeof a);for(int i=4;x;i--){a[i]=x%2;x>>=1;}for(int i=0;i<5;i++)printf("%d",a[i]);}void do_cross(int &x,int &y){//为了贯彻遗传算法的随机精髓，把x，y的位项打乱重造！！！int bit[5];for(int i=0;i<5;i++){bit[i]=(x&(1<<i))+(y&(1<<i));}x=y=0;for(int i=0;i<5;i++){if(bit[i]==0)continue;if(bit[i]==2){x^=(1<<i);y^=(1<<i);}else{//随机选择变种int choice=rand()%2;if(choice==0)x^=(1<<i);else y^=(1<<i);}}}void cross(int &s1,int &s2,int &s3,int &s4){//交叉模式是两两交叉，尽可能选择不同的两个数交叉if(s1!=s2){do_cross(s1,s2);do_cross(s3,s4);}else if(s1!=s3){do_cross(s1,s3);do_cross(s2,s4);}else if(s1!=s4){do_cross(s1,s4);do_cross(s2,s3);}//注意下面这些else if并不是多余的！！！！！！else if(s2!=s3){do_cross(s2,s3);do_cross(s1,s4);}else if(s2!=s4){do_cross(s2,s4);do_cross(s1,s3);}else if(s3!=s4){do_cross(s3,s4);do_cross(s1,s2);}}void do_variation(int &x,int type){if(!x)return;int xx=x;int index[2][6]={0};int cnt[2]={0};for(int i=0;x;i++,x>>=1)index[x%2][cnt[x%2]++]=i;if(cnt[!type]==0)type=1-type;int choice=rand()%cnt[!type];x=xx^(1<<index[!type][choice]);}void variation(int &s1,int &s2,int &s3,int &s4){int choice=rand()%4;int type=rand()%2;//删除基因还是增添基因switch(choice){case 0:do_variation(s1,type);break;case 1:do_variation(s2,type);break;case 2:do_variation(s3,type);break;case 3:do_variation(s4,type);break;}}int f(int x){return x*x;}void copy(int &s1,int &s2,int &s3,int &s4,int cnt1,int cnt2,int cnt3,int cnt4){if(min(cnt1,cnt2,cnt3,cnt4)!=0)return;if(max(cnt1,cnt2,cnt3,cnt4)!=2){int max_specil=max(s1,s2,s3,s4);if(cnt1==0)s1=max_specil;if(cnt2==0)s2=max_specil;if(cnt3==0)s3=max_specil;if(cnt4==0)s4=max_specil;}else{int _[2],tot=0;if(cnt1==2)_[tot++]=s1;if(cnt2==2)_[tot++]=s2;if(cnt3==2)_[tot++]=s3;if(cnt4==2)_[tot++]=s4;if(cnt1==0)s1=_[rand()%2];if(cnt2==0)s2=_[rand()%2];if(cnt3==0)s3=_[rand()%2];if(cnt4==0)s4=_[rand()%2];}}int main(){int s1,s2,s3,s4;init(s1,s2,s3,s4);int cas=1;while(true){int suff_1=f(s1),suff_2=f(s2),suff_3=f(s3),suff_4=f(s4);//适应度int suff_sum=suff_1+suff_2+suff_3+suff_4;//这是选择概率float prob_1=(float)suff_1/suff_sum;float prob_2=(float)suff_2/suff_sum;float prob_3=(float)suff_3/suff_sum;float prob_4=1.0-prob_1-prob_2-prob_3;//这是累积概率float sum_prob_1=prob_1;float sum_prob_2=sum_prob_1+prob_2;float sum_prob_3=sum_prob_2+prob_3;float sum_prob_4=1.0;//printf("\n\n这是第%d代的信息:\n",cas++);//下面是赌轮选择float r[5];r[1]=rand()/(float)(RAND_MAX);r[2]=rand()/(float)(RAND_MAX);r[3]=rand()/(float)(RAND_MAX);r[4]=rand()/(float)(RAND_MAX);//计算被选中次数int cnt_1=0,cnt_2=0,cnt_3=0,cnt_4=0;for(int i=1;i<=4;i++){if(r[i]>sum_prob_3)cnt_4++;else if(r[i]>sum_prob_2)cnt_3++;else if(r[i]>sum_prob_1)cnt_2++;else cnt_1++;}/*printf("\n染色体\t");printf("\t适应度\t");printf("选择概率\t");printf("积累概率\t");printf("选择次数\t\n");printf("s1=");show(s1);printf("\t%d",f(s1));printf("\t%.2f",prob_1);printf("\t\t%.2f",sum_prob_1);printf("\t\t%d\n",cnt_1);printf("s2=");show(s2);printf("\t%d",f(s2));printf("\t%.2f",prob_2);printf("\t\t%.2f",sum_prob_2);printf("\t\t%d\n",cnt_2);printf("s3=");show(s3);printf("\t%d",f(s3));printf("\t%.2f",prob_3);printf("\t\t%.2f",sum_prob_3);printf("\t\t%d\n",cnt_3);printf("s4=");show(s4);printf("\t%d",f(s4));printf("\t%.2f",prob_4);printf("\t\t%.2f",sum_prob_4);printf("\t\t%d\n",cnt_4);printf("r1=%f\tr2=%f\tr3=%f\tr4=%f\n",r[1],r[2],r[3],r[4]);*///选择过程结束if(max(s1,s2,s3,s4)==31)break;//种群已进化至最优//下面是复制过程copy(s1,s2,s3,s4,cnt_1,cnt_2,cnt_3,cnt_4);//下面是交叉过程cross(s1,s2,s3,s4);//变异过程百分之一的变异率int ran_1=rand()%100,ran_2=rand()%100;if(ran_1==ran_2)variation(s1,s2,s3,s4);cas++;}printf("一共经历了%d代",cas);printf("最终的种群是:\n");int suff_1=f(s1),suff_2=f(s2),suff_3=f(s3),suff_4=f(s4);//适应度int suff_sum=suff_1+suff_2+suff_3+suff_4;//这是选择概率float prob_1=(float)suff_1/suff_sum;float prob_2=(float)suff_2/suff_sum;float prob_3=(float)suff_3/suff_sum;float prob_4=1.0-prob_1-prob_2-prob_3;//这是累积概率float sum_prob_1=prob_1;float sum_prob_2=sum_prob_1+prob_2;float sum_prob_3=sum_prob_2+prob_3;float sum_prob_4=1.0;printf("\n\n这是第%d代的信息:\n",cas);//下面是赌轮选择float r[5];r[1]=rand()/(float)(RAND_MAX);r[2]=rand()/(float)(RAND_MAX);r[3]=rand()/(float)(RAND_MAX);r[4]=rand()/(float)(RAND_MAX);//计算被选中次数int cnt_1=0,cnt_2=0,cnt_3=0,cnt_4=0;for(int i=1;i<=4;i++){if(r[i]>sum_prob_3)cnt_4++;else if(r[i]>sum_prob_2)cnt_3++;else if(r[i]>sum_prob_1)cnt_2++;else cnt_1++;}printf("\n染色体\t");printf("\t适应度\t");printf("选择概率\t");printf("积累概率\t");printf("选择次数\t\n");printf("s1=");show(s1);printf("\t%d",f(s1));printf("\t%.2f",prob_1);printf("\t\t%.2f",sum_prob_1);printf("\t\t%d\n",cnt_1);printf("s2=");show(s2);printf("\t%d",f(s2));printf("\t%.2f",prob_2);printf("\t\t%.2f",sum_prob_2);printf("\t\t%d\n",cnt_2);printf("s3=");show(s3);printf("\t%d",f(s3));printf("\t%.2f",prob_3);printf("\t\t%.2f",sum_prob_3);printf("\t\t%d\n",cnt_3);printf("s4=");show(s4);printf("\t%d",f(s4));printf("\t%.2f",prob_4);printf("\t\t%.2f",sum_prob_4);printf("\t\t%d\n",cnt_4);printf("r1=%f\tr2=%f\tr3=%f\tr4=%f\n",r[1],r[2],r[3],r[4]);//coder 辽宁大学 何勇return 0;}
