ga.cpp

基因算法（GA） GA 是一种启发式的优化法 （heuristic optimization method）

#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define popsize 100                    //种群大小
#define totalgen 100                   //遗传总代数
#define pm 0.2                         //变异概率
#define pc 0.4                         //交换概率
#define w 0.001157                     //旋转角速度
#define n 3
//#define maxJ 500               //求适应度函数的常参数
 struct individual                     //个体
  {
        double chromosome;              //染色体
        double J;                //个体对应的变量值
        double fitness;                //个体适应度
        double totalfitness;             //累计适应度
  };

 struct individual nowpop[100];        //当前代种群
 struct individual nextpop[100];        //新一代种群
 double min;                             //目标变量T所允许的最小值
 double max;                             //目标变量T所允许的最大值
 double maxJ=500;                            //为变量J找到最大的值
 float  k;                             //燃料与时间的比例权值
 double p0[n][1];                       //初始相对位置
 double v0[n][1];                      //初始相对速度
 double av1[n][1];                                  //起始速度增量
 double av2[n][1];                                  //终端速度增量

 double randf()
 {
        return   (double)(rand()/(double)32767);
 }



void calSpeed(double chromosome)                       //计算v1v2
{
     int i,j;
	 double q=w*chromosome;
     double temp[n][n];                                //临时存放计算数据
     double temp1[n][n];
	 double temp2[n][1];                               //临时存放计算数据
	 double temp3[n][1];                               //临时存放计算数据
	 for(i=0;i<3;i++)
		 for(j=0;j<3;j++)
		 {
              temp[i][j]=0;
			  temp1[i][j]=0;
		 }
     for(i=0;i<3;i++)
	 {
		 temp2[i][0]=0;
		 temp3[i][1]=0;
	 }
  double a11;
	  a11=sin(q);
  double a12;
	  a12=14*(1-cos(q))-6*q*sin(q);
  double a21;
	  a21=-2*(1-cos(q));
  double a22;
	  a22=4*sin(q)-3*q*cos(q);
  double a33;
	  a33=-cos(q);
  double b;
	  b=3*q*sin(q)-8*(1-cos(q));
  double t11[3][3]={a11/b,a12/b,0,
                    a21/b,a22/b,0,
	                0,  0,      a33};
  double t12[3][3]={(4*cos(q)-3),-2*sin(q),0,
                     2*sin(q),cos(q),0,
					 0,0,cos(q)};
  double t21[3][3]={0,-6*w*(1-cos(q)),0,
                    0,3*w*sin(q),0,
					0,0,-w*sin(q)};
  for(i=0;i<3;i++)
	 {
       av1[i][0]=0;
       av2[i][0]=0;
	 }
   for(i=0;i<3;i++)
		 for(j=0;j<3;j++)
		 {
              temp[i][j]=w*t11[i][j];
		 }
   for(i=0;i<3;i++) 
   {  
       temp2[i][0]=temp[i][0]*p0[0][0]+temp[i][1]*p0[1][0]+temp[i][2]*p0[2][0];
   }
   for(i=0;i<3;i++)
   {
       av1[i][0]=temp2[i][0]-v0[i][0];
   }
    for(i=0;i<3;i++)
		 for(j=0;j<3;j++)
		 {
              temp[i][j]=w*t12[i][j];
		 }
    for(i=0;i<3;i++)
		 for(j=0;j<3;j++)
		 {
              temp1[i][j]=temp[i][0]*t11[0][j]+temp[i][1]*t11[1][j]+temp[i][2]*t11[2][j];
		 }
    for(i=0;i<3;i++)
		 for(j=0;j<3;j++)
		 {
              temp1[i][j]=temp1[i][j]+t21[i][j];
		 }
    for(i=0;i<3;i++) 
		{  
           av2[i][0]=-(temp1[i][0]*p0[0][0]+temp1[i][1]*p0[1][0]+temp1[i][2]*p0[2][0]);
		}
   
}




void Jfitness(struct individual *a)                     //算适应度
 {
	    double temp;
		double temp2;
		calSpeed(a->chromosome);
		temp=sqrt(av1[0][0]*av1[0][0]+av1[1][0]*av1[1][0]+av1[2][0]*av1[2][0]);
		temp2=sqrt(av2[0][0]*av2[0][0]+av2[1][0]*av2[1][0]+av2[2][0]*av2[2][0]);
        a->J=(temp+temp2+k*a->chromosome)/1000;
        a->fitness=maxJ-a->J;
        a->J=a->J*1000;
 }
 
void Initialpop()                      //种群的初始化
{
	int i;
	cout<<"            以下是初代种群"<<endl;
    srand((unsigned) time(NULL));
	for(i=0;i<popsize;i++)
	{
         nowpop[i].chromosome=(max-min)*randf()+min;
		 cout<<nowpop[i].chromosome<<endl;
		 Jfitness(&nowpop[i]);
		 if(i==0)                                           //这里算好了总适应度
            nowpop[i].totalfitness=nowpop[i].fitness;
		 else
			nowpop[i].totalfitness=nowpop[i-1].totalfitness+nowpop[i].fitness;
	}
    cout<<"             初始种群结束"<<endl;
} 


int select()                   //有分歧
 {
	    srand((unsigned) time(NULL));
        double j=randf();
	    int i=0;
        for(;i<popsize;i++)
			if(j<nowpop[i].fitness/nowpop[popsize-1].totalfitness)
	    return i;  
			else 
				return -1;
 }

void crossover(int j)
{
	    double b=randf();                           //0 1间的随机数
		struct individual temp1,temp2;
        temp1.chromosome=nextpop[j].chromosome-b*(nextpop[j].chromosome-nextpop[j+1].chromosome);
        temp2.chromosome=nextpop[j+1].chromosome+b*(nextpop[j].chromosome-nextpop[j+1].chromosome);
        Jfitness(&temp1);
        Jfitness(&temp2);
        if(temp1.fitness>nextpop[j].fitness)   nextpop[j]=temp1;
        if(temp2.fitness>nextpop[j+1].fitness) nextpop[j+1]=temp2;
}



void mutation(int i,int generation)                   //变异
  {
	int R;
	int j;
	int b=500;
    double r;
    double flag;                                     
		R=rand()%2;
        r=randf();
    //flag=(max-min)*(1-pow(r,pow((1-generation/totalgen),b)));      //这个算子影响搜索空间的大小
	flag=b*(1-pow(r,(1-generation/totalgen)));
    if(R)
           nextpop[i].chromosome=nextpop[i].chromosome-flag;
    else
           nextpop[i].chromosome=nextpop[i].chromosome+flag;
           Jfitness(&nextpop[i]);
   }

void generations(int generation)                          //遗传
   {
    int  i;
	int  temp;
	int j;
	cout<<"第 "<<generation+1<<" 代种群:"<<endl;
    for(i=0;i<popsize;i++)
    {
        
        //temp=select();
		//if(temp!=-1)
        nextpop[i]=nowpop[i];
		//else
    }
    for(i=0;i<popsize*pc;i++)
    {
        j=rand()%(popsize-2);
		crossover(j);
    }
    for(i=0;i<popsize*pm;i++)
    {
         j=rand()%(popsize-1);
         mutation(j,generation);
    }
    for(i=0;i<popsize;i++)
    {
       nowpop[i]=nextpop[i];
       if(i==0) nowpop[i].totalfitness=nowpop[i].fitness;
       else   nowpop[i].totalfitness=nowpop[i-1].totalfitness+nowpop[i].fitness;
	  cout<<"运行时间T: "<<nowpop[i].chromosome<<"   J: "<<nowpop[i].J<<endl;
    }
}


void main()
{
	int i;                                                       //遗传代数的控制参数
	int x;
    double high;                                                     //目标轨道的高度
	cout<<"***********************Satelite rendezvous in GA*****************************"<<endl;
    cout<<"Please enter the data: "<<endl;
	cout<<"    1: Height of the target orbit:";
	cin>>high;
    cout<<"    2:Initial position:";
    for(i=0;i<3;i++)
	{
		cin>>p0[i][0];
	}
	cout<<"    3:Initial speed:";
	for(i=0;i<3;i++)
	{
		cin>>v0[i][0];
	}
	cout<<"    4:  K:";
    cin>>k;
	cout<<"    5:Minimum of T: ";
	cin>>min;
	cout<<"    6:Maximum of T: ";
	cin>>max;
    Initialpop();
	for(i=0;i<totalgen;i++)
            generations(i);
    for(i=1,x=0;i<popsize;i++)
            if(nowpop[i].J<nowpop[x].J)       x=i;
	cout<<"优化的时间为: "<<nowpop[x].chromosome<<endl;
	cout<<"优化的目标函数的最小值为: "<<nowpop[x].J;
	Jfitness(&nowpop[x]);
   }