sga.txt

基本遗传算法及其在函数优化中的应用

/************************************************************************************************
                        作者：jiangsai
*************************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/*********************************************************************************************************/
/*                定义常量                                                                               */
/********************************************************************************************************/
#define POPSIZE 500//种群大小/************************************************************************************************
                        作者：jiangsai
*************************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.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//染色体总长
#define MAXGA 30//进行遗传算法的次数
int FunctionMode=MAXIMIZATION; //最优化类型
int PopSize =80;//下一代种群大小
int MaxGeneration =200;//最大遗传代数
double Pc =0.6;//交叉概率
double Pm =0.001;//变异概率
FILE *fp;
/***********************************************************************************************************/
/*                       定义结构体                                                                      */
/**********************************************************************************************************/
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 GenerateNextPopulation();//下一代初始化函数
void EvaluatePopulation();//评价函数
int DecodeChromosome(char *string,int point ,int length);//解码从二进制到十进制 
//void FindBestAndWorstValue();//寻找最优最差基因
void CalculateObjectValue();//计算一个染色体的函数目标值
void CalculateFitnessValue();//计算一个染色体的适应度值
void FindBestWorstIndividual();//寻找最优最差基因
void PerformEvolution();//最优替换最差的
void SelectionOperator();//选择算子
void CrossoverOperator();//交叉算子
void MutationOperator();//变异算子
void OutputTextReport();//输出操作
/*************************************************************************************************************/
/*                                        主函数　　                                                         */
/*************************************************************************************************************/
int main()
{
    if((fp=fopen("result.txt","w+"))==NULL)
	{
		exit(1);
	}
	fprintf

(fp,"********************************************************************************************\n");
	fprintf(fp,"***用遗传算法求解函数(f(x)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1)的最大值***\n");
	fprintf(fp,"**********作者：蒋赛，赵玉芹，董金明（计算机科学学院06级研究生）**********\n");
	fprintf

(fp,"********************************************************************************************\n");
	generation=0;
    GenerateInitialPopulation();
    EvaluatePopulation();
    double  mmax=-1.0;
    int ccount=0;
    while(1)
    {
    while(generation<MaxGeneration)//控制遗传的代数
    {
       generation++;//代数加一
       GenerateNextPopulation();//对下一代进行选择、交叉、变异操作
       EvaluatePopulation();//对操作后的新一代染色体进行评价
       PerformEvolution();//用最优的结果替换最差的 
       OutputTextReport();//输出结果
       if(mmax<currentbest.value)
       mmax=currentbest.value;
     
    } 
     ccount++;
     generation=0;//重新开始新一轮的遗传算法 这样的好处是为了避免出现由于初始种群比较劣等使得这一次的遗传运算结果不理想
     GenerateInitialPopulation();
     EvaluatePopulation();
     if(ccount>MAXGA)//进行RECL次以上的遗传运算然后找到最好的值
     break;
	}
     printf("best= %lf\n",mmax);
     fprintf(fp,"best= %lf\n",mmax);
	 return 0;
  
}

/**************************************************************************************************************/
/*                         种群第0代初始化函数　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　*/
/***************************************************************************************************************/
void GenerateInitialPopulation( )
{
    int i,j;
    srand( (unsigned)time( NULL ) );//初始化使得rand()函数每次随机产生的数不一样
    for(i=0;i<PopSize;i++)
    {
     for(j=0;j<CHROMLENGTH;j++)
     {
        population[i].chrom[j]=(rand()%10<5)?'0':'1';
     }
     population[i].chrom[CHROMLENGTH]='\0';
    //  printf("%s\n",population[i].chrom);
    // fprintf(,"%s\n",population[i].chrom);
     }
    //fprintf(fp,"初始化结束\n");
    //printf("初始化结束\n");

}
/*******************************************************************************************************************
/*      评价函数                                                                                                           */
/*******************************************************************************************************************/
void EvaluatePopulation()//评价函数
{
    CalculateObjectValue();//计算目标值
    CalculateFitnessValue();//计算适合值
    FindBestWorstIndividual();//找最好的最差的个体
    
}
/*************************************************************************************************
                                   种群第1代初始化函数
**************************************************************************************************/
void GenerateNextPopulation()
{
    SelectionOperator();//选择
    CrossoverOperator();//交叉
    MutationOperator();//变异
}
/**********************************************************************************************
二进制转十进制
***********************************************************************************************/


int DecodeChromosome(char *string,int point ,int length)//二进制转十进制
{
   int decimal=0;
   char *pointer;
   int i;
   for(i=0,pointer=string+point;i<length;i++,pointer++)
   {
         decimal+=(*pointer-'0')<<(length-1-i);
   }
   return decimal;
   
}
/*************************************************************************************
*                         计算目标函数值                                             *
*                  f(x1,x2)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);                 * 
*          3905.926227                                                               *
**************************************************************************************/
void CalculateObjectValue()
{
   int i;
   int 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()
{
      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 FindBestWorstIndividual()
{
     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()
{
     if(bestindividual.fitness >currentbest.fitness )
     {
         currentbest=population[best_index];
     }
     else
     {
         population[worst_index]=currentbest;
     }
}
/***********************************************************************************************
                    　　进行选择运算
*************************************************************************************************/
 void  SelectionOperator()
{
    int i,index;
    double p,sum=0.0;
    double cfitness[POPSIZE];//计算适应度
    struct individual newpopulation[POPSIZE];
    srand( (unsigned)time( NULL ) );//保证rand()每次产生的数不一样

    //计算相关适应度
    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]
    {
        population[i]=newpopulation[i];
      // printf("%s\n",population[i].chrom);
	}
// printf("选择结束\n");
}

/*******************************************************************************
       　　　　　　　　　　进行交叉运算
*********************************************************************************/
void CrossoverOperator()
{
    int i,j;
    int index[POPSIZE];
    int point,temp;
    double p;
    char ch;
    srand( (unsigned)time( NULL ) );//保证rand()每次产生的数不一样


    //进行随机交叉
    for(i=0;i<PopSize;i++)
    index[i]=i;
    for(i=0;i<PopSize;i++)
    {
       point=rand()%(PopSize-i);
       temp=index[i];
       index[i]=index[point+i];
       index[point+i]=temp;
    }
    //单点交叉
    for(i=0;i<PopSize;i+=2)
    {
        p=rand()%1000/1000.0;
        if(p<Pc)
		{
          point=rand()%(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;
		  }

		}
// printf("%s\n",population[i].chrom);
 // fprintf(fp,"%s\n",population[i].chrom);
	}
  //  printf("交叉结束\n");
    // fprintf(fp,"交叉结束\n");

}

/*********************************************************************************************
              　　　　　　　　　 进行变异运算
**********************************************************************************************/
void MutationOperator()
{
    int i,j;
    double p;
    srand( (unsigned)time( NULL ) );//保证rand()每次产生的数不一样


    //位变异
    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';
			}
	   }
      // printf("%s\n",population[i].chrom);
	}
   // printf("变异结束\n");
}
/**********************************************************************************************
                           打印结果
***********************************************************************************************/
void OutputTextReport()
{
    int i;
    double sum;
    double average;