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

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

Douglas Carlos da Silva Oliveira1; Luciano Soares de Souza2

1Graduando em Sistemas de Informação – IFNMG. e-mail: [e-mail]

2Professor Doutor do Instituto Federal do Norte de Minas Gerais – Campus Pirapora. e-mail: [e-mail]

Resumo: O Problema do Caixeiro Viajante consiste em encontrar a rota mais curta através de cidades em uma determinada região, começando por qualquer cidade, sem visitá-las duas vezes, retornando à cidade de origem. Este é um dos problemas em matemática computacional mais investigados, antecedendo 1832. A solução para o problema cresce exponencialmente com o tamanho do mesmo, aumentando o esforço computacional. Sendo usado para encontrar a rota mais curta através de cidades em uma determinada região, ele pode ser empregado para solucionar diversos problemas, e usando Algoritmos Genéticos pode se encontrar melhores resultados com esforços menores. Este trabalho tem 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.

Palavras–chave: algoritmo genético, caixeiro viajante, obx, bpx, order-based crossover, position-based crossover

1. Introdução

O Problema do Caixeiro Viajante – PCV (do inglês Traveling Salesman Problem – TSP) é um dos problemas na área de matemática computacional mais estudados. Esse problema tem inspirado estudos de matemáticos, cientistas da computação, químicos, físicos, psicólogos e uma série de profissionais e pesquisadores (APPLEGATE et. al, 2007).

De acordo com Applegate et. al. (2007), o PCV tem aplicações nas áreas de logística, genética, fabricação, telecomunicação, neurociências, etc. A sua simplicidade juntamente com sua intransponibilidade, torna uma plataforma ideal para desenvolver ideias e técnicas para resolver problemas computacionais.

Na área de otimização, o PCV faz parte dos problemas NP-difícil (do inglês NP-Hard), possuindo uma complexidade exponencial. Assim, a solução para o problema cresce exponencialmente com o tamanho do mesmo, aumentando esforço computacional.

Esse trabalho tem o objetivo de comparar a performance dos resultados obtidos por dois operadores de cruzamento, propostos na literatura, em um Algoritmo Genético aplicado ao PCV.

1. Material e Métodos

O PCV consiste em encontrar a rota mais curta através de cidades em uma determinada região, começando por qualquer cidade, sem visitá-las duas vezes, retornando à cidade de origem, minimizando os custos da viagem. Na figura 1 pode-se ver uma solução para o problema de Caixeiro Viajante no qual se busca a melhor rota.

Seja n o número de cidades a serem visitadas, o número total de rotas possíveis que abrange todas as cidades pode ser dado como um conjunto de soluções viáveis do PCV e são dadas como:

(n-1)! / 2

[Eq. 01]

Em geral, o PCV é classificado como simétrico, assimétrico ou viagens múltiplas. O PCV simétrico encontra um percurso fechado de comprimento mínimo que visita cada cidade uma vez. Neste caso, as cidades são dadas por suas coordenadas e a distância euclidiana entre as coordenadas, assim temos o PCV simétrico.

O PCV pode ser definido em um grafo complexo G = (V, E) sem direção se for simétrico. O conjunto V = {1, ... , n} é o conjunto de vértices, E = {(i,j):i,j∈V,i∈V,i≠j} é um conjunto de arco.

[pic 2]

Figura 1  Solução de um problema de Caixeiro Viajante: a linha preta mostra o ciclo mais curto possível que conecta cada ponto vermelho. Fonte: Xypron (2010)^[1]

1. Resultados e Discussão

Os algoritmos heurísticos são uma alternativa computacional viável usada pelos pesquisadores para resolver o PCV. Nessa alternativa muitas vezes não se obtém uma solução necessariamente ótima. Os algoritmos genéticos são um método heurístico para encontrar boas soluções.

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).