ga-3.cpp

很好的遗传算法例题

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "conio.h"
#include <math.h>
#include "UTLab.h"

#define FollowerNumber 3    //Number of followers in the decentralized decision-making problems.
#define PrintNumber   100   //
#define LN 3                // number of variables controled by the leader.
#define FN 2                // number of variables controled by each follower.
#define LM 1                // number of objectives of the leader.
#define FM 1                // number of objectives of each follower.
#define LeaderType 1        // 1=max;-1=min.
#define FollowerType 1      // 1=max;-1=min.
#define LeaderGen 1000      // maximum generation number of genetic algorithm at the leader's level.
#define FollowerGen 1000    // maximum generation number of genetic algorithm at the leader's level.
#define PopSize 30          //Population size in genetic algorithm.
#define PrMutation 0.2      //Probability of one chromosome's being selected to mutate.
#define PrCrossover 0.5     //Probability of one chromosome's being selected to crossover.  

// Define variables and functions related to genetic algorithm procedure of the leader's level. 
double LeaderObj[PopSize+1][LM+1],LeaderChromosome[PopSize+1][LN+1];

static void LeaderInitialization(void);
static int  LeaderConstraintCheck(double LeaderSolution[LN+1]);
static void LeaderEvaluation(unsigned Gen);
static void LeaderSelection(void);
static void LeaderCrossover(void);
static void LeaderMutation(void);
static void LeaderObjective(void);

// Define variables and functions related to genetic algorithm procedure of the follower's level. 
double FollowerObj[PopSize+1][FM+1],FollowerChromosome[PopSize+1][FN+1];

static void FollowerInitialization(unsigned FollowerNo,double LeaderDecision[LN+1]);
static int  FollowerConstraintCheck(unsigned FollowerNo,double LeaderDecision[LN+1],double FollowerDecision[FN+1]);
static void FollowerEvaluation(unsigned FollowerNo,unsigned Gen,double LeaderDecision[LN+1]);
static void FollowerSelection(void);
static void FollowerCrossover(unsigned FollowerNo,double LeaderDecision[LN+1]);
static void FollowerMutation(unsigned FollowerNo,double LeaderDecision[LN+1]);
static void FollowerObjective(unsigned FollowerNo,double LeaderDecision[LN+1]);
static void FollowerGA(unsigned FollowerNo,double LeaderDecision[LN+1],double FollowerDecision[FollowerNumber][FN+1]);

// Define the routhllete used in selection process of GA procedure.
double Roulette[PopSize+1];
static void RouletteInitialization(void);


static int LeaderConstraintCheck(double LeaderDecision[])
{
	double sum=0;
	for(unsigned i=1;i<=LN;i++)
	{
		if(0>LeaderDecision[i]||LeaderDecision[i]>10) return 0;
		sum+=LeaderDecision[i];
	}
	if(sum>10) return 0;
	return 1;
}

static void LeaderInitialization(void)
{
	double LeaderDecision[LN+1];
	unsigned i,j;
	for(i=1; i<=PopSize; i++)
	{
		do
		{
			LeaderDecision[1]=myu(0,10);
			LeaderDecision[2]=myu(0,10);
			LeaderDecision[3]=myu(0,10);
		}while(LeaderConstraintCheck(LeaderDecision)==0);
		for(j=1;j<=LN;j++) 
			LeaderChromosome[i][j]=LeaderDecision[j];
	}
}


static int FollowerConstraintCheck(unsigned FollowerNo,double LeaderDecision[],double FollowerDecision[])
{
	if(FollowerDecision[1]<0||FollowerDecision[2]<0) return 0;
	if(FollowerDecision[1]+FollowerDecision[2]>LeaderDecision[FollowerNo]) return 0;
	return 1;
}


static void FollowerInitialization(unsigned FollowerNo,double LeaderDecision[])
{
	double FollowerDecision[FN+1];
	unsigned i,j;
	for(i=1;i<=PopSize;i++)
	{
		do
		{
			FollowerDecision[1]=myu(0,LeaderDecision[FollowerNo]);
			FollowerDecision[2]=myu(0,LeaderDecision[FollowerNo]);
		}while(FollowerConstraintCheck(FollowerNo,LeaderDecision,FollowerDecision)==0);
		for(j=1;j<=FN;j++) FollowerChromosome[i][j]=FollowerDecision[j];
		
	}
}


int main()
{
	srand(100);
	RouletteInitialization();
	LeaderInitialization();
	LeaderEvaluation(0);
	FILE *fp;
	fp=fopen("RESULT.dat","w");
	unsigned i,j,FollowerNo;
	for(i=1;i<=LeaderGen;i++) 
	{
		LeaderSelection();
		LeaderCrossover();
		LeaderMutation();
		LeaderEvaluation(i);
		if(i%PrintNumber==0)
		{
			printf("\nGeneration NO.%d\n", i);
			fprintf(fp,"\nGeneration NO.%d\n",i);
			printf("Leader's decision x=(");
			fprintf(fp,"Leader's decision x=(");
			double LeaderDecision[LN+1],FollowerDecision[FollowerNumber+1][FN+1];
			for(j=1;j<=LN;j++) 
			{
				LeaderDecision[j]=LeaderChromosome[0][j];
				printf("%f",LeaderChromosome[0][j]);
				if(j<LN) printf(",");
				fprintf(fp,"%f",LeaderChromosome[0][j]);
				if(j<LN) fprintf(fp,",");
			}
			printf("),");
			fprintf(fp,"),");
			printf(" objective F=");
			fprintf(fp," objective F=");
			for(j=1;j<=LM;j++) 
			{
				printf("%f.\n",LeaderObj[0][j]);
				fprintf(fp,"%f.\n",LeaderObj[0][j]);
			}

			for(FollowerNo=1;FollowerNo<=FollowerNumber;FollowerNo++)
				FollowerGA(FollowerNo,LeaderDecision,FollowerDecision);
			double Output[2];
			for(FollowerNo=1;FollowerNo<=FollowerNumber;FollowerNo++) 
			{
				Output[1]=FollowerDecision[FollowerNo][1]*sin(FollowerDecision[FollowerNo][2])+FollowerDecision[FollowerNo][2]*sin(FollowerDecision[FollowerNo][1]);
				printf("Follower%d's decision y%d=(",FollowerNo,FollowerNo);
				fprintf(fp,"Follower%d's decision y%d=(",FollowerNo,FollowerNo);
				for(j=1;j<=FN;j++) 
				{
					printf("%f",FollowerDecision[FollowerNo][j]);
					if(j<FN) printf(",");
					fprintf(fp,"%f",FollowerDecision[FollowerNo][j]);
					if(j<FN) fprintf(fp,",");
				}
				printf("),");
				fprintf(fp,"),");
				printf(" objective f%d=",FollowerNo);
				fprintf(fp," objective f%d=",FollowerNo);
				for(j=1;j<=FM;j++) 
				{
					printf("%6.4f.\n",Output[j]);
					fprintf(fp,"%6.4f.\n",Output[j]);
				}
			}

		}
	}
	fclose(fp);
	return 1;
}

//Define the function to calculate a population's objective function value. 
static void LeaderObjective(void)
{
	double LeaderDecision[LN+1],FollowerDecision[FollowerNumber+1][FN+1];
	unsigned i,j,FollowerNo;
	for(i=1;i<=PopSize;i++) 
	{
		for(j=1;j<=LN;j++) 
		{
			LeaderDecision[j]=LeaderChromosome[i][j];
		}
		for(FollowerNo=1;FollowerNo<=FollowerNumber;FollowerNo++)
		{
			FollowerGA(FollowerNo,LeaderDecision,FollowerDecision);
		}
		LeaderObj[i][1]=FollowerDecision[1][1]*FollowerDecision[1][2]*sin(LeaderDecision[1])
			+2*FollowerDecision[2][1]*FollowerDecision[2][2]*sin(LeaderDecision[2])
			+3*FollowerDecision[3][1]*FollowerDecision[3][2]*sin(LeaderDecision[3]);

	}
	for(i=1;i<=PopSize;i++) 
	{
		LeaderObj[i][0]=LeaderObj[i][1];
	}	
}

static void LeaderEvaluation(unsigned Gen)
{
	double temp;
	unsigned i,j,k,label;
	LeaderObjective();
	if(Gen==0)
	{
		for(i=0;i<=LM;i++) LeaderObj[0][i]=LeaderObj[1][i];
		for(i=1;i<=LN;i++) LeaderChromosome[0][i]=LeaderChromosome[1][i];
	}

	for(i=0;i<=PopSize;i++)
	{
		label=0;  
		temp=LeaderObj[i][0];
		for(j=i+1;j<=PopSize;j++)
		{
			if((LeaderType*temp)<(LeaderType*LeaderObj[j][0])) 
			{
				temp=LeaderObj[j][0];
				label=j;
			}
		}
		if(label!=0) 
		{
			for(k=0;k<=LM;k++) 
			{
				temp=LeaderObj[i][k];
				LeaderObj[i][k]=LeaderObj[label][k];
				LeaderObj[label][k]=temp;
			}
			for(j=1;j<=LN;j++) 
			{
				temp=LeaderChromosome[i][j];
				LeaderChromosome[i][j]=LeaderChromosome[label][j];
				LeaderChromosome[label][j]=temp;
			}
		}
	}
}

static void LeaderSelection(void)
{
	double r, temp[PopSize+1][LN+1];
	unsigned i,j,k;
	for(i=1;i<=PopSize;i++) 
	{
		r=myu(0,0.785);
		for(j=0;j<=PopSize; j++) 
		{
			if(r<=Roulette[j]) 
			{
				for(k=1;k<=LN;k++) temp[i][k]=LeaderChromosome[j][k];
				break;
			}
		}
	}
	for(i=1; i<=PopSize; i++)
		for(k=1;k<=LN;k++)
			LeaderChromosome[i][k]=temp[i][k];
}

static void LeaderCrossover(void)
{
	int   i, j, jj, k, pop;
	double r, x[LN+1], y[LN+1];
	pop=PopSize/2;
	for(i=1; i<=pop; i++) 
	{
		if(myu(0,1)>PrCrossover) continue;
		j=1+rand()%PopSize;
		jj=1+rand()%PopSize;
		do
		{
			r=myu(0,1);
			for(k=1;k<=LN;k++) 
			{
				x[k]=r*LeaderChromosome[j][k]+(1-r)*LeaderChromosome[jj][k];
			}
		}while(LeaderConstraintCheck(x)==0);
		do
		{
			r=myu(0,1);
			for(k=1;k<=LN;k++) 
			{
				y[k]=r*LeaderChromosome[jj][k]+(1-r)*LeaderChromosome[j][k];
			}
		}while(LeaderConstraintCheck(y)==0);

		for(k=1;k<=LN;k++) LeaderChromosome[j][k]=x[k];
		for(k=1;k<=LN;k++) LeaderChromosome[jj][k]=y[k];
	}
}

static void LeaderMutation(void)
{
	unsigned i, j, k;
	double x[LN+1],y[LN+1],infty,direction[LN+1];
	double INFTY=10,precision=0.0001;
	for(i=1; i<=PopSize; i++) 
	{
		if(myu(0,1)>PrMutation) continue;
		for(k=1;k<=LN;k++) x[k]=LeaderChromosome[i][k];
		for(k=1; k<=LN; k++)
		{
			if(myu(0,1)<0.5) direction[k]=myu(-1,1);
			else direction[k]=0;
		}
		infty=myu(0,INFTY);
		while(infty>precision) 
		{
			for(j=1;j<=LN;j++) y[j]=x[j]+infty*direction[j];
			if(LeaderConstraintCheck(y)==1) 
			{
				for(k=1;k<=LN;k++) 
					LeaderChromosome[j][k]=y[k];
				break;
			}
			else
			{
				infty=myu(0,infty);
			}
		}
	}
}
static void FollowerObjective(unsigned FollowerNo,double LeaderDecision[])
{
	double FollowerDecision[FN+1];
	unsigned i,j;
	for(i=1;i<=PopSize;i++) 
	{
		for(j=1;j<=FN;j++) 
		{
			FollowerDecision[j]=FollowerChromosome[i][j];
		}
		FollowerObj[i][1]=FollowerDecision[1]*sin(FollowerDecision[2])+FollowerDecision[2]*sin(FollowerDecision[1]);
	}
	for(i=1;i<=PopSize;i++) 
	{
		FollowerObj[i][0]=FollowerObj[i][1];
	}
}

static void FollowerEvaluation(unsigned FollowerNo,unsigned Gen,
							   double LeaderDecision[LN+1])
{
	double temp;
	unsigned j,k,l,label;
	FollowerObjective(FollowerNo,LeaderDecision);
	if(Gen==0)
	{
		for(k=0;k<=FM;k++) FollowerObj[0][k]=FollowerObj[1][k];
		for(j=1;j<=FN;j++) FollowerChromosome[0][j]=FollowerChromosome[1][j];
	}
	for(j=0;j<=PopSize;j++)
	{
		label=j;  temp=FollowerObj[j][0];
		for(k=j+1;k<=PopSize;k++)
		{
			if((FollowerType*temp)<(FollowerType*FollowerObj[k][0])) 
			{
				temp=FollowerObj[k][0];
				label=k;
			}
		}
		if(label!=j) 
		{
			for(l=0;l<=FM;l++) 
			{
				temp=FollowerObj[j][l];
				FollowerObj[j][l]=FollowerObj[label][l];
				FollowerObj[label][l]=temp;
			}
			for(l=1;l<=FN;l++) 
			{
				temp=FollowerChromosome[j][l];
				FollowerChromosome[j][l]=FollowerChromosome[label][l];
				FollowerChromosome[label][l]=temp;
			}
		}
	}
}

static void FollowerSelection(void)
{
	double p[PopSize+1],a;
	a=0.05;p[0]=0.05;
	for(unsigned i=1;i<=PopSize;i++) 
	{
		a=a*0.95; 
		p[i]=p[i-1]+a;
	}
	double r, temp[PopSize+1][FN+1];
	unsigned j,k;
	for(i=1; i<=PopSize; i++) 
	{
		r=myu(0, 0.785);
		for(j=0; j<=PopSize; j++) 
		{
			if(r<=p[j]) 
			{
				for(k=1; k<=FN; k++) temp[i][k]=FollowerChromosome[j][k];
				break;
			}
		}
	}
	for(i=1;i<=PopSize;i++)
		for(k=1;k<=FN;k++)
			FollowerChromosome[i][k]=temp[i][k];
}

static void FollowerCrossover(unsigned FollowerNo,double LeaderDecision[LN+1])
{
	unsigned   i, j, jj, k, pop;
	double r, x[FN+1], y[FN+1];
	pop=PopSize/2;
	for(i=1; i<=pop; i++) 
	{
		if(myu(0,1)>PrCrossover) continue;
		j=1+rand()%PopSize;
		jj=1+rand()%PopSize;
		r=myu(0,1);
		for(k=1;k<=FN;k++) 
		{
			x[k]=r*FollowerChromosome[j][k]+(1-r)*FollowerChromosome[jj][k];
			y[k]=r*FollowerChromosome[jj][k]+(1-r)*FollowerChromosome[j][k];
		}
		if(FollowerConstraintCheck(FollowerNo,LeaderDecision,x)==1)
			for(k=1;k<=FN;k++) FollowerChromosome[j][k]=x[k];
		if(FollowerConstraintCheck(FollowerNo,LeaderDecision,y)==1)
			for(k=1;k<=FN;k++) FollowerChromosome[jj][k]=y[k];
	}
}

static void FollowerMutation(unsigned FollowerNo,double LeaderDecision[LN+1])
{
	int i, j, k;
	double x[FN+1],y[FN+1],infty,direction[FN+1];
	double INFTY=10,precision=0.0001;
	for(i=1; i<=PopSize; i++) 
	{
		if(myu(0,1)>PrMutation) continue;
		for(k=1;k<=FN;k++) x[k]=FollowerChromosome[i][k];
		for(k=1; k<=FN; k++)
		{
			direction[k]=myu(-1,1);
		}
		infty=myu(0,INFTY);
		while(infty>precision) 
		{
			for(j=1;j<=FN;j++) y[j]=x[j]+infty*direction[j];
			if(FollowerConstraintCheck(FollowerNo,LeaderDecision,y)==1) 
			{
				for(k=1; k<=FN; k++) FollowerChromosome[i][k]=y[k];
				break;
			}
			infty=myu(0,infty);
		}
	}
}
static void FollowerGA(unsigned FollowerNo,double LeaderDecision[LN+1],
					   double FollowerDecision[FollowerNumber+1][FN+1])
{
	double temp[1000];
	FollowerInitialization(FollowerNo,LeaderDecision);
	unsigned Gen=0;
	FollowerEvaluation(FollowerNo,Gen,LeaderDecision);
	do
	{
		Gen++;
		FollowerSelection();
		FollowerCrossover(FollowerNo,LeaderDecision);
		FollowerMutation(FollowerNo,LeaderDecision);
		FollowerEvaluation(FollowerNo,Gen,LeaderDecision);
		temp[Gen]=FollowerObj[0][1];
		if(Gen<=101) 
			temp[0]=1;
		else
			temp[0]=temp[Gen]-temp[Gen-100];
		if(temp[0]<0.001) break;
	}while(Gen<FollowerGen);
	for(unsigned i=1;i<=FN;i++) FollowerDecision[FollowerNo][i]=FollowerChromosome[0][i];
}

static void RouletteInitialization(void)
{
	Roulette[0]=0.05; 
	double temp=0.05;
	for(unsigned i=1;i<=PopSize;i++) 
	{
		temp=temp*0.95; 
		Roulette[i]=Roulette[i-1]+temp;
	}
}