Algoritmos Genéticos (# Reinas)

Presentado a:

• Julio Cesar Sierra

Por:

• Maria Jose Velandia
• Jorge Barrera

Archivos:

Se recomienda instalar la ultima versión del jre7 http://www.java.com/es/download/

• Runnable Jar

ALGORTIRMOS GENETICOS

Los Algoritmos Genéticos (AG's) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin (1859). Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

LAS 8 REINAS

El problema de las ocho reinas es un pasatiempo en el que se colocan ocho reinas sin que se amenacen. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848. En el juego del ajedrez la reina amenaza a aquellas piezas que se encuentren en su misma fila, columna o diagonal. El juego de las 8 reinas consiste en colocar sobre un tablero de ajedrez ocho reinas sin que estas se amenacen entre ellas.

import java.util.*;
import javax.swing.*;

public class Reinas {

    private static int poblacionIni = 75;           // Tamaño de la poblacion 
    private static double probApareamiento = 0.7;   // Probabilidad de reproduccion entre dos cromosomas. rango: 0.0 < probMutacion < 1.0
    private static double tasaMutacion = 0.001;     // Tasa de mutacion. rango: 0.0 < tasaMutacion < 1.0
    private static int minSeleccion = 10;           // Minimo de padres para la seleccion.
    private static int maxSeleccion = 50;           // Maximo de padres para la seleccion. rango: minSeleccion < maxSeleccion < poblacionIni
    private static int numDesendencia = 20;         // Cantidad desendencia por generacion. rango: 0 < numDesendencia < maxSeleccion.
    private static int minBaraja = 8;               // Rango para generar aleatorios
    private static int maxBaraja = 20;
    private static int ptsCruce = 4;                // Maximo de puntos de cruce. rango: 0 < ptsCruce < 8 (> 8 isn't good).
    private static int anchoTablero = 8;            // Ancho del tablero.
    private static int generacion = 0;
    private static int numHijos = 0;
    private static int sigMutacion = 0;             // Programa las mutaciones.
    private static int numMutaciones = 0;
    private static List<Cromosoma> poblacion  = new ArrayList<Cromosoma>();

    /**
     * Metodo que emula un algortimo genetico Simple
     */
    public static void AlgoritmoGenetico(JTextArea tablero, JTextArea generaciones) {

        int tamanioPoblacion = 0;
        Cromosoma cromosoma = null;
        boolean terminado = false;
        GenerarPoblacionInicial();                          //Genera población inicial

        numMutaciones = 0;
        sigMutacion = NumeroAleatorio(0, (int) Math.round(1.0 / tasaMutacion));

        while (!terminado) {                                //Mientras no terminada la búsqueda
            tamanioPoblacion = poblacion.size();            //Tamaño de población
            for (int i = 0; i < tamanioPoblacion; i++) {
                cromosoma = poblacion.get(i);
                if ((cromosoma.getConflictos() == 0)) {
                    terminado = true;
                }
            }

            Fitness();                                      //Calcula el fitness dependiendo la cantidad de conflictos

            Seleccion();                                    //Selecciona los padres de la siguiente generación

            Reproduccion();                                 //Realiza el cruce parcial de los padres

            PrepararSiguienteGeneracion();                  //Selecciona los hijos de la siguiente generación

            generacion++;
        }

        tamanioPoblacion = poblacion.size();
        for (int i = 0; i < tamanioPoblacion; i++) {
            cromosoma = poblacion.get(i);
            if (cromosoma.getConflictos() == 0) {
                ImprimirSolucion(cromosoma, tablero);
            }
        }

        generaciones.setText(generaciones.getText() + "Resuelto en " + generacion + " generaciones \nencontrado con " + numMutaciones + " mutaciones \nen el " + numHijos + " cromosoma.");
    }

    /**
     * Busca la mejor actitud
     */
    private static void Fitness() {
        // Menor error = 100%, Mayor Error = 0%
        int tamanioPoblacion = poblacion.size();
        Cromosoma cromosoma = null;
        double mejor = 0;
        double peor = 0;

        // La peor puntuación sería el que tiene la mayor energía, mejor más bajo.
        peor = poblacion.get(Maximo()).getConflictos();

        // Convertir a un porcentaje ponderado.
        mejor = peor - poblacion.get(Minimo()).getConflictos();

        for (int i = 0; i < tamanioPoblacion; i++) {
            cromosoma = poblacion.get(i);
            cromosoma.SetFitness((peor - cromosoma.getConflictos()) * 100.0 / mejor);
        }
    }

    /**
     * Seleccion de cromosomas de la generacion
     */
    private static void Seleccion() {

        int j = 0;
        int tamanioPoblacion = poblacion.size();
        double genTotal = 0.0;
        double selTotal = 0.0;
        int maximoSeleccionar = NumeroAleatorio(minSeleccion, maxSeleccion);
        double seleccionar = 0.0;
        Cromosoma cromosoma = null;
        Cromosoma comosomaAux = null;
        boolean terminado = false;

        for (int i = 0; i < tamanioPoblacion; i++) {
            cromosoma = poblacion.get(i);
            genTotal += cromosoma.getFitness();
        }

        genTotal *= 0.01;

        for (int i = 0; i < tamanioPoblacion; i++) {
            cromosoma = poblacion.get(i);
            cromosoma.setProbSeleccion(cromosoma.getFitness() / genTotal);
        }

        for (int i = 0; i < maximoSeleccionar; i++) {
            seleccionar = NumeroAleatorio(0, 99);
            j = 0;
            selTotal = 0;
            terminado = false;
            while (!terminado) {
                cromosoma = poblacion.get(j);
                selTotal += cromosoma.getProbSeleccion();
                if (selTotal >= seleccionar) {
                    if (j == 0) {
                        comosomaAux = poblacion.get(j);
                    } else if (j >= tamanioPoblacion - 1) {
                        comosomaAux = poblacion.get(tamanioPoblacion - 1);
                    } else {
                        comosomaAux = poblacion.get(j - 1);
                    }
                    comosomaAux.setSeleccionado(true);
                    terminado = true;
                } else {
                    j++;
                }
            }
        }
    }

    /**
     * Produce una nueva generacion
     */
    private static void Reproduccion() {
        int getRand = 0;
        int padreA = 0;
        int padreB = 0;
        int newIndex1 = 0;
        int newIndex2 = 0;
        Cromosoma newChromo1 = null;
        Cromosoma newChromo2 = null;

        for (int i = 0; i < numDesendencia; i++) {
            padreA = SeleccionarPadre();
            // Probabilidad de prueba de reproduccion.
            getRand = NumeroAleatorio(0, 100);
            if (getRand <= probApareamiento * 100) {
                padreB = SeleccionarPadre(padreA);
                newChromo1 = new Cromosoma(anchoTablero);
                newChromo2 = new Cromosoma(anchoTablero);
                poblacion.add(newChromo1);
                newIndex1 = poblacion.indexOf(newChromo1);
                poblacion.add(newChromo2);
                newIndex2 = poblacion.indexOf(newChromo2);

                // Elige uno o ambos de los siguientes:
                CruceParcial(padreA, padreB, newIndex1, newIndex2);

                if (numHijos - 1 == sigMutacion) {
                    IntercambiarMutacion(newIndex1, 1);
                } else if (numHijos == sigMutacion) {
                    IntercambiarMutacion(newIndex2, 1);
                }

                poblacion.get(newIndex1).CalcularConflictos();
                poblacion.get(newIndex2).CalcularConflictos();

                numHijos += 2;

                // Programa la siguiente mutacion.
                if (numHijos % (int) Math.round(1.0 / tasaMutacion) == 0) {
                    sigMutacion = numHijos + NumeroAleatorio(0, (int) Math.round(1.0 / tasaMutacion));
                }
            }
        } // i
    }

    /**
     * Cruza con probabilidad dos individuos obteniendo dos decendientes
     *
     * @param chromA
     * @param chromB
     * @param hijo1
     * @param hijo2
     */
    private static void CruceParcial(int chromA, int chromB, int hijo1, int hijo2) {
        int j = 0;
        int item1 = 0;
        int item2 = 0;
        int pos1 = 0;
        int pos2 = 0;
        Cromosoma cromosoma = poblacion.get(chromA);
        Cromosoma comosomaAux = poblacion.get(chromB);
        Cromosoma newChromo1 = poblacion.get(hijo1);
        Cromosoma newChromo2 = poblacion.get(hijo2);
        int crossPoint1 = NumeroAleatorio(0, anchoTablero - 1);
        int crossPoint2 = NumeroAleatorioExclusivo(anchoTablero - 1, crossPoint1);

        if (crossPoint2 < crossPoint1) {
            j = crossPoint1;
            crossPoint1 = crossPoint2;
            crossPoint2 = j;
        }

        // Copia los genes de padres a hijos.
        for (int i = 0; i < anchoTablero; i++) {
            newChromo1.getGenes(i, cromosoma.setGenes(i));
            newChromo2.getGenes(i, comosomaAux.setGenes(i));
        }

        for (int i = crossPoint1; i <= crossPoint2; i++) {
            // Obtener los dos elementos que intercambian.
            item1 = cromosoma.setGenes(i);
            item2 = comosomaAux.setGenes(i);

            // Obtiene los items, posiciones en la descendencia.
            for (j = 0; j < anchoTablero; j++) {
                if (newChromo1.setGenes(j) == item1) {
                    pos1 = j;
                } else if (newChromo1.setGenes(j) == item2) {
                    pos2 = j;
                }
            } // j

            // Intercambiar.
            if (item1 != item2) {
                newChromo1.getGenes(pos1, item2);
                newChromo1.getGenes(pos2, item1);
            }

            // Obtiene los items, posiciones en la descendencia.
            for (j = 0; j < anchoTablero; j++) {
                if (newChromo2.setGenes(j) == item2) {
                    pos1 = j;
                } else if (newChromo2.setGenes(j) == item1) {
                    pos2 = j;
                }
            } // j

            // Intercambiar.
            if (item1 != item2) {
                newChromo2.getGenes(pos1, item1);
                newChromo2.getGenes(pos2, item2);
            }

        } // i
    }

    /**
     * Cruza con probabilidad dos individuos obteniendo dos decendientes
     *
     * @param chromA
     * @param chromB
     * @param hijo1
     * @param hijo2
     */
    private static void CrucePorPosicion(int chromA, int chromB, int hijo1, int hijo2) {
        int k = 0;
        int numPoints = 0;
        int tempArray1[] = new int[anchoTablero];
        int tempArray2[] = new int[anchoTablero];
        boolean matchFound = false;
        Cromosoma cromosoma = poblacion.get(chromA);
        Cromosoma comosomaAux = poblacion.get(chromB);
        Cromosoma newChromo1 = poblacion.get(hijo1);
        Cromosoma newChromo2 = poblacion.get(hijo2);

        // Elegir y ordenar los puntos de cruce.
        numPoints = NumeroAleatorio(0, ptsCruce);
        int crossPoints[] = new int[numPoints];
        for (int i = 0; i < numPoints; i++) {
            crossPoints[i] = NumeroAleatorio(0, anchoTablero - 1, crossPoints);
        } // i

        // Obtenga no elegidos de los padres 2
        k = 0;
        for (int i = 0; i < anchoTablero; i++) {
            matchFound = false;
            for (int j = 0; j < numPoints; j++) {
                if (comosomaAux.setGenes(i) == cromosoma.setGenes(crossPoints[j])) {
                    matchFound = true;
                }
            } // j
            if (matchFound == false) {
                tempArray1[k] = comosomaAux.setGenes(i);
                k++;
            }
        } // i

        // Insertar elegido al hijo 1.
        for (int i = 0; i < numPoints; i++) {
            newChromo1.getGenes(crossPoints[i], cromosoma.setGenes(crossPoints[i]));
        }

        // Rellene no elegidos para hijos 1.
        k = 0;
        for (int i = 0; i < anchoTablero; i++) {
            matchFound = false;
            for (int j = 0; j < numPoints; j++) {
                if (i == crossPoints[j]) {
                    matchFound = true;
                }
            } // j
            if (matchFound == false) {
                newChromo1.getGenes(i, tempArray1[k]);
                k++;
            }
        } // i

        // Obtenga no elegidos de los padres 1
        k = 0;
        for (int i = 0; i < anchoTablero; i++) {
            matchFound = false;
            for (int j = 0; j < numPoints; j++) {
                if (cromosoma.setGenes(i) == comosomaAux.setGenes(crossPoints[j])) {
                    matchFound = true;
                }
            } // j
            if (matchFound == false) {
                tempArray2[k] = cromosoma.setGenes(i);
                k++;
            }
        } // i

        // Inserte elegido en hijos 2.
        for (int i = 0; i < numPoints; i++) {
            newChromo2.getGenes(crossPoints[i], comosomaAux.setGenes(crossPoints[i]));
        }

        // Rellene no elegidos para hijos 2.
        k = 0;
        for (int i = 0; i < anchoTablero; i++) {
            matchFound = false;
            for (int j = 0; j < numPoints; j++) {
                if (i == crossPoints[j]) {
                    matchFound = true;
                }
            } // j
            if (matchFound == false) {
                newChromo2.getGenes(i, tempArray2[k]);
                k++;
            }
        } // i
    }

    /**
     * Intercambia los genes, realiza la mutacion
     *
     * @param indice
     * @param intercambio
     */
    private static void IntercambiarMutacion(int indice, int intercambio) {
        int i = 0;
        int tempData = 0;
        Cromosoma cromosoma = null;
        int gene1 = 0;
        int gene2 = 0;
        boolean terminado = false;

        cromosoma = poblacion.get(indice);

        while (!terminado) {
            gene1 = NumeroAleatorio(0, anchoTablero - 1);
            gene2 = NumeroAleatorioExclusivo(anchoTablero - 1, gene1);

            // Cambia los genes seleccionados.
            tempData = cromosoma.setGenes(gene1);
            cromosoma.getGenes(gene1, cromosoma.setGenes(gene2));
            cromosoma.getGenes(gene2, tempData);

            if (i == intercambio) {
                terminado = true;
            }
            i++;
        }
        numMutaciones++;
    }

    /**
     * Seleccionar los padres para la reproduccion
     *
     * @return
     */
    private static int SeleccionarPadre() {
        // Función sobrecargada, consulta "choosepadre (ByVal Parenta As Integer)".
        int padre = 0;
        Cromosoma cromosoma = null;
        boolean terminado = false;

        while (!terminado) {
            // Elige al azar un padre elegible.
            padre = NumeroAleatorio(0, poblacion.size() - 1);
            cromosoma = poblacion.get(padre);
            if (cromosoma.getSeleccionado() == true) {
                terminado = true;
            }
        }

        return padre;
    }

    /**
     * Seleccionar los padres para la reproduccion, diferente al seleccionado
     *
     * @return int
     */
    private static int SeleccionarPadre(int padreA) {
        // Función sobrecargada, consulta "choosepadre()".
        int padre = 0;
        Cromosoma cromosoma = null;
        boolean terminado = false;

        while (!terminado) {
            // Elige al azar un padre elegible.
            padre = NumeroAleatorio(0, poblacion.size() - 1);
            if (padre != padreA) {
                cromosoma = poblacion.get(padre);
                if (cromosoma.getSeleccionado() == true) {
                    terminado = true;
                }
            }
        }

        return padre;
    }

    /**
     * Prepara la poblacion de la siguiente generacion
     */
    private static void PrepararSiguienteGeneracion() {
        int tamanioPoblacion = 0;
        Cromosoma cromosoma = null;

        // Restaura estado de cromosoma
        tamanioPoblacion = poblacion.size();
        for (int i = 0; i < tamanioPoblacion; i++) {
            cromosoma = poblacion.get(i);
            cromosoma.setSeleccionado(false);
        }
    }

    /**
     * Imprime la mejor solucion
     *
     * @param mejorSolucion
     */
    private static void ImprimirSolucion(Cromosoma mejorSolucion, JTextArea visorTablero) {
        String tablero[][] = new String[anchoTablero][anchoTablero];

        // Limpia el tablero.
        for (int x = 0; x < anchoTablero; x++) {
            for (int y = 0; y < anchoTablero; y++) {
                tablero[x][y] = "";
            }
        }

        for (int x = 0; x < anchoTablero; x++) {
            tablero[x][mejorSolucion.setGenes(x)] = "Q";
        }

        // Muestra el tablero.
        for (int y = 0; y < anchoTablero; y++) {
            for (int x = 0; x < anchoTablero; x++) {
                if (tablero[x][y] == "Q") {
                 visorTablero.setText(visorTablero.getText() + "X ");
                } else {
                 visorTablero.setText(visorTablero.getText() + "O ");
                }
            }
            visorTablero.setText(visorTablero.getText() + "\n");
        }
    }

    /**
     * Obtiene un numero aleatorio en el rango
     *
     * @param low
     * @param high
     * @return
     */
    private static int NumeroAleatorio(int low, int high) {
        return (int) Math.round((high - low) * new Random().nextDouble() + low);
    }

    /**
     *
     * @param high
     * @param except
     * @return
     */
    private static int NumeroAleatorioExclusivo(int high, int except) {
        boolean terminado = false;
        int getRand = 0;

        while (!terminado) {
            getRand = new Random().nextInt(high);
            if (getRand != except) {
                terminado = true;
            }
        }

        return getRand;
    }

    /**
     * Obtener numero aleatorio fuera del rango
     *
     * @param low
     * @param high
     * @param except
     * @return
     */
    private static int NumeroAleatorio(int low, int high, int[] except) {
        boolean terminado = false;
        int getRand = 0;

        if (high != low) {
            while (!terminado) {
                terminado = true;
                getRand = (int) Math.round((high - low) * new Random().nextDouble() + low);
                for (int i = 0; i < except.length; i++) //UBound(except)
                {
                    if (getRand == except[i]) {
                        terminado = false;
                    }
                } // i
            }
            return getRand;
        } else {
            return high; // or low (it doesn't matter).
        }
    }

    /**
     * Obtiene el minimo cromosoma
     *
     * @return int
     */
    private static int Minimo() {
        // Devuelve un índice de matriz.
        int tamanioPoblacion = 0;
        Cromosoma cromosoma = null;
        Cromosoma comosomaAux = null;
        int winner = 0;
        boolean foundNewWinner = false;
        boolean terminado = false;

        while (!terminado) {
            foundNewWinner = false;
            tamanioPoblacion = poblacion.size();
            for (int i = 0; i < tamanioPoblacion; i++) {
                if (i != winner) {             // Avoid self-comparison.
                    cromosoma = poblacion.get(i);
                    comosomaAux = poblacion.get(winner);
                    if (cromosoma.getConflictos() < comosomaAux.getConflictos()) {
                        winner = i;
                        foundNewWinner = true;
                    }
                }
            }
            if (foundNewWinner == false) {
                terminado = true;
            }
        }
        return winner;
    }

    /**
     * Obtiene el maximo cromosoma
     *
     * @return
     */
    private static int Maximo() {
        // Devuelve un índice de matriz.
        int tamanioPoblacion = 0;
        Cromosoma cromosoma = null;
        Cromosoma comosomaAux = null;
        int winner = 0;
        boolean foundNewWinner = false;
        boolean terminado = false;

        while (!terminado) {
            foundNewWinner = false;
            tamanioPoblacion = poblacion.size();
            for (int i = 0; i < tamanioPoblacion; i++) {
                if (i != winner) {             // Avoid self-comparison.
                    cromosoma = poblacion.get(i);
                    comosomaAux = poblacion.get(winner);
                    if (cromosoma.getConflictos() > comosomaAux.getConflictos()) {
                        winner = i;
                        foundNewWinner = true;
                    }
                }
            }
            if (foundNewWinner == false) {
                terminado = true;
            }
        }
        return winner;
    }

    /**
     * Generar poblacion inicial
     */
    private static void GenerarPoblacionInicial() {
        int shuffles = 0;
        Cromosoma newChromo = null;
        int chromoIndex = 0;

        for (int i = 0; i < poblacionIni; i++) {
            newChromo = new Cromosoma(anchoTablero);
            poblacion.add(newChromo);
            chromoIndex = poblacion.indexOf(newChromo);

            // Escoja al azar el número de baraja realizar.
            shuffles = NumeroAleatorio(minBaraja, maxBaraja);

            IntercambiarMutacion(chromoIndex, shuffles);

            poblacion.get(chromoIndex).CalcularConflictos();

        }
        return;
    }
}

public class Cromosoma {

    private int anchoTablero = 0;
    private int genes[];
    private double fitness = 0.0;
    private boolean seleccionado = false;
    private double probSeleccion = 0.0;
    private int conflictos = 0;

    /**
     * Constructor del la clase
     */
    public Cromosoma(int longitud) {

        this.anchoTablero = longitud;
        genes = new int[longitud];

        for (int i = 0; i < longitud; i++) {
            this.genes[i] = i;
        }
    }

    /**
     * Calcula los conflictos de movimiento entre las reinas
     */
    public void CalcularConflictos() {
        int x = 0;
        int y = 0;
        int auxx = 0;
        int auxy = 0;
        String tablero[][] = new String[anchoTablero][anchoTablero];
        int numConflictos = 0;
        int dx[] = new int[]{-1, 1, -1, 1};
        int dy[] = new int[]{-1, 1, 1, -1};
        boolean terminado = false;

        // Limpia el tablero.
        for (int i = 0; i < anchoTablero; i++) {
            for (int j = 0; j < anchoTablero; j++) {
                tablero[i][j] = "";
            }
        }

        for (int i = 0; i < anchoTablero; i++) {
            tablero[i][this.genes[i]] = "Q";
        }

        // Recorrer cada una de las Reinas y calcular el número de conflictos.
        for (int i = 0; i < anchoTablero; i++) {
            x = i;
            y = this.genes[i];

            // Evaluar diagonales.
            for (int j = 0; j <= 3; j++) {
                auxx = x;
                auxy = y;
                terminado = false;
                while (!terminado) {
                    auxx += dx[j];
                    auxy += dy[j];
                    if ((auxx < 0 || auxx >= anchoTablero) || (auxy < 0 || auxy >= anchoTablero)) {
                        terminado = true;
                    } else {
                        if (tablero[auxx][auxy].compareToIgnoreCase("Q") == 0) {
                            numConflictos++;
                        }
                    }
                }
            }
        }

        this.conflictos = numConflictos;
    }

    /**
     * Coloca conflicto
     *
     * @param value
     */
    public void setConflictos(int value) {
        this.conflictos = value;
    }

    /**
     * Obtiene conflicto
     *
     * @return int
     */
    public int getConflictos() {
        return this.conflictos;
    }

    /**
     * Obtiene la probabilidad de seleccion
     *
     * @return double
     */
    public double getProbSeleccion() {
        return probSeleccion;
    }

    /**
     * Coloca la probabilidad de seleccion
     *
     * @param SelProb
     */
    public void setProbSeleccion(double SelProb) {
        probSeleccion = SelProb;
    }

    /**
     * Obtiene si esta seleccionado
     *
     * @return boolean
     */
    public boolean getSeleccionado() {
        return seleccionado;
    }

    /**
     * Selecciona el cromosoma
     *
     * @param sValue
     */
    public void setSeleccionado(boolean sValue) {
        seleccionado = sValue;
    }

    /**
     * Obtiene el grado de optitud del cromosoma
     *
     * @return double
     */
    public double getFitness() {
        return fitness;
    }

    /**
     * Coloca el grado de aptitud del cromosoma
     *
     * @param score
     */
    public void SetFitness(double score) {
        fitness = score;
    }

    /**
     * Coloca los genes al cromosoma
     *
     * @param index
     * @return int
     */
    public int setGenes(int index) {
        return genes[index];
    }

    /**
     * Obtiene los genes del cromosoma
     *
     * @param index
     * @param value
     */
    public void getGenes(int index, int value) {
        genes[index] = value;
    }
}