ga.cpp

与遗传算法混合的模拟退火算法的应用

#include <string>
#include "ga.h"
#include <sys/time.h> 
#include <math.h>
#include <stdio.h> 
#include <stdlib.h>
#include <stack>
#define RAND1_MAX 1
float crossovert_ratio=0.6;
float mutation_ratio=0.03;
//int   module_number=fp.size();
vector<vector<int> > ModulecodeVector; 
//int	  InstanceNum;   


int SeqCross(int seqcross_a[], int seqcross_b[], int seqcross_num, int cp);
int Crossover(double pc, int crossover_size);

double sum(vector<double> &chain)             
{ //computer the sum
  double sum=0;
  for(int i=0; i < chain.size();i++)
     sum+= chain[i];
  return sum;
}

int max(vector<double> chain)
{ 
  int p;
  double max=0;
  for(int i=0; i < chain.size();i++)
   { 
     if(chain[i]>max)
        {
         max=chain[i];
         p=i; 
        }
    }
   return p;
}

int min(vector<double> chain)
{ 
  int p;
  double min=chain[0];
  for(int i=0; i < chain.size();i++)
   { 
     if(chain[i]<min)
        {
         min=chain[i];
         p=i; 
        }
    }
   return p;
}

int Equal_individual(int equal_a[],int equal_b[],int num)   //determine the same individual
{
	int i;
	for(i=0; i<num; i++)
		if(equal_a[i] != equal_b[i])
			return 0;
	return 1;
}

void re_order(int array[],int m,int n)     //array[m.....n]反序 
{
  int temp;
  int interval=(int)(n-m+1)/2;
  for(int i=0;i<interval;i++)
  {
   temp=array[n-i];
   array[n-i]=array[m+i];
   array[m+i]=temp;
  }
}


int CopySeq(int copyseq_a[], int copyseq_b[], int copyseq_num)  //	复制长度为num的数组b到数组a
//int		*copyseq_a;
//int		*copyseq_b;

{
	int i;
	for(i=0; i<copyseq_num; i++)
		copyseq_a[i] = copyseq_b[i];
	
}



int ExchangeSeq(int exchangeseq_a[], int exchangeseq_b[], int num)   //	交换长度为num的数组a[],b[]的值
//int		*exchangeseq_a;
//int		*exchangeseq_b;

{
	int temp;
	int i;
	for (i=0; i<num; i++){
		temp = exchangeseq_a[i];
		exchangeseq_a[i] = exchangeseq_b[i];
		exchangeseq_b[i] = temp;
	}

}


int Crossover(double crossovert_ratio, int module_number,int pop_size)   //	以pc为概率对规模为size的染色体种群ch实行交叉
{
	int		i, j;
	int		cp;                              //交叉位 
	int		Type;
	float	r;
	int     seq_a[module_number];
	int     seq_b[module_number];
	for (i=0; i<module_number; i++)
     {
		r = (rand()%1000000)/1000000.0;
		if (r < crossovert_ratio)
         {				
			for (j=i+1; j<pop_size; j++)
              {
				r = (rand()%1000000)/1000000.0;
				if (r < crossovert_ratio)	
                   {    for(int m = 0; m < module_number; m++)
                            {
                            seq_a[m] = ModulecodeVector[i][m];
                            seq_b[m] = ModulecodeVector[j][m];
                            }	
						cp = rand()%(int(module_number/2));
						SeqCross(seq_a, seq_b, module_number, cp);
						for(int m = 0; m < module_number; m++)
                            {
                            ModulecodeVector[i][m] = seq_a[m];
                            ModulecodeVector[j][m] = seq_b[m];
                            }
					}
				break;
			  }
		  }
			i = j;
		
	 }
	//return 1;
}


int SeqCross(int seqcross_a[], int seqcross_b[], int module_number, int cp)
//int	*seqcross_a; 
//int	*seqcross_b;
//int	seqcross_num;
//int	cp;	//对长度为num，交叉位为cp的两个整数序列编码a[]和b[]进行“常规交叉”
{
	int		i, j, k;
	int		ta[module_number+1];
	int		tb[module_number+1];

	CopySeq(ta, seqcross_a, module_number);
	CopySeq(tb, seqcross_b, module_number);
	for (i=cp; i<module_number; i++){	/* 获得交叉后的a[] */
		for (j=0; j<module_number; j++)
           {
			for (k=0; k<i; k++)
                {
				if (tb[j] == seqcross_a[k])
					break;
			     }
			if (k >= i) 
               {
				seqcross_a[i] = tb[j];
				break;
			   }
		   }
	}
	for (i=cp; i<module_number; i++){	/* 获得交叉后的b[] */
		for (j=0; j<module_number; j++){
			for (k=0; k<i; k++){
				if (ta[j] == seqcross_b[k])
					break;
			}
			if (k >= i) {
				seqcross_b[i] = ta[j];
				break;
			}
		}
	}
	//return 1;
}


void ga_floorplan(FPlan &fp,int iteration,int pop_size)
{
 vector<int> Modulecode;
 vector<double>  select_probability;     //select  probability 
 vector<double> area_ratio;
 
 vector<double> Area;
 
 stack<int> s1,s2;
 double sum_selectprobability;
 int fmax,fmin;                 //the best and worest individual
 int mutation_number;
 int temp_array[1000];
 string en;
 int iter_count=1;   //computer the iteration number
 int temp,count=2;
 int module_number=fp.size();
 //initial the population
 //-------------------------------------------------------------------------------------
 for(int i=0; i<module_number;i++)
  {
    Modulecode.push_back(i);     
  }  
 for(int j=0;j<pop_size;j++)
  { 
    for(int i=0; i<module_number;i++)
    {     
       Modulecode[i]=(Modulecode[i]+1)%module_number;
      }    
    ModulecodeVector.push_back( Modulecode); 
    if(j%module_number==0)
     {
       count++;
       temp= Modulecode[count];
       Modulecode[count]= Modulecode[count+1];
       Modulecode[count+1]=temp; 
      }
   } 
 
  en=fp.encode();
 cout<<"the initial population is :"<<endl<<endl;
  for(int j=0;j<pop_size;j++)
  {   
    for(int i=0;i<module_number;i++)
     {
      temp_array[i]=ModulecodeVector[j][i];
     }       
   fp.decode_tree(temp_array,en);
   fp.packing();
   area_ratio.push_back(100-fp.getDeadSpace());
   cout<<"the individual "<<j<<" area ration is :"<<area_ratio[j]<<endl;    
  }
  
//iteration begin  
  while(iter_count<iteration)
  {
    cout<<"the iteration "<<iter_count<<":"<<endl;
 
 //----------------------------------------------------------------------------------------------
 //strategy for select (roulette algorithm and protect the best individual)
   int st[pop_size];     //每个编码再一次中被选中的个数     
   double sum_arearation=sum(area_ratio);   //average of the efficacy
    for(int j=0;j<pop_size;j++)
    {
     select_probability.push_back(area_ratio[j]/sum_arearation);
      st[j]=0;
    }
  
   for(int i=0;i<pop_size;i++)
    {
      double   r=(double)(rand()%100000)/100000;  //精度为10^-4
	  double s = 0; 
      int  j = 0;
	  while (s < r) 
      {
		s += select_probability[j];
		j ++;
	   }
      st[j-1]++;
	}
	
   for(int i=0;i<pop_size;i++)
    { 
     if(st[i]==0)
       s1.push(i);
     else 
       if(st[i]>1)
         s2.push(i);
    }
   while(!s2.empty())
    {
     int p=s2.top();
     int copy_number=st[p]-1;
     for(int j=0;j<copy_number;j++)
      {
      for(int i=0;i<module_number;i++)
        ModulecodeVector[s1.top()][i]=ModulecodeVector[p][i];
      s1.pop(); 
      }
     s2.pop();
    }
     
 //-----------------------------------------------------------------------------------------
 //list this iteration information	
	
/*	for(int j=0;j<pop_size;j++)
    {   
      for(int i=0;i<module_number;i++)
      {
      cout<<ModulecodeVector[j][i]<<"  ";
      } 
      cout<<"   ";
      cout<<"select_probability["<<j<<"]  = "<<select_probability[j]<<" ";
      cout<<"    "<<st[j];
      cout<<endl;
    }   */
 //----------------------------------------------------------------------------------------------
 //crossovert operation	
Crossover(crossovert_ratio, module_number,pop_size);   //调用交叉函数 
 
 //----------------------------------------------------------------------------------------------
 //mutation operation
   mutation_number=int(module_number*mutation_ratio);  
   int mutation_position= rand()%(module_number-mutation_number); //the position of  mutate  
   int mutation_encoding= rand()%pop_size;   // rand a  code mutating
 //ModulecodeVector[mutation_encoding][mutation_position~(mutation_position+mutation_number)]  
   for(int i=0;i<module_number;i++)
     {
      temp_array[i]=ModulecodeVector[mutation_encoding][i];
     } 
   re_order(temp_array, mutation_position,mutation_position+mutation_number);
 //----------------------------------------------------------------------------------------------
 //produce the new population and show them
    area_ratio.clear();
    
    for(int j=0;j<pop_size;j++)
    {   
      for(int i=0;i<module_number;i++)
      {
       temp_array[i]=ModulecodeVector[j][i];
      }       
      fp.decode_tree(temp_array,en);
      fp.packing();
      //area_ratio.push_back(100-fp.getDeadSpace());
      Area.push_back(fp.getArea()*1e-6);
    }
 //------------------------------------------------------------   
   	for(int j=0;j<pop_size;j++)
    {   
      for(int i=0;i<module_number;i++)
      {
      cout<<ModulecodeVector[j][i]<<"  ";
      } 
      //cout<<"   "<<area_ratio[j];
      cout<<"   "<<Area[j];
      cout<<endl;
    }   
    //fmax=max(area_ratio);
    //fmin=min(area_ratio); 
    fmax=max(Area);
    fmin=min(Area); 
    
    for(int i=0;i<module_number;i++)
     {
       //ModulecodeVector[fmin][i]=ModulecodeVector[fmax][i];    //the best take the place of the worst
      ModulecodeVector[fmax][i]=ModulecodeVector[fmin][i];
      }   
    //area_ratio[fmin]=area_ratio[fmax];  
    Area[fmax]=Area[fmin];
    cout<<"the best individual's area is "<<Area[fmin]<<endl;
    //cout<<"the best individual's area ratio is"<<area_ratio[fmax]<<endl;
 //---------------------------------------------------------------------------------------------
   iter_count++;   //iteration number add one 
   }
 }