O Estudo Comparativo da Performance de Técnicas de Cruzamento Utilizadas em um Algoritmo Genético Aplicado ao Problema do Caixeiro Viajante

...

Os Algoritmos Genéticos são baseados na seleção e evolução natural dos organismos biológicos, com o objetivo de resolver problemas complexos espelhando-se no processo de evolução dos seres vivos (HOLLAND, 1975). Foram propostos por John Holland e seus colaboradores da Universidade de Michigan na década de 70.

O algoritmo genético canônico, idealizado por Holland, opera sobre uma população de cromossomos iniciais codificados em cadeias de strings 0’s e 1’s. Cada cromossomo representa uma potencial solução do problema. A cada geração, os cromossomos são avaliados de acordo com uma função de adaptação, também chamada de fitness. Os indivíduos mais aptos (com melhores valores de adaptação) possuem maior probabilidade de reproduzir-se (seleção) mediante cruzamentos com outros indivíduos da população, produzindo descendentes com características de ambas as partes. Também é possível modificar características da população através de mutações. A seleção, o cruzamento e a mutação são operadores genéticos que transformam a população através de sucessivas gerações. Após a aplicação desses operadores, ao longo das gerações, espera-se que os indivíduos da população convirjam para uma boa solução, não necessariamente a ótima (GOLDBERG, 1989).

No problema do Caixeiro Viajante cada solução é um cromossomo juntando para se tornar uma rota. A adaptação dependerá do tamanho da rota que depende da ordem em que as cidades aparecem. Para gerar os cromossomos, o algoritmo genético deve usar permutações.

Uma permutação de m elementos é uma sequência de m elementos em que nenhum elemento é repetido. Um grande número de problemas de otimização combinatória pode ter suas soluções representados por permutações, entre os quais o PCV (DE LACERDA, 1999).

Existem vários operadores de crossover para permutação, entre elas estão a OBX (Order-Based Crossover) e a PBX (Position-Based Crossover) (Goldberg, 1989).

O crossover OBX começa selecionando um conjunto de posições aleatoriamente. Depois é imposto aos elementos de pai(1), nas posições selecionadas, o mesmo ordenamento que estes mesmos elementos apresentam em pai(2). Em seguida, o novo ordenamento nas posições selecionadas de pai(1) é copiado para filho(1). Os elementos nas posições não selecionadas de pai(1) são copiados sem alterações para filho(1). O cromossomo filho(2) é obtido através de um processo similar (DE LACERDA, 1999).

O crossover PBX também começa selecionando um conjunto de posições aleatórias. Porém, ao invés de impor a ordem, impõe a posição. É imposto, nas posições selecionadas, que filho(1) tenha os mesmos elementos de pai(2). Os demais elementos de filho(1) provêm de pai(1) mantendo o mesmo ordenamento presente em pai(1) (já que manter um elemento em mais de uma posição não é possível). Filha(2) é obtido através de processo similar (DE LACERDA, 1999).

Um estudo comparativo é uma das formas para se conduzir um experimento de forma simples. Muito usado como método de pesquisa uma experimentação é onde se assume condições especiais – sob grande controle – das variáveis de interesse (RIBEIRO, 2000). Essas variáveis podem ser independentes, por exemplo tamanho, gerações, posições entre outros.

Foram usados para a análise um conjunto de dados do Qatar que tem 194 cidades e está disponível no site[2] da universidade de Waterloo para gerar soluções para o Problema do Caixeiro Viajante por meio de permutações usando o OBX e a PBX. Para realizar a análise comparativa, resultante da coleta de dados fez-se necessário o desenvolvimento de um protótipo atendendo características em comum. Os detalhes das condições iniciais do experimento foram: População de 100 indivíduos, método de seleção por torneio com 3 indivíduos, taxa de cruzamento de 0.9, taxa de mutação de 0.05 e 30 execuções com 1000 gerações.

A seguir, são apresentadas as tabelas contendo os resultados do experimento referente aos dados da comparação entre os algoritmos tomando como base o tempo de execução.

Tabela 1 Média (M), melhor resultado (ME), pior resultado (P), desvio padrão (DP), para as técnicas de crossovers.

Cruzamento

M

ME

P

DP

OBX

22965,43

19787

25844

1487,782

PBX

22965,73

20686

25775

1338,615

Conforme pode-se observar na Tabela 1, o OBX apresentou em média um melhor resultado que o PBX. Devido ao fato dos valores de média serem bem próximos, seria necessário um estudo mais aprofundado com testes estatísticos para definir se essa diferença nos resultados das técnicas é estatisticamente significativa (estudo este fora do escopo do presente trabalho).

---------------------------------------------------------------

- Conclusões

O presente trabalho teve como objetivo realizar um estudo comparativo inicial das técnicas de cruzamento OBX e PBX de um Algoritmo Genético aplicados ao Problema do Caixeiro Viajante.

Os resultados do experimento mostraram que a técnica OBX em média obteve um melhor resultado que a PBX, mas, devido a semelhança entre as