digitalmap.cpp

Digital map algorithm. it could demonstrate the function and the effectiveness of the digital map

#include <iostream.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
//#include <mrnds.c>

//#define RAND_MAX 32767
#define Np 100
#define maxGen 10000
#define Pc 0.45
#define Pm 0.5

//int n;
//int Np=100, maxGen=2000, Pc=0.75, Pm=0.2;
//int gV=10000, sV=0;
//int X[D][Np]; // Define the location of genes and the global location
//int gVI[maxGen]; // Define the value of each iteration 
void geneticMagic(int,int,int);
void selection(int,int);
//int fValue(int,int);
void crossover(int,int);
void mutation(int,int);

int s;
int X[1000][Np],Xs[1000][Np],X1[1000][50],X2[1000][50];
//int G[1000];

//Calculate the objective
int fValue(int P[],int n1)
{
	int i, j, k; 
	int c, a, b;
	int M[100][100];
	int sum1=0,sum2=0,sum3=0,sum4=0,sum,fJ=0;
	
	a=0;
	b=0;
	c=n1*(pow(n1,2)+1)/2;

	for (i=0; i<n1; i=i+1)
	{
		for (j=0; j<n1; j=j+1)
			M[j][i]=P[i+j*n1];
	}

	for (i=0; i<n1; i=i+1)
	{
        sum=0;
		for (k=0; k<n1; k=k+1)
			sum=sum+M[i][k];
		sum1=sum1+fabs(c-sum);
	}

	for (j=0; j<n1; j=j+1)
	{
        sum=0;
		for (k=0; k<n1; k=k+1)
			sum=sum+M[k][j];
		sum2=sum2+fabs(c-sum);
	}

	for (i=0; i<n1; i=i+1)
	{
		a=a+M[i][i];
		b=b+M[i][n1-i-1];
	}

	sum3=fabs(c-a);
	sum4=fabs(c-b);
	fJ=sum1+sum2+sum3+sum4;
	//cout<<fJ<<endl;
	return fJ;
}

///////////////main function////////////////////////////////////////////////////////////
void main(int n)
{
	//int n; // The dimension of magic square
	//const int Np=100, maxGen=2000, Pc=0.75, Pm=0.2; // Define the population size, maximum iteration, crossover probability, 
	                          //mutation pro and dimension of solutions 
	int D,opti;

    clock_t   tBegin,tEnd,Time;   
     tBegin=clock();   
     //do   something   

	srand(time(NULL));

	cout<<"Please input the dimension of magic square :  n "<<endl;
	cin>>n;

	D=n*n;
	opti=2*n+2;
	//cout<<D;

	geneticMagic(D,opti,n);

    tEnd=clock();   
    Time=(tEnd-tBegin)/CLOCKS_PER_SEC;   
    cout<<(double)Time<<endl;

}
////////////////////////////////////////////////////////////////////////////////////////////////////////
void geneticMagic(int D,int opti,int n)
{
	//int X[][Np];
    //int X[1000][Np],Xs[1000][Np],X1[1000][50],X2[1000][50];
    //int X[1000][Np],Xs[1000][Np],X1[1000][50],X2[1000][50];
	int X00[1000],Xi[1000],Xk[1000],G[1000];
	//int	X00[D], X11[D], G[D], Xj[D], Xk[D]; // Define the location of genes and the global location
	int gVI[maxGen]; // Define the value of each iteration
	int Mf[100][100];
	int gV=10000000, sV=0;
	int gen,i,j,m,k;

	//(X,G,gV)=initialization(n,D,X00,X,gV,G);

	int L,index,fV=0;

	for (i=1;i<1000;i=i+1)
	{
		X00[i]=0;Xi[0]=0;Xk[i]=0;G[i]=0;
	}
 
	//srand((unsigned)time(NULL));
    
    //cout<<(double)rand()/(double)RAND_MAX<<endl;

	for (i=0;i<Np; i=i+1)
		for (j=0;j<1000; j=j+1)
		{
			X[j][i]=0;
			Xs[j][i]=0;
		}

	for (i=0;i<Np/2; i=i+1)
		for (j=0;j<1000; j=j+1)
		{
			X1[j][i]=0;
			X2[j][i]=0;
		}
    
	for (i=0; i<Np; i=i+1)
	{ 
		L=D;
		for (m=0; m<L; m=m+1) X00[m]=m+1;

		for (j=0; j<D; j=j+1)
		{
			//srand(time(NULL)); 
            //cout<<(double)rand()/(double)RAND_MAX<<endl;
			//index=floor(L*(double)rand()/(double)RAND_MAX);
			index=rand()%L;
			//cout<<index<<endl;
			X[j][i]=X00[index];

			for (k=0;k<L-index;k=k+1)
				X00[k+index]=X00[k+index+1];
			L=L-1;
		}
		//cout<<X[D-1][i]<<endl;
	}

	for(i=0; i<Np; i=i+1)
	{
		for (j=0; j<D; j=j+1)
			Xi[j]=X[j][i];

		fV=fValue(Xi,n);

		if (fV<gV)
		{
			gV=fV;
			for (j=0; j<D; j=j+1)
				G[j]=X[j][i];
		}
	}
   //for (i=0; i<Np; i=i+1) 
		//for (j=0; j<D; j=j+1)
			//cout<<X[j][i]<<endl;
	//cout<<fValue(G,n)<<endl;


/////////////////////////

	for (gen=0; gen<maxGen; gen=gen+1)
	{
		
		selection(D,n);
		
		crossover(D,n); // the crossover manipulation
		mutation(D,n); // the mutation manipulation

		//X=[X1 X2];
		for (i=0;i<Np;i=i+1)
		{
			if (i<Np/2)
			{
				for (j=0;j<D;j=j+1)
					X[j][i]=X1[j][i];
			}
			else
				for (j=0;j<D;j=j+1)
					X[j][i]=X2[j][i-50];
		}
		
		//reserve the best genes
		for (i=0; i<Np; i=i+1)
		{
			for (j=0; j<D; j=j+1)
			    Xk[j]=X[j][i];
			fV=fValue(Xk,n);
			if (fV<gV)
			{
				gV=fV;
				for (j=0; j<D; j=j+1)
					G[j]=X[j][i];
			}
		}

		gVI[gen]=gV;
		
		if (fValue(G,n)==0)
			break;
	}

	for (i=0;i<D;i=i+1)
		cout<<G[i]<<endl;

	cout<<"\n"<<fValue(G,n)<<"\n"<<endl;
	cout<<gen<<"\n"<<endl;
    for (j=0; j<n; j=j+1)
	{
		for (i=0; i<n; i=i+1)
		{
			Mf[j][i]=G[i+j*n];
			cout<<Mf[j][i]<<"\ ";
		}
		cout<<"\n";
	}
		

	//cout<<Mf<<endl;
	cout<<"Your result is amazing, it is really magic!"<<endl;

	return;

}


////////////////////////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Selection manipulation
void selection(int D,int n)
{       
	    //extern X[1000][Np];
        int i,j,k2;
		int Xj[1000],X0[Np];
		double eVal[Np],Pga[Np],PPga[Np];
		//int Xs1[1000][Np];
		double sEval,sum1,r;
		
    //for (i=0; i<Np; i=i+1) 
		//for (j=0; j<D; j=j+1)
			//cout<<X[j][i]<<endl;

		for (i=0;i<1000;i=i+1)
			Xj[i]=0;
		for (i=0;i<Np;i=i+1)
			X0[i]=0;

	    sEval=0.0;
		for (i=0; i<Np; i=i+1)
		{
            for (j=0; j<D; j=j+1)
			{
				//Xj[j]=*(*(u1+j)+i);
				Xj[j]=X[j][i];
				//cout<<Xj[j]<<endl;
			};
			//cout<<fValue(Xj,n)<<endl;
			eVal[i]=1/(double)(fValue(Xj,n)+1);
			sEval=sEval+eVal[i];
		}
		//for (i=0; i<Np; i=i+1)
			//cout<<eVal[i]<<endl;
		for (i=0; i<Np; i=i+1)
		{
			Pga[i]=(eVal[i])/sEval;
			sum1=0;
			for (j=0; j<=i; j=j+1)
				sum1=sum1+Pga[j];
			PPga[i]=sum1;
		}
		//for (i=0; i<Np; i=i+1)
			//cout<<PPga[i]<<endl;

		//Selection manipulation
		s=0;
		r=0.0;
        for (i=0; i<Np; i=i+1)
		{
			//srand((unsigned)time(NULL));
			r=(double)rand()/(double)RAND_MAX;
			if (r<=PPga[i])
			{
				X0[i]=1;
                //s=s+1;
                //for (k1=0;k1<s;k1=k1+1)
					for (k2=0;k2<D;k2=k2+1)
						//*(*(u2+k2)+s)=*(*(u1+k2)+i);
						Xs[k2][s]=X[k2][i];
					s=s+1;
				//Xs=[Xs X[][i]];
				//Xidx=[Xidx i];
				
			}
		}
        //cout<<s<<endl;

		return;


}

////////////////////////////////////////////////////////////////////////////////////////////////////
void crossover(int D,int n)
{
	int q1=0, L=0;
	int i0,j0,i,j,s1,s2;
	int cut_point1,cut_point2,mcut;
	int p1[1000],p2[1000],c1[1000],c2[1000],c11[1000],c22[1000],c111[1000],c222[1000];
	double r1;
	//int N2;

	//N2=Np/2;

	for (i=0;i<1000;i=i+1)
	{
		p1[i]=0;p2[i]=0;c1[i]=0;c2[i]=0;c11[i]=0;c22[i]=0;c111[i]=0;c222[i]=0;
	}

	while (q1<(int)(Np/2))
	{
		//select parents
	    //srand((unsigned)time(NULL));
		//i0=floor(s*(double)rand()/(double)RAND_MAX);
        i0=rand()%s;
		j0=i0;
		while (j0==i0)
		{	
			//srand((unsigned)time(NULL));
			//j0=floor(s*(double)rand()/(double)RAND_MAX);
			j0=rand()%s;
		};

		//Decide whether they will be crossovered
		//srand((unsigned)time(NULL));
		r1=(double)rand()/(double)RAND_MAX;

		if (r1<=Pc)
		{
			L=D;
			//srand((unsigned)time(NULL));
			cut_point1=(rand()%(L-1));
			cut_point2=cut_point1;
			while (cut_point2==cut_point1)
			{
				//srand((unsigned)time(NULL));
				cut_point2=(rand()%(L-1));
			};

			if (cut_point1>cut_point2)
			{
				mcut=cut_point1;
				cut_point1=cut_point2;
				cut_point2=mcut;
			}

			for (i=0; i<D; i=i+1)
			{
				//p1[i]=*(*(u3+i)+i0);
                //p2[i]=*(*(u3+i)+j0);
				p1[i]=Xs[i][i0];
				p2[i]=Xs[i][j0];
			}

			for (i=0; i<D-cut_point2; i=i+1)
			{
				c11[i]=p2[cut_point2+i];
				c11[D-cut_point2+i]=p2[i];
				c22[i]=p1[cut_point2+i];
				c22[D-cut_point2+i]=p1[i];
			}

			for (i=cut_point1; i<cut_point2; i=i+1)
			{
				for (j=0; j<D; j=j+1)
				{
					if (p1[i]==c11[j])
						c11[j]=0;
					if (p2[i]==c22[j])
						c22[j]=0;
				}
			}
            s1=0;
			s2=0;
			for (j=0; j<D; j=j+1)
			{
				if (c11[j]!=0)
				{
					c111[s1]=c11[j];
					s1=s1+1;
					//c111=[c111 c11[j]];
				}

				if (c22[j]!=0)
				{
					c222[s2]=c22[j];
				    s2=s2+1;
					//c222=[c222 c22[j]];
				}
			}

			for (i=0; i<cut_point1; i=i+1)
			{
				c1[i]=c111[i];
				c2[i]=c222[i];
			}

			for (i=cut_point1; i<cut_point2; i=i+1)
			{
				c1[i]=p1[i];
                c2[i]=p2[i];
			}

			for (i=cut_point2; i<D; i=i+1)
			{
				c1[i]=c111[cut_point1+i];
				c2[i]=c222[cut_point1+i];
			}

			if (fValue(c1,n)<=fValue(p1,n))
			{
				//X1=[X1 c1];
				for (j=0;j<D;j=j+1)
					//*(*(u4+j)+q1)=c1[j];
					X1[j][q1]=c1[j];
			}
			else
			{
				//X1=[X1 p1];
				for (j=0;j<D;j=j+1)
					//*(*(u4+j)+q1)=p1[j];
					X1[j][q1]=p1[j];
			};
			q1=q1+1;

			if (fValue(c2,n)<=fValue(p2,n))
			{
				//X1=[X1 c1];
				for (j=0;j<D;j=j+1)
                    //*(*(u4+j)+q1)=c2[j];
					X1[j][q1]=c2[j];
			}
			else
			{
				//X1=[X1 p1];
				for (j=0;j<D;j=j+1)
					//*(*(u4+j)+q1)=p2[j];
					X1[j][q1]=p2[j];
			};
			q1=q1+1;
		}
	}


	return;
}

////////////////////////////////////////////////////////////////////////////////////////////////
void mutation(int D,int n)
{
	int q2=0, L=0;
	int k0,i,j;
	int cut_point1,cut_point2,mcut,mx;
	int p3[1000],p0[1000];
	float r2;
	int N1;

	for (i=0;i<1000;i=i+1)
	{
		p3[i]=0;p0[i]=0;
	};

	N1=Np/2;

	while (q2<N1)
	{
		//srand((unsigned)time(NULL));
		//k0=floor(s*(double)rand()/(double)RAND_MAX);
		k0=rand()%s;

		//srand((unsigned)time(NULL));
		r2=(double)rand()/(double)RAND_MAX;

		if (r2<=Pm)
		{
			for (i=0; i<D; i=i+1)
			{
				//p3[i]=*(*(u5+i)+k0);
				p3[i]=Xs[i][k0];
				p0[i]=p3[i];
			}

			L=D;
			//srand((unsigned)time(NULL));
			cut_point1=(rand()%(L-1));
			//cout<<cut_point1<<endl;
			cut_point2=cut_point1;

			while (cut_point2==cut_point1)
			{
				//srand((unsigned)time(NULL));
				cut_point2=(rand()%(L-1));
			}
		    
			if (cut_point1>cut_point2)
			{
				mcut=cut_point1;
				cut_point1=cut_point2;
				cut_point2=mcut;
			}

			mx=p3[cut_point1];
			p3[cut_point1]=p3[cut_point2];
			p3[cut_point2]=mx;

			if (fValue(p3,n)<=fValue(p0,n))
			{
				//X2=[X2 p3];
				for (j=0;j<D;j=j+1)
					//*(*(u6+j)+q2)=p3[j];
					X2[j][q2]=p3[j];
				q2=q2+1;
			}
		}
	}

	return;
}