Colaboradores - Cristiano LehrerLehrer, Cristiano; Borges, Paulo Sergio da Silva. Métodos de Seleção Hawk-Dove para Algoritmos Genéticos Baseado no Jogo Hawk-Dove. Trabalho apresentado no I Congresso Brasileiro de Computação, Itajaí/SC, 2001. 11 páginas.
Alguns conceitos 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 contariam 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 o método, o paradigma selecionado é 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 se esforçam para melhorar sua adaptabilidade individual. Para testar o método, o Problema do Caixeiro Viajante é utilizado. Uma série de simulações são realizadas e os resultados alcançados apresentados, especialmente uma comparação com os métodos usuais de operadores dos AG. Algumas evidências encontradas indicam vantagens no uso da metodologia pesquisada.
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 know 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 indicates the advantage of the investigated methodology.
A Computação Evolucionária é uma área que utiliza ideias da evolução biológica para resolver computacionalmente, através de técnicas de Inteligência Artificial, problemas complexos, os quais requerem buscas em um vasto campo de soluções possíveis (Mitchell, 1996).
A Biologia Evolucionária é uma forte fonte de inspiração para resolver esses tipos de problemas. A própria natureza teve que realizar uma busca em um enorme conjunto de soluções possíveis, as sequências genéticas, para desenvolver organismos aptos a viverem e a se reproduzirem em seus ambientes (Mitchell, 1996).
Os Algoritmos Genéticos são métodos da Computação Evolucionária que seguem os princípios da seleção natural e da sobrevivência do mais apto, expostos no livro The Origin of Species de Charles Darwin, para simular o processo da evolução natural para desenvolver soluções para o mundo real (Beasley, 1993). A estes princípios estão acrescentados os conceitos iniciados por Mendel, no que se refere à estrutura genética dos seres vivos (Mangano, 1996).
A maioria das implementações desses algoritmos considera os indivíduos como agentes passivos, que nascem com sua adaptabilidade definida e imutável. Isso ocorre porque a adaptabilidade de um indivíduo é calculada com base apenas no seu material genético, e o genótipo de um indivíduo não é alterado durante a sua existência.
Na natureza, a adaptabilidade dos seres vivos não é influenciada apenas pelo seu material genético. Ela também é afetada pela interação entre os indivíduos, seja entre os da mesma espécie ou de espécies diferentes, que estão competindo para melhorar suas aptidões individuais.
A Teoria dos Jogos procura modelar, de maneira matematicamente formal, aspectos gerais de situações competitivas essencialmente estratégicas, como batalhas militares ou jogos de tabuleiro, dando ênfase especial ao processo de tomada de decisão dos adversários (Hillier, 1998).
Dentre as várias classes de jogos estudadas pela Teoria dos Jogos se encontra a Teoria dos Jogos Evolucionários, que é uma maneira de se pensar sobre a evolução num nível fenotípico, quando a adaptabilidade de um particular fenótipo depende de sua frequência na população (Smith, 1993).
A Teoria dos Jogos Evolucionários considera que os indivíduos são de certa forma pré-programados com algum comportamento, formalmente uma estratégia para um jogo, e que algum processo de seleção evolucionário operará na população distribuindo os comportamentos (Weibull, 1996).
A competição entre os indivíduos pelos recursos necessários a sua sobrevivência pode ser modelada com o auxílio da Teoria dos Jogos. Por exemplo, o jogo Hawk-Dove proposto por Maynard Smith & Price objetiva representar disputas entre pares de animais que estão lutando por um determinado recurso (Smith, 1993).
Os Algoritmos Genéticos (AG) inspiram-se nos conceitos da genética e da Teoria da Seleção Natural de Charles Darwin, sendo um poderoso mecanismo de busca de soluções e uma das técnicas que compõem a Computação Evolucionária (Goldberg, 1989).
O objetivo básico de um AG é evoluir uma população de soluções candidatas (cromossomo) para um determinado problema, até encontrar uma solução satisfatória (Mitchell, 1996).
O conjunto de parâmetros representado por um particular cromossomo é definido como genótipo, e contem as informações necessárias para a construção de um organismo, definido como fenótipo. Por exemplo, o conjunto de parâmetros especificando um particular projeto de construção de uma ponte é o genótipo, enquanto que a ponte construída é o fenótipo daquele indivíduo (Beasley, 1993).
Cada cromossomo possui uma adaptabilidade, também conhecida como fitness, que em termos biológicos pode ser a probabilidade do indivíduo se reproduzir (viabilidade) ou o número de descendentes que o indivíduo produzirá (fertilidade) (Mitchell, 1996).
A função de adaptabilidade transforma a medida do desempenho de um particular cromossomo, numa distribuição de oportunidades reprodutivas para o mesmo, levando em consideração o desempenho dos outros membros da população. A medida do desempenho do cromossomo é inferida através da função de avaliação, que considera o seu conjunto particular de parâmetros, independentemente dos outros indivíduos da população (Whitley, 1994).
A implementação de um AG inicia-se com a criação de uma população inicial de cromossomos; cada indivíduo desta população é avaliado segundo sua adaptabilidade, que permitirá definir a probabilidade que cada indivíduo tem de gerar descendentes.
Os operadores de seleção, recombinação e mutação são aplicados sobre a população a fim de gerar uma nova, que será a população inicial da próxima iteração. O processo é repetido até que soluções satisfatórias sejam alcançadas ou um número máximo de gerações (Koza, 1990).
A operação de seleção consiste na escolha de dois cromossomos da população, chamados de pais, que serão submetidos a operação de recombinação, gerando os descendentes. O método mais comum é o da Roleta Tradicional, que consiste na entrega de um setor de uma roleta para cada cromossomo proporcional a sua adaptabilidade, de forma que os mais aptos terão maior probabilidade de serem selecionados como pais (Coello, 1995).
A operação de recombinação, também conhecida como crossover, consiste na troca de partes do genótipo de dois pais para gerar dois novos descendentes. O método usual é a utilização de um único ponto de corte escolhido aleatoriamente, que divide o cromossomo em duas partes. Caso a operação não ocorra, os descendentes serão cópias exatas dos pais (Mitchell, 1996).
A operação de mutação altera aleatoriamente os valores de alguns genes do cromossomo, podendo ocorrer em cada gene com uma probabilidade muito pequena (Whitley, 1994).
Proposto originalmente por Maynard Smith & Price, o jogo Hawk-Dove modela disputas entre pares de animais, que estão lutando por um recurso de valor V. A interpretação dada ao valor é que o indivíduo que ganhar o recurso terá sua adaptabilidade Darwiniana aumentada em V, e o perdedor não sofrerá nenhuma alteração em sua adaptabilidade (Smith, 1993).
O jogo considera que cada competidor pode assumir duas estratégias, sendo elas:
A Tabela 1 mostra os pagamentos para o jogador adotando as estratégias das linhas, se o seu oponente adotar as estratégias das colunas. Os seguintes resultados podem ocorrer com base nesta tabela (Smith, 1993):
| Hawk | Dove | |
|---|---|---|
| Hawk | 1/2(V - C) | V |
| Dove | 0 | V/2 |
O presente trabalho propõe novos métodos para a operação de seleção dos AG, considerando não apenas o nível genotípico, mas também o nível fenotípico dos cromossomos. Este objetivo é alcançado através do emprego dos conceitos da Teoria dos Jogos, de modo que os cromossomos sejam selecionados como reprodutores não apenas pelo desempenho dos seus genótipos, mas também pelo desempenho de seus fenótipos em disputas com outros cromossomos.
O jogo Hawk-Dove, descrito na seção anterior, é o paradigma escolhido para os cromossomos tentarem aumentar suas probabilidades de reprodução. Ele é um jogo de dois participantes, no qual cada competidor deve assumir na disputa o comportamento Hawk ou Dove. Conforme o comportamento de cada participante, os seguintes resultados ocorrerão:
A melhora na adaptabilidade de um competidor está diretamente relacionada com o comportamento adotado pelo adversário e pelo seu próprio comportamento. O indivíduo que adotar a melhor estratégia na escolha do comportamento a ser utilizado em cada disputa, melhorará significativamente sua adaptabilidade.
As estratégias disponibilizadas para os cromossomos utilizarem nas disputas são:
A estratégia tit-for-tat é proposta pelo professor Anatol Rapoport, sendo composta por duas regras (Casti, 1994) (Axelrod, 1990):
Os métodos propostos para a operação de seleção utilizam o jogo Hawk-Dove e o método da Roleta, diferindo apenas na forma como estes são combinados.
No primeiro método, chamado de Hawk-Dove Roleta (HDR), o jogo Hawk-Dove é disputado pelos cromossomos antes que os setores da roleta sejam distribuídos, de modo que as alterações em suas aptidões durante o jogo estejam refletidas na roleta.
A adaptabilidade utilizada pela Roleta para distribuir os setores não representa mais exclusivamente o desempenho do genótipo, estando influenciada pelo desempenho do fenótipo de cada cromossomo.
O jogo consiste na escolha aleatória, com igual probabilidade, de dois cromossomos da população, para realizarem uma disputa. Cada competidor deverá assumir um comportamento a fim de melhorar a sua adaptabilidade.
No segundo método, chamado de Método Roleta Hawk-Dove sem alteração das probabilidades de seleção de cada cromossomo na Roleta (RHDSA), o jogo Hawk-Dove é mesclado junto com a Roleta, de forma que a Roleta não escolha diretamente os reprodutores, mas escolha os competidores de uma disputa, sendo que o ganhador será considerado como pai.
Deste modo, a Roleta precisa selecionar quatro cromossomos para que dois pais sejam entregues à operação de recombinação. Conforme as disputas vão ocorrendo, a adaptabilidade dos cromossomos vai sendo alterada, mas o ângulo de seu setor na Roleta não sofre modificação, pois a Roleta é montada uma única vez, no início do processo.
O resultado do jogo, indicando quem será o pai dos descendentes, é definido pelo comportamento adotado e pela adaptabilidade de cada competidor. No caso do comportamento dos competidores ser diferente, o competidor adotando o comportamento Hawk é selecionado como pai.
No caso dos competidores utilizarem o mesmo comportamento, o competidor com a maior adaptabilidade é selecionado como pai. A exceção ocorre quando ambos possuem a mesma adaptabilidade, quando o pai será selecionado aleatoriamente, com igual probabilidade, entre os dois competidores.
O último método, chamado de Método Roleta Hawk-Dove com alteração das probabilidades de seleção de cada cromossomo na Roleta (RHDCA), possui o mesmo funcionamento do RHDSA, com exceção que a Roleta é reconstruída depois que dois pais são selecionados na operação de seleção, refletindo a alteração na adaptabilidade dos cromossomos que disputaram o jogo.
Os métodos propostos são comparados com o método da Roleta Tradicional, utilizando como plataforma de testes o Problema do Caixeiro Viajante, com uma instância de 26 cidades com distâncias simétricas, representando as capitais dos estados brasileiros (DNER, 2000).
A base de dados é criada armazenando a menor distância encontrada e a geração em que ela foi encontrada, para cada execução de um AG empregando qualquer um dos métodos, objetivando observar a qualidade das repostas encontradas e o desempenho dos métodos.
As execuções são iniciadas com a mesma população inicial, e os seguintes parâmetros permanecem fixos para todas as execuções:
Alguns parâmetros são combinados entre si, para gerarem uma configuração de parâmetros, sendo eles:
Para identificar a estratégia que auxilia os métodos a produzirem os melhores resultados, são formados grupos conforme as estratégias utilizadas pelos cromossomos, sendo eles:
Cada método proposto possui quatro grupos de dados, sendo a combinação das estratégias citadas acima. Cada grupo é formado pelas amostras obtidas pelas execuções das 48 configurações de parâmetros, sendo que cada configuração gera 100 amostras independentes, totalizando 4.800 amostras por grupo.
A Tabela 2, que mostra o desempenho dos métodos através do número de gerações necessárias para alcançar a menor distância, indica que os métodos RHDSA e RHDCA são aproximadamente 50% mais rápidos do que o método da Roleta Tradicional para encontrar a menor distância, enquanto que o método HDR é aproximadamente 5% mais rápido.
| Métodos | Média | Desvio Padrão | Valor Mínimo | Valor Máximo |
|---|---|---|---|---|
| Roleta Tradicional | 5.523,95 | 2.857,90 | 137 | 10.000 |
| HDR Aleatório | 5.330,62 | 2.909,55 | 200 | 9.999 |
| HDR TFT25 | 5.283,19 | 2.937,68 | 246 | 10.000 |
| HDR TFT50 | 5.312,15 | 2.900,85 | 194 | 9.999 |
| HDR TFT75 | 5.387,74 | 2.885,21 | 183 | 10.000 |
| RHDSA Aleatório | 2.945,48 | 3.008,14 | 65 | 10.000 |
| RHDSA TFT25 | 2.914,69 | 2.993,13 | 53 | 9.999 |
| RHDSA TFT50 | 2.956,07 | 3.029,10 | 78 | 9.998 |
| RHDSA TFT75 | 2.946,17 | 3.034,30 | 64 | 9.997 |
| RHDCA Aleatório | 2.974,59 | 3.007,66 | 73 | 10.000 |
| RHDCA TFT25 | 2.946,15 | 3.010,15 | 64 | 9.999 |
| RHDCA TFT50 | 2.921,59 | 3.017,49 | 69 | 9.999 |
| RHDCA TFT75 | 2.990,11 | 3.019,31 | 55 | 10.000 |
A Tabela 3, que mostra a qualidade das repostas fornecidas através das menores distâncias encontradas, indica que não existe uma grande diferença entre os métodos propostos e o método da Roleta Tradicional.
Os resultados fornecidos pelo método HDR são aproximadamente 2% melhores que os resultados do método da Roleta Tradicional. Os métodos RHDSA e RHDCA apresentaram resultados aproximadamente 0,5% inferiores aos do método da Roleta Tradicional, mas com um desempenho muito superior.
| Métodos | Média | Desvio Padrão | Valor Mínimo | Valor Máximo |
|---|---|---|---|---|
| Roleta Tradicional | 24.607,10 | 2.407,83 | 20.409 | 35.580 |
| HDR Aleatório | 24.268,59 | 2.324,55 | 20.409 | 34.764 |
| HDR TFT25 | 24.220,27 | 2.276,46 | 20.409 | 34.432 |
| HDR TFT50 | 24.217,69 | 2.272,65 | 20.409 | 32.344 |
| HDR TFT75 | 24.216,33 | 2.264,14 | 20.409 | 32.937 |
| RHDSA Aleatório | 24.920,02 | 2.339,09 | 20.409 | 35.037 |
| RHDSA TFT25 | 24.820,20 | 2.285,42 | 20.409 | 35.660 |
| RHDSA TFT50 | 24.819,20 | 2.325,64 | 20.409 | 36.074 |
| RHDSA TFT75 | 24.791,70 | 2.282,28 | 20.409 | 35.437 |
| RHDCA Aleatório | 24.805,72 | 2.298,63 | 20.409 | 35.179 |
| RHDCA TFT25 | 24.824,82 | 2.266,60 | 20.409 | 35.420 |
| RHDCA TFT50 | 24.808,35 | 2.318,67 | 20.409 | 36.312 |
| RHDCA TFT75 | 24.821,90 | 2.321,48 | 20.409 | 34.838 |
Os conjuntos que obtiveram as menores médias para a variável Distância foram aquelas que utilizavam a estratégia tit-for-tat, sendo que conforme a porcentagem de indivíduos adotando tal estratégia aumenta, a qualidade da resposta fornecida pelo método também sofre um aumento.
Todos os métodos encontraram o mesmo valor mínimo para a variável Distância. Esse ponto provavelmente é um ponto de mínimo local na superfície de resposta, não sendo possível comprovar se tal ponto é o mínimo global. De forma geral, os métodos propostos tiveram um resultado satisfatório em relação ao obtido pelo método da Roleta Tradicional.
Diversos autores já propuseram utilizar Algoritmos Genéticos como um mecanismo para desenvolver novas estratégias para competidores envolvidos em determinados jogos, auxiliando as pesquisas em Teoria dos Jogos.
Utilizar a Teoria dos Jogos como um mecanismo para melhorar o desempenho dos Algoritmos Genéticos ainda é uma novidade, sendo um vasto campo a ser pesquisado.
A inserção de uma competição entre os indivíduos nos Algoritmos Genéticos, guiada não somente por fatores aleatórios, pode tornar a busca dos indivíduos pelo aumento de suas aptidões mais eficiente e provida de uma certa "racionalidade". Essa adaptabilidade tem características dinâmicas, variando conforme o resultado das disputas no qual o indivíduo se engaja. É uma forma de fazer com que os Algoritmos Genéticos trabalhem também com os fenótipos dos indivíduos, em vez de trabalharem apenas no nível genotípico.
O desempenho dos indivíduos nas disputas está diretamente relacionado com a estratégia adotada pelos mesmos na escolha dos movimentos. O emprego de estratégias racionais pode fornecer uma eficiência adicional aos Algoritmos Genéticos na busca de soluções satisfatórias para problemas difíceis.
Axelrod, Robert. (1990). The Evolution of Cooperation. London: Penguin Books. 241 pages.
Beasley, David. (1993). An Overview of Genetic Algorithms: Part 1, Fundamentals. In University Computing 15 (2), 58-69. 12 pages.
Casti, John L. (1994). Cooperation: The Ghost in the Machinery of Evolution. In Cooperation and Conflict in General Evolutionary Processes, 63-88, John Wiley & Sons, Inc. 26 pages.
Coello, Carlos Artemio Coello. (1995). Introducción a los Algoritmos Genéticos. In Soluciones Avanzadas: tecnologías de información y estrategias de negocios 3 (17), 5-11. 7 pages.
DNER. (2000). Departamento Nacional de Estradas de Rodagem. Acessado em Fevereiro de 2000.
Goldberg, David Edward. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Inc. 412 pages.
Hillier, Frederick S. (1998). Introdução à Pesquisa Operacional. Rio de Janeiro: Editora Campus. 828 páginas.
Koza, John R. (1990). Genetically Breeding Populations of Computer Programs to Solve Problems in Artificial Intelligence. In Proceedings of the Second International Conference on Tools for AI, 819-827. Los Alamitos, CA: IEEE Computer Society Press. 9 pages.
Mangano, Salvatore R. (1996). A Genetic Algorithm White Paper: an introduction to genetic algorithm implementation, theory, application, history and future potencial. In Man Machine Interfaces, Inc. 24 pages.
Mitchell, Melanie. (1996). An Introduction to Genetic Algorithms. Cambridge: MIT Press. 221 pages.
Smith, John Maynard. (1993). Evolution and the Theory of Games. Cambridge: Cambridge University Press. 234 pages.
Weibull, Jörgen W. (1996). Evolutionary Game Theory. Cambridge: MIT Press. 265 pages.
Whitley, Darrell. (1994). A Genetic Algorithm Tutorial. In Statistics and Computing 4, 65-85. 37 pages.
Artigo científico apresentado no I Congresso Brasileiro de Computação
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 