/**利用遗传算法寻找y=x6-10x5+344x3+193x2-1846x-1680在(-8,+8)达到最小值的x*/
/**************一些结构体的定义********************/
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#define QS 30//定义群的规模
#define MAXloop 1200//定义最大进化代数
#define error 0.01//定义两次最优值之差小于0.01则认为结果没有改变
#define pc 0.7//定义随机的两个体的随机交叉概率为0.7
#define pm 0.04//定义随机个体变异概率为0.04
struct chromosome//定义染色体的结构
{
int geninfo;//染色体的结构,用一整型数的后14位作为染色体的编码
double suitability;//此染色体对应的适应度
};
struct chromosome chromosome_group[QS];//定义含有40个染色体的种群
struct chromosome chromosome_newgrp[QS];//定义含有40个染色体的种群,记录交叉产生子代的染色体
struct chromosome chromosome_result;//记录上一轮循环中得到的最优染色体
int result_unchange_time;//当相邻两轮得到的最优值对应的适应度之差小于error时,其值增1,否则清0
struct log//形成链表,记录每次循环所产生的最优的适应度
{
double suitability;
struct log *next;
}llog,*head,*end;
int log_num;//记录链表长度;
/****************函数声明部分*******************/
void initiate();/*随机生成初始种群*/
void evaluation(int flag);/*评估种群中各染色体的适应度,并据此进行排序*/
void cross();/*交叉函数*/
void selection();/*选择函数*/
int record();/*记录每次循环所产生的最优解并判断循环是否终止*/
void mutation();/*变异函数*/
void showresult();/*显示结果*/
int randsign(float p);/*按概率p产生随机数0,1,值是1的概率为p*/
int randbit(int i,int j);/*随机生成1个在i,j之间的整数*/
int randnum();/*随机产生一个由14个基因组成的染色体*/
int creatmask(int a);/*用于交叉操作*/
int convertionD2B(double x);/*对现实空间的可能解x进行二进制编码*/
double convertionB2D(int x);/*将二进制编码进行译码*/
/********************主函数部分***************************/
void main()
{
int i,flag;
flag=0;
initiate();//产生初始化种群
evaluation(0);//对初始化种群进行评估、排序
for(i=0;i<MAXloop;i++)
{//进入进化循环、当循环次数超过MAXloop所规定的值时循环终止,flag保持为0值
cross();//进行交叉操作
evaluation(1);//进行子种群的评估和排序
selection();//从父代、子代中选择最优的30个染色体作为新的父种群
if(record()==1)//如果满足终止规则时将flag置1,停止循环
{
flag=1;
break;
}
mutation();//进行变异操作
}
showresult();//显示寻优结果
}
/**************************产生初始化种群********************************/
void initiate()
{
int i,stime;
long ltime;
ltime=time(NULL);
stime=(unsigned)ltime/2;
srand(stime);
for(i=0;i<QS;i++)
chromosome_group[i].geninfo=randnum();//调用randnum()建立初始种群
chromosome_result.suitability=1000;
result_unchange_time=0;
head=end=(struct log*)malloc(sizeof(llog));//初始化记录最优的适应度的链表
if(head==NULL)
{
printf("\n内存错误\n");
exit(0);
}
end->next=NULL;
log_num=1;
}
/************************对父群、子群的评估和排序**************************/
void evaluation(int flag)
{
int i,j;
struct chromosome *genp;
int gentinfo;//定义中间变量gentinfo,gentsuitability
double gentsuitability;
double x;
if(flag==0)
genp=chromosome_group;
else
genp=chromosome_newgrp;
for(i=0;i<QS;i++);
{
x=convertionB2D(genp[i].geninfo);
genp[i].suitability=x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680;
}
for(i=0;i<QS-1;i++)//按有由小到大的适应度排序
{
for(j=i+1;j<QS;j++)
{
if(genp[i].suitability>genp[j].suitability)
{
gentinfo=genp[i].geninfo;
genp[i].geninfo=genp[j].geninfo;
genp[j].geninfo=gentinfo;
gentsuitability=genp[i].suitability;
genp[i].suitability=genp[j].suitability;
genp[j].suitability=gentsuitability;
}
}
}
}
/*****************************进行随机配对、双亲双子法交叉操作*******************************/
void cross()
{
int i,j,k;
int mask1,mask2;
int a[QS];
for(i=0;i<QS;i++) a[i]=0;
k=0;
for(i=0;i<QS;i++)
{
if(a[i]==0)
{
for(;;)
{
j=randbit(i+1,QS-1);//随机生成(i+1)~(QS-1)中的任意1位
if(a[j]==0) break;
}
if(randsign(pc)==1)
{
mask1=creatmask(randbit(0,14));
mask2=~mask1;
chromosome_newgrp[k].geninfo=(chromosome_group[i].geninfo)&mask1+(chromosome_group[j].geninfo)&mask2;
Chromosome_newgrp[k+1].geninfo=(chromosome_group[i].geninfo)&mask2+(chromosome_group[j].geninfo)&mask1;
k=k+2;
}
else
{
chromosome_newgrp[k]=chromosome_group[i];
chromosome_newgrp[k+1]=chromosome_group[j];
k=k+2;
}
a[i]=a[j]=1;
}
}
}
/***************************类似2分法的选择算法*******************************/
void selection()
{
int i,j,k;
j=0;
i=QS/2-1;
if(chromosome_group[i].suitability<chromosome_newgrp[i].suitability)
{
for(j=1;j<QS/2;j++)
{
if(chromosome_group[i+j].suitability>chromosome_newgrp[i-j].suitability)
break;
}
}
else
if(chromosome_group[i].suitability>chromosome_newgrp[i].suitability)
for(j=-1;j>-QS/2;j--)
{
if(chromosome_group[i+j].suitability<=chromosome_newgrp[i-j].suitability);
break;
}
for(k=j;k<QS/2+1;k++)
{
chromosome_group[i+k].geninfo=chromosome_newgrp[i-k].geninfo;
chromosome_group[i+k].suitability=chromosome_newgrp[i-k].suitability;
}
}
/******************************记录各轮循环的最优值*********************************/
int record()
{
double x;
struct log *r;
r=(struct log*)malloc(sizeof(llog));
if(r==NULL)
{
printf("\n内存错误\n");
exit(0);
}
r->next=NULL;
end->suitability=chromosome_group[0].suitability;
end->next=r;
end=r;
log_num++;
//判断是否满足循环停止条件
x=chromosome_result.suitability-chromosome_group[0].suitability;
if(x<0) x=-x;
if(x<error)
{
result_unchange_time++;
if(result_unchange_time>=20)
return 1;
}
else
{
chromosome_result.geninfo=chromosome_group[0].geninfo;
chromosome_result.suitability=chromosome_group[0].suitability;
result_unchange_time=0;
}
return 0;
}
/****************************个体的变异操作********************************/
void mutation()
{
int i,j,m;
int gentinfo;
double gentsuitability;
double x;
double hpm,ps;//以概率为spm发生变异,ps为该个体的生存概率
ps=pow(1-pm,11);
hpm=1-ps;
for(i=0;i<QS;i++)
{
if(randsign(hpm)==1)
{
j=randbit(0,14);
m=1<<j;
Chromosome_group[i].geninfo=Chromosome_group[i].geninfo^m;
x=convertionB2D(Chromosome_group[i].geninfo);
x=x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680;
Chromosome_group[i].suitability=x;
}
}
for(i=0;i<QS-1;i++)
{
for(j=i+1;j<QS;i++)
{
if(Chromosome_group[i].suitability>Chromosome_group[j].suitability)
{
gentinfo=Chromosome_group[i].geninfo;
Chromosome_group[i].geninfo=Chromosome_group[j].geninfo;
Chromosome_group[j].geninfo=gentinfo;
gentsuitability=Chromosome_group[i].suitability;
Chromosome_group[i].suitability=Chromosome_group[j].suitability;
Chromosome_group[j].suitability=gentsuitability;
}
}
}
}
/************************显示搜索结果并释放内存****************************/
void showresult()
{
int i,flag;
struct Chromosome *logprint;
logprint=Chromosome_group;
// FILE *flog;
if(flag==0)
printf("已达到最大搜索次数,搜索失败!");
else
{
printf("当取%f时,表达式达到最小值为%f\n",convertionB2D(Chromosome_result.geninfo),Chromosome_result.suitability);
// printf("收敛过程记录于文件log.txt\n");
// if((flog=fopen("log.txt","w+"))==NULL)
// {
// printf("cann't open the file!");
// exit(1);
// }
for(i=0;i<log_num;i=i+5)
{
printf("%20f",logprint[i].suitability);
}
// printf(flog,"\n\n");
}
}
/**************************建立初始种群函数********************************/
int randnum()
{
int x;
x=rand()/2;
return x;
}
/*****************************产生i,j之间的任意随机数*********************/
int randbit(int i,int j)
{
int a,k;
k=j-i+1;
a=i+rand()*k/32768;
return a;
}
/***************************