Un algoritmo genético multimodal y su aplicación al problema de ruteo de vuelos con múltiples paradas PDF Download

Author: Eduardo Uresti Charre
Publisher:
ISBN:
Category :
Languages : es
Pages : 184

Get Book Here

Book Description
En los algoritmos genéticos la población tiene un doble papel. Por un lado representa lo que puede ser el resultado entregado por el algoritmo, y por otro, la población es la materia prima para la exploración de espacio de búsqueda. Siendo la población lo que el algoritmo entrega en su finalización ésta debe ser cuidadosamente reemplazada por nuevas soluciones que mejor en lo ya encontrado y no destruyan soluciones adecuadas ya descubiertas. Si el problema consiste en encontrar la mejor solución posible en el espacio de búsqueda, es sencillo cuidar el mejor elemento a lo largo de las generaciones. Cuando la solución al problema consiste en encontrar un conjunto múltiple y diverso de puntos, la población debe modificarse con un cuidado adecuado. Este cuidado puede comprometer sustancialmente la capacidad de exploración del espacio de búsqueda. Con el propósito de mantener un nivel adecuado de diversidad en la población el aumentar el tamaño de la población aumenta sustancialmente los recursos requeridos para hacer la evolución de la población y, en el contexto de un problema donde el número de evaluaciones disponible sea limitado o costoso, también puede comprometer el nivel de exploración. El presente trabajo propone y analiza un algoritmo genético que se aplica a problemas de optimización multimodal donde el rol de la población está separado. Este proceso de división es llevado a cabo mediante el manejo de dos poblaciones. Una primera población que hace el papel de una población memoria que representa el conjunto respuesta al problema de búsqueda. Esta población memoria es concebida como un salón de la fama donde se almacenan los mejores individuos encontrados en el proceso de búsqueda. El concepto de mejores el resultado de una combinación entre la aptitud del individuo, una medida descriptiva de la sobrepoblación en el nicho que ocupa, y de un indicador de cómo se compara su evaluación respecto a la de sus compañeros en el nicho. La segunda población representa el medio de exploración en el espacio de soluciones. A la par con estas dos poblaciones, un mecanismo de administración es desarrollado. Este mecanismo se encargará de reemplazar elementos en la población memoria por aún mejores elementos encontrados en el proceso de búsqueda. La otra función importante a su cargo consistirá en formar las poblaciones para cada una de las nuevas exploraciones. El algoritmo desarrollado es comparado experimentalmente con dos de los algoritmos genéticos que mejor se han desempeñado en la solución a problemas de optimización multimodal resultando con ventajas sobro olios. Este algoritmo es aplicado al problema de ruteo de vuelos con múltiples paradas el cual es un problema de optimización discreta de alta complejidad y relevancia práctica. En este problema la evaluación de los individuos tiene un costo computacional elevado, de manera que el overead computacional causado por la administración de la población memoria es reducido cuando se le compara contra los costos de evaluación.