Metodologia estatística na solução do problema do caixeiro viajante e na avaliação de algoritmos : um estudo aplicado à transgenética computacional

AUTOR(ES)

Iloneide Carlos de Oliveira Ramos

DATA DE PUBLICAÇÃO

2005

RESUMO

Os problemas de otimização combinatória têm envolvido um grande número de pesquisadores na busca por soluções aproximativas para aqueles, desde a aceitação de que eles são considerados insolúveis em tempo polinomial. Inicialmente, essas soluções eram focalizadas por meio de heurísticas. Atualmente, as metaheurísticas são mais utilizadas para essa tarefa, especialmente aquelas baseadas em algoritmos evolucionários. As duas principais contribuições deste trabalho são: a criação de uma heurística, denominada Operon, para a construção de cadeias de informações necessárias à implementação de algoritmos transgenéticos (evolucionários) utilizando, principalmente, a metodologia estatística - Análise de Agrupamentos e Análise de Componentes Principais -; e a utilização de análises estatísticas adequadas à avaliação da performance de algoritmos destinados à solução desses problemas. O Operon visa construir, de forma dinâmica e de boa qualidade, cadeias de informações a fim de promover uma busca -inteligente- no espaço de soluções. O Problema do Caixeiro Viajante (PCV) é focalizado para as aplicações que são realizadas com base num algoritmo transgenético, denominado ProtoG. Propõe-se, também, uma estratégia de renovação de parte da população de cromossomos indicada pela adoção de um limite mínimo no coeficiente de variação da função de adequação dos indivíduos, calculado com base na população. São propostas três análises estatísticas para avaliar a performance de algoritmos. A primeira é realizada através da Análise de Regressão Logística, com base na probabilidade de obtenção da solução ótima de uma instância do PCV pelo algoritmo em teste. A segunda é realizada através da Análise de Sobrevivência, com base numa probabilidade envolvendo o tempo de execução observado até que a solução ótima seja obtida. A terceira é realizada por meio da Análise de Variância não paramétrica, considerando o Erro Percentual da Solução (EPS) obtido pela percentagem em que a solução encontrada excede a melhor solução disponível na literatura. Utiliza-se essa metodologia para a avaliação da performance de quatro algoritmos, a saber: o ProtoG proposto, dois algoritmos meméticos e um algoritmo Simulated Annealing. Foram realizados seis experimentos, aplicados a sessenta e uma instâncias do PCV euclidiano, com tamanhos de até 1.655 cidades. Os dois primeiros experimentos tratam do ajuste de quatro parâmetros utilizados no algoritmo ProtoG, visando melhorar a performance do mesmo. Os quatro últimos são utilizados para avaliar a performance do ProtoG em comparação aos três algoritmos adotados. Para essas sessenta e uma instâncias, conclui-se, sob testes estatísticos, que há evidências de que o ProtoG é superior a esses três algoritmos em cinqüenta instâncias. Além disso, para as trinta e seis instâncias consideradas nos três últimos experimentos, nos quais a avaliação da performance dos algoritmos foi realizada com base no EPS, observou-se que o ProtoG obteve EPSs médios menores que 1% em quase metade das instâncias, tendo atingido a maior média para uma instância composta por 1.173 cidades, com EPS médio igual a 3,52%. Logo, o ProtoG pode ser considerado um algoritmo competitivo para solucionar o PCV, pois não é raro serem reportados, na literatura, EPSs médios maiores que 10% para instâncias desse porte.

ASSUNTO(S)

análise de componentes principais cluster analysis transgenética computacional engenharia eletrica análise de agrupamentos análise de sobrevivência statistical methodology computacional transgenetic traveling salesman problem metodologia estatística principal component analysis survival analysis problema do caixeiro viajante

Documentos Relacionados

• Algoritmo treansgenético na solução do problema do Caixeiro Viajante
• O problema do caixeiro viajante alugador : um estudo algorítmico
• Algoritmos Evolucionários Aplicados ao Problema do Caixeiro Viajante Multiobjetivo.
• Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos
• Plasticidade sináptica e o problema do caixeiro viajante