pga1.cpp

用c++和MPI写的并行遗传算法

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
template <class T> void  Make2DArray(T *** x, int rows, int cols)
{
        T **xx=new T*[rows];
        for(int i=0; i < rows; i++)
             xx[i]=new T[cols];
        *x=xx;
}
                                           
void main()
{
	float recom=0.5;
	float mutate=0.01;
	int i,j,k,a,b,c,z;//计数器
	int n=10000;//初始pool size
	//float recom, mutate;//初始化杂交率，变异率
	int reco[40];//杂交缓存
    int ** seq;
	int ** select;
	float fit[10000];//每个序列的适配值
	float sigmafit;//适配值之和
	float selecton;//轮盘赌上的小球，选择子
	int sat;//满足全部条件的解的个数
	z=0;
	//设置初始pool个体数目//
	/*
	cout<<"Input the size of initial pool: ";
	cin>>n0;
	cout<<"Input the recombination rate: ";
	cin>>recom;
	cout<<"Input the mutation rate: ";
	cin>>mutate;
	*/

	//设置所有初始解//
	Make2DArray(&seq,n,40);
	Make2DArray(&select,n,40);
	srand((unsigned)time(NULL));
	for(i=0; i<n; i++)
	{
		for(j=0;j<40;j++)
		{
			seq[i][j]=rand()%2;
		
		}
	}
	/******************************************开始计算*************************************************/
loop:
	//step1.计算所有解的适配值//
	for(i=0;i<n;i++)
	{
		k=(1-(1-seq[i][0])*(1-seq[i][1])*(1-seq[i][2]))+(1-seq[i][0]*seq[i][1]*(1-seq[i][2]))+(1-(1-seq[i][0])*seq[i][1]*(1-seq[i][2]))+(1-seq[i][0]*(1-seq[i][1])*(1-seq[i][2]))+(1-(1-seq[i][0])*(1-seq[i][1])*seq[i][2])+(1-(1-seq[i][0])*seq[i][1]*seq[i][2])+(1-seq[i][0]*(1-seq[i][1])*seq[i][2]);
			for(j=3;j<40;j++)
			{
				k=k+(1-seq[i][j-2]*seq[i][j-1]*(1-seq[i][j]));
			}
			fit[i]=k;
			
	}
	//
	//计算归一化适配值,并令每个适配值叠加前一项
	
	sigmafit=0;
	for(i=0;i<n;i++)
	{
		sigmafit+=fit[i];
	}

	fit[0]=fit[0]/sigmafit;

	for(i=1;i<n;i++)
	{
		fit[i]=fit[i]/sigmafit+fit[i-1];
	}

	//根据适配值的大小进行选择，被选择的概率和适配值大小成正比
	for(k=0;k<n;k++)
	{
		selecton=rand()/32767;
		for(i=0;i<n;i++)
		{
			if(selecton<=fit[i])
			{
				for(j=0;j<40;j++)
				{
					select[k][j]=seq[i][j];
				}
			}
		}
		
	}
	//将选择产物进行判断，若满足全部条件的解超过1000条，则停止计算，否则杂交变异
	sat=0;
    for(i=0;i<n;i++)
	{
		k=(1-(1-seq[i][0])*(1-seq[i][1])*(1-seq[i][2]))+(1-seq[i][0]*seq[i][1]*(1-seq[i][2]))+(1-(1-seq[i][0])*seq[i][1]*(1-seq[i][2]))+(1-seq[i][0]*(1-seq[i][1])*(1-seq[i][2]))+(1-(1-seq[i][0])*(1-seq[i][1])*seq[i][2])+(1-(1-seq[i][0])*seq[i][1]*seq[i][2])+(1-seq[i][0]*(1-seq[i][1])*seq[i][2]);
		for(j=3;j<40;j++)
			{
				k=k+(1-seq[i][j-2]*seq[i][j-1]*(1-seq[i][j]));
			}
			fit[i]=k;
			if(fit[i]==46)
			{
				sat++;
			
			}
	}
	if(sat<1000)//判断是否有足够的满足所有条件的解：没有，进行杂交变异
	{
		z++;
		cout<<sat<<endl;
		for(k=0;k<recom*n;k++)
		{
			a=n*rand()/32767;
			b=n*rand()/32767;
			c=40*rand()/32768;
			for(j=c;j<40;j++)
			{
				reco[j]=select[b][j];
				select[b][j]=select[a][j];
				select[a][j]=reco[j];
			}
		}//杂交完成
		
		for(k=0;k<mutate*n;k++)
		{
			a=rand()/32767*n;
			b=rand()/40;
			select[a][b]=1-select[a][b];
		}//变异完成

		goto loop;
	}
	
        for(i=0;i<n;i++)
		{
                delete[] seq[i];
                delete[] select[i];
		}
				delete[] seq;       
                delete[] select;
	cout<<" The problem was done in "<<z<<" cycles.";
	cout<<sat;
}