遗传算法并行源程序.docx
《遗传算法并行源程序.docx》由会员分享，可在线阅读，更多相关《遗传算法并行源程序.docx（18页珍藏版）》请在冰点文库上搜索。
遗传算法并行源程序
//THBGFSHFGBCVXNCH
#defineWIN32_LEAN_AND_MEAN//从Windows头中排除极少使用的资料
#include
#include
#include
#include
#include
#include
#include
#include
#pragmacomment（lib,"Wininet.lib"）
#pragmacomment（lib,"mpi.lib"）
#pragmacomment（lib,"cxx.lib"）
#definePOPSIZE6/*群体大小，其实就是基因总数*/
#defineMAXGENS10/*进化代数*/
#defineNVARS3/*问题变量数，即基因的长度*/
#definePXOVER0.8/*交叉概率*/
#definePMUTATION0.15/*变异概率*/
#defineTRUE1
#defineFALSE0
intgeneration;/*记录当前已经进化的代数*/
intcur_best;/*最优个体*/
FILE*galog;/*日志文件*/
structgenotype/*基因类型*/
{
doublegene[NVARS];/*染色体字符串*/
doubleupper[NVARS];/*每个基于的上界*/
doublelower[NVARS];/*每个基因的下界*/
doublefitness;/*个体适应度*/
doublerfitness;/*相对适应度*/
doublecfitness;/*累积适应度*/
};
structgenotypepopulation[POPSIZE+1];/*种群*/
structgenotypenewpopulation[POPSIZE+1];/*新种群*/
voidinitialize（void）;/*种群初始化函数*/
doublerandval（double,double）;/*随机函数*/
voidkeep_the_best（void）;/*寻找最优个体*/
voidelitist（void）;/*保持最优*/
voidselect（void）;/*选择算子*/
voidcrossover（void）;/*交叉算子*/
voidXover（int,int）;/*交叉操作*/
voidswap（double*,double*）;/*交换*/
voidevaluate（void）;/*个体适应度评价*/
voidworker（genotype*,int）/*从处理器操作,突变和适应度评价*/
voidreport（void）;/*记录*/
/**************************************************************
初始化基因值，适应值。
从gadata.txt中读入每
个变量的上下限，然后随机产生。
**************************************************************/
voidinitialize（void）
{
FILE*infile;
inti,j;
doublelbound,ubound;
if（（infile=fopen（"gadata.txt","r"））==NULL）
{
fprintf（galog,"\nCannotopeninputfile!
\n"）;
exit
（1）;
}
for（i=0;i{
fscanf（infile,"%lf",&lbound）;
fscanf（infile,"%lf",&ubound）;
for（j=0;j{
population[j].fitness=0;
population[j].rfitness=0;
population[j].cfitness=0;
population[j].lower[i]=lbound;
population[j].upper[i]=ubound;
population[j].gene[i]=randval（population[j].lower[i],
population[j].upper[i]）;
}
}
fclose（infile）;
}
/***********************************************************/
/*在上下界间产生一个数*/
/***********************************************************/
doublerandval（doublelow,doublehigh）
{
doubleval;
val=（（double）（rand（）%1000）/1000.0）*（high-low）+low;
return（val）;
}
/***************************************************************/
/*Keep_the_bestfunction:
保持对最优个体的追踪*/
/***************************************************************/
voidkeep_the_best（）//将最优的值放在最后一个空位上
{
intmem;
inti;
cur_best=0;/*最优个体索引*/
for（mem=0;mem{
if（population[mem].fitness>population[POPSIZE].fitness）
{
cur_best=mem;
population[POPSIZE].fitness=population[mem].fitness;
}
}
/*oncethebestmemberinthepopulationisfound,copythegenes*/
for（i=0;ipopulation[POPSIZE].gene[i]=population[cur_best].gene[i];
}
/****************************************************************/
/*Elitistfunction:
如果这一代的最好值比上一代的*/
/*差，那么用上一代的最好值替代本代的最差值*/
/****************************************************************/
voidelitist（）
{
inti;
doublebest,worst;/*bestandworstfitnessvalues*/
intbest_mem,worst_mem;/*indexesofthebestandworstmember*/
best=population[0].fitness;
worst=population[0].fitness;
for（i=0;i{
if（population[i].fitness>population[i+1].fitness）
{
if（population[i].fitness>=best）
{
best=population[i].fitness;
best_mem=i;
}
if（population[i+1].fitness<=worst）
{
worst=population[i+1].fitness;
worst_mem=i+1;
}
}
else
{
if（population[i].fitness<=worst）
{
worst=population[i].fitness;
worst_mem=i;
}
if（population[i+1].fitness>=best）
{
best=population[i+1].fitness;
best_mem=i+1;
}
}
}
/*如果新一代种群中的最优个体比前一代的最优个体好，*/
/*best取此值，反之用上一代最优个体取代当前代的最差个体。
*/
if（best>=population[POPSIZE].fitness）
{
for（i=0;ipopulation[POPSIZE].gene[i]=population[best_mem].gene[i];
population[POPSIZE].fitness=population[best_mem].fitness;
}
else
{
for（i=0;ipopulation[worst_mem].gene[i]=population[POPSIZE].gene[i];
population[worst_mem].fitness=population[POPSIZE].fitness;
}
}
/*************************************************************************/
/*Selectionfunction:
适者生存通过适应度大小筛选，适*/
/*应度越大，出现的次数越多（会有重复）*/
/*************************************************************************/
voidselect（void）//
{
intmem,i,j,k=0;
doublesum=0;
doublep;
/*计算适应度总和*/
for（mem=0;mem{
sum+=population[mem].fitness;
}
/*计算相对适应度，有点像概率密度*/
for（mem=0;mem{
population[mem].rfitness=population[mem].fitness/sum;
}
/*计算累计适应度，有点像分布函数*/
population[0].cfitness=population[0].rfitness;
for（mem=1;mem{
population[mem].cfitness=population[mem-1].cfitness+
population[mem].rfitness;
}
/*使用累计适应度确定幸存者,落在哪个概率区域就选择相应的概率区域上的染色体*/
for（i=0;i{
p=rand（）%1000/1000.0;
if（pnewpopulation[i]=population[0];//选择
else
{
for（j=0;jif（p>=population[j].cfitness&&
pnewpopulation[i]=population[j+1];//选择
}
}
/*确定全部的幸存者后，拷贝回population完成选择*/
for（i=0;ipopulation[i]=newpopulation[i];
}
/***************************************************************/
/*Crossoverselection:
单随机点交叉，前后两个*/
/*个体交叉，得到两个新的个体，原来的个体消失*/
/***************************************************************/
voidcrossover（void）
{
inti=0,mem,one;
intfirst=0;/*countofthenumberofmemberschosen*/
doublex;
for（mem=0;mem{
x=rand（）%1000/1000.0;
if（x{
++first;
if（first%2==0）
Xover（one,mem）;//相邻的两个交叉
else
one=mem;
}
}
}
/**************************************************************/
/*Crossover:
交叉操作*/
/**************************************************************/
voidXover（intone,inttwo）
{
inti;
intpoint;/*crossoverpoint*/
/*selectcrossoverpoint*/
if（NVARS>1）//等于1时就没有交叉的必要
{
if（NVARS==2）
point=1;
else
point=（rand（）%（NVARS-1））+1;
for（i=0;iswap（&population[one].gene[i],&population[two].gene[i]）;
}
}
/*************************************************************/
/*Swap:
互换*/
/*************************************************************/
voidswap（double*x,double*y）
{
doubletemp;
temp=*x;
*x=*y;
*y=temp;
}
voidevaluate（void）/*个体适应度评价函数*/
{
intmem;
inti;
doublex[NVARS+1];
for（mem=0;mem{
for（i=0;ix[i+1]=population[mem].gene[i];
population[mem].fitness=x[1]*x[1]+x[2]*x[2]+x[3]*x[3];//计算得到适应度
}
}
voidreport（void）
{
doublebest_val;/*种群中最高适应度值*/
doubleavg;/*平均适应度值*/
doublestddev;/*标准方差*/
doublesum_square;/*平方的总数*/
doublesquare_sum;/*总数的平方*/
doublesum;/*适应度值总和*/
sum=0.0;
sum_square=0.0;
for（inti=0;i{
sum+=population[i].fitness;
sum_square+=population[i].fitness*population[i].fitness;
}
avg=sum/（double）POPSIZE;
square_sum=avg*avg*POPSIZE;
stddev=sqrt（（sum_square-square_sum）/（POPSIZE-1））;
best_val=population[POPSIZE].fitness;
fprintf（galog,"%5d\t\t%6.3f\t%6.3f\t%6.3f\n",generation,best_val,avg,stddev）;
printf（"%5d\t\t%6.3f\t%6.3f\t%6.3f\n",generation,best_val,avg,stddev）;
}
voidworker（genotype*subpopulation,intmysize）/*突变和适应度评价操作*/
{
doublelbound,hbound;
doublex;
for（inti=0;i{
for（intj=0;j{
x=rand（）%1000/1000.0;
if（x{
lbound=subpopulation->lower[j];
hbound=subpopulation->upper[j];
subpopulation[i].gene[j]=randval（lbound,hbound）;
}
}
}//end变异
//适应度评价
intmem;
doublexchorm[NVARS+1];
for（mem=0;mem{
for（inti=0;ixchorm[i+1]=subpopulation[mem].gene[i];
subpopulation[mem].fitness=（xchorm[1]*xchorm[1]）+（xchorm[1]*xchorm[2]）+xchorm[3]*xchorm[3];//计算得到适应度F1
}//end适应度评价
}
/****************************************************************/
/*主函数*/
/****************************************************************/
voidmain（intargc,char*argv[]）
{
intmyid,numprocs,mysize;
inti,j;
doublestarttime,endtime;
MPI_Statusstatus;
MPI_Requestrequest;
MPI_Init（&argc,&argv）;
MPI_Comm_rank（MPI_COMM_WORLD,&myid）;
MPI_Comm_size（MPI_COMM_WORLD,&numprocs）;
if（numprocs>1）
mysize=POPSIZE/（numprocs-1）;//每个从处理器上应该分配的个体数
elseif（numprocs==1）mysize=POPSIZE;
genotype*subpopulation=（genotype*）malloc（mysize*sizeof（genotype））;
if（!
subpopulation）
{
printf（"不能获得%d个大小的空间\n",mysize）;
MPI_Abort（MPI_COMM_WORLD,1）;
}
//自定义数据类型
MPI_Datatypemystruct;
intblocklens[6];
MPI_Aintindices[6];
MPI_Datatypeold_types[6];
//各块中数据个数
blocklens[0]=NVARS;
blocklens[1]=NVARS;
blocklens[2]=NVARS;
blocklens[3]=1;
blocklens[4]=1;
blocklens[5]=1;
//数据类型
for（i=0;i<6;i++）old_types[i]=MPI_DOUBLE;
//求地址和相对偏移
MPI_Address（&population->gene,&indices[0]）;
MPI_Address（&population->upper,&indices[1]）;
MPI_Address（&population->lower,&indices[2]）;
MPI_Address（&population->fitness,&indices[3]）;
MPI_Address（&population->rfitness,&indices[4]）;
MPI_Address（&population->cfitness,&indices[5]）;
indices[5]=indices[5]-indices[0];
indices[4]=indices[4]-indices[0];
indices[3]=indices[3]-indices[0];
indices[2]=indices[2]-indices[0];
indices[1]=indices[1]-indices[0];
indices[0]=0;
MPI_Type_struct（6,blocklens,indices,old_types,&mystruct）;//生成新的mpi数据类型
MPI_Type_commit（&mystruct）;
//输出表头，初始化，初步测评，初步寻优
if（my
升级会员 