sga.c

遗传算法的好代码

#include   <stdio.h>
#include   <stdlib.h>
#include   <time.h>
#include   <math.h>
#include   <string.h>
#define    POPSIZE         500
#define    MAXIMIZATION    1
#define    MINIMIZATION    2
#define    Cmax            100
#define    Cmin            0
#define    LENGTH1         10
#define    LENGTH2         10
#define    CHROMLENGTH     LENGTH1+LENGTH2
int        FunctionMode    = MAXIMIZATION;
int        PopSize         = 80;
int        MaxGeneration   = 300;
double     Pc              = 0.6;
double     Pm              =0.001;

                        
struct     individual         //结构变量和函数定义
{
    char    chrom[CHROMLENGTH +1];
    double  value;
    double  fitness;
};
int    generation;
int    best_index;
int    worst_index;
struct individual    bestindividual;
struct individual    worstindividual;
struct individual    currentbest;
struct individual    population[POPSIZE];
void   GenerateInitialPopulation(void);
void   GenerateNextPopulation(void);
void   EvaluatePopulation(void);
long   DecodeChromosome(char * ,int ,int);
void   CalculateObjectValue(void);
void   CalculateFitnessValue(void);
void   FindBestAndWorstIndividual(void);
void   PerformEvolution(void);
void   SelectionOperator(void);
void   CrossoverOperator(void);
void   MutationOperator(void);
void   OutputTextReport(void);

int random(int n)              //随机数产生函数
{
    int ret=rand()%n;
    return ret;
}

void main(void)               //主函数
{
    generation =0;
    GenerateInitialPopulation();
    EvaluatePopulation();
    while(generation < MaxGeneration)
    {
        generation++;
        GenerateNextPopulation();
        EvaluatePopulation();
        PerformEvolution();
        OutputTextReport();
    }
}

//---------------------------------------------------
void GenerateInitialPopulation(void)    //产生初始群体
{
    int    i ,j;
    for( i=0;i<PopSize;i++)
    {
        for(j=0;j<CHROMLENGTH;j++)
        {
            population[i].chrom[j]=(random(10) <5)?'0':'1';
            population[i].chrom[CHROMLENGTH] = '\0';
        }
    }
}

//----------------------------------------------------
void GenerateNextPopulation(void)      //下代群体产生
{
    SelectionOperator();
    CrossoverOperator();
    MutationOperator();
}

//-----------------------------------------------
void EvaluatePopulation(void)         //群体评估
{
    CalculateObjectValue();
    CalculateFitnessValue();
    FindBestAndWorstIndividual();
}


//---------------------------------------------------------------
long DecodeChromosome(char * string, int point, int length)     //染色体解码
{
    int i;
    long decimal =0L;
    char * pointer;
    int nstr=strlen(string);

    for (i=0,pointer =string+point; i<length; i++,pointer++)
    {
        decimal +=(*pointer-'0')<<(length-1-i);
    }
    return decimal;
}

//-------------------------------------------------------------------
void CalculateObjectValue(void)                   //计算目标函数值函数
{
    int i;
    long temp1,temp2;
    double x1,x2;
    
	for(i=0;i<PopSize;i++)
    {
        temp1 =DecodeChromosome(population[i].chrom, 0, LENGTH1);
        temp2 =DecodeChromosome(population[i].chrom, LENGTH1, LENGTH2);
        x1 = 4.096*temp1/1023.0 -2.048;
        x2 = 4.096*temp2/1023.0 -2.048;

        population[i].value =100*(x1*x1 - x2)*(x1*x1 -x2) + (1-x1)*(1-x1);
    }
}

//---------------------------------------------------
void CalculateFitnessValue(void)          //计算适应度
{
    int i;
    double temp;
    for (i =0;i<PopSize;i++)
    {
        if (FunctionMode == MAXIMIZATION)
        {
            if((population[i].value +Cmin) >0.0)
            {
                temp = Cmin +population[i].value;
            }
            else
            {
                temp=0.0;
            }
        }
        else if(FunctionMode ==MINIMIZATION)
        {
            if (population[i].value <Cmax)
            {
                temp = Cmax - population[i].value;
            }
            else
            {
                temp =0.0;
            }
        }
        population[i].fitness =temp;
    }
}

//-------------------------------------------------------------
void FindBestAndWorstIndividual(void)     //寻找最佳最差个体函数
{
    int i;
    double sum =0.0;
    bestindividual =population[0];
    worstindividual = population[0];
    
	for(i=1;i<PopSize;i++)
    {
        if(population[i].fitness>bestindividual.fitness)
        {
            bestindividual =population[i];
            best_index =i;
        }
        else if (population[i].fitness <worstindividual.fitness)
        {
            worstindividual =population[i];
            worst_index =i;
        }
        sum +=population[i].fitness;
    }
    
	if (generation ==0)
    {
        currentbest = bestindividual;
    }
    else
    {
        if(bestindividual.fitness >currentbest.fitness)
        {
            currentbest = bestindividual;
        }
    }
}

//--------------------------------------------------------
void PerformEvolution(void)                  //执行评价函数
{
    if(bestindividual.fitness > currentbest.fitness)
    {
        currentbest = population[best_index];
    }
    else
    {
        population[worst_index] = currentbest;;
    }
}

//----------------------------------------
void SelectionOperator(void)     //选择算子
{
    int i,index;
    double p,sum =0.0;
    double cfitness[POPSIZE];
    struct individual newpopulation[POPSIZE];
    
	for(i=0;i<PopSize;i++)
    {
        sum +=population[i].fitness;
    }
    for(i =0; i<PopSize;i++)
    {
        cfitness[i] =population[i].fitness/sum;
    }
    for(i=1;i<PopSize;i++)
    {
        cfitness[i] = cfitness[i-1] +cfitness[i];
    }

    for(i=0;i<PopSize;i++)
    {
        p =rand()%1000/1000.0;
        index =0;
        while(p >cfitness[index])
        {
            index ++;
        }
        newpopulation[i] = population[index];
    }
    for(i=0;i<PopSize;i++)
    {
        population[i] =newpopulation[i];
    }
}

//---------------------------------------------
void CrossoverOperator(void)          //交叉算子
{
    int i,j;
    int index[POPSIZE];
    int point,temp;
    double p;
    char ch;
    for(i=0;i<PopSize;i++)
    {
        index[i] =i;
    }
    for(i=0;i<PopSize;i++)
    {
        point =random(PopSize-i);
        temp =index[i];
        index[i] =index[point+i];    //swap
        index[point+i] =temp;
    }
    
    for(i=0;i<PopSize-1;i+=2)
    {
        p =rand()%1000/1000.0;
        if(p<Pc)
        {
            point =random(CHROMLENGTH-1)+1;
            for (j=point;j<CHROMLENGTH;j++)
            {
                ch =population[index[i]].chrom[j];
                population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
                population[index[i+1]].chrom[j] =ch;
            }
        }
    }
}

//-------------------------------------
void MutationOperator(void)   //变异算子
{
    int i,j;
    double p;
    for(i=0;i<PopSize;i++)
    {
        for(j=0;j<CHROMLENGTH;j++)
        {
            p =rand()%1000/1000.0;
            if(p<Pm)
            {
                population[i].chrom[j] =(population[i].chrom[j]=='0')?'1':'0';
            }
        }
    }
}

//-----------------------------------------
void OutputTextReport(void)       //输出函数

{
    int i;
    double sum;
    double average;
    sum=0.0;
    
	for (i=0;i<PopSize;i++)
    {
        sum+=population[i].value;
    }
    average =sum/PopSize;
    printf("gen=%d, avg=%f, best=%f,",generation,average,currentbest.value);
    printf("Chromosome=");
    for(i=0;i<CHROMLENGTH;i++)
    {
        printf("%c",currentbest.chrom[i]);
    }
    printf("\n");
}