基本遗传算法C程序基本遗传算法实现求函数极值

////////////////////////文件说明////////////////////////// // // //文件名: 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