Técnicas Evolutivas Para El Problema Del Viajante

Abstract

El Problema del Viajante consiste en encontrar la ruta de mínimo “costo” para un
viajante que debe visitar cada ciudad en una lista exactamente una vez y regresar al punto de
partida. Nuestra experimentación previa con seis técnicas evolutivas basadas en
representación ordinal y de permutaciones, ambas combinadas con los siguientes operadores
de cruzamiento: Single Crossover Per Couple (SCPC), Multiple Crossover Per Couple
(MCPC) y Multiple Crossover with Multiple Parents (MCMP), evidenció un bajo desempeño
de la tercera forma de cruzamiento. En este trabajo se analiza la causa de tal
comportamiento en base a una modificación adecuada en el criterio de convergencia. Se
diseñó una nueva condición de terminación y se la aplicó con MCMP para varios casos de
estudio. De los resultados se concluye que la fuerte presión selectiva del MCMP provoca la
convergencia prematura del proceso evolutivo.