moga2.cpp

多目标遗传算法优化程序

#include "moga2.h"
#include "aleatorio.h"

Representacion::Representacion(int b,int ngenes,double *linf, double *lsup, int *pres,int iguales){
  int j=0;
  bits=0;
  base=b;  
  presicion=new(int[ngenes]);
  bitsXgene=new(int[ngenes]);
  lInf=new(double[ngenes]);
  lSup=new(double[ngenes]);
  for(int i=0;i<ngenes;i++){
    presicion[i]=pres[j];//cuantos decimales de presicion se trabajara
    //calculo del numero de bits
    bitsXgene[i]=(int)ceil(log((lsup[j]-linf[j])*pow(10,pres[j])*1.000001)/log(base));
    bits+=bitsXgene[j];
    lInf[i]=linf[j];//lower bound
    lSup[i]=lsup[j];//upperbound
    if(iguales!=1)j++;
  }
  cout<<bits<<"bits\n";
  nGenes=ngenes;
}
int Representacion::retBits(){
  return bits;
}

Representacion::~Representacion(){
  delete [] presicion;
  delete [] bitsXgene;
  delete [] lInf;
  delete [] lSup;
}

/*
 Metodo que copia un arreglo de enteros (genotipo) hacia memoria y regresa un puntero hacia ese espacio de memoria 
*/

void Representacion::copia(int *num,int *num2,int n)
{
  int *pnum=num;
  for(int i=0;i<n;i++,pnum++,num2++)//recorre todo el genotipo,haciendo
    *pnum=*num2;//una copia hacia la memoria creada.
}

void Representacion::copia(double *num,double *num2,int n)
{
  double *pnum=num;
  for(int i=0;i<n;i++,pnum++,num2++)//recorre todo el genotipo,haciendo
    *pnum=*num2;//una copia hacia la memoria creada.
}

/*
Metodo que convierte de Gray a binario
*/
int *Representacion::gray_A_binario(int *g){
  int *b=new int[bits];
  int *pb;
  pb=b;
  int valor=*g;
  *pb=valor;
  g++;
  pb++;
  for(int k=1;k<bits;k++,g++,pb++){
    if(*g==1)valor=(valor==1)?0:1; //simula el not.
    *pb=valor;
  }
  return b;
}

/*
  metodo que a partir de un arreglo de enteros (genotipo(simulacion de arreglo binario)) de codifica su valor (fenotipo) dentro de un rango minimo y un rango maximo 
*/
double Representacion::decodifica (int cual,int *num)
{
  double fenotipo=0.0;
  int cantbits=0;
  int i;
  int *cadena,*pb;
  if(base==2) //si es base 2 entonces  decodifica a binario
    cadena=gray_A_binario(num);
  else cadena=num;
  for(i=0;i<cual;i++)
    cantbits+=bitsXgene[i];
  
  pb=cadena;
  for(i=0;i<bitsXgene[cual];i++)//recorrer todo el genotipo, para hacer la suma
    fenotipo+=ldexp(pb[i+cantbits],i);//de las potencias de dos reespectivas y
  if(base==2)
    delete [] cadena;
  double regreso=(lInf[cual]+fenotipo*(lSup[cual]-lInf[cual])/(pow(base,bitsXgene[cual])-1));  //mediante la formula que dio en clase adecuo los valores dentro de los 
  return regreso;
}

/*
metodo que imprime el genotipo
*/
void Representacion::imprime(double *num,int n)
{
  for(int i=0;i<n;i++,num++)//recorre el genotipo, e imprime su valor.
    cout<<*num<<" ";
}

void Representacion::imprime(int *num,int n){
  for(int i=0;i<n;i++,num++)//recorre el genotipo, e imprime su valor.
    cout<<*num<<" ";
}

/*
  metodo que genera un genotipo con la seleccion del valor de los alelos al azar con probabilidad de 0.5
*/
int *Representacion::genera(){
  int *gtemp,*genotipo;
  genotipo=new(int[bits]);//asigna memoria hacia el genotipo a generar
  gtemp=genotipo;
  for(int i=0;i<bits;i++,gtemp++){//genera el genotipo, alelo a alelo,mediante
   *gtemp=(int)Aleatorio(0,base-1);//probabilidad.
  }
  return genotipo;//regresa el genotipo generado
}

/*
  metodo que genera un genotipo con la seleccion del valor de los alelos al azar con probabilidad de 0.5
*/
int *Representacion::inicializa(){
  int *gtemp,*genotipo;
  genotipo=new(int[bits]);//asigna memoria hacia el genotipo a generar
  gtemp=genotipo;
  for(int i=0;i<bits;i++,gtemp++)//genera el genotipo, alelo a alelo,mediante
    *gtemp=0;//probabilidad.
  return genotipo;//regresa el genotipo generado
}

/*
  Metodo que cruza dos genotipos, a partir de dos posiciones dadas
  (cruza de dos puntos)
*/
void Representacion::cruza(int *padre1,int *padre2,int posicion1,int posicion2){
  int cambio;
  for(int i=0;i<bits;i++,padre1++,padre2++){
    cambio=(posicion1<=i&&i<=posicion2)?1:0;
    if(cambio){
      int t=*padre1;
      *padre1=*padre2;
      *padre2=t;
    }
  }
}

/*
  metodo que muta a un genotipo a partir de una probabilidad dada y regresa el numero de mutaciones efecutadas
*/
int Representacion::muta(int *padre,float Pm){
  int *ptemp, mutaciones=0,r;
  ptemp=padre;
  for(int i=0;i<bits;i++,ptemp++){//recorre el genotipo, y si el flip da 
    int valor=flip(Pm);
    if(valor){//1 entonces muta
      mutaciones++;
      do{
	r=(int) Aleatorio(0,base-1);}
      while(r==*ptemp);
      *ptemp=r;
    }
  }
  return mutaciones;//regresa el total de las mutaciones.
}


/*
  Metodo donde se efectua la cruza, y la mutacion.

 */
void MOGAII::CruzaYMutacion(){
  //se recorre la poblacion generada, de 2 en dos, y de acuerdo al Pc y a Pm 
  //se cruzan y se mutan
  int pDeCruza[2],menor;
  for(int i=0;i<M;i+=2){
    if(flip(Pc)){//para checar si va a haber cruza
      pDeCruza[0]=(int)Aleatorio(1,bits-2);//se busca el punto de 
      //cruza1 y dos  y se realiza la cruza
      do
	pDeCruza[1]=(int)Aleatorio(1,bits-2);
      while(pDeCruza[1]==pDeCruza[0]);
      menor=(pDeCruza[0]<pDeCruza[1])?0:1;
      cruza(poblacionNueva[i].genotipo,poblacionNueva[i+1].genotipo,pDeCruza[menor],pDeCruza[1-menor]);
    }

    muta(poblacionNueva[i].genotipo,Pm);//se muta de acuerdo a Pm
    muta(poblacionNueva[i+1].genotipo,Pm);//se muta de acuerdo a Pm
    evalua(poblacionNueva[i].genotipo,poblacionNueva[i].aptObj);//se calcula su aptitud
    evalua(poblacionNueva[i+1].genotipo,poblacionNueva[i+1].aptObj);//se calcula su aptitud
  }
}

/*Selecci'on por universal estocastico:
Propuesta por Baker (1987)
El objetivo es minimizar la mala distribuci'on de los individuos en la poblaci'on en funci'on de sus valores esperados.
El algoritmo es O(n)

*/
void MOGAII::Seleccion(){
	int i;
  double media=0;
  //se recorre la poblacion, para encontrar al mas apto, y se almacena
  //tambien en este ciclo se hace la suma de aptitudes
  
  sumaValores=0;
  //Calculo de los valores esperados.
  for( i=0;i<M;i++)
    sumaValores+=poblacion[i].apt;//se hace la suma de aptituds

  media=sumaValores/M;//se saca la media (aptitudes entre poblacion
  for( i=0;i<M;i++){
    poblacion[i].valEsp=poblacion[i].apt/media;
  }
  /*  
  for(int i=0;i<M;i++)
   cout<<poblacion[arrordenado[i]].valEsp<<endl;
  
    exit(0);
  */
}

void MOGAII::NuevaPoblacion()
{
  double aleatorio;
    //generacion de la nueva poblacion a partir de la ruleta
  double ptr=Aleatorio2(0,1);//probabilidad.
  double sum=0.0;
  int j=0;
  for(int i=0;i<M;i++){
    int repetido=0;
    for(sum+=poblacion[arrordenado[i]].valEsp;sum>ptr;ptr+=1,j++){
      copia(poblacionNueva[j].genotipo,poblacion[arrordenado[i]].genotipo,bits);//se almacena el genotipo seleccio;//nado y se dispone ha generar al 2oindividuo
      poblacionNueva[j].rank=poblacion[arrordenado[i]].rank;     
      //      if(repetido>1)cout<<"encontre uno\n";
      repetido++;

    }
  }
}

void MOGAII::GenerarPoblacionAleatoria(){
  poblacion=new (Individuo[M]);
  poblacionNueva=new (Individuo[M]);
  for(int i=0;i<M;i++){
    poblacion[i].genotipo=genera();
    poblacionNueva[i].genotipo=genera();
    poblacion[i].aptObj=new (double[nObjs]);
    poblacionNueva[i].aptObj=new (double[nObjs]);
    poblacion[i].aptObjEsc=new (double[nObjs]);
    poblacionNueva[i].aptObjEsc=new (double[nObjs]);
    poblacion[i].loc=0;
    poblacionNueva[i].loc=0;
    //    evalua(poblacion[i].genotipo,poblacion[i].aptObj);
  }
}
void MOGAII::EvaluarPoblacion(){
  for(int i=0;i<M;i++)
    evalua(poblacion[i].genotipo,poblacion[i].aptObj);
}
void MOGAII::evalua(int *genotipo,double *aptObj){
  double x1,x2;
  double q_=4,alfa=2,PI=3.1415926;
  x1=decodifica(0,genotipo);
  x2=decodifica(1,genotipo);
  aptObj[0]=x1;
  aptObj[1]=(1+10*x2)*(1-(pow(x1/(1+10*x2),alfa))-(x1/(1+10*x2)*sin(2*PI*q_*x1)));

}
void MOGAII::NuevaGeneracion(){
  Individuo *poblatemp;
  poblatemp=poblacion;//ahora la poblacion incial, va a ser la que
  poblacion=poblacionNueva;//va a ser generada (pero sin adicion extra de memoria)
  poblacionNueva=poblatemp;//y la generada, ahora se convierte en la
  //padre
}

MOGAII::MOGAII(int gmax,int m, double pc, double pm,int ngenes,int nobjs,double *linf, double *lsup, int *pres,int tampareto):Representacion(2,ngenes,linf,lsup,pres,1){

  M=m;
  Pc=pc;
  nGenes=ngenes;
  nObjs=nobjs;
  Pm=pm;
  Gmax=gmax;
  srand(time(0)); 
  malla=new MallaAdap(nobjs,tampareto,bits);
}

void MOGAII::ImprimeValores(){
  for(int i=0;i<M;i++){
    if(poblacion[i].rank==1)
	cout<<poblacion[i].aptObj[0]<<" "<<poblacion[i].aptObj[1]<<endl;
  }
}

/*
  Funcion que indica si un individuo domina a otro
si el primero domina al segundo retorna 1
si el segundo domina al primero retoruna -1
si son iguales retorna 0
si ninguno domina retorna 11
*/

int MOGAII::Domina(Individuo *I1,Individuo *I2){

  
  int anterior = 0;
  int mejor;
  double *ind1=I1->aptObj;
  double *ind2=I2->aptObj;
  /*
  if (ind1[0]<=ind2[0]&&ind1[1]<ind2[1] || ind1[0]<ind2[0]&&ind1[1]<=ind2[1])return 1;
  else if(ind1[0]>=ind2[0]&&ind1[1]>ind2[1] || ind1[0]>ind2[0]&&ind1[1]>=ind2[1])return -1;
  else return 0;
  */
  
  //  int a=restricciones(I1->genotipo);
  //  int b=restricciones(I2->genotipo);
  //  if(a<b)//el primero domina
  //    return 1;
  //  else if(b<a)//el segundo domina
  //    return -1;
  for(int i=0;i<nObjs;i++,ind1++,ind2++){
    if(*ind1 <*ind2)	mejor = 1;
    else if(*ind2<*ind1)mejor = -1;
    else mejor = 0;
    if(mejor!=anterior&&anterior!=0&&mejor!=0) return(11);
    if(mejor!=0) anterior = mejor;
  }
  return(anterior);
  
}

void MOGAII::AsignarJerarquia(){
	int i,j;
  NMayor=0;
  Individuo *pp=poblacion;

  for( i=0;i<M;i++)
    poblacion[i].rank=1;

  for( i=0;i<M;i++){
    for(int j=0;j<M;j++){
      switch(Domina(pp+i,pp+j)){
      case 11://nadie domina
      case 0://son iguales
	break;//no pasa nada
      case 1://el primero domina al segundo
	//poblacion[j].rank++;
	//if(NMayor<poblacion[j].rank)NMayor=poblacion[j].rank;
	break;
      case -1://el segundo domina al primero
	poblacion[i].rank++;
	if(NMayor<poblacion[i].rank)NMayor=poblacion[i].rank;
	break;
      }
    }
  }
  //  ImprimeValores();
  //exit(0);
}

void MOGAII::AsignarAptitudLineal(){
	int i,j,k,l;
  double *sumatoriaApt=new (double[M]);
  int *cantidadSumApt=new(int[M]);

  arrordenado=new(int[M]);

  for( i=0;i<M;i++){
    sumatoriaApt[i]=0;
    cantidadSumApt[i]=0;
    arrordenado[i]=0;
  }
  //ordenamiento del arreglo mediante llaves en arrordenado y calculo de la aptitud
  for( i=0,k=M+1,l=0;i<M;i++){
    for( j=0;j<M;j++){
      if(poblacion[j].rank==i+1){
	sumatoriaApt[poblacion[j].rank-1]+=pow(k,2);
	cantidadSumApt[poblacion[j].rank-1]++;
	k--;
	arrordenado[l]=j;
	l++;
      }
    }
  }

  //promediar la aptitud de los individuos con similar jerarqu'ia
  for(i=0;i<M;i++){
    poblacion[i].apt=sumatoriaApt[poblacion[i].rank-1]/cantidadSumApt[poblacion[i].rank-1];
    //    cout<<poblacion[arrordenado[i]].apt<<endl;
  }
}

void MOGAII::calculoSigmaShare(){
	int i,j;
  double *max=new double[nObjs];
  double *min=new double [nObjs];
  double sumatoria=0;
  for( i=0;i<nObjs;i++){
    min[i]=10*pow(10,5);
    max[i]=-10*pow(10,5);
  }
  for( i=0;i<M;i++){
    for( j=0;j<nObjs;j++){
      min[j]=(min[j]<poblacion[i].aptObj[j])?min[j]:poblacion[i].aptObj[j];
      max[j]=(max[j]>poblacion[i].aptObj[j])?max[j]:poblacion[i].aptObj[j];
    }
  }
  for( i=0;i<nObjs;i++)
    sumatoria+=pow(max[i]-min[i],2);
  q=3;
  sigmaShare=sumatoria/(M-1);

  //sigmaShare=sqrt(sumatoria)/pow(2*q,1/nObjs);
  
  //cout<<sigmaShare<<endl;
}


void MOGAII::EscalarApt(){

	int i,j;
  double *max=new(double[nObjs]);
  for( i=0;i<nObjs;i++)
    max[i]=-10000;
  for( i=0;i<M;i++)
    for(j=0;j<nObjs;j++)
      max[j]=(poblacion[i].aptObj[j]>max[j])?poblacion[i].aptObj[j]:max[j];
  for( i=0;i<M;i++)
    for( j=0;j<nObjs;j++)
      poblacion[i].aptObjEsc[j]=poblacion[i].aptObj[j]/max[j];
}

void MOGAII::AsignarAptitudCompartida(){
	int i,j,k;
  double *sumatoriaPhis=new(double[M]);
  for( i=0;i<M;i++)sumatoriaPhis[i]=0;

  for( i=0;i<M;i++){
    for( j=i+1;j<M;j++){
      double dist=0;
      for( k=0;k<nObjs;k++)
	dist+=pow(poblacion[i].aptObjEsc[k]-poblacion[j].aptObjEsc[k],2);
      dist=sqrt(dist);
      if(dist<sigmaShare){
	sumatoriaPhis[i]+=1-(dist/sigmaShare);
	sumatoriaPhis[j]+=1-(dist/sigmaShare);
      }
    }
    poblacion[i].apt/=sumatoriaPhis[i];
    poblacion[i].apt+=1/(poblacion[i].rank);
  }
}

void MOGAII::Algoritmo(){
int i;
  GenerarPoblacionAleatoria();
  Individuo *pp=poblacion;
    EvaluarPoblacion();

    AsignarJerarquia();
    AsignarAptitudLineal();
    calculoSigmaShare();
    EscalarApt();
    AsignarAptitudCompartida();
    for( i=0;i<M;i++)
      malla->FunPARETO(pp+i);

  for( i=0;i<Gmax;i++){
    Seleccion();
    NuevaPoblacion();
    CruzaYMutacion();
    NuevaGeneracion();

    AsignarJerarquia();
    AsignarAptitudLineal();
    calculoSigmaShare();
    EscalarApt();
    AsignarAptitudCompartida();

   for( i=0;i<M;i++)
    malla->FunPARETO(pp+i);
  }
  malla->ImprimeValores();
  //ImprimeValores();
}


int main(){
  double *linf,*lsup;
  int *pre,p=6;
  int nObjs=2;
  int nGenes=2;
  double pc=0.8;
  double pm=1.0/40.0;
  int gmax=200;
  int m=100;
  int tampareto=100;
  linf=new(double[nObjs]);
  linf[0]=0;
  linf[1]=0;
  lsup=new(double[nObjs]);
  lsup[0]=1;
  lsup[1]=1;
  pre=new(int[nObjs]);
  pre[0]=6;
  pre[1]=6;

  MOGAII moga2(gmax,m,pc,pm,nGenes,nObjs,linf,lsup,pre,tampareto);
  moga2.Algoritmo();
  cout<<"the program is over"<<endl;
  return 0;
}