package optimizacion;

import java.util.Random;

/**
 * <p>Title: Algoritmos geneticos binarios</p>
 * <p>Description: Minimiza una funcion utilizando la heuristica
 * basada en la evolucion de las especies</p>
 * <p>Copyright: Copyright (c) 2007</p>
 * <p>Company: UMSNH</p>
 * @author Dr. Felix Calderon Solorio
 * @version 1.0
 */

public class geneticos_binarios {
    int Npar,Npop,Ngood,Nans,Nmut,Ngene, Niter;
    int Cromosomas[][][], Parejas[][];
    double Costos[],CostoN[],Rangos[][];
    Random r;

    public geneticos_binarios(int poblacion, int parametros, int iter, int genes, double Ran[][])
    {
        Npar  = parametros;        // numero de parametros.
        Npop  = poblacion;         // Tama�o de la poblacion.
        Ngood = Npop/4;            // Dimension para los mejores.
        Nans  = Npop/8;            // Numero de parejas.
        Nmut  = (int)(Npop*0.05);  // Numero de mutaciones.
        Ngene = genes;             // Tama�o de los genes
        Niter = iter;              // Numero de generaciones

        Cromosomas = new int[Npop][Npar][Ngene];
        Costos     = new double[Npop];
        CostoN     = new double[Npop/2];
        Rangos    = new double[Npar][2];
        for(int i=0; i<Npar; i++)
        {
            Rangos[i][0] = Ran[i][0];
            Rangos[i][1] = Ran[i][1];
        }
        Parejas   = new int[Nans][Npar];
        r = new Random();
    }

    /**
     * Rutina principal que itera el algoritmo genetico
     */

    public void Itera()
    {
      r.nextDouble();
      genera_poblacion();

      for (int k = 0; k < Niter; k++) {
          Parejas();
          Aparea();
          Mutacion();
          ordena();
          System.out.print("En la generacion = " + k + ", el mejor costo es " +
                           Costos[0] + " [");
          for (int j = 0; j < Npar; j++)
              System.out.print(decodificar(Cromosomas[0][j], j) + ",  ");
          System.out.println("]");
      }
      //imprime();
      System.out.println("El mejor costo es " +
                         Costos[0]);
    }

    /**
     * Rutina de generaci�n de la poblaci�n inicial
     */

    public void genera_poblacion()
    {
      int i, j;
      int k = 0;

      for (i = 0; i < Npop; i++) {
        k = 0;
        for (j = 0; j < Npar; j++) {
          GeneraCromosoma(i, j);
        }
        Costos[i] = funcion(Cromosomas[i]);
      }
      ordena();
      //imprime();

      Npop /= 2.0;
    }

    /**
     * Rutina para calcular el crosoma correspondiente al
     * i-esimo individuo en su j-esimo parametro
     * @param i int numero de individuo
     * @param j int numero de parametro
     */

    public void GeneraCromosoma(int i, int j)
    {
      int k;

      for(k=0; k<Ngene; k++)
        Cromosomas[i][j][k] = (int) (r.nextDouble() + 0.5);
    }

    /**
     * Genera parejas aleatorias utilizando ponderacion
     * basada en costos
     */

    public void Parejas()
    {
      int i, j;
      double suma = 0, ant = 0;

      for(i=0; i<Ngood; i++) suma += (Costos[i] - Costos[Ngood]);

      for(i=0; i<Ngood; i++)
      {
        ant += (Costos[i] - Costos[Ngood]) / suma;
        CostoN[i] = ant;
      }

      for(i=0; i<Nans; i++)
      {
        for (j = 0; j < Npar; j++) {
          Parejas[i][j] = Busca(CostoN, Ngood, r.nextDouble());
        }
      }
    }

    /**
     * Busca al elemento con probabilidad mas cercana
     * @param A double[]
     * @param n int
     * @param azar double
     * @return int
     */

    public int Busca(double A[], int n, double azar)
    {
      for(int i=0; i<n; i++)
        if(A[i] > azar) return i;

      return 1;
    }

    /**
     * Crea dos nuevos individuos a partir de un
     * padre y una madre
     */

    public void Aparea()
    {
      int i, j, k, l, p, m;
      int aux, nbits, azar;

      l     = Ngood;
      azar  = (int) Math.round(r.nextDouble() * (double) (Npar*Ngene -1));
      nbits = 0;

      for (i= 0; i < Nans; i++) {
        m = Parejas[i][0];
        p = Parejas[i][1];

        for(i=0; i<Npop; i++)
          for(j=0; j<Npar; j++)
            for(k=0; k<Ngene; k++)
            {
              if(nbits > azar){
                aux = p;
                p   = m;
                m   = aux;
              }
              Cromosomas[l][j][k]   = Cromosomas[m][j][k];
              Cromosomas[l+1][j][k] = Cromosomas[p][j][k];
              nbits++;
            }
        l+=2;
      }
      for (i = Ngood; i < Npop; i++)
        Costos[i] = funcion(Cromosomas[i]);
    }

    /**
     * Realiza la mutaci�n de los individuos sin tocar
     * al mas apto
     */

    public void Mutacion()
    {
      int i, j, k, n;

      for(n=0; n<Nmut; n++)
      {
        i = 1 + (int) Math.round(r.nextDouble() * (double) (Npop - 2));
        j = (int) Math.round(r.nextDouble() * (double) (Npar - 1));
        k = (int) Math.round(r.nextDouble() * (double) (Ngene - 1));
        if(Cromosomas[i][j][k] == 1)
          Cromosomas[i][j][k] = 0;
        else  Cromosomas[i][j][k] = 1;
        Costos[i] = funcion(Cromosomas[i]);
     }
    }

    /**
     * Codifica el parameto de real a binario
     * @param P double
     * @param k int
     * @return int[]
     */

    public int[] codificar(double P, int k)
    {
      double Pnorm = (P - Rangos[k][0])/(Rangos[k][1] - Rangos[k][0]);
      double suma;
      int gene[] = new int[Ngene];
      int i, aux;

      for(i=0; i<Ngene; i++)
      {
        Pnorm *= 2.0;
        aux = (int) Pnorm;
        gene[i] = aux;
        Pnorm -= aux;
      }
      return gene;
    }

    /**
     * Calcula el valor de un gen en binario a real
     * @param gene int[]
     * @param k int
     * @return double
     */

    public double decodificar(int gene[], int k)
    {
      int i, n = gene.length;
      double suma = 0, fac = 0.5, valor;

      for(i=0; i<n; i++)
      {
        suma += gene[i]*fac;
        fac /=2.0;
      }

      valor = suma*(Rangos[k][1] - Rangos[k][0]) + Rangos[k][0];
      return valor;
    }

    /**
     * Rutina de ordenamiento
     */

    public void ordena()
    {
        quiksort(0, Npop - 1);
        //burbuja();
    }

    /**
     * Metodo de ordenamiento de la burbuja
     */

    public void burbuja()
    {
      int i, j, k, li;
      boolean bandera = true;
      double aux;
      int aux2;

      while(bandera)
      {
        bandera = false;

        for(i=0; i<Npop-1; i++)
        {
          if(Costos[i] > Costos[i+1])
          {
            aux = Costos[i];
            Costos[i] = Costos[i + 1];
            Costos[i + 1] = aux;

            for (k = 0; k < Npar; k++) {
              for(li = 0; li< Ngene; li++) {
                aux2 = Cromosomas[i][k][li];
                Cromosomas[i][k][li] = Cromosomas[i + 1][k][li];
                Cromosomas[i + 1][k][li] =  aux2;
              }
            }
            bandera = true;
          }
        }
      }
    }

    /**
   * Algoritmo de ordenamiento de quicksort
   * @param lo int l�mite inferior
   * @param ho int l�mite superior
   */

  public void quiksort(int lo,int ho)
  {
    int  l = lo, h = ho, aux2;
    double aux, mid;

    if (ho > lo) {
      mid = Costos[ (lo + ho) / 2];
      while (l < h) {
        while ( (l < ho) && (Costos[l] < mid)) ++l;
        while ( (h > lo) && (Costos[h] > mid)) --h;
        if (l <= h) {

          aux = Costos[l];
          Costos[l] = Costos[h];
          Costos[h] = aux;

          for (int k = 0; k < Npar; k++) {
            for(int li = 0; li< Ngene; li++) {
              aux2 = Cromosomas[l][k][li];
              Cromosomas[l][k][li] = Cromosomas[h][k][li];
              Cromosomas[h][k][li] =  aux2;
            }
          }
          ++l;
          --h;
        }
      }

      if (lo < h)
        quiksort(lo, h);
      if (l < ho)
        quiksort(l, ho);
    }
  }

  /**
   * imprime los valores
   */

  public void imprime()
    {
      int i, j, k;
      double f;

      for(i=0; i<Npop; i++)
      {
        System.out.print(i + "\t ");
        for (j = 0; j < Npar; j++) {
          for (k = 0; k < Ngene; k++)
            System.out.print(Cromosomas[i][j][k]);
          System.out.print("\t ");
        }
        for(j=0; j<Npar; j++)
          System.out.print(decodificar(Cromosomas[i][j], j) + "\t ");

        f = funcion(Cromosomas[i]);

        System.out.print(f + "\t ");
        System.out.print(Costos[i]);

        if(f != Costos[i] ) System.out.print(" error ");

        System.out.println(" ");
      }
    }

    /**
     * imprime los bits en un gene
     * @param gene int[]
     */

    public void imprime(int gene[])
    {
      int i, n = gene.length;

      for(i=0; i<n; i++)
        System.out.print(gene[i]);

      System.out.println("");
    }

    /**
     * Funci�n a optimizar
     * @param vector int[][]
     * @return double
     */

    public double funcion(int vector[][])
    {
        return 0.0;
    }
}