A jornada do cavalo de xadrez é um problema que vem sendo estudado há séculos por jogadores de xadrez e matemáticos. É proposta uma rota do cavalo, com seu salto característico, de forma que cubra todos os quadrados do tabuleiro (64 quadrados, 8 × 8) tocando cada um apenas uma vez.
Os primeiros dados sobre esse problema foram encontrados em um manuscrito árabe do ano 840 (Murray, 1913), onde duas rotas foram detalhadas. A primeira análise matemática foi apresentada por Leonhard Euler em Berlim, em 1759. Outros matemáticos conhecidos que lidaram com ela foram Taylor, de Moivre e Lagrange.
Mais perto do nosso tempo, McKay e Mordecki usavam mainframes poderosos, procurando as rotas mais possíveis em uma placa 8 × 8. McKay calculou o número total de rotas fechadas (quando o cavalo completa o circuito, o próximo salto o leva ao quadrado inicial) em
13.267.364.410.532, enquanto Mordecki encontrou
1.305 × 10 35 rotas abertas.
Quanto aos sistemas de busca, eles variam de sistemas puramente heurísticos (Warnsdorff 1823), busca / retorno em profundidade, redes neurais, algoritmos genéticos, algoritmos de colônia de formigas, etc.
Para a resolução deste trabalho, um algoritmo genético baseado no desenvolvido por
Chu-Beasley
Algorítmos genéticos
Algoritmos Genéticos (AGs) são métodos usados para resolver problemas de pesquisa e otimização. Eles são baseados na evolução das populações na natureza, de acordo com os princípios de seleção natural e sobrevivência dos mais aptos, postulados por Charles Darwin (1859)
Ao imitar esses processos adaptativos, os AGs podem gerar soluções para problemas da vida real. Codificando adequadamente a população inicial da GA e implementando corretamente os métodos evolutivos, soluções ótimas podem ser alcançadas.
Os princípios básicos das AGs foram estabelecidos pela Holanda em 1975, mas essa técnica só se tornou popular em meados da década de 1980, especialmente através do trabalho de Goldberg (1989).
Na natureza, os indivíduos competem pelos recursos de sobrevivência e também pela reprodução. Aqueles que têm as melhores condições para sobreviver e atrair seus parceiros são os que têm mais chances de gerar descendentes. Pelo contrário, os menos talentosos terão poucas chances de se reproduzir. As características dos melhores adaptados são herdadas pelos filhos, que recebem dos pais uma combinação dos melhores genes e, assim, evoluem, conseguindo uma maior adaptação ao ambiente em que vivem.
AGs funcionam de maneira semelhante ao sistema natural. Eles têm uma população de indivíduos em que cada um é a solução potencial para um determinado problema. Cada um desses indivíduos terá um valor de aptidão ou adaptação relacionado a quão próximos ou distantes estão de alcançar tal solução.
Analogamente à natureza, esses indivíduos serão capazes de cruzar e gerar descendentes, que receberão o melhor de seus ancestrais e, com o passar das gerações, convergirão para a solução ideal para o problema.
Um AG típico emprega noções simplificadas de seleção, cruzamento, mutação e sobrevivência dos mais aptos para que, com relativamente pouco conhecimento dos métodos de solução de um problema, você também possa encontrar uma solução.
Nos campos em que existem técnicas específicas para soluções específicas, elas sempre funcionam melhor que um AG. A idéia de usar esses algoritmos é pesquisar em campos sem uma solução delimitada ou, se essa solução existir, pode ser aprimorada combinando-a com o uso do AG.
Os AGs são usados em uma ampla variedade de áreas, como: otimização numérica e combinatória, aprendizado de máquina, programação automática, economia, sistemas imunológicos, ecologia, evolução e aprendizado, sistemas sociais, etc.
Estrutura e funcionamento de um algoritmo genético
Um AG simples (como o criado pela Holanda e um dos mais utilizados) é constituído por uma população de indivíduos, também chamados cromossomos. Cada cromossomo representa uma possível solução para o problema proposto e é composto de uma série de valores, que podem ser {0,1}, números inteiros, reais, etc. Esses valores correspondem a cada um dos genes que compõem o cromossomo. Uma possível representação gráfica é a seguinte:
O AG também possui operadores genéticos, que realizam os processos de seleção, cruzamento e mutação. Como esses três operadores são os mais comuns e básicos, alguns AGs especializados incorporam operadores de melhoria de viabilidade, otimização de otimização etc.
Algoritmo Genético de Chu-Beasley
Como mencionado acima, o Chu-Beasley GA foi usado para este trabalho. As diferenças mais importantes com AGs simples são:
- Não pode haver cromossomos iguais na população. Em AGs simples, toda ou quase toda a população é substituída em cada geração. Em Chu-Beasley, apenas um indivíduo é substituído, desde que o novo possua as características desejadas de diversidade, viabilidade, etc. Ele incorpora um operador de melhoria de otimização.
Adaptação da AG ao problema do cavalo de xadrez
Dependendo do quadrado em que está localizado, o cavalo pode ter de dois a oito movimentos legais, que podem ser codificados de várias maneiras. Neste trabalho, uma codificação com números inteiros foi resolvida:
Assim, uma corrida parcial de cavalos pode ser representada com uma faixa inteira semelhante a esta:
4 - 6 - 0 - 0 - 2 - 4…
Se pegarmos um ponto de partida como e4 (centro do quadro) e representamos esse caminho na notação algébrica, teríamos:
(e4) - f6 - h5 - g3 - f1 - d2 - e4
Observe que o último movimento nos leva a um espaço visitado anteriormente (e4), tornando essa rota ilegal. Portanto, poderíamos dizer que essa rota tem um comprimento válido de cinco saltos. Esse número de saltos é o que chamamos de função de condicionamento físico do indivíduo. Para esse problema, uma função de adequação de 63 saltos legais é uma solução válida. Voltando à semelhança com a natureza, um indivíduo ou cromossomo é mais ou menos apto, dependendo se o número de sua função de condicionamento físico é maior ou menor. Quanto maior a função de aptidão, mais perto você estará da solução do problema: completar a jornada do cavalo ao redor do tabuleiro de xadrez.
Implementação do Algoritmo Genético
Decidiu-se criar uma população inicial de 64 indivíduos ou cromossomos (testes subsequentes confirmaram que é o número mais apropriado). Cada um dos genes desses cromossomos foi completado com um número aleatório entre 0 e 7. A única restrição inicial que foi tomada foi que o salto de um quadrado x não tirou o cavalo do tabuleiro.
Com a população inicial criada, um ciclo ou geração começa, o que pode ser simplificado da seguinte maneira:
- Seleção de Progenitor Cruzamento de Progenitor e Geração de uma Mutação Infantil da Criança Melhoria da Adaptabilidade da Incorporação Infantil (Possível) da Criança na População
Seleção dos pais
Existem vários métodos para selecionar os pais que irão gerar um descendente da população. Os mais utilizados são:
- Roleta Elite ou Ranking de torneios Monte Carlo
Neste trabalho, foram feitas as seleções de Torneo, Elitista e Montecarlo, sendo esta a que produziu os melhores resultados, como veremos mais adiante.
Seleção por Torneio
Dois pares de progenitores candidatos (cromossomos) são escolhidos aleatoriamente na população. O cromossomo com a melhor função de condicionamento físico é escolhido de cada par e a cruz é produzida a partir dos dois escolhidos.
Seleção elitista
Os dois melhores cromossomos são sempre retirados da população e ocorre um cruzamento entre eles para gerar o filho.
Seleção de Monte Carlo ou Roleta
Com esse método, a probabilidade de um indivíduo se reproduzir é proporcional à diferença entre sua aptidão e a de seus concorrentes. Isso pode ser representado como um jogo de roleta, em que cada indivíduo recebe uma seção ou parte da roleta, mas o mais apto obtém seções maiores do que o menos adequado. Em seguida, a roleta é girada (um número é escolhido aleatoriamente) e toda vez que o indivíduo é escolhido, quem tem a seção na qual a roleta para.
Ao executar a roleta duas vezes, os dois pais são selecionados para cruzar.
Travessia dos pais
Um cruzamento genético ocorre com os dois cromossomos selecionados, dos quais dois filhos serão gerados. Somente as mais aptas dessas crianças podem entrar na população.
Assim como existem vários métodos de seleção, isso também ocorre com o cruzamento. Neste trabalho, os operadores de cruzamento por um ponto e por dois pontos foram testados, resultando no cruzamento com um ponto sendo o mais bem-sucedido. Sua implementação é a seguinte:
Depois que os dois pais são escolhidos, seus cromossomos são cortados em um ponto selecionado aleatoriamente. Com isso, dois segmentos diferentes são gerados em cada cromossomo: cabeça e cauda. Então os genes das caudas são trocados entre cada indivíduo e, dessa maneira, são criados dois filhos que herdam características de ambos os pais. Finalmente, apenas a criança com a melhor função de aptidão terá possibilidades de entrar na população.
Mutação do Filho
A mutação do filho faz com que alguns de seus genes, geralmente apenas um, variem seu valor aleatoriamente. Dessa forma, o comportamento que ocorre na natureza é imitado, pois quando os filhotes são gerados, geralmente ocorre algum tipo de erro, geralmente sem grande significado, na passagem da carga genética dos pais para os filhos. Normalmente a probabilidade de mutação é muito baixa, inferior a 1%. No entanto, os testes neste trabalho tiveram melhores resultados com uma mutação próxima a 85%.
Os operadores de mutação genética mais utilizados são a substituição aleatória e a troca de dois genes do cromossomo.
No presente trabalho, existe a possibilidade de que qualquer um dos dois operadores possa ser aplicado em uma mutação.
Melhoria da adaptabilidade infantil
Este ponto é mais que importante no AG. Os testes realizados por vários autores (e também no presente trabalho), com AGs simples, falharam na busca de rotas válidas para o cavalo de xadrez. Para melhorar o funcionamento dos AGs, foram implementados vários métodos que especializam parcialmente o processo. Essa idéia de adaptabilidade foi explorada por Whitley (1994)
Gordon e Slocum (2004) introduziram a técnica de reparo, que será explicada abaixo. Outra especialização foi a de Al-Gharaibeh, Qqwagneh e Al-zahawi (2007), que melhoraram a adaptabilidade dos filhos por meio de heurísticas.
A idéia de Gordon e Slocum foi a seguinte: para cada cromossomo da população, no ponto em que um salto é inválido (ou seja, tira o cavalo do tabuleiro ou de uma praça já visitada), é aplicado um reparo. Esse movimento é examinado e é feita uma tentativa de substituí-lo por outro movimento válido que permite que a jornada continue. Se não houver salto válido, a avaliação desse cromossomo será encerrada. Caso haja um salto válido, o gene inválido é modificado por esse salto e é passado para o gene que segue à direita. Isso continua até que um quadrado reapareça sem possíveis saltos ou a solução do caminho do cavalo seja alcançada. Nenhuma heurística ou retorno é aplicada, como acontece com outras técnicas.
No exemplo apresentado acima, a avaliação do cromossomo terminou quando o cavalo voltou à caixa e4. Ou seja, a cadeia genética:
4 - 6 - 0 - 0 - 2 - 4…
(e4) - f6 - h5 - g3 - f1 - d2 - e4 em que o último valor (4) é inválido.
O processo de reparo tenta encontrar um valor correto para esse gene, digamos o valor 7, que nos tiraria do papel. Em seguida, procuramos outro valor, por exemplo, 3, que nos levaria a c4, que é uma caixa ainda não visitada. Então a cadeia genética seria deixada
4 - 6 - 0 - 0 - 2 - 3…
(e4) - f6 - h5 - g3 - f1 - d2 - c4
e prosseguiríamos da mesma maneira com o próximo gene à direita da cadeia.
A diferença entre o presente trabalho e o de Gordon e Slocum é que eles aplicam reparação a toda a população, enquanto em nosso Chu-Beasley AG trabalhamos apenas no filho recém-criado.
Incorporação do Filho à População
Uma vez que a criança é obtida e melhorada, sua função de aptidão é calculada, ou seja, quantos saltos válidos possui sua cadeia genética. Essa função é comparada com cada um dos membros da população atual. Se a função de condicionamento físico for melhor que a do pior membro da população, esse indivíduo será eliminado e substituído pela criança atual. Sempre respeitando a diversidade: que a criança não é igual a nenhum dos membros presentes na população.
Se um cromossomo com os mesmos genes que a criança atual já existe na população, ou se essa criança não é melhor que o pior dos indivíduos, então ele é descartado e supõe-se que não houve filhos nessa geração.
Resultados obtidos
Para o trabalho, a linguagem C # foi usada em conjunto com o framework A-Forge.Net, um excelente produto de código aberto e gratuito, orientado à Inteligência Artificial e que permite acelerar os tempos de desenvolvimento.
Tentamos realizar um processo de teste semelhante às investigações anteriores, mas como Chu-Beasley é um AG diferente, os mesmos parâmetros não podem ser usados. Finalmente, uma população inicial de 64 cromossomos foi criada e 1.000.000 de gerações foram criadas para cada quadrado no quadro. O processo foi repetido cinco vezes para cada caixa, a fim de obter médias comparáveis às demais propostas. Os resultados podem ser vistos na tabela a seguir:
Os três métodos de seleção permitiram encontrar, pelo menos uma vez, uma viagem na primeira geração. Isto é graças ao mecanismo de reparo.
Vale ressaltar que, embora o AG de Gordon e Slocum tenha encontrado o maior número de execuções em um único quadrado (642 vs. 529), nosso AG reconheceu uma média mais alta em quase todos os quadrados do tabuleiro.
Por outro lado, não houve testes que deram resultado negativo, ou seja, o GA sempre encontrou rotas válidas em cada teste.
Médias de viagem em cinco testes.
Referências:
- Murray HJR (1913) História do xadrez BD McKay, "visitas de cavaleiros a um tabuleiro de xadrez 8 × 8", Ph.D. dissertação, Departamento de Ciência da Computação, Universidade Nacional da Austrália, 1997. Mordecki, “Sobre o número de visitas de cavaleiros”, em Prepublicaciones de Matematica da Universidad de la Republica, Uruguai 2001/57, 2001.BEASLEY, JE E CHU, PC A Algoritmo genético para o problema de atribuição generalizada. Computers Operations Research, 24 (1), pp 17-23, 1997. Holland, J., Adaptação em Sistemas Naturais e Artificiais, 1ª ed., Univ. Of Michigan, 1975. 2ª ed. 1992 pela MIT Press. Goldberg, D., Algoritmos Genéticos em Pesquisa, Otimização e Aprendizado de Máquina. Addison-Wesley, 1989. Whitley, D., Gordon, VS e Mathias, K., "Evolução Lamarckiana, Efeito de Baldwin e Otimização de Funções", Parallel Prob. Solving from Nature 3, Israel, pp 6-15, 1994
- Gordon VS e Slocum TJ (2004) The Knight's Tour - Evolucionário vs. Pesquisa em profundidade. Em trabalhos do Congresso de Computação Evolutiva 2004 (CEC'04), Portland, Oregon, pp. 1435-1440
- Al-Gharaibeh, Z. Qawagneh e H. Al-zahawi, "Algoritmos genéticos com heurística - problema de turnê de Knight", em Proc. da Conferência Internacional sobre Métodos Genéticos e Evolucionários, 2007, pp. 177-81.A-Forge.Net
