Colaboradores - Cristiano LehrerLehrer, Cristiano; Borges, Paulo Sergio da Silva. Algoritmos Genéticos com Operação de Recombinação em Função da Distância das Adaptabilidades dos Cromossomos. Trabalho apresentado na 54ª Reunião da Sociedade Brasileira para o Progresso da Ciência, Goiânia/GO, 2002. 1 página.
(INTRODUÇÃO) A Computação Evolucionária (CE) é uma das áreas da Inteligência Artificial (IA) que inspira-se na evolução biológica para resolver, computacionalmente, problemas complexos, que requerem a busca em um vasto campo de soluções candidatas, e quando não estão disponíveis métodos e/ou conhecimentos para direcionar produtivamente essa busca.
Os Algoritmos Genéticos (AGs) são métodos da CE que seguem o paradigma neo-darwiniano, o qual associa as ideias de sobrevivência do mais apto, expostas por Charles Darwin no livro The Origin of Species, e os conceitos iniciados por Mendel, referentes à hereditariedade e à estrutura genética dos seres vivos.
Na maioria das implementações de AGs, os parâmetros utilizados pelos operadores genéticos (por exemplo, a taxa de recombinação - crossover e a taxa de mutação), são definidos à priori e mantêm-se fixos durante toda a execução do algoritmo, sem considerar as particularidades dos indivíduos que serão submetidos aos operadores.
O presente trabalho apresenta alternativas ao operador de recombinação, propondo que os seus parâmetros sejam regulados pela distância entre os índices de adaptabilidade dos indivíduos escolhidos para a operação. O objetivo é verificar se é possível melhorar a qualidade dos resultados encontrados pelos AGs.
(METODOLOGIA) Os métodos propostos atuam sobre a probabilidade de ocorrência da operação de recombinação, sobre dois indivíduos escolhidos pelo método da Roleta. Os métodos são guiados pelo valor da adaptabilidade de cada indivíduo (x e y), ou seja, conforme os cromossomos se apresentam ao método de recombinação, a probabilidade de ocorrência da operação é alterada. Para que essa metodologia fosse possível, a adaptabilidade dos indivíduos é normalizada, num valor real entre zero e quatro.
O método Proximity, denotado por Proximity(x, y) = e-|x-y|, beneficia dois cromossomos com aptidões semelhantes, ou seja, a medida que a adaptabilidade de x se aproxima da adaptabilidade de y, a taxa de recombinação tende a 100%.
O método Distance, especificado por Distance(x, y) = 1 - Proximity(x, y), beneficia dois cromossomos com aptidões opostas, ou seja, a medida que a adaptabilidade de x se afasta da adaptabilidade de y, a taxa de recombinação tende a 100%.
O método Central, denotado por Central(x, y) = e-|0,5 - Proximity(x, y)|, beneficia dois cromossomos que não sejam nem muito parecidos, nem muito diferentes, ou seja, a taxa de recombinação tenderá a 100% quando a distância da adaptabilidade dos cromossomos envolvidos esteja a 50%.
A cada método é acrescentado uma variação, chamada de operação forçada. Essa variação inibe que cópias idênticas dos pais sejam inseridas na nova população, caso a operação de recombinação não ocorra.
(RESULTADOS) Os métodos propostos são comparados com o operador tradicional, cuja taxa de recombinação é fixa para todos os cromossomos, utilizando como plataforma de teste o problema do caixeiro viajante, com uma instância de 58 cidades com distâncias simétricas. A base de dados para a análise é formada por 8.000 amostras, sendo 1.000 para cada método. A análise é baseada na média das menores distâncias encontradas por método.
O método com o melhor desempenho sobre o método Tradicional (40.878,47 km) é o Central com operação forçada (40.248,44 km) com uma melhora de 1,54%. Em seguida, o método Distance com operação forçada (40.270,53 km) com uma melhora de 1,48%, e o método Proximity (40.596,29 km) com 0,69%. Os outros métodos, Proximity com operação forçada (42.844,01 km), Distance (43.479,15 km) e Central (41.052,70 km) apresentaram resultados inferiores aos do método tradicional.
Ao método Tradicional também se aplicou a operação forçada (40.644,92 km), com uma melhora de 0,57% sobre o método Tradicional puro. Comparando os métodos propostos com o método Tradicional com operação forçada, os desempenhos alcançados sofrem uma redução. O método Central com operação forçada alcança uma melhora de 0,97%, o método Distance com operação forçada 0,92% e o Proximity 0,11%.
(CONCLUSÕES) 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 eficiência 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.
Artigo científico apresentado na 54ª Reunião da Sociedade Brasileira para o Progresso da Ciência
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 