Aplicação da metaheurística Algoritmos Genéticos na solução do problema das n rainhas

 

Introdução

 

O Problema das n rainhas é muito conhecido da forma como ele foi resolvido originalmente em 1850 por Gauss: com 8 rainhas. Posteriormente essa demonstração foi extendida para n rainhas por Hoffman em 1969.

O problema constitui em colocar-se n rainhas em um tabuleiro de xadrez sem que as mesmas se ataquem simultaneamente, onde n é um número inteiro maior ou igual a 2. Além disso deve-se dizer de quantas formas é possível dispor essas rainhas.

Uma vez demonstrado que é possível colocar n rainhas no tabuleiro, elaborou-se um algoritmo utilizando técnicas baseadas em heurísticas, em particular Algoritmos Genéticos (AG´s) para verificar sua eficiência e eficácia na solução do problema.

Os AG’s tratam problemas de otimização como um processo iterativo de busca da melhor solução dentro do espaço de possíveis respostas para o problema, iniciando com um conjunto aleatório de soluções iniciais, que constituem a população inicial. Combinando os melhores representantes dessa população obtém uma nova, que passa a substituir a anterior, caracterizando-se como a próxima geração. O mecanismo é repetitivo. A cada nova iteração a população é refinada gerando novas e melhores soluções para o problema em questão, culminando com sua convergência (Fernandes, 2003).

Para o desenvolvimento do software seguiu-se a metodologia Orientada a Objetos.

Diante da especificação do sistema iniciou-se a construção do projeto utilizando como ferramenta o software Rational Rose para a confecção dos diagramas em UML (Unified Modeling Language), em especial dos diagramas de Caso de Uso e de Classe.

Para a implementação, utilizou-se o software Borland Delphi 7.0. Como trabalhos futuros pretende-se migrar a aplicação para JAVA tornando-o completamente independente de plataforma e disponibiliza-lo para utilização via WEB.

 

O Problema e sua importância

 

Problemas enxadrísticos sempre foram uma constante na história da Matemática e na Ciência da Computação. Com o passar do tempo, novas tecnologias e novas teorias permitem novas abordagens de antigos problemas.
O Problema das n rainhas é muito conhecido da forma como ele foi resolvido originalmente em 1850 por Gauss: com 8 rainhas. Posteriormente essa demonstração foi extendida para n rainhas por Hoffman (1969).
O problema constitui em colocar-se n rainhas em um tabuleiro de xadrez sem que as mesmas se ataquem simultaneamente, onde n é um número inteiro maior ou igual a 2. Além disso deve-se dizer de quantas formas é possível dispor essas rainhas. 
               Uma vez demonstrado que é possível colocar n rainhas no tabuleiro, elaborou-se um algoritmo que terá como saída todas as formas possíveis de disposição das peças utilizando técnicas baseadas em heurísticas, em particular Algoritmos Genéticos (AG´s) para verificar sua eficiência e eficácia na solução do problema.
 Utilizam-se técnicas baseadas em algoritmos Heurísticos como algoritmos genético e Simulated Annealing como forma de verificar a eficiência e eficácia na solução do problema.
Segundo Fernandes (2003), “os algoritmos Genéticos (AG’s) são métodos adaptativos que podem ser usados para resolver problemas de busca e otimização. Estão inspirados no processo genético e evolutivo dos organismos vivos, baseados na Teoria da Evolução de Darwin.
               Os AG’s usam uma analogia direta com o comportamento natural. Trabalham com uma população de indivíduos, cada qual representando uma solução do problema dado. O poder do AGs provém do fato de se tratar de uma técnica robusta, podendo manipular com êxito uma grande variedade de problemas provenientes das mais diferentes áreas, incluindo aqueles que os outros métodos encontram dificuldades para resolver.”
Segundo Groth(1998), citado por Fernandes(2003), algoritmos genéticos são métodos de otimização combinatorial baseadas no processo de evolução biológica. A idéia básica é que com o tempo, a evolução tenha selecionado as espécies mais resistentes. Aplicando esta idéia ao DM, igualmente envolve modelo de otimização dos dados usando métodos genéticos para obter modelos de adaptação.
               “Resumindo, os AG’s tratam problemas de otimização como um processo iterativo de busca da melhor solução dentro do espaço de possíveis respostas para o problema. Inicia com um conjunto aleatório de soluções iniciais, que constituem a população inicial. Combinando os melhores representantes dessa população obtém uma nova, que passa a substituir a anterior, caracterizando-se como a próxima geração. O mecanismo é repetitivo. A cada nova iteração a população é refinada gerando novas e melhores soluções para o problema em questão, culminando com sua convergência.” (Fernandes, 2003).

 

Justificativa

 

Com esse  trabalho, é possível expor um exemplo completo de Matemática Aplicada e Otimização Computacional.
Encontra-se na literatura diversas técnicas tradicionais para a solução do problema proposto, tais como algoritmos exatos e algoritmos gulosos. Pretende-se realizar uma análise comparativa entre as técnicas existentes com uma abordagem heurística a ser desenvolvida, medindo a eficiência e eficácia na solução do problema.

 

Objetivos

 

O objetivo desse trabalho é demonstrar de forma clara e didática a resolução do problema das n rainhas, baseado na demonstração feita por Hoffman em 1969.  Criar um algoritmo heurístico implementando a solução para n rainhas. E desenvolver um programa de computador baseado no algoritmo que exibe graficamente as soluções encontradas.
               Especificamente pretende-se:
                  -  Modelar o sistema utilizando técnicas orientadas a objetos
                  -  Desenvolver uma heurística utilizando Algoritmos Genéticos para determinar uma solução aproximada. 
                  -  Implementar uma aplicação para testar a heurística desenvolvida
                  -  Realizar testes comparativos para medir o desempenho e a performance do sistema desenvolvido

 

Estrutura de um Algoritmo Genético

 

A disposição da estrutura de um AG simples constitui da seguinte forma:
                  -  Inicialização: Uma população de indivíduos é gerada aleatoriamente, cada um representando uma possível solução.
                  -  Cálculo da aptidão: É realizado o cálculo da aptidão de cada indivíduo com base numa função objetivo  que depende das especificações de cada projeto. A aptidão é calculada apartir do genótipo.
                  -  Critério de parada: Verifica se a solução encontrada é válida.
                  -  Seleção: Os indivíduos mais aptos são selecionados. Cada indivíduo tem uma probabilidade de ser selecionado proporcional à sua aptidão.

   -  Cruzamento (Cross Over): Os indivíduos selecionados na etapa anterior são cruzados. Os cromossomos de cada par de indivíduos a serem cruzados são particionados em um ou mais pontos chamados pontos de corte. Estes pontos de corte podem ou não ser escolhidos aleatoriamente. 
                  -  Mutação: O operador de mutação se aplica a cada filho de maneira individual, e consiste em uma alteração, de maneira aleatória (normalmente com probabilidade pequena), de cada gene componente do cromossomo, garantindo que nenhum ponto do espaço de busca tenha probabilidade zero para ser examinado, e é de fundamental importância para assegurar a convergência  dos AG’s.

ag.JPG

 

 

Métodos

 

  - Caso de Uso

use case.JPG

 

  - Diagrama de Classe

diagrmade classe.JPG

 

Resultado

 

  -Tela do sistema

 

imagem_programa_n_rainhas2.JPG

 

 

Conclusão

 

Através da utilização dos AG´s implementou-se uma solução alternativa para a solução do problema das N-Rainhas. Percebe que a determinação dos parâmetros dos AG´s é de fundamental importância para o obtenção das soluções de forma mais eficiente. Como trabalhos futuros pretende-se migrar a implementação para o código JAVA, tornando-o independente de plataforma e disponibiliza-lo para utilização pela WEB, em um Applet JAVA.

 

Contatos

 

Duvidas, sugestões, ou trocas de conhecimentos sobre a metaheurística algoritmos genéticos ou o problema n-rainhas, a disposição e interessados na aplicação do projeto, entrar em contato:

 

E-Mail: henriquefari@yahoo.com.br
                MSN: henriquefo@hotmail.com

 

Abraços a todos,

Henrique Faria de Oliveira