package optimizacion;


import java.util.Random;

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

public class geneticos {
    public int Npar, Npop, Ngood, Nmut, Niter;

    public double Cromosomas[][], Costos[], CostoN[], Rangos[][];

    public int Parejas[][];
    public Random r;

    /**
     * Constructor que resive
     * @param poblacion int Tamano de la poblacion
     * @param parametros int Numero de parametros de la funcion a minimizar
     * @param iter int Maximo numero de generaciones
     * @param Ran double[][] Rangos de busqueda.
     */

    public geneticos(int poblacion, int parametros, int iter, double Ran[][])
    {
      Npar = parametros; // numero de parametros.
      Npop = poblacion; // Tama�o de la poblacion.
      Ngood = Npop / 4; // Dimension para los mejores.
      Nmut = (int) (Npop * 0.01); // Numero de mutaciones.
      Niter = iter; // Numero maximo de generaciones
      Cromosomas = new double[Npop][Npar];
      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[Ngood][2];
      r = new Random();
    }

    /**
     * Itera el algoritmo para encontrar el m�nimo de la funci�n
     */

    public void Itera() {
        genera_poblacion();
        for (int k = 0; k < Niter; k++) {
            System.out.print(k + " " + Costos[0] + " [");
            Parejas();
            Aparea();
            Mutacion();
            quiksort(0, Npop - 1);
            for (int j = 0; j < Npar; j++)
                System.out.print(Cromosomas[0][j] + ", ");
            System.out.println("] ");
        }
        //imprime();
    }

    /**
     * Genera una poblaci�n dentro de los rangos dados para cada
     * variable
     */

    public void genera_poblacion() {
      int i, j;

      for (i = 0; i < Npop; i++) {
        for (j = 0; j < Npar; j++)
          Cromosomas[i][j] = r.nextDouble() * (Rangos[j][1] - Rangos[j][0]) +
              Rangos[j][0];

        Costos[i] = funcion(Cromosomas[i]);
      }
      quiksort(0, Npop-1);

      Npop /= 2.0;

    }

    /**
     * Crea parejas de manera aleatorio. Utilizando costos pesados
     */

    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 < Ngood; i++) {
        for (j = 0; j < 2; j++) {
          Parejas[i][j] = Busca(CostoN, Ngood, r.nextDouble());
        }
      }
    }

    /**
     * Genera nuevos individuos a partir de una pareja de cromosomas
     */

    public void Aparea() {
      int i, j, k, l, p, m;
      double beta;

      l = Ngood;

      for (i = 0; i < Ngood; i++) {
        k = (int) Math.round(r.nextDouble() * (double) (Npar - 1));
        beta = r.nextDouble();

        m = Parejas[i][0];
        p = Parejas[i][1];

        for (j = 0; j < Npar; j++) {
          if (j < k) {
            Cromosomas[l][j] = Cromosomas[m][j];
            Cromosomas[l + 1][j] = Cromosomas[p][j];
          }
          else {
            if (j == k) {
              Cromosomas[l][j] = Cromosomas[m][j] -
                  beta * (Cromosomas[m][j] - Cromosomas[p][j]);
              Cromosomas[l + 1][j] = Cromosomas[p][j] +
                  beta * (Cromosomas[m][j] - Cromosomas[p][j]);
              //Cromosomas[l][j] = (1 - beta) * Cromosomas[m][j] +
              //    beta * Cromosomas[p][j];
              //Cromosomas[l + 1][j] = (1 - beta) * Cromosomas[p][j] +
              //    beta * Cromosomas[m][j];
            }
            else {
              Cromosomas[l][j] = Cromosomas[p][j];
              Cromosomas[l + 1][j] = Cromosomas[m][j];
            }
          }
        }
        l += 2;
      }
      for (i = Ngood; i < Npop; i++)
        Costos[i] = funcion(Cromosomas[i]);
    }

    /**
     * Muta aleatoriamente a un individuo a exepci�n del mas apto
     */

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

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

    /**
     * Busca al individuo con el mejor costo
     * @param A double[]
     * @param n int
     * @param azar double
     * @return int
     */

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

      return 1;
    }

    /**
     * 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;
      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 j=0; j<Npar; j++)
            {
              aux = Cromosomas[l][j];
              Cromosomas[l][j] = Cromosomas[h][j];
              Cromosomas[h][j] = aux;
            }
            ++l;
            --h;
          }
        }

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

    /**
     * Imprime al mejor individo de una generaci�n
     */

    private void imprime() {
      for (int i = 0; i < Npop; i++)
      {
        System.out.print(i + ".- ");
        for (int j = 0; j < Npar; j++)
          System.out.print(Cromosomas[i][j] + " " );
        System.out.println(Costos[i]);

      }
    }

    /**
     * funci�n a minimizar
     * @param X double[] valor en el cual se evalua la funci�n
     * @return double
     */

    public double funcion(double X[]) {
        return 0;
    }
}