Algorítmo Genético

Estava lendo um problema sobre como colocar 8 rainhas num tabuleiro de xadrez de tal forma que nenhuma rainha possa atacar a outra rainha.

Este problema pode ser resolvido por algoritmo genético (GA).

Um GA tem os seguintes conceitos:

- função fitness: esta é uma função que irá mensurar cada estado, retornando valores mais altos quanto melhor o estado.

- crossover: troca de "gens" (bits, bytes, informação) dos pais para gerar o filho. O ponto de crossover é determinado aleatoriamente a cada iteracao.

- mutação: em cada nova posição da população, esta esta sujeita a uma mutação, com baixa probabilidade.

Exemplo:

Estado 0: população inicial

pai 1: 00010001
pai 2: 01000110

Estado 1: iteração 1

aleatoriamente foi selecionado crossover posicao 3 e sem mutação

pai 1: 00010001
pai 2: 01000110
-----------------
filho1: 000001100
filho2: 01010001

Estado 2: iteração 2

aleatoriamente foi selecionado crossover posicao 2 e mutação no filho1

pai1: 000001100
pai2: 01010001
-----------------
filho1: 00010010
filho2: 010001100


Como em qualquer problema a dificuldade maior esta na representação do estado e na correta definição da função fitness.

Um tabuleiro de xadrex é formado por 8x8 casas e como temos 8 rainhas, podemos representar o estado com 8 digitos variando de 1 a 8.

Ex: 28451823 significará o seguinte:

   1    2    3    4    5    6    7    8
+----+----+----+----+----+----+----+----+
A|    | x  |    |    |    |    |    |    |
 +----+----+----+----+----+----+----+----+
B|    |    |    |    |    |    |    | x  |
 +----+----+----+----+----+----+----+----+
C|    |    |    | x  |    |    |    |    |
 +----+----+----+----+----+----+----+----+
D|    |    |    |    | x  |    |    |    |
 +----+----+----+----+----+----+----+----+
E| x  |    |    |    |    |    |    |    |
 +----+----+----+----+----+----+----+----+
F|    |    |    |    |    |    |    | x  |
 +----+----+----+----+----+----+----+----+
G|    | x  |    |    |    |    |    |    |
 +----+----+----+----+----+----+----+----+
H|    |    | x  |    |    |    |    |    |
 +----+----+----+----+----+----+----+----+

A função fitness deverá verificar quantas rainhas estão livres de ataque.
No exemplo acima temos apenas a rainha em E1 então a função fitness deve retornar 1.

Ok, chega de conceito, vamos ao código:

package br.com.technique.rharari.ia.sample.geneticAlgorithm

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * @author Ricardo Alberto Harari - ricardo.harari@gmail.com
 * 
 * 
 */
public class OitoRainhas {

    private static final int MAX_FITNESS = 8;
    private static Random randomico = new Random();

    public static void main(String[] args) {
        go();
    }

    /**
     * inicio do processo
     */
    private static void go() {
        long startTime = System.currentTimeMillis();
        System.out.println("Populacao Inicial");

        // gerar a populacao inicial com 10 individuos
        Set populacao = new HashSet();
        while (populacao.size() <>
            String individuo = gerarIndividuo(8);
            System.out.println("individuo=" + individuo);
            populacao.add(individuo);
        }
        System.out.println("------------------------------");

        double probabilidadeMutacao = 0.10;
        int maxIteracoes = 10000000;

        String melhorIndividuo = null;
        boolean achouSolucao = false;
        int bestFitness = 0;

        int i = 0;

        for (i = 0; i <>
            melhorIndividuo = geneticAlgorithm(populacao, probabilidadeMutacao);
            int ftness = fitness(melhorIndividuo);
            if (ftness > bestFitness) {
                System.out.println("novo fitness = " + ftness);
                bestFitness = ftness;
                if (ftness == MAX_FITNESS) {
                    achouSolucao = true;
                    break;
                }
            }
        }

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

        if (achouSolucao) {
            System.out.println("Solucao encontrada em " + i + " iteracoes");
            System.out.println("Solucao =" + melhorIndividuo);
            System.out.println("Fitness =" + fitness(melhorIndividuo));
        } else {
            System.out.println("Solucao nao encontrada após " + i
                    + " iteracoes");
            System.out.println("Melhor Individuo =" + melhorIndividuo);
            System.out.println("Fitness =" + fitness(melhorIndividuo));
        }

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

        mostrarTabuleiro(melhorIndividuo);
        System.out.println("Elapsed time = "
                + (System.currentTimeMillis() - startTime) + "ms");
    }

    /**
     * mostrar o tabuleiro graficamente
     * 
     * @param melhorIndividuo
     * @return
     */
    private static void mostrarTabuleiro(String melhorIndividuo) {
        System.out.println("|---+---+---+---+---+---+---+---|");
        for (int i = 0; i <>
            System.out.print("|");
            int posicaoRainha = Integer.parseInt(melhorIndividuo.substring(i,
                    i + 1)) - 1;
            for (int j = 0; j <>
                if (posicaoRainha == j) {
                    System.out.print(" x |");
                } else {
                    System.out.print("   |");
                }
            }
            System.out.println("\r\n|---+---+---+---+---+---+---+---|");
        }
    }

    /**
     * logica GA mantendo os melhores na populacao retorna o melhor individuo
     * 
     * @param populacao
     * @param probabilidadeMutacao
     */
    private static String geneticAlgorithm(Set populacao,
            double probabilidadeMutacao) {
        String melhor = null;
        Set filhos = new HashSet();
        int tamanhoPopulacao = populacao.size();

        while (filhos.size() <>
            String p1 = selecionarAleatorio(populacao, "");
            String p2 = selecionarAleatorio(populacao, p1);
            String filho = crossover(p1, p2);
            if (randomico.nextDouble() <= probabilidadeMutacao) {
                filho = mutate(filho);
            }
            filhos.add(filho);
        }
        filhos.addAll(populacao);
        Object[] pop = filhos.toArray();
        int[] f = new int[pop.length];
        int melhorF = -1;
        for (int i = 0; i <>
            f[i] = fitness((String) pop[i]);
            if (melhorF <>
                melhorF = f[i];
                melhor = (String) pop[i];
            }
        }
        populacao.clear();
        while (populacao.size() <>
            if (melhorF <>
                // should never happen...
                System.out.println("???????");
                break;
            }
            for (int i = 0; i <>
                if (f[i] == melhorF && populacao.size() <>
                    populacao.add((String) pop[i]);
                }
            }
            melhorF--;
        }
        return melhor;
    }

    /**
     * @param filho
     * @return
     */
    private static String mutate(String filho) {
        int mp = randomico.nextInt(filho.length());
        int mc = randomico.nextInt(filho.length()) + 1;
        filho = filho.substring(0, mp) + mc
                + (mp + 1 == filho.length() ? "" : filho.substring(mp + 1));
        return filho;
    }

    /**
     * crossover
     * 
     * @param p1
     * @param p2
     * @return
     */
    private static String crossover(String p1, String p2) {
        int i = randomico.nextInt(p1.length());
        String ret = p1.substring(0, i) + p2.substring(i);
        return ret;
    }

    /**
     * seleciona um individuo da populacao aleatoriamente
     * 
     * @param populacao
     * @return
     */
    private static String selecionarAleatorio(Set populacao, String px) {
        String pn = px;
        Object[] tmp = populacao.toArray();
        while (pn.equals(px)) {
            int i = randomico.nextInt((populacao.size()));
            pn = (String) tmp[i];
        }
        return pn;
    }

    /**
     * gerar um individuo com n posicoes
     * 
     * @param n
     * @return
     */
    private static String gerarIndividuo(int n) {
        String ret = "";
        while (ret.length() <>
            ret += (randomico.nextInt(n) + 1);
        return ret;
    }

    /**
     * função fitness, retorna a quantidade de rainhas a salvo.
     * 
     * @param individuo
     * @return
     */
    public static int fitness(String individuo) {
        int ret = 0;

        int[][] tabuleiro = new int[8][8];
        // primeiro representamos o tabuleiro com 0 e 1
        for (int i = 0; i <>
            int posicaoRainha = Integer.parseInt(individuo.substring(i, i + 1)) - 1;
            for (int j = 0; j <>
                tabuleiro[i][j] = posicaoRainha == j ? 1 : 0;
            }
        }
        // agora verificamos quantas rainhas estao a salvo, este será o nosso
        // retorno da função fitness
        for (int i = 0; i <>
            for (int j = 0; j <>
                if (tabuleiro[i][j] == 1) {
                    if (!temAtacante(tabuleiro, i, j)) {
                        ret++;
                    }
                }
            }
        }
        return ret;
    }

    /**
     * verifica se existe uma rainha ameaçando a posicao i,j existindo retorna
     * true caso contrário retorna false
     * 
     * @param tabuleiro
     * @param i
     * @param j
     * @return
     */
    private static boolean temAtacante(int[][] tabuleiro, int i, int j) {
        // verificar na horizontal
        for (int k = 0; k <>
            if (k != i && tabuleiro[k][j] == 1)
                return true;
        }
        // verificar na vertical
        for (int k = 0; k <>
            if (k != j && tabuleiro[i][k] == 1)
                return true;
        }
        // verificar na diagonal1
        int i0 = i - 1;
        int j0 = j - 1;
        while (i0 >= 0 && j0 >= 0) {
            if (tabuleiro[i0][j0] == 1)
                return true;
            i0--;
            j0--;
        }
        // verificar na diagonal2
        i0 = i + 1;
        j0 = j + 1;
        while (i0 <>
            if (tabuleiro[i0][j0] == 1)
                return true;
            i0++;
            j0++;
        }
        // verificar na diagonal3
        i0 = i + 1;
        j0 = j - 1;
        while (i0 <>= 0) {
            if (tabuleiro[i0][j0] == 1)
                return true;
            i0++;
            j0--;
        }
        // verificar na diagonal4
        i0 = i - 1;
        j0 = j + 1;
        while (i0 >= 0 && j0 <>
            if (tabuleiro[i0][j0] == 1)
                return true;
            i0--;
            j0++;
        }
        return false; // esta a salvo
    }

}



Após executar terá um resultado como o abaixo:

Populacao Inicial
individuo=81778444
individuo=14826627
individuo=76637684
individuo=23138245
individuo=58827174
individuo=71447712
individuo=88725475
individuo=51845453
individuo=31454745
individuo=16465533
------------------------------
novo fitness = 2
novo fitness = 3
novo fitness = 4
novo fitness = 6
novo fitness = 8
------------------------------
Solucao encontrada em 113 iteracoes
Solucao =16837425
Fitness =8
------------------------------
|---+---+---+---+---+---+---+---|
| x |   |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   |   |   |   |   | x |   |   |
|---+---+---+---+---+---+---+---|
|   |   |   |   |   |   |   | x |
|---+---+---+---+---+---+---+---|
|   |   | x |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   |   |   |   |   |   | x |   |
|---+---+---+---+---+---+---+---|
|   |   |   | x |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   | x |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   |   |   |   | x |   |   |   |
|---+---+---+---+---+---+---+---|
Elapsed time = 32ms

Como existe mais de uma solução poderá ter uma disposição diferente das rainhas a cada execução.
No próximo artigo discutirei sobre outras técnicas para resolver este problema.