Un Algoritmo Genético Multimodal y su Aplicación al Problema de Ruteo de Vuelos con MÚltiples Paradas

Hdl Handle:
http://hdl.handle.net/11285/572490
Title:
Un Algoritmo Genético Multimodal y su Aplicación al Problema de Ruteo de Vuelos con MÚltiples Paradas
Authors:
Uresti Charre, Eduardo
Issue Date:
01/05/2003
Abstract:
En los algoritmos gene?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 bu?squeda. Siendo la población lo que el algoritmo entrega en su finalización e?sta debe ser cuidadosamente reemplazada por nuevas soluciones que mejoren 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 bu?squeda, es sencillo cuidar el mejor elemento a lo largo de las generaciones. Cuando la solución al problema consiste en encontrar un conjunto mu?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 bu?squeda. Con el propósito de mantener un nivel adecuado de diversidad en la población el aumentar el taman?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 nu?mero de evaluaciones disponible sea limitado o costoso, tambie?n puede compromenter el nivel do exploración. El presente trabajo propone y analiza un algoritmo gene?tico que se aplica a pro- blemas de optimización multimodal donde el rol de la población esta? separado. Este proceso de división es llevado a cabo mediante el manejo de dos poblaciones. Una prime- ra población que hace el papel de una población memoria que representa el conjunto respuesta al problema de bu?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 bu?squeda. El concepto de mejor es 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 compan?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 encargara? de reemplazar elementos en la población memoria por au?n mejores elementos encontrados en el proceso de bu?squeda. La otra función importante a su cargo consistira? en formar las poblaciones para cada una de las nuevas exploraciones. El algoritmo desarrollado es comparado experimentalmente con dos de los algorit- mos gene?ticos que mejor se han desempen?ado en la solución a problemas de optimi- zación multimodal resultando con ventajas sobro olios. Este algoritmo es aplicado al problema de ruteo de vuelos con mu?ltiples paradas el cual es un problema de optimiza- ción discreta de alta complejidad y relevancia pra?ctica. En este problema la evaluación de los individuos tiene un costo computacional elevado, de manera que el overhead com- putacional causado por la administración de la población memoria es reducido cuando se le compara contra los costos de evaluación.
Keywords:
Algoritmo; Genética; Vuelos
Degree Program:
Programa de Graduados en Electrónica, Computación, Información y computación
Advisors:
Dr. Manuel Valenzuela Rendón
Committee Member / Sinodal:
Dr. Hugo Terashima Marín; Dr. José Luis González Velarde; Dr. Carlos Artemio Coello Coello
Degree Level:
Doctor en Informática
School:
Escuela de Graduados en Electrónica, Computación, Información y Comunicación
Campus Program:
Campus Monterrey
Discipline:
Ingeniería y Ciencias Aplicadas / Engineering & Applied Sciences
Appears in Collections:
Ciencias Exactas

Full metadata record

DC FieldValue Language
dc.contributor.advisorDr. Manuel Valenzuela Rendónes
dc.contributor.authorUresti Charre, Eduardoes
dc.date.accessioned2015-08-17T11:33:34Zen
dc.date.available2015-08-17T11:33:34Zen
dc.date.issued01/05/2003-
dc.identifier.urihttp://hdl.handle.net/11285/572490en
dc.description.abstractEn los algoritmos gene?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 bu?squeda. Siendo la población lo que el algoritmo entrega en su finalización e?sta debe ser cuidadosamente reemplazada por nuevas soluciones que mejoren 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 bu?squeda, es sencillo cuidar el mejor elemento a lo largo de las generaciones. Cuando la solución al problema consiste en encontrar un conjunto mu?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 bu?squeda. Con el propósito de mantener un nivel adecuado de diversidad en la población el aumentar el taman?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 nu?mero de evaluaciones disponible sea limitado o costoso, tambie?n puede compromenter el nivel do exploración. El presente trabajo propone y analiza un algoritmo gene?tico que se aplica a pro- blemas de optimización multimodal donde el rol de la población esta? separado. Este proceso de división es llevado a cabo mediante el manejo de dos poblaciones. Una prime- ra población que hace el papel de una población memoria que representa el conjunto respuesta al problema de bu?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 bu?squeda. El concepto de mejor es 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 compan?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 encargara? de reemplazar elementos en la población memoria por au?n mejores elementos encontrados en el proceso de bu?squeda. La otra función importante a su cargo consistira? en formar las poblaciones para cada una de las nuevas exploraciones. El algoritmo desarrollado es comparado experimentalmente con dos de los algorit- mos gene?ticos que mejor se han desempen?ado en la solución a problemas de optimi- zación multimodal resultando con ventajas sobro olios. Este algoritmo es aplicado al problema de ruteo de vuelos con mu?ltiples paradas el cual es un problema de optimiza- ción discreta de alta complejidad y relevancia pra?ctica. En este problema la evaluación de los individuos tiene un costo computacional elevado, de manera que el overhead com- putacional causado por la administración de la población memoria es reducido cuando se le compara contra los costos de evaluación.es
dc.language.isoesen
dc.rightsOpen Accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleUn Algoritmo Genético Multimodal y su Aplicación al Problema de Ruteo de Vuelos con MÚltiples Paradases
dc.typeTesis de Doctoradoes
thesis.degree.grantorInstituto Tecnológico y de Estudios Superiores de Monterreyes
thesis.degree.levelDoctor en Informáticaes
dc.contributor.committeememberDr. Hugo Terashima Marínes
dc.contributor.committeememberDr. José Luis González Velardees
dc.contributor.committeememberDr. Carlos Artemio Coello Coelloes
thesis.degree.disciplineEscuela de Graduados en Electrónica, Computación, Información y Comunicaciónes
thesis.degree.namePrograma de Graduados en Electrónica, Computación, Información y computaciónes
dc.subject.keywordAlgoritmoes
dc.subject.keywordGenéticaes
dc.subject.keywordVueloses
thesis.degree.programCampus Monterreyes
dc.subject.disciplineIngeniería y Ciencias Aplicadas / Engineering & Applied Scienceses
All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.