Colaboradores - Cristiano Lehrer
Colaboradores
Cristiano Lehrer

1. Ybadoo
2. Colaboradores
3. Cristiano Lehrer
4. Artigos Científicos
5. Algoritmos Genéticos com Operação de Crossover Utilizando o Jogo Hawk-Dove com Fenótipos Fixos

Algoritmos Genéticos com Operação de Crossover Utilizando o Jogo Hawk-Dove com Fenótipos Fixos

Lehrer, Cristiano; Borges, Paulo Sergio da Silva. Algoritmos Genéticos com Operação de Crossover Utilizando o Jogo Hawk-Dove com Fenótipos Fixos. Trabalho apresentado no I Simpósio Catarinense de Computação, Itajaí/SC, 2000. 10 páginas.

Resumo

Neste trabalho, alguns dos conceitos importantes pertencentes a teoria dos jogos evolucionários são empregados para testar como eles podem aprimorar a atuação dos operadores utilizados em Algoritmos Genéticos (AG). O emprego de estratégias racionais pode fornecer uma eficiência adicional aos AG na busca de soluções satisfatórias para problemas difíceis. Neste caso, os operadores tradicionais dos AG, especialmente seleção, recombinação e mutação, não mais contam somente com critérios aleatórios para realizar a exploração da superfície adaptativa. Esta ideia é implementada através da promoção de uma competição entre os cromossomos pela melhor adaptabilidade, que é considerada como um recurso escasso e limitado. Para completar este método, o paradigma selecionado foi o jogo Hawk-Dove, conhecido como um importante modelo de comportamento estratégico em estudos ecológicos. Os participantes do jogo são os cromossomos, os quais exercem suas respectivas estratégias e esforçam­-se para melhorar sua adaptabilidade individual. Para testar o método, utilizou-se o Problema do Caixeiro Viajante, para os quais diversas simulações foram executadas. Apresentou­-se os resultados alcançados, especialmente algumas comparações com métodos usuais dos operadores dos AG. Algumas evidências encontradas indicam vantagens no uso da metodologia pesquisada.

Abstract

In this work, some important concepts belonging to evolutionary game theory are employed to test how they can improve the performance of the operators used in Genetic Algorithms (GA). The use of rational strategies can provide additional efficiency to the GA regarding the search of satisfactory solutions to difficult problems. In this case, the traditional GA operators, namely, selection, crossover and mutation will no more rely solely on random criteria to carry out the exploration of the fitness landscape. This idea is implemented by promoting a competition between the chromosomes for better fitness, herein considered as a limited and scarce resource. To accomplish this method, the selected paradigm has been the Hawk­-Dove Game, well known as an important model of strategic behavior in ecological studies. The participants of the game are the chromosomes, which exert their respective strategies and strive for improving their individual fitness. To test the method, the Traveling Salesman Problem has been used. A program of simulations has been run and the achieved results are presented, especially some comparisons between the usual methods regarding the GA operators. Some evidence has been found that indicate the advantage of the investigated methodology.

01. Introdução

A utilização de conceitos da Teoria dos Jogos em Algoritmos Genéticos (AG) ainda é prematura, sendo um vasto campo a ser pesquisado, em busca de respostas para perguntas do tipo: Constitui­-se em uma vantagem? Ajudará os Algoritmos Genéticos a encontrar respostas mais próximas do melhor resultado possível?

Buscando responder estas e outras perguntas, apresenta-se uma variação dos AG utilizando conceitos da Teoria dos Jogos, através da inserção do jogo Hawk-Dove na operação de seleção, auxiliando na escolha dos pais que gerarão os descendentes.

Para testar se tal variação funciona, ela é comparada com outros dois AG já citados na literatura, o algoritmo genético tradicional (Seleção Aleatória), cujo a seleção dos pais para a operação de recombinação é totalmente aleatória, e o algoritmo genético com seleção graduada (Seleção Rank), onde os pais são ordenados segundo sua adaptabilidade e então selecionados segundo tal ordem.

Para providenciar um sistema para a comparação entre o esquema proposto e os outros, utilizou-­se o Problema do Caixeiro Viajante, usando uma lista de cidades e distâncias reais do Brasil.

02. Algoritmos Genéticos

Inspirados nos conceitos da genética e da Teoria da Seleção Natural de Charles Darwin, são um poderoso mecanismo de busca de soluções, sendo uma das técnicas que compõem a Computação Evolucionária (Goldberg, 1989).

Proposto por John Holland entre os anos de 1960 e 1970 na Universidade de Michigan, os AG são uma abstração da evolução biológica. O embasamento teórico dos AG foi apresentado no livro Adaptation in Natural and Artificial Systems (Holland, 1975).

O objetivo principal de Holland não foi o desenvolvimento de algoritmos para resolver problemas específicos, mas um estudo formal dos fenômenos da adaptação que ocorrem na natureza e desenvolver um modo em que tais mecanismos da adaptação natural poderiam ser importados para dentro dos computadores (Mitchell, 1996).

Frequentemente vistos como métodos de otimização, os AG podem ser aplicados a um conjunto de problemas que cresce a cada dia (Whitley, 1994), incluindo sistemas sociais, ecologia, economia, evolução do aprendizado e diversas outras áreas do conhecimento (Mitchell, 1996).

Os AG incluem uma população inicial de cromossomos, onde cada cromossomo possui um certo número de genes. Cada cromossomo codifica uma possível solução para o problema em questão (genótipo). A adaptabilidade ou fitness de cada indivíduo (cromossomo) é calculada através de uma função de avaliação (Mitchell, 1996).

A operação de mutação consiste na troca do conteúdo de um determinado gene do cromossomo segundo uma certa probabilidade. A operação de recombinação ou crossover, é a troca de segmentos entre dois cromossomos pais para gerarem dois cromossomos filhos, também de acordo com uma regra probabilística. Caso não ocorra a troca de segmentos, os filhos serão cópias idênticas dos pais (Mitchell, 1996).

03. Jogo Hawk-Dove

Proposto originalmente por Maynard Smith & Price em 1973, o jogo Hawk-Dove modela disputas entre pares de animais, que estão competindo por um recurso de valor V. Este valor representa a adaptabilidade Darwiniana do indivíduo que obtiver o recurso, que será incrementada de V. O perdedor não terá alterações na sua adaptabilidade (Smith, 1993). Cada indivíduo pode assumir uma das seguintes estratégias (Prestwich, 1999):

• Hawk: caracteriza-se pela agressividade, lutando pelo recurso contra o oponente até se ferir ou até que seu oponente desista;
• Dove: caracteriza­-se pela não agressividade, nunca lutando pelo recurso, preferindo medir forças contra o oponente através da exibição. Caso seja atacado, foge imediatamente sem se ferir.

Nesta matriz, as células representam os payoffs para o jogador da linha, que significam mudanças na sua adaptabilidade em decorrência do par de estratégias adotadas. As seguintes suposições podem ser escritas com base na Tabela 1 (Smith, 1993):

• Hawk versus Hawk: cada competidor tem 50% de probabilidade de obter o recurso V, e 50% de sair ferido na disputa, o que diminuirá de C sua adaptabilidade;
• Hawk versus Dove: Hawk obtêm o recurso, e Dove foge sem se ferir;
• Dove versus Dove: o recurso é compartilhado igualmente pelos dois competidores.

04. Algoritmo Genético Hawk­-Dove

Cada cromossomo da população possui um fenótipo, que é o comportamento que o indivíduo pode adotar, neste caso Hawk ou Dove. Os fenótipos dos indivíduos da população inicial são gerados segundo uma probabilidade.

Para o caso do Problema do Caixeiro Viajante, quanto menor for a distância da rota representada pelo cromossomo, maior será sua adaptabilidade, e consequentemente, mais forte este será nas disputas com os outros cromossomos. Conforme o comportamento de cada participante, os seguintes resultados poderão ocorrer:

• Hawk versus Hawk: o indivíduo com a maior adaptabilidade, por ser mais forte, ganha a disputa, e tem sua adaptabilidade aumentada em 1/2(V - C), enquanto o perdedor a tem reduzida no mesmo valor. No caso dos dois participantes terem a mesma força, ambos serão considerados vencedores;
• Hawk versus Dove: o indivíduo adotando o procedimento Hawk tem sua adaptabilidade aumentada em V, nada acontecendo com o perdedor;
• Dove versus Dove: o indivíduo mais forte ganha a disputa, aumentando sua adaptabilidade em V/2, e o perdedor a tem reduzida no mesmo valor. No caso dos dois participantes terem a mesma força, ambos serão considerados vencedores.

Como cada cromossomo tem um fenótipo, os filhos devem herdar o fenótipo dos pais, segundo a regra: os filhos herdam o fenótipo do pai que possuir a maior adaptabilidade. Se os dois pais possuem a mesma adaptabilidade, então um filho herdará o fenótipo de um pai, e outro filho herdará o fenótipo do outro pai.

Um indivíduo utilizará o fenótipo herdado durante todas as disputas em que participar dentro de uma geração, quando passará seu fenótipo, caso seja apto, para seus descendentes. Ele não pode alterar seu fenótipo dentro da geração, ou seja, jogar algumas vezes como Hawk e outras como Dove, utilizando por isso um fenótipo fixo.

O funcionamento do algoritmo proposto é muito parecido com a seleção Rank, diferindo apenas que antes dos pais serem ordenados para a operação de seleção, eles passam pelo jogo Hawk-Dove.

Serão utilizados dois algoritmos genéticos Hawk-Dove: o Hawk-Dove com limite (HDL) e o Hawk-Dove sem limite (HDSL). No HDL a adaptabilidade dos cromossomos durante o jogo não pode ultrapassar um limite preestabelecido, enquanto que para o HDSL não existe limite.

05. Resultados

Realizou­-se um total de 320.000 execuções dos AG, distribuídos igualmente entre os quatro tipos de métodos analisados - Aleatório (tradicional), Rank, HDL e HDSL - permitindo uma base razoável de dados para realizar as comparações entre os algoritmos.

Durante o levantamento dos dados, alguns parâmetros foram fixados e outros alterados de modo a analisar o comportamento nas diversas situações. Os parâmetros fixados foram:

• Tamanho da população: especifica o número máximo de indivíduos por geração, fixado em 20 indivíduos;
• Gerações: especifica o número máximo de evoluções que o algoritmo poderá atingir, fixado em 1.000 gerações;
• Probabilidade de Hawks: especifica a porcentagem de Hawks na população inicial, fixado em 50%;
• Torneio: especifica o número de disputas realizados pelos indivíduos durante o jogo Hawk-Dove, fixado em 500.

Os parâmetros alterados durante a obtenção dos dados foram:

• Taxa de crossover: especifica a probabilidade de ocorrer a operação de recombinação sobre dois indivíduos, indicando o ponto de corte no cromossomo. Assume os valores 0,4 ou 0,7;
• Taxa de mutação: especifica a probabilidade de ocorrer a operação de mutação sobre um indivíduo, indicando o gene que deverá ser alterado. O indivíduo pode ter mais de um gene alterado durante esta operação. Assume os valores 0,010 ou 0,001;
• Valores do recurso e do preço por ferir-se (V, C): especificam quanto valem o recurso (V) e a perda (C) para os competidores do jogo. Assume os pares de valores (10, 20), (20, 10), (25, 50) ou (50, 25);
• Ordem de seleção: utilizado apenas pelos algoritmos Rank, HDL e HDSL, especifica se os indivíduos depois de ordenados, serão chamados para a operação de recombinação em sequência, ou seja, o indivíduo 1 com o indivíduo 2, o indivíduo 3 com o indivíduo 4 e assim por diante; ou serão chamados pelos extremos, ou seja, o indivíduo 1 com o indivíduo N, o indivíduo 2 com o indivíduo N - 1, e assim por diante até passar por todos os indivíduos.

Cada execução de um algoritmo retorna os seguintes dados: a menor distância (D), a geração onde esta distância foi encontrada (G) e a respectiva rota (R). Cada algoritmo é executado 50 vezes, formando um bloco, de onde se extraem os seguintes dados: média de G, desvio padrão da média de G, o menor G do bloco, o maior G do bloco, média de D, desvio padrão da média de D, o menor D, o maior D e a rota do menor D.

Os dados fornecidos por um bloco são armazenados como uma observação de uma configuração de parâmetros. Para cada configuração de parâmetros são realizados 50 observações de cada algoritmo, ou seja, 50 blocos são gerados. Sobre estas observações serão feitas as análises.

Existem no total 32 configurações de parâmetros, que é a combinação dos parâmetros que são alterados para a geração da base de dados. A Tabela 2 exemplifica as possíveis configuração de parâmetros.

Primeiramente, analise-se a média de G. Observa-se que quanto maior for a média, mais gerações foram efetivamente utilizadas no processo de encontrar a menor distância, havendo um decréscimo no número de gerações em que a evolução não reduziu a distância encontrada.

Observa-se claramente o fraco desempenho da seleção aleatória, que é o algoritmo tradicional, sobre os demais, e uma equivalência entre a seleção Rank, HDL e HDSL, pois possuem quase que a mesma média.

Observando o agrupamento dos dados, o método HDSL possui uma leve superioridade sobre os demais, possuindo seus dados mais agrupados, consequentemente, com uma dispersão menor.

Analisaremos agora a média de D. Observa-se que quanto menor a média encontrada, melhor o desempenho do método, indicando que as distâncias das trajetórias se aproximam da menor distância possível, que não é conhecida.

De novo o algoritmo tradicional deve um desempenho inferior, possuindo uma média muito elevada em relação aos outros métodos, além de possuir uma grande dispersão de valores.

Claramente observa-se uma equivalência entre os métodos Rank, HDL e HDSL, pois suas médias foram muito próximas, variando apenas na casa das dezenas. Observando o agrupamento dos valores, o método HDL teve uma leve superioridade, pois possui suas observações mais agrupadas do que os demais métodos.

As menores distâncias encontradas indicam uma certa superioridade dos algoritmos utilizando o jogo Hawk-Dove sobre os outros algoritmos analisados, sendo que o algoritmo HDL encontrou a menor distância dentre todas as execuções.

06. Conclusão

Um longo caminho ainda será necessário trilhar para se conhecer se os Algoritmos Genéticos, com conceitos da Teoria dos Jogos incluídos, farão alguma diferença significativa sobre os outros métodos tradicionais, já divulgados pela literatura, mas segundo podemos averiguar pelos resultados obtidos até o momento, esta união promete ser vantajosa.

Existem inúmeras maneiras diferentes de modificar os Algoritmos Genéticos com a inclusão dos conceitos da Teoria dos Jogos, sendo esta apenas uma das alternativas investigadas. Outras maneiras serão futuramente criadas e analisadas para se averiguar aquelas que se destacam, em busca de um novo método.

07. Referências Bibliográficas

Goldberg, David Edward. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Inc. 412 pages.

Holland, John Henry. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. 211 pages.

Mitchell, Melanie. (1996). An Introduction to Genetic Algorithms. Cambridge: MIT Press. 221 pages.

Prestwich, Kenneth Neal. (1999). A Simple Game: hawks and doves. Acessado em Fevereiro de 2000.

Smith, John Maynard. (1993). Evolution and the Theory of Games. Cambridge: Cambridge University Press. 234 pages.

Whitley, Darrell. (1994). A Genetic Algorithm Tutorial. In Statistics and Computing 4, 65-85. 37 pages.

Download

Artigo científico apresentado no I Simpósio Catarinense de Computação