Colaboradores - Cristiano LehrerLehrer, Cristiano; Borges, Paulo Sergio da Silva. Algoritmos Genéticos com Operação de Seleção Hawk-Dove com Estratégia Tit-For-Tat, e com Operação de Recombinação com Taxas Variáveis. Trabalho apresentado no XXII Encontro Nacional de Engenharia de Produção, Curitiba/PR, 2002. 8 páginas.
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 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 Biologia Evolucionária é uma fonte de inspiração para resolver problemas complexos, os quais requerem uma busca em um vasto campo de soluções possíveis (Mitchell, 1999). A própria natureza teve que realizar uma busca num grande 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 do mais apto, simulando o processo da evolução natural para desenvolver soluções para o mundo real (Beasley, 1993). A estes princípios são acrescentados os conceitos iniciados por Mendel, referentes à hereditariedade e à estrutura genética dos seres vivos (Smith, 2000).
A maioria das implementações de AG consideram os indivíduos (cromossomos) como agentes passivos. Os indivíduos nascem com uma aptidão definida e inalterável, uma vez que a adaptabilidade do indivíduo é calculada com base apenas no seu código genético, e o genótipo do indivíduo não se altera durante a sua existência.
O conjunto de dados 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 (Goldberg, 1989). A adaptabilidade ou aptidão (do inglês 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).
Na natureza, a adaptabilidade dos organismos não é apenas influenciada pelo seu material genético, sendo também afetada pela interação existente entre os indivíduos, seja entre indivíduos da mesma espécie ou entre indivíduos de espécies diferentes, que estão competindo para melhorarem 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).
Outro pressuposto utilizado pela maioria das implementações de AG, se refere a definição dos valores dos parâmetros utilizados pelos operadores genéticos, em especial a taxa de recombinação - crossover. Na maioria dos casos, eles são definidos à priori e se mantêm fixos durante toda a execução do algoritmo, não considerando as particularidades dos indivíduos que são submetidos aos operadores.
Na natureza, a probabilidade de dois indivíduos gerarem descendentes é calculada com base na análise das características de um indivíduo pelo outro. Cada animal possui algum critério de avaliação para comparar seus pretendentes, de modo a escolher o melhor pretendente disponível (Miller, 2000).
Alguns indivíduos podem estar procurando parceiros com preferências semelhantes as suas, ou com preferências totalmente opostas, ou ainda com preferências nem muito iguais e nem muito diferentes.
O presente trabalho apresenta novos métodos para a operação de seleção utilizada pelos AG, considerando o nível fenotípico junto com o nível genotípico, em vez de considerar apenas o material genético dos organismos. Também é apresentado alternativas ao operador de recombinação, propondo que seus parâmetros sejam regulados pela distância entre a aptidão dos indivíduos escolhidos para a operação de recombinação.
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).
O método proposto para a operação de seleção considera que a Roleta não utiliza apenas informações advindas exclusivamente do genótipo do indivíduo, mas também emprega informações provenientes do fenótipo.
Este objetivo é alcançado através da utilização dos conceitos da Teoria dos Jogos, de forma que os indivíduos sejam selecionados como reprodutores não apenas pelo seu material genético, mas também pelo seu desempenho em disputas com outros indivíduos da população. O paradigma escolhido para que os cromossomos tentem melhorar sua probabilidade de reprodução é o jogo Hawk-Dove.
Proposto originalmente por Maynard Smith, 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. Cada indivíduo pode assumir um dos seguintes comportamentos (Smith, 1993):
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. Os seguintes resultados podem ocorrer (Smith, 1993):
| Hawk | Dove | |
|---|---|---|
| Hawk | 1/2(V - C) | V |
| Dove | 0 | V/2 |
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 (Axelrod, 1990), (Casti, 1994):
Para evitar que a mesma estratégia seja utilizada por todos os cromossomos da população, se definiu que os 25% melhores cromossomos utilizam a estratégia tit-for-tat, e os demais (75%) escolhem aleatoriamente o comportamento a ser adotado, com iguais probabilidades entre o comportamento Hawk e Dove.
O jogo Hawk-Dove é mesclado com o método da Roleta, de modo que a mesma não selecione os reprodutores diretamente, mas selecione os competidores para o jogo. A Figura 1 exibe o pseudocódigo de um AG utilizando o método proposto.
1. Criar a população inicial;
2. Avaliar a população inicial;
3. Repetir para m gerações:
3.1. Criar a roleta;
3.2. Repetir até o número de descendentes ser igual ao tamanho da população:
3.2.1. Selecionar dois competidores utilizando a roleta;
3.2.2. Selecionar o primeiro pai através do jogo Hawk-Dove;
3.2.3. Selecionar dois competidores utilizando a roleta;
3.2.4. Selecionar o segundo pai através do jogo Hawk-Dove;
3.2.5. Aplicar a operação de recombinação sobre os pais selecionados pelo jogo;
3.2.6. Aplicar a operação de mutação sobre os descendentes gerados na etapa anterior;
3.3. Substituir a população antiga pela nova;
3.4. Avaliar a nova população.
Figura 1: Pseudocódigo de um AG utilizando o método de seleção RHDSA
Os competidores são selecionados para o jogo utilizando apenas a informação proveniente de seus genótipos, uma vez que as seções da Roleta são distribuídas entre os cromossomos antes que qualquer disputa ocorra (Etapa 3.1 da Figura 1), e não são mais alteradas durante aquela geração.
O jogo Hawk-Dove é realizado nas etapas 3.2.2 e 3.2.4 da Figura 1. É necessário a realização de duas disputas para que dois reprodutores sejam selecionados para a operação de recombinação. Cada disputa seleciona um reprodutor entre os dois competidores selecionados pela Roleta.
O primeiro passo realizado pelos competidores é a escolha do comportamento que adotarão na disputa, de acordo com a estratégia adotada por indivíduo. Os seguintes resultados podem ocorrer:
Neste artigo são apresentados três métodos para a operação de recombinação, sugeridos por Vieira (2000), que utilizando informações provenientes dos cromossomos, buscam obter a melhor taxa de recombinação sobre os dois indivíduos em análise.
Os métodos atuam diretamente sobre a probabilidade da operação de recombinação, utilizando os valores de aptidão (fitness) de um par de cromossomos (x e y), previamente selecionados pelo operador de seleção, para auferir o valor da probabilidade de ocorrência da operação de recombinação.
O primeiro método é chamado de Proximity, utilizando a seguinte função para auferir as probabilidades de ocorrência do operador:
Proximity(x, y) = e-|x-y| (Equação 1)
O método Proximity utiliza uma função simétrica para calcular as probabilidades de ocorrência, ou seja, conforme o valor da adaptabilidade do indivíduo x se aproxima do valor da adaptabilidade do indivíduo y a equação tenderá a 1.
Num contexto biológico se pode afirmar que o método Proximity beneficia pares de indivíduos com preferências ou personalidades semelhantes, dando-lhes uma probabilidade de gerarem descendentes maior do que a de casais com preferências opostas.
A Figura 2 ilustra o comportamento da função utilizada pelo método Proximity. Os valores utilizados são normalizados entre quatro negativo e quatro positivo, e uma das variáveis é fixada em zero, para efeito de visualização.
O segundo método proposto é Distance, utilizando a seguinte equação para calcular as probabilidades de ocorrência do operador:
Distance(x, y) = 1 - Proximity(x, y) (Equação 2)
O método Distance, da mesma forma que o método Proximity, utiliza uma equação simétrica, com valores inversamente proporcionais aos fornecidos pelo método Proximity, ou seja, conforme o valor da adaptabilidade do indivíduo x se afasta do valor da adaptabilidade do indivíduo y, a função tenderá a 1.
Num contexto biológico se pode afirmar que o método Distance beneficia pares de indivíduos com preferências ou personalidades opostas, dando-lhes uma probabilidade de gerarem descendentes maior do que a de casais com preferências semelhantes. O método Distance é uma abstração do velho ditado popular: "Os opostos se atraem!".
A Figura 2 ilustra o comportamento da função utilizada pelo método Distance. Os valores utilizados são normalizados entre quatro negativo e quatro positivo, e uma das variáveis é fixada em zero, para efeito de visualização.
O último método proposto é o Central, que se utiliza da seguinte função para calcular a probabilidade de ocorrência do operador recombinação sobre um par de indivíduos:
Central(x, y) = e-|0,5 - Proximity(x, y)| (Equação 3)
O método Central beneficia pares de indivíduos cujos valores de adaptabilidade não sejam nem muito semelhantes e nem muito diferentes, ou seja, os valores de adaptabilidade devem estar num meio termo entre os extremos.
Em um contexto biológico se pode afirmar que o método Central beneficia pares de indivíduos que possuam algumas preferências iguais e ao mesmo tempo possuam algumas preferências opostas, dando-lhes uma maior probabilidade de gerarem descendentes.
Essa função procura representar que indivíduos com aptidões nem muito semelhantes e nem muito opostas. O método Central nunca fornece uma probabilidade de ocorrência da operação de recombinação para um par de indivíduos menor do que 0,6, em oposição aos demais métodos propostos que podem fornecer valores abaixo de 0,6, inclusive zero.
A Figura 3 ilustra o comportamento da função utilizada pelo método Central. Os valores utilizados são normalizados entre quatro negativo e quatro positivo, e uma das variáveis é fixada em zero, para efeito de visualização.
Aos métodos propostos é acrescentado ainda um modificador, chamado de operação forçada. A utilização desse modificador inibe que os pais sejam copiados na nova população caso a operação de recombinação não ocorra, ou seja, os filhos não podem ser cópias idênticas dos seus respectivos pais.
Os métodos propostos são comparados com o método tradicional, que utiliza taxas fixas para a operação de recombinação e o método da Roleta no método da seleção. A plataforma de teste utilizado é o problema do caixeiro viajante, um problema típico da Engenharia da Produção, com uma instância de 58 cidades com distâncias simétricas (West, 1994).
A base de dados é criada armazenando, para cada execução de um AG empregando algum dos métodos propostos, a menor distância encontrada e a geração onde essa distância apareceu na população pela primeira vez, objetivando observar a qualidade das respostas encontradas e o desempenho dos métodos.
A análise dos métodos será realizada em duas etapas. A primeira etapa objetiva encontrar a melhor configuração de parâmetros para o método em análise, através de um planejamento de experimentos e da análise de superfície de resposta.
Utilizando a configuração de parâmetros fornecida pela primeira etapa, são geradas 1.000 novas amostras, que formarão a base de dados a ser utilizada na análise descritiva, utilizada para comparar os resultados dos métodos, apresentado no presente trabalho.
As execuções se iniciam sempre com uma população inicial criada aleatoriamente e uma cidade de origem definida também de modo aleatório. Dentre os vários parâmetros que podem ser manipulados num AG, os seguintes são mantidos fixos em todas as execuções:
Com o objetivo de encontrar o conjunto de parâmetros que produza o melhor resultado, são geradas 100 amostras para cada combinação dos parâmetros abaixo relacionados:
A Tabela 2 apresenta a análise descritiva da variável geração para os dados obtidos na segunda etapa. Essa análise objetiva avaliar o desempenho dos métodos quanto ao número de gerações necessários, em média, para encontrar a menor distância.
| Seleção - Recombinação | Média | Desvio Padrão | Valor Mínimo | Valor Máximo |
|---|---|---|---|---|
| Roleta - Fixa | 3.918,56 | 957,07 | 922 | 5.000 |
| Roleta - Fixa/forçada | 3.969,67 | 936,40 | 1.000 | 5.000 |
| RHDSA - Fixa | 4.349,77 | 664,39 | 1.556 | 5.000 |
| RHDSA - Fixa/forçada | 4.214,80 | 795,86 | 1.039 | 5.000 |
| RHDSA - Proximity | 4.475,97 | 591,01 | 1.283 | 5.000 |
| RHDSA - Proximity/forçada | 3.807,64 | 939,56 | 550 | 5.000 |
| RHDSA - Distance | 4.175,23 | 790,47 | 727 | 5.000 |
| RHDSA - Distance/forçada | 3.926,17 | 952,68 | 696 | 5.000 |
| RHDSA - Central | 4.201,94 | 795,89 | 1.125 | 5.000 |
| RHDSA - Central/forçada | 4.165,03 | 834,61 | 1.154 | 5.000 |
Conforme apresentado na Tabela 2, os métodos propostos necessitam de uma quantidade maior de gerações, em média, para encontrar a melhor resposta para o problema do que o método Tradicional (seleção Roleta e recombinação Fixa).
A Tabela 3 apresenta a análise descritiva da variável distância para os dados obtidos na segunda etapa. Essa análise objetiva avaliar o desempenho dos métodos quanto a qualidade das respostas encontradas, buscando o método que encontre as menores distâncias, uma vez que a plataforma de teste é um problema de minimização.
| Seleção - Recombinação | Média | Desvio Padrão | Valor Mínimo | Valor Máximo |
|---|---|---|---|---|
| Roleta - Fixa | 40.878,47 | 3.163,35 | 31.634 | 50.108 |
| Roleta - Fixa/forçada | 40.644,92 | 3.081,16 | 32.680 | 52.693 |
| RHDSA - Fixa | 36.429,47 | 3.101,34 | 27.539 | 47.619 |
| RHDSA - Fixa/forçada | 36.535,54 | 3.018,52 | 29.322 | 48.467 |
| RHDSA - Proximity | 36.764,74 | 3.104,01 | 29.025 | 48.862 |
| RHDSA - Proximity/forçada | 36.549,07 | 3.040,47 | 29.318 | 46.564 |
| RHDSA - Distance | 36.748,88 | 2.728,33 | 28.852 | 45.334 |
| RHDSA - Distance/forçada | 37.787,37 | 2.881,34 | 30.820 | 47.430 |
| RHDSA - Central | 36.658,18 | 3.031,26 | 29.393 | 47.898 |
| RHDSA - Central/forçada | 36.877,17 | 3.117,18 | 28.529 | 47.235 |
Conforme os resultados apresentados na Tabela 3, todos os métodos propostos apresentaram um resultado superior ao do método Tradicional. O melhor desempenho foi obtido pelo método RHDSA - Fixa, que obteve uma melhora de aproximadamente 10,88% sobre o método Tradicional.
Em comparação com o método Tradicional com operação forçada, que obteve uma melhora de 0,57% sobre o método Tradicional puro, os desempenhos alcançados pelos métodos propostos sofrem uma redução. O método RHDSA - Fixa/forçada alcança uma melhora de 10,11% sobre o método tradicional com operação forçada.
O desvio padrão apresentado pelos métodos propostos são melhores que o apresentado pelo método Tradicional, chegando no caso do método RHDSA - Distance ser 13,75% melhor do 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.
A utilização de critérios racionais para especificar a taxa de ocorrência da operação de recombinação, considerando características dos indivíduos envolvidos na operação, procura tornar a busca por soluções satisfatórias na superfície adaptativa uma atividade mais eficiente do que as utilizadas pelos métodos convencionais.
Os métodos propostos eliminam a necessidade de se especificar uma taxa, a priori, para a operação de recombinação, que na maioria dos casos é estimada com base na experiência pessoal do pesquisador, auxiliando que resultados mais significativos ou idênticos aos encontrados pelo método tradicional, sejam apresentados sem a necessidade de se experimentar ou estimar várias taxas, até que a mais adequada ao problema em questão seja especificada.
O emprego de critérios racionais, para auxiliar o trabalho dos operadores genéticos, 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.
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.
Miller, Geoffrey F. (2000). A Mente Seletiva: como a escolha sexual influencia a evolução da natureza humana. Rio de Janeiro: Campus. 422 páginas.
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.
Smith, John Maynard. (2000). The Theory of Evolution. Cambridge, University Press. 380 pages.
Vieira, Richard G. S. (2000). Algoritmos Genéticos com Probabilidade de Crossover Variável. Artigo Técnico Interno. Florianópolis: Pós-Graduação em Ciência da Computação.
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.
Artigo científico apresentado no XXII Encontro Nacional de Engenharia de Produção
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 