Colaboradores - Cristiano LehrerLehrer, Cristiano; Borges, Paulo Sergio da Silva. Método de Seleção Hawk-Dove Roulette para Algoritmos Genéticos. Trabalho apresentado na Semana de Informática de Cascavel, Cascavel/PR, 2001. 7 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 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.
A Biologia Evolucionária é uma fonte de inspiração para resolver problemas complexos, os quais requerem buscas em um vasto campo de soluções possíveis (Mitchell, 1999).
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 (AG) são métodos baseados nos princípios da seleção natural e da sobrevivência dos mais apto, simulando o processo de 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.
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).
Inspirados nos conceitos da genética e da Teoria da Seleção Natural de Charles Darwin, os Algoritmos Genéticos (AG) são um poderoso mecanismo de busca de soluções e uma das técnicas que compõem a Computação Evolucionária (Goldberg, 1989).
Propostos por John Holland entre os anos 1960 e 1970 na Universidade de Michigan, os AG são uma abstração da evolução biológica. A base teórica dos AG é apresentada no seu livro Adaptation in Natural Artificial and Systems (Holland, 1975).
O objetivo principal de Holland não era o desenvolvimento de algoritmos para resolver problemas específicos, mas um estudo formal do fenômeno da adaptação que acontece na natureza, e desenvolver um modo em que os mecanismos da adaptação natural pudessem ser incorporados pelos computadores (Mitchell, 1996).
Frequentemente visto como métodos de otimização, os AG podem ser aplicados num grupo de problemas que cresce a cada dia (Whitley, 1994), incluindo sistemas sociais, ecologia, economia, evolução do aprendizado e várias outras áreas do conhecimento (Mitchell, 1996).
Conforme a definição de Koza (1990), um AG é um algoritmo matemático altamente paralelo que transforma populações de objetos matemáticos individuais em novas populações utilizando operações genéticas, como a reprodução sexual (recombinação), e a reprodução proporcional a adaptabilidade, que é o princípio Darwiniano da sobrevivência do mais apto.
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. A adaptabilidade ou fitness do indivíduo como solução do problema, depende da ação do fenótipo que pode ser deduzido através do genótipo, isto é, ele pode ser calculado com base no cromossomo utilizando uma função de adaptabilidade ou função de fitness (Beasley, 1993).
A implementação de um AG inicia 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 de modo a gerar uma nova, que será a população inicial na próxima iteração. O processo é repetido até que soluções satisfatórias ou um número máximo de gerações sejam alcançados (Koza, 1992).
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 normalmente utilizado é o da Roleta, que consiste na entrega de um setor de uma roleta para cada cromossomo proporcional a sua adaptabilidade, de forma que os mais aptos tenham mais chances 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. A probabilidade de acontecer a operação normalmente é muito pequena, por volta de 1% para cada gene (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 Hawk-Dove considera que cada competidor deve assumir uma das duas estratégias disponíveis, sendo que cada estratégia possui um comportamento em particular. As estratégias são:
A Tabela 1 exibe os valores pagos ao jogador adotando as estratégias das linhas, se o seu oponente adotar as estratégias das colunas, ou seja, os pagamentos são referentes apenas para o jogador da linha.
| Hawk | Dove | |
|---|---|---|
| Hawk | 1/2(V - C) | V |
| Dove | 0 | V/2 |
Com base na Tabela 1 os seguintes resultados podem ocorrer (Smith, 1993):
O presente trabalho propõe um novo método para a operação de seleção utilizada em Algoritmos Genéticos, 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 genótipos 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 um dos dois comportamentos disponibilizados: 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.
A única informação disponibilizada para os cromossomos antes da realização de uma disputa é a identidade do seu adversário.
A estratégia utilizada pelo adversário pode ser deduzida indiretamente, analisando os comportamentos adotados nas jogadas anteriores, caso seja necessário. A adaptabilidade real do adversário não é fornecida e nem pode ser deduzida.
Para auxiliar os cromossomos na difícil tarefa de escolher qual o comportamento a ser adotado frente a um adversário, algumas estratégias foram disponibilizadas.
A estratégia tit-for-tat é proposta pelo professor Anatol Rapoport, sendo composta por duas regras (Casti, 1994):
A estratégia tit-for-tat é uma estratégia que possui uma boa combinação entre gentileza, retaliação, perdão e clareza. A gentileza a previne de problemas desnecessários. A retaliação desencoraja o outro lado a explorá-la. O perdão ajuda ao retorno da mútua colaboração e a clareza facilita que a mesma seja reconhecida pelo adversário (Axelrod, 1990).
As estratégias disponibilizadas para os cromossomos utilizarem durante as disputas são:
No método Hawk-Dove Roulette (HDR), o Jogo Hawk-Dove (Figura 1 - passo 3.1) é realizado antes que os setores da roleta sejam distribuídos aos cromossomos (Figura 1 - passo 3.2), de modo que as alterações sofridas pelos cromossomos durante as disputas estejam refletidas na roleta.
1. Carregar população inicial;
2. Avaliar a população inicial;
3. Repetir até g gerações:
3.1. Repetir até d disputas:
3.1.1. Selecionar dois competidores;
3.1.2. Obter o comportamento dos competidores;
3.1.3. Alterar a adaptabilidade dos competidores conforme o comportamento adotado por cada um;
3.2. Montar a roleta;
3.3. Repetir até número de descendentes = tamanho da população:
3.3.1. Selecionar dois pais utilizando a roleta;
3.3.2. Aplicar a operação de recombinação sobre os pais selecionados no passo anterior;
3.3.3. Aplicar a operação de mutação sobre os descendentes gerados no passo anterior;
3.4. Substituir a população antiga pela nova;
3.5. Avaliar a nova população.
Figura 1: Pseudocódigo do algoritmo com o método HDR
A adaptabilidade utilizada pela Roleta para distribuir os setores não representa mais exclusivamente o desempenho do genótipo, estando influenciado 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á adotar um comportamento a fim de melhorar sua adaptabilidade.
O método proposto é comparado com o método da Roleta Tradicional, utilizando como plataforma de teste 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).
O Problema do Caixeiro Viajante (PCV), também conhecido como Traveling Salesman Problem, é um problema clássico da otimização combinatória, tendo despertado grande interesse nos pesquisadores da área. É um problema simples de descrever mas difícil de resolver, possuindo inúmeras aplicações práticas. O PCV pertence a classe de problemas NP-difíceis, no qual o tempo gasto para resolvê-lo cresce exponencialmente ao tamanho da instância (Bureal, 2000).
O número total de soluções candidatas (rotas) para um PCV simétrico é (n - 1)! / 2 (West, 1996). Utilizando uma instância de 26 cidades (n = 26), tem-se 7,75 x 1024 possibilidades. Considerando a existência de uma máquina que consiga avaliar 1.000.000.000 possibilidades por segundo, o que totalizaria 3,15 x 1016 possibilidades avaliadas por ano. Esta máquina conseguiria avaliar todas as possibilidades, encontrando a solução ótima para esta coleção de cidades, em 2,46 x 108 anos.
A base de dados é criada armazenando a menor distância encontrada e a geração em que a menor distância apareceu pela primeira vez, para cada execução de um AG empregando qualquer um dos métodos.
Com estas duas variáveis é possível medir o desempenho do método (variável geração) e a qualidade das repostas fornecidas (variável distância).
Normalmente a população inicial de um AG é criada aleatoriamente, mas a fim de controlar este fator a população inicial utilizada pelos ensaios é fixa (Figura 1 - passo 1).
Há muitos fatores que influenciam nas repostas encontradas pelo método, sendo alguns oriundos do algoritmo genético e outros do Jogo Hawk-Dove. Os fatores cujos níveis permanecerão constantes durante os ensaios são:
Os fatores cujos níveis serão alterados durante a realização do experimento são:
Para identificar a estratégia que auxilia o método HDR a produzir os melhores resultados, são formados grupos conforme as estratégias utilizadas pelos cromossomos, sendo elas:
Para cada grupo de estratégias existem 48 tratamentos a serem ensaiados, que são as combinações específicas dos diferentes níveis dos fatores analisados.
De modo a minimizar os efeitos aleatórios, para cada tratamento são realizados 100 ensaios, formando uma base de dados com 4.800 amostras para cada método analisado. Para a analise em questão foram gerados 38.400 amostras.
A Tabela 2 exibe o desempenho dos métodos através do número de gerações necessárias para alcançar a menor distância. Conforme se pode observar, o método HDR é aproximadamente 5% mais rápido que o método Tradicional, encontrando a melhor resposta com um número menor de gerações, em média.
| Método | Média | Desvio Padrão |
|---|---|---|
| Tradicional | 5.523,95 | 2.857,901 |
| HDR Aleatório | 5.330,62 | 2.909,556 |
| HDR Hawk | 5.404,71 | 2.889,578 |
| HDR Dove | 5.440,28 | 2.916,775 |
| HDR TFT25 | 5.283,19 | 2.937,682 |
| HDR TFT50 | 5.312,15 | 2.900,859 |
| HDR TFT75 | 5.387,74 | 2.885,216 |
| HDR Misto | 5.372,40 | 2.902,922 |
A Tabela 3 exibe a qualidade das respostas fornecidas pelos métodos através das menores distâncias encontradas, em quilômetros, indicando que não existe uma diferença substancial entre o método proposto e o método da Roleta Tradicional.
| Método | Média | Desvio Padrão |
|---|---|---|
| Tradicional | 24.607,10 | 2.407,838 |
| HDR Aleatório | 24.268,59 | 2.324,559 |
| HDR Hawk | 24.328,30 | 2.276,145 |
| HDR Dove | 24.375,95 | 2.320,724 |
| HDR TFT25 | 24.220,27 | 2.276,465 |
| HDR TFT50 | 24.217,69 | 2.272,653 |
| HDR TFT75 | 24.216,33 | 2.264,144 |
| HDR Misto | 24.275,28 | 2.296,201 |
Os resultados fornecidos pelo Método HDR são aproximadamente 2% melhores que os resultados obtidos pelo método da Roleta Tradicional.
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.
Se todos os indivíduos adotassem a estratégia tit-for-tat, poderia se esperar que o resultado encontrado seria melhor que o encontrado pelo TFT75, mas essa conclusão é errônea.
A estratégia tit-for-tat especifica que no primeiro encontro o participante deve colaborar, ou seja, adotar o comportamento Dove. Se todos os cromossomos adotam tal estratégia, o resultado é o mesmo encontrado pela estratégia Dove, cujo desempenho é mais fraco que a da estratégia TFT75.
Todos os grupos encontraram o mesmo valor mínimo para a variável Distância, sendo de 24.409 km. 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. A Figura 2 exibe a melhor rota encontrada.
De forma geral, o método HDR obteve o melhor desempenho, encontrando, em média, os melhores resultados no mesmo intervalo de tempo que o método Tradicional.
Diversos autores já propuseram utilizar Algoritmos Genéticos como 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 a 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 cromossomos, 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.
Buriol, Luciana Salete. (2000). Algoritmo Memético para o Problema do Caixeiro Viajante Assimétrico como Parte de um Framework para Algoritmos Evolutivos. Dissertação de Mestrado, Universidade Estadual de Campinas, Departamento de Engenharia de Sistemas, Faculdade de Engenharia Elétrica e de Computação, UNICAMP, Campinas, São Paulo.
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.
Holland, John Henry. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. 211 pages.
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.
Koza, John R. (1992). Genetic Programming: on the programming of computers by means of natural selection. A Broad Book. 840 pages.
Mitchell, Melanie. (1996). An Introduction to Genetic Algorithms. Cambridge: MIT Press. 221 pages.
Mitchell, Melanie. (1999). Evolutionary Computation: an overview. In Annual Review of Ecology and Systematics, 20, 593-616. 24 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.
West, Douglas Brent. (1996). Introduction to Graph Theory. Upper Saddle River: Prentice Hall, Inc. 470 pages.
Whitley, Darrell. (1994). A Genetic Algorithm Tutorial. In Statistics and Computing 4, 65-85. 37 pages.
Artigo científico apresentado na Semana de Informática de Cascavel
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 