ga.cpp

生物的进化是一个奇妙的优化过程

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#define randint(max) (rand()%max)
#define randfloat() ((double)rand()/RAND_MAX)

#define xmax 5.12
#define xmin -5.12
#define POPULATION 20
#define DOMINASION 10
#define MAX_RUNTIME 20
#define MAX_GENERATION 3000
#define PC 0.8
#define PM 0.001

double f1_fitness(int um);
void initialize();
void select();
void crossover();
void mutation();
void preserve();
void statistic();

typedef struct _Individal  
{
	double fitness;
	double rfitness;           /* relative fitness */
    double cfitness;           /* cumulative fitness */
	double position[DOMINASION];
}Individal;

Individal individal[POPULATION], best_individal, parent_invividal[POPULATION];

int main()
{
	srand(time(0));

	int i, j;

	for (i=0; i<MAX_RUNTIME; i++)
	{
		initialize();//初始化
    
		for (j=0; j<MAX_GENERATION; j++)
		{
			select();//选择
			crossover();//杂交，交叉
			mutation();//变异
			preserve();//保存
			
		}
		statistic();//统计
	}
	return 0;
}

double f1_fitness(int num)
{
	int i;
	double sum = 0.0;

	for (i=0; i<DOMINASION; i++)
//		sum+=(individal[num].position[i])*(indvidal[num].position[i]);     ????
		sum+=pow(individal[num].position[i],2.0);
	return sum;
    
}//衡量染色体的好坏

void initialize()
{
	int i, j, flag = 0;
	double tmp;

	for (i=0; i<POPULATION; i++)
	{
		for (j=0; j<DOMINASION; j++)
		{
			individal[i].position[j] = xmin+(xmax-xmin)*randfloat();
		}
		individal[i].fitness = f1_fitness(i);
	}

	tmp= individal[0].fitness;
	for (i=1; i<POPULATION; i++)
		if (individal[i].fitness<tmp)
		{
			tmp = individal[i].fitness;
			flag = i;
		}

	best_individal = individal[flag];

}

void select()
{
	int i,j;
	double ratio[POPULATION] = {0.0},sum = 0.0;
	for (i=0; i<POPULATION; i++)
	{
		sum += 1.0/(individal[i].fitness+1.0);
	}
	
	for (i=0; i<POPULATION; i++)
	{
		ratio[i] = 1.0/((individal[i].fitness+1.0)*sum);
	}

	for (i=1; i<POPULATION; i++)
	{
		ratio[i] = ratio[i]+ratio[i-1];
	}
	
	for (i=0; i<POPULATION; i++)
	{
		double tmp = randfloat();
		for (j=0; j<POPULATION; j++)
		{
			if (tmp<=ratio[j])
			{
				parent_invividal[i] = individal[j];
				break;
			}
		}
	}
}

void crossover()
{
	int i,j;
	double sum;

	for (i=0; i<POPULATION/2; i++)
	{
		if (randfloat()<PC)
		{
			sum = randfloat();
			
			for (j=0; j<DOMINASION; j++)
			{
				individal[2*i].position[j] =
                    sum*parent_invividal[2*i].position[j]+(1-sum)*parent_invividal[2*i+1].position[j];
				individal[2*i+1].position[j] =
                    (1-sum)*parent_invividal[2*i].position[j]+sum*parent_invividal[2*i+1].position[j];
			}
		}

	}
}

void mutation()
{
	int i,j;
	for (i=0; i<POPULATION; i++)
	{
		if (randfloat()<PM)
		{
			j = randint(DOMINASION);
			individal[i].position[j] = xmin+(xmax-xmin)*randfloat();
		}
	}
	for (i=0; i<POPULATION; i++)
		individal[i].fitness = f1_fitness(i);
}

void preserve()
{
	int i;
	for (i=0; i<POPULATION; i++)
		if (individal[i].fitness<best_individal.fitness)
		{
			best_individal = individal[i];
		}
}

void statistic()
{
	printf("%f\t",best_individal.fitness);
}