Problema das N Rainhas - Algoritmo Genético - Java

Introdução

Já mencionei Algoritmos Genéticos em outra postagem, veja aqui, abaixo a introdução da mesma, se você já esta familiarizado com AGs ou já leu este post, vá para Descrição do Algoritmo.

Algoritmos Genéticos, AGs, são métodos de busca inspirados na evolução dos seres vivos, introduzidos por John Holland (1975) e popularizados por um de seus alunos, David Goldberg (1989), seguem o princípio da seleção natural e sobrevivência dos mais aptos, segundo Charles Darwin (1859). Ele propôs que quanto mais apto um indivíduo for de sobreviver em um meio ambiente, mais chances ele terá de se reproduzir e passar sua carga genética para seus descendentes.

É nisto que se baseia os Algoritmos Genéticos, buscar boas soluções em um espaço de busca grande, em que uma busca pontual seria muito cara.

Se quiser saber mais sobre AGs, leia este ótimo material: INTRODUÇÃO AOS ALGORITMOS GENÉTICOS (Estéfane G. M. de Lacerda e André Carlos P. L. F. de Carvalho)

Durante esses estudos, me deparei com esse problema de otimização denominado "Problema das N Rainhas".

Descrição do Algoritmo

Como todos sabem, a rainha é a peça mais poderosa do xadrez, pois pode se movimentar em qualquer direção e por qualquer número de casas. Esse problema propõe colocar n rainhas em um tabuleiro de dimensão n, em uma certa posição que não ocorra nenhum ataque por nenhuma das peças.

Por exemplo, em um problema com n=4, a solução seria a seguinte:

[caption id="attachment_923" align="aligncenter" width="300"] Solução do problema das N-Rainhas com n=4[/caption]

Implementação

Nesta aplicação, desenvolvida em Java, cada Indivíduo da população, representa uma possível solução, o gene é representado por um vetor de n posições, onde o índice do vetor é a posição x e o valor deste índice a posição y, de uma rainha no tabuleiro.

O tabuleiro acima seria representado pelo vetor {2,0,3,1}. Deste modo cada rainha é representada em uma coluna deste tabuleiro.

Parâmetros

O crossover de um ponto é de 90% por padrão, e a mutação de 1%, que gera valores de y aleatórios nas posições x do vetor.

A população de de 100 indivíduos e o máximo de gerações para n igual a 64 por exemplo deve ser de 10.000.

[caption id="attachment_927" align="aligncenter" width="600"] Problema das N Rainhas em Java com AG. n=8[/caption]

Utilizo a biblioteca JFreeChart para apresentar um gráfico de convergência da população ao longo das gerações. Jars para importar: jcommon-1.0.17.jar e jfreechart-1.0.14.jar.

[caption id="attachment_926" align="aligncenter" width="600"] Gráfico de convergência ao longo das gerações. n=8[/caption]

Resultados

A aplicação aceita valores de n de 4 até 64, que com esse valor alto, a solução demora um pouco mais para convergir, mas alcança, bons resultados:

[caption id="attachment_929" align="aligncenter" width="600"] Problema das N Rainhas. n=64[/caption]

[caption id="attachment_930" align="aligncenter" width="600"] Gráfico de convergência ao longo das gerações. n=64[/caption]

Código fonte

Você pode baixar o código fonte completo aqui ou pelo meu github https://github.com/pcollares/exemplos-blog/tree/master/AG-NRainhas/src, abaixo apenas demonstrações de algumas das classes do projeto.

Individuo.java

package dominio;

import java.util.Random;
import operacao.Algoritimo;

//Classe que define uma possível solução
public class Individuo {

    private double aptidao;
    private int[] posicoesY;
    private Tabuleiro tabuleiro;
    private int colisoes;

    public Individuo(boolean rainhasAleatorias) {
        posicoesY = new int[Algoritimo.getN()];
        tabuleiro = new Tabuleiro(Algoritimo.getN());

        for (int i = 0; i < posicoesY.length; i++) {
            posicoesY[i] = -1;
        }

        for (int i = 0; i < posicoesY.length; i++) {
            if (rainhasAleatorias) {
                posicoesY[i] = this.gerarYAleatorioExclusivo();
                tabuleiro.atualizaTabuleiro(posicoesY);
            }
        }

        if (rainhasAleatorias) {
            geraAptidao();
        }
    }

    //Gera aleatóriamente um valor de Y sem colisões
    public int gerarYAleatorioExclusivo() {
        int y;
        Random r;
        boolean encontrou;

        do {
            r = new Random();
            y = r.nextInt(Algoritimo.getN());
            encontrou = false;

            for (int i = 0; i < Algoritimo.getN(); i++) {
                if (posicoesY[i] == y) {
                    encontrou = true;
                    break;
                }
            }

        } while (encontrou);

        return y;
    }

    //Gera a aptidão baseado no número de colisões
    public void geraAptidao() {
        this.colisoes = geraColisoes();
        this.aptidao = colisoes;
    }

    //adiciona uma rainha no tabuleiro
    public void addRainha(int x, int y) {
        Random r = new Random();
        if (r.nextDouble() < Algoritimo.getTaxaDeMutacao()) {
            y = gerarYAleatorioExclusivo();
        }
        posicoesY[x] = y;
        tabuleiro.atualizaTabuleiro(posicoesY);
    }

    public double getAptidao() {
        return aptidao;
    }

    public Tabuleiro getTabuleiro() {
        return tabuleiro;
    }

    public void setTabuleiro(Tabuleiro tabuleiro) {
        this.tabuleiro = tabuleiro;
    }

    public int getColisoes() {
        return colisoes;
    }

    public int geraColisoes() {
        int x = 0;
        int y = 0;
        int tempx = 0;
        int tempy = 0;

        int conflicts = 0;
        int dx[] = new int[]{-1, 1, -1, 1};
        int dy[] = new int[]{-1, 1, 1, -1};
        boolean done;

        //Checa na horizontal
        for (int i = 0; i < Algoritimo.getN(); i++) {
            y = posicoesY[i];
            if (y != -1) {
                for (int j = 0; j < Algoritimo.getN(); j++) {
                    if (posicoesY[j] == y && j != i) {
                        conflicts++;
                    }
                }
            }
        }

        //Checa nas diagonais
        for (int i = 0; i < Algoritimo.getN(); i++) {
            x = i;
            y = this.posicoesY[i];
            if (y != -1) {
                for (int j = 0; j <= 3; j++) {
                    tempx = x;
                    tempy = y;
                    done = false;
                    while (!done) {
                        tempx += dx[j];
                        tempy += dy[j];
                        if ((tempx < 0 || tempx >= Algoritimo.getN()) || (tempy < 0 || tempy >= Algoritimo.getN())) {
                            done = true;
                        } else {
                            if (tabuleiro.getTabuleiro()[tempx][tempy]) {
                                conflicts++;
                            }
                        }
                    }
                }
            }
        }

        return conflicts;
    }

    public int[] getPosicoesY() {
        return posicoesY;
    }

    @Override
    public String toString() {
        String s = "";
        for (int i = 0; i < Algoritimo.getN(); i++) {
            s += "[" + i + "," + posicoesY[i] + "] ";
        }
        return s;
    }
}

Populacao.java

package dominio;

//Define uma população
public class Populacao {

    private Individuo[] individuos;
    private int tamPopulacao;

    public Populacao(int tamPop, boolean individuosAleatorios) {
        tamPopulacao = tamPop;
        individuos = new Individuo[tamPop];

        for (int i = 0; i < individuos.length; i++) {
            if (individuosAleatorios) {
                individuos[i] = new Individuo(true);
            } else {
                individuos[i] = null;
            }
        }
    }

    public void setIndividuo(Individuo individuo, int posicao) {
        individuos[posicao] = individuo;
    }

    public void setIndividuo(Individuo individuo) {
        for (int i = 0; i < individuos.length; i++) {
            if (individuos[i] == null) {
                individuos[i] = individuo;
                return;
            }
        }
    }

    public void ordenaPopulacao() {
        boolean trocou = true;
        while (trocou) {
            trocou = false;
            for (int i = 0; i < individuos.length - 1; i++) {                 if (individuos[i].getAptidao() > individuos[i + 1].getAptidao()) {
                    Individuo temp = individuos[i];
                    individuos[i] = individuos[i + 1];
                    individuos[i + 1] = temp;
                    trocou = true;
                }
            }
        }
    }

    public int getNumIndividuos() {
        int num = 0;
        for (int i = 0; i < individuos.length; i++) {
            if (individuos[i] != null) {
                num++;
            }
        }
        return num;
    }

    public double getMediaAptidao() {
        return getTotalAptidao() / getNumIndividuos();
    }

    public double getTotalAptidao() {
        double total = 0;
        for (int i = 0; i < individuos.length; i++) {
            if (individuos[i] != null) {
                total += individuos[i].getAptidao();
            }
        }
        return total;
    }

    public int getTamPopulacao() {
        return tamPopulacao;
    }

    public Individuo getIndivduo(int pos) {
        return individuos[pos];
    }

    public Individuo[] getIndividuos() {
        return individuos;
    }
}

Tabuleiro.java

package dominio;

import operacao.Algoritimo;

//Define um tabuleiro de dimensão n
public class Tabuleiro {

    public boolean[][] tabuleiro;
    public int tamanho;

    public Tabuleiro(int tamanho) {
        this.tamanho = tamanho;
        tabuleiro = new boolean[tamanho][tamanho];
        zeraTabuleiro();
    }

    public void zeraTabuleiro() {
        for (int y = 0; y < tamanho; y++) {
            for (int x = 0; x < tamanho; x++) {
                tabuleiro[x][y] = false;
            }
        }
    }

    public void atualizaTabuleiro(int posicoesY[]) {
        zeraTabuleiro();
        for (int i = 0; i < Algoritimo.getN(); i++) {
            if (posicoesY[i] != -1) {
                tabuleiro[i][posicoesY[i]] = true;
            }
        }
    }

    public boolean[][] getTabuleiro() {
        return tabuleiro;
    }

    public boolean estaLivre(int x, int y) {
        boolean livre = true;
        if (tabuleiro[x][y]) {
            livre = false;
        }
        return livre;
    }

    @Override
    public String toString() {
        String r = "";
        for (int y = 0; y < tamanho; y++) {
            for (int x = 0; x < tamanho; x++) {
                if (tabuleiro[x][y]) {
                    r += " x";
                } else {
                    r += " o";
                }
            }
            r += "\n";
        }
        return r;
    }
}

Algoritimo.java

package operacao;

import dominio.Individuo;
import dominio.Populacao;
import ihm.Frame;
import java.util.ArrayList;
import java.util.Random;

public class Algoritimo {

    private static int N;
    private static double taxaDeCrossover;
    private static double taxaDeMutacao;
    private static int numeroMaximoGeracoes;
    private static int tamanhoPopulacao;
    private static boolean elitismo;

    public static void AG(Frame frame) {
        new Thread(new ExecutaAG(frame)).start();
    }

    public static Populacao novaGeracao(Populacao populacao) {

        Random r;
        Populacao novaPopulacao = new Populacao(populacao.getTamPopulacao(), false);

        if (isElitismo()) {
            novaPopulacao.setIndividuo(populacao.getIndivduo(0));
        }

        while (novaPopulacao.getNumIndividuos() < novaPopulacao.getTamPopulacao()) {

            Individuo pais[] = new Individuo[2];
            Individuo filhos[] = new Individuo[2];

            pais[0] = selecaoTorneio(populacao);
            pais[1] = selecaoTorneio(populacao);

            r = new Random();
            if (r.nextDouble() <= taxaDeCrossover) {
                filhos = Algoritimo.crossover(pais[0], pais[1]);
                filhos[0].geraAptidao();
                filhos[1].geraAptidao();
            } else {
                filhos[0] = pais[0];
                filhos[1] = pais[1];
            }

            novaPopulacao.setIndividuo(filhos[0]);
            novaPopulacao.setIndividuo(filhos[1]);

        }
        novaPopulacao.ordenaPopulacao();
        return novaPopulacao;
    }

    public static Individuo[] crossover(Individuo pai1, Individuo pai2) {
        Random r = new Random();
        Individuo filhos[] = new Individuo[2];

        filhos[0] = new Individuo(false);
        filhos[1] = new Individuo(false);

        int pontoCorte = r.nextInt(Algoritimo.N);

        for (int i = 0; i < Algoritimo.N; i++) {
            if (i < pontoCorte) {
                filhos[0].addRainha(i, pai1.getPosicoesY()[i]);
                filhos[1].addRainha(i, pai2.getPosicoesY()[i]);
            } else {
                filhos[0].addRainha(i, pai2.getPosicoesY()[i]);
                filhos[1].addRainha(i, pai1.getPosicoesY()[i]);
            }
        }

        filhos[0].geraAptidao();
        filhos[1].geraAptidao();

        return filhos;
    }

    public static Individuo selecaoTorneio(Populacao populacao) {
        Random r = new Random();
        Populacao populacaoIntermediaria = new Populacao(2, false);

        populacaoIntermediaria.setIndividuo(populacao.getIndivduo(r.nextInt(populacao.getTamPopulacao())));
        r = new Random();
        populacaoIntermediaria.setIndividuo(populacao.getIndivduo(r.nextInt(populacao.getTamPopulacao())));

        populacaoIntermediaria.ordenaPopulacao();

        int pos;

        r = new Random();
        if (r.nextDouble() < 0.9) {
            pos = 0;
        } else {
            pos = 1;
        }

        return populacaoIntermediaria.getIndivduo(pos);
    }

    public static Individuo[] selecaoRodaDaRoleta(Populacao populacao) {
        Individuo[] individuosEscolhidos = new Individuo[2];

        ArrayList individuosTemp = new ArrayList();

        double aptidaoAcumulada = 0;

        for (int i = 0; i < populacao.getNumIndividuos(); i++) {
            if (i == 0) {
                aptidaoAcumulada = populacao.getIndivduo(i).getAptidao();
            } else {
                aptidaoAcumulada += populacao.getIndivduo(i).getAptidao();
            }

            individuosTemp.add(i, aptidaoAcumulada);
        }

        Random r = new Random();
        double ponteiro = r.nextDouble() * aptidaoAcumulada;

        for (int i = 0; i < individuosTemp.size(); i++) {             if (individuosTemp.get(i) > ponteiro) {
                individuosEscolhidos[0] = populacao.getIndivduo(i);
                break;
            }
        }

        r = new Random();
        ponteiro = r.nextDouble() * aptidaoAcumulada;

        for (int i = 0; i < individuosTemp.size(); i++) {             if (individuosTemp.get(i) > ponteiro) {
                individuosEscolhidos[1] = populacao.getIndivduo(i);
                break;
            }
        }

        return individuosEscolhidos;
    }

    public static double getTaxaDeCrossover() {
        return taxaDeCrossover;
    }

    public static void setTaxaDeCrossover(double taxaDeCrossover) {
        Algoritimo.taxaDeCrossover = taxaDeCrossover;
    }

    public static double getTaxaDeMutacao() {
        return taxaDeMutacao;
    }

    public static void setTaxaDeMutacao(double taxaDeMutacao) {
        Algoritimo.taxaDeMutacao = taxaDeMutacao;
    }

    public static int getNumeroMaximoGeracoes() {
        return numeroMaximoGeracoes;
    }

    public static void setNumeroMaximoGeracoes(int numeroMaximoGeracoes) {
        Algoritimo.numeroMaximoGeracoes = numeroMaximoGeracoes;
    }

    public static int getN() {
        return N;
    }

    public static void setN(int N) {
        Algoritimo.N = N;
    }

    public static int getTamanhoPopulacao() {
        return tamanhoPopulacao;
    }

    public static void setTamanhoPopulacao(int tamanhoPopulacao) {
        Algoritimo.tamanhoPopulacao = tamanhoPopulacao;
    }

    public static boolean isElitismo() {
        return elitismo;
    }

    public static void setElitismo(boolean elitismo) {
        Algoritimo.elitismo = elitismo;
    }

    private static class ExecutaAG implements Runnable {

        private Frame frame;

        public ExecutaAG(Frame frame) {
            this.frame = frame;
        }

        @Override
        public void run() {

            frame.setEstadoIniciarBotao(false);

            int geracao = 1;

            Populacao populacao = new Populacao(getTamanhoPopulacao(), true);
            populacao.ordenaPopulacao();
            frame.setLog("Geração " + geracao + ":\n"
                    + "Melhor: " + populacao.getIndivduo(0).getAptidao() + " (" + populacao.getIndivduo(0).getColisoes() + ")" + "\n"
                    + "Média: " + populacao.getMediaAptidao() + "\n"
                    + "Pior: " + populacao.getIndivduo(populacao.getNumIndividuos() - 1).getAptidao() + "(" + populacao.getIndivduo(populacao.getNumIndividuos() - 1).getColisoes() + ")" + "\n"
                    + "-------------------------------------");

            frame.getTabuleiroVisual().setTabuleiro(populacao.getIndivduo(0).getTabuleiro());

            while (geracao < getNumeroMaximoGeracoes()) {
                geracao++;

                populacao = Algoritimo.novaGeracao(populacao);

                frame.setLog("Geração " + geracao + ":\n"
                        + "Melhor: " + populacao.getIndivduo(0).getAptidao() + " (" + populacao.getIndivduo(0).getColisoes() + ")" + "\n"
                        + "Média: " + populacao.getMediaAptidao() + "\n"
                        + "Pior: " + populacao.getIndivduo(populacao.getNumIndividuos() - 1).getAptidao() + "(" + populacao.getIndivduo(populacao.getNumIndividuos() - 1).getColisoes() + ")" + "\n"
                        + "-------------------------------------");

                if (geracao % (getNumeroMaximoGeracoes() / 1000) == 0) {
                    frame.getChart().update(geracao, populacao.getIndivduo(0).getAptidao(), populacao.getMediaAptidao(), populacao.getIndivduo(populacao.getNumIndividuos() - 1).getAptidao());
                }

                if (populacao.getIndivduo(0).getColisoes() == 0) {
                    frame.setLog("SOLUÇÃO ENCONTRADA!");
                    frame.getChart().update(geracao, populacao.getIndivduo(0).getAptidao(), populacao.getMediaAptidao(), populacao.getIndivduo(populacao.getNumIndividuos() - 1).getAptidao());
                    break;
                }

            }
            frame.getTabuleiroVisual().setTabuleiro(populacao.getIndivduo(0).getTabuleiro());

            frame.setEstadoIniciarBotao(true);

        }
    }
}

[]'s