de_example_in_c.txt

differentail Evolution example in c. please study this code and enjoy it

Sample Program of Differential Evolution
/* Coded by T.Takahama */

#include <stdio.h>
#include <stdlib.h>

/* Random number generator in [0, 1] */
#define Rand()		((double)rand()/RAND_MAX)
/* Random integer generator in [0, n-1] */
#define RandInt(n)	(rand()%n)

/* Structure of an individual */
typedef struct {
	double *x;	/* genes */
	double f;	/* fitness value */
} IndividualRec, *Individual;

/*
	Parameters for DE
*/

/* Number of individuals */
#define Nindividuals	50
/* Maximum number of iterations */
#define T_MAX		1000
/* parameters for crossover */
#define Pc		0.9
#define F		0.8

/*
	Definitions for a problem
*/

/* Number of variables: problem dependent */
#define Nvariables	5

/* Objective function for minimization: problem dependent */
#define better(y1, y2)	(y1<y2)

/* The following is the function of Sum_i (x_i-1)^2 */
void Evaluate(Individual P)
{
	int i;

	P->f=0.0;
	for(i=0; i<Nvariables; i++)
		P->f+=(P->x[i]-1)*(P->x[i]-1);
}

/* Initialization of individuals: problem dependent */
/* The function returns the index of the best individual */
int Initialize(Individual P, int n)
{
	int i, j;
	int best;		/* the index of the best individual */

	best=0;
	for(i=0; i<n; i++) {
		for(j=0; j<Nvariables; j++)
			P[i].x[j]=Rand();		/* problem dependent */
		Evaluate(&P[i]);
		if(better(P[i].f, P[best].f)) best=i;
	}
	return best;
}

/*
	Definitions for DE
*/

/* allocate new data structures */
#define New(type, n, msg)	(type *)NewCell(sizeof(type), n, msg)

void *NewCell(int size, int n, char *msg)
{
	void *new;

	if((new=malloc(size*n))==NULL) {
		fprintf(stderr, "Cannot allocate memory for %d %s\n", n, msg);
		exit(1);
	}
	return new;
}

/* allocate "n" new individuals */
Individual NewIndividuals(int n)
{
	int i;
	Individual P;

	P=New(IndividualRec, n, "individuals");
	for(i=0; i<n; i++) {
		P[i].x=New(double, Nvariables, "x");
	}
	return P;
}

/* Copy an individual */
void CopyIndividual(Individual dest, Individual src)
{
	int j;

	for(j=0; j<Nvariables; j++)
		dest->x[j]=src->x[j];
	dest->f=src->f;
}

/* Print a individual */
void Print(Individual P)
{
	int j;

	for(j=0; j<Nvariables; j++)
		printf("%f ", P->x[j]);
	printf(" = %g\n", P->f);
}

/* crossover & mutation */
void DEoperation(Individual New, Individual Old, int i)
{
	int p1, p2, p3, j, l;

	do {
		p1=RandInt(Nindividuals);
	} while(p1==i);
	do {
		p2=RandInt(Nindividuals);
	} while(p2==i || p2==p1);
	do {
		p3=RandInt(Nindividuals);
	} while(p3==i || p3==p1 || p3==p2);
#ifdef BINARY
/* DE/rand/1/bin */
	j=RandInt(Nvariables);
	for(l=0; l<Nvariables; l++) {
		if(l==1 || Rand()<Pc)
			New[i].x[j]=Old[p1].x[j]+F*(Old[p2].x[j]-Old[p3].x[j]);
		else
			New[i].x[j]=Old[i].x[j];
		j=(j+1)%Nvariables;
	}
#else
/* DE/rand/1/exp */
	CopyIndividual(&New[i], &Old[i]);
	j=RandInt(Nvariables);
	l=0;
	do {
		New[i].x[j]=Old[p1].x[j]+F*(Old[p2].x[j]-Old[p3].x[j]);
		j=(j+1)%Nvariables;
		l++;
	}
	while(l<Nvariables && Rand()<Pc);
#endif
}

/* Differential Evolution */
main()
{
	int t, i;
	Individual P[2];
	int old, new;
	Individual Best;
	int best;

	P[0]=NewIndividuals(Nindividuals);
	P[1]=NewIndividuals(Nindividuals);
	Best=NewIndividuals(1);
	best=Initialize(P[0], Nindividuals);
	CopyIndividual(Best, &P[0][best]);
	old=0; new=1;
	for(t=1; t<=T_MAX; t++) {
		for(i=0; i<Nindividuals; i++) {
			DEoperation(P[new], P[old], i);
			Evaluate(&P[new][i]);
			if(better(P[old][i].f, P[new][i].f)) /* new is worse than old */
				CopyIndividual(&P[new][i], &P[old][i]);
			else if(better(P[new][i].f, Best->f))
				CopyIndividual(Best, &P[new][i]);
		}
		old=!old; new=!new;
		printf("%4d: ", t); Print(Best);
	}
}