Diseño de un modelo basado en algoritmos genéticos (AG´s) utilizando migración para mejorar el proceso de diversificación en la resolución del problema del viajante de comercio (TSP)

Abstract

RESUMEN El presente trabajo es el resultado de una ardua investigación que abarca desde el sustento teórico que envuelve a los Algoritmos Genéticos (AG), las bases de las que surgen, su evolución hasta nuestros días, sus fortalezas y debilidades, el tipo de problemas que mejor resuelven, hasta la generación de nuevos recursos que pueden fortalecerlos y mejorarlos para resolver el problema del viajante de comercio y generar las rutas óptimas para la recolección de basura en San Francisco de los Romo. Los AG están basados en la Teoría de la Evolución de las Especies propuesta por Charles Darwin (Biólogo Británico) donde se plantea la forma en que distintas especies han evolucionado por medio de un lento proceso de selección natural, que es como el medio ambiente influye en su supervivencia y/o reproducción [Darwin1859]. También influyeron los trabajos que realizó con aproximadamente 28,000 plantas de guisantes que aisló y polinizó de forma artificial Gregor Mendel (Monje Austriaco), para luego basándose en los resultados obtenidos de sus experimentos, describir las leyes que rigen la herencia y que actualmente apoyan los estudios que se realizan en genética [Riol2008]. Se generó un modelo que permite mejorar la diversificación de las poblaciones dentro de los AG‟s y que se refleja en la calidad de los resultados obtenidos; ésto se logra introduciendo el operador de migración (que ha sido utilizado en trabajos como los modelos de islas) y que junto con una adecuada elección de los operadores de selección, cruza y mutación permiten alcanzar dicho objetivo. Para probar el modelo se resolvió el problema del viajante de comercio (TSP por sus siglas en inglés), ya que por sus características, durante muchos años ha sido uno de los problemas que se toman como base para probar distintas heurísticas. DOCTORADO EN CIENCIAS DE LA COMPUTACIÓN

El TSP consiste en encontrar la ruta más corta o menos costosa para recorrer cierto número de ciudades, pasando por todas sin que estas se repitan [Bryant2000]. Por esta razón se hace un estudio concienzudo del mismo.