////////////////////////文件说明//////////////////////////
// //
//文件名: GA_Basic.c //
//功能: 基本遗传算法 //
//作者: 朱寅 //
//功能: 求函数f(x)=x*x的最大值,x范围:[0,31] //
//////////////////////////////////////////////////////////
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include "zyGABasic.h"
randM rndM = { 11, 0 }; //伪随机数初始化
prandM prndM=&rndM;
int main( )
{
questSolved qstSolved;
pquestSolved pqst=&qstSolved;
grpGA grp;
pgrpGA pgrp=&grp;
indivGA ind[SIZEGROUP];
pindivGA pind[SIZEGROUP];
int codeNum;//个体编码位数
int icount;
int flag=0;
grp.fitnessMeanPrior=0;//上一代种群的平均适应度
grp.generationCount = 0;//现今种群的代数
grp.generationMax = 150;//终止代数,一般50~1000
grp.perfectCount = 0;//平均适应度的差异小于一个指定阈值的连续代数的计数,先初始化
grp.perfectCountReq = 5;//当grp.perfectCount大于或等于该值时,进化计算结束
grp.perfThreshold = 0.5;//当平均适应度的差异小于该阈值时,则计数
grp.probCross = 0.1;//probability crossover 交叉概率,一般0.4~0.99
grp.probMutat = 0.001;//变异概率,一般0.0001~0.1
grp.size = 50;//个体数,一般取20~100
qstSolved.precision = 0.1;//计算求解精度
qstSolved.uMax = 31;//求解范围的上限
qstSolved.uMin = -1;//求解范围的下限
for( icount=0; icount<SIZEGROUP; icount++ )
{
pind[icount]=&ind[icount];
}
codeNum = GroupInit(pind, pqst);
do
{
FitnessCmp(pind);
flag=Termination(pind, pgrp);
if( flag )
{
break;
}
Selection(pind, pgrp);
Crossover(pind, codeNum, pgrp, pqst);
Mutation(pind, codeNum, pgrp, pqst);
} while( 1 );
ResultOutput(pind, pqst);
printf("generationCount:%d\n", pgrp->generationCount);
getch();
return 0;
}
//群体初始化,个体编码,返回值为个体编码位数
int GroupInit(pindivGA pind[], pquestSolved pqst)
{
int icount;
int codeNum;
double temp;
typelong gain;
for( icount=0; icount<SIZEGROUP; icount++ )
{
RandG(prndM);
temp = prndM->eRand;
pind[icount]->valueD = temp* ( pqst->uMax - pqst->uMin ) + pqst->uMin;
temp=(pind[icount]->valueD - pqst->uMin) / pqst->precision;
pind[icount]->valueB = DecimalToBinary( (typelong)temp );
}
gain=(typelong)( ( pqst->uMax - pqst->uMin ) / pqst->precision );
//floor(x)返回的是小于或等于x的最大整数,ceil(x)返回的是大于x的最小整数
codeNum = (int)(ceil( log(gain +1) / log(2) ));
pqst->uMaxB = DecimalToBinary( gain);
return codeNum;
}
//计算每个个体的适应度
int FitnessCmp(pindivGA pind[])
{
double sum;
double temp;
int icount;
for( icount=0; icount<SIZEGROUP; icount++ )
{
pind[icount]->fitness = FitCmpFun(SolvedFun(pind[icount]->valueD));
}
sum=0;
for( icount=0; icount<SIZEGROUP; icount++ )
{
sum += pind[icount]->fitness;
}
temp=0;
for( icount=0; icount<SIZEGROUP; icount++ )
{
pind[icount]->probSelect = pind[icount]->fitness / sum;
temp += pind[icount]->probSelect;
pind[icount]->probAcc = temp;
}
return 0;
}
//根据个体适应度进行选择,产生下一代个体
int Selection(pindivGA pind[], pgrpGA pgrp)
{
int icount;
int jcount;
double temp;
int a[SIZEGROUP];
indivGA indTemp[SIZEGROUP];
pindivGA pindTemp[SIZEGROUP];
for( icount=0; icount<SIZEGROUP; icount++ )
{
pindTemp[icount]=&indTemp[icount];
}
for( icount=0; icount<SIZEGROUP; icount++ )
{
RandG(prndM);
temp = prndM->eRand;
for( jcount=0; jcount< SIZEGROUP; jcount++ )
{
if( temp<pind[jcount]->probAcc )
{
a[icount]=jcount;
break;
}
}
}
for( icount=0; icount<SIZEGROUP; icount++ )
{
IndivCopy(pind[ a[icount] ], pindTemp[icount] );
}
for( icount=0; icount<SIZEGROUP; icount++ )
{
IndivCopy( pindTemp[icount], pind[icount] );
}
pgrp->generationCount++;
return 0;
}
//交叉操作
int Crossover(pindivGA pind[], int codeNum, pgrpGA pgrp, pquestSolved pqst)
{
int icount;
int tSize;
int tBlockPrior;
int tBlockNext;
typelong gain;
int n;
//随机打乱样本顺序
for( icount=SIZEGROUP-1; icount>0; icount-- )//SizeGroup-1
{
RandG(prndM);
n=(int)(prndM->eRand *(icount-1));
IndivSwap(pind, icount, n);
}
//两两配对
tSize=SIZEGROUP/2;
for( icount=0; icount<tSize; icount++ )
{
//首先确定是否需要交叉
RandG( prndM );
if( prndM->eRand < pgrp->probCross )//交叉概率
{
//单点交叉,交叉点左边的数据交换
RandG( prndM );
n=(int)( (codeNum-1)*prndM->eRand + 1 );
gain=(typelong)pow( 10, n );
tBlockPrior=pind[icount]->valueB / gain;
tBlockNext=pind[icount+tSize]->valueB / gain;
pind[icount]->valueB=pind[icount]->valueB % gain + tBlockNext * gain;
pind[icount+tSize]->valueB
= pind[icount+tSize]->valueB % gain+ tBlockPrior * gain;
if( pind[icount]->valueB > pqst->uMaxB )
{
pind[icount]->valueB = pqst->uMaxB;
}
if( pind[icount+tSize]->valueB > pqst->uMaxB )
{
pind[icount+tSize]->valueB = pqst->uMaxB;
}
}
}
pgrp->generationCount++;
return 0;
}
//变异操作
int Mutation(pindivGA pind[], double codeNum, pgrpGA pgrp, pquestSolved pqst)
{
int icount;
int n;
int dataBit;
typelong temp1, temp2;
for( icount=0; icount<SIZEGROUP; icount++ )
{
//首先确定是否需要变异
RandG( prndM );
if( prndM->eRand < pgrp->probMutat )//变异概率
{
//随机选取要变异的串位
RandG( prndM );
n=(int)( (codeNum-1)*prndM->eRand ) + 1;
temp1=(typelong)(pow(10, n));
temp2=(typelong)(pow(10, n-1));
dataBit=pind[icount]->valueB % temp1 / temp2;//获取某一位的值
if(dataBit==0)
{
pind[icount]->valueB=pind[icount]->valueB + dataBit* temp2;
if( pind[icount]->valueB > pqst->uMaxB )
{
pind[icount]->valueB = pqst->uMaxB;
}
}
else
{
pind[icount]->valueB=pind[icount]->valueB - dataBit* temp2;
}
}
for( icount=0; icount<SIZEGROUP; icount++ )
{
pind[icount]->valueD
= BinaryToDecimal( pind[icount]->valueB )*pqst->precision
+ pqst->uMin;
}
}
return 0;
}
//判断是否停止进化计算,若是则返回1
int Termination(pindivGA pind[], pgrpGA pgrp)
{
int icount;
double sum=0;
double temp;
for( icount=0; icount<SIZEGROUP; icount++ )
{
sum += pind[icount]->fitness;
}
pgrp->fitnessMean = sum/SIZEGROUP;
temp=fabs(pgrp->fitnessMean - pgrp->fitnessMeanPrior );
if( temp < pgrp->perfThreshold )
{
pgrp->perfectCount++;
}
else
{
pgrp->perfectCount=0;
}
if( ( pgrp->generationCount < pgrp->generationMax)
&& ( pgrp->perfectCount < pgrp->perfectCountReq ) )
{
return 0;
}
else
{
printf("generationCount:%d\n", pgrp->generationCount);
printf("perfectCount:%d\n", pgrp->perfectCount);
return 1;
}
}
//十进制转二进制
typelong DecimalToBinary(typelong valueDec)
{
typelong valueB=0;
int a[32];
int icount=0;
int temp;
int n=1;
do
{
a[icount]=valueDec % 2;
valueDec=valueDec/2;
icount++;
} while( valueDec != 0 );
temp=icount;
for(icount=0; icount<temp; icount++ )
{
valueB += n*a[icount];
n = n*10;
}
return valueB;
}
//二进制转十进制
typelong BinaryToDecimal(typelong valueB)
{
typelong valueDec=0;//typelong, 0~4294967295 即0~(2^32-1)
int icount=0;
int k=1;
int n;
do
{
n=valueB % 10;
valueDec += n * k;
valueB=valueB/10;
k=k*2;
icount++;
} while( valueB != 0 );
return valueDec;
}
//产生(0-1)均匀分布的随机数,用于网络权重的初始化
int RandG( prandM prndM )
{
typelong M;
int A;
M = 32768;
// M=(typelong)(pow(2,25));
A = 179;
prndM->randSeed = ( A*prndM->randSeed )%M;
prndM->eRand = ( double )prndM->randSeed/M;
return 0;
}
//被求解问题的函数表示
double SolvedFun(double x)
{
double temp;
// temp=sin(x*x)+cos(x);
temp=x*x;
return temp;
}
//适应度函数,度量个体适应度
double
- 1
- 2
前往页