Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2694| Estudio de operadores genéticos para un problema de calendarización multi-objetivo Genetic Operators Analysis for a Multi-Objective Scheduling Problem | |
| Rodrigo Aceves Pérez | |
| Carlos Alberto Brizuela Rodriguez | |
| Acceso Abierto | |
| Atribución | |
| Operadores de cruzamiento,Flujo de Tareas,Programación,Algoritmos genéticos,Calendarización,Frente Pareto,Multi-objetivo,Operadores de mutación | |
| En este trabajo se presenta un análisis experimental de las combinaciones de cuatro operadores de cruzamiento y tres de mutación, a fin de encontrar aquella combinación que genere las mejores soluciones. Sin embargo, no es f´acil decidir entre dos o más conjuntos de soluciones nodominadas cuál es el mejor. El enfoque aquí propuesto se basa en utilizar las relaciones de dominancia entre los conjuntos para lograr tal decisión. Se propone un criterio de comparación de conjuntos de soluciones no-dominadas. Esta propuesta se hizo debido a que la mayoría de los criterios actuales están basados en la hipótesis de que las funciones objetivo son continuas, y el problema de flujo de tareas multi-objetivo tiene funciones objetivo discretas. Se analizan varios de los criterios actuales y se contrastan con el criterio aquí propuesto. Los operadores se analizaron sobre tres algoritmos gen éticos distintos, para comprobar que la supremacía de la combinación ganadora sea independiente del algoritmo. Además, se estudiaron dos conjuntos de casos de tamaño distinto para evaluar la forma en que el tamano˜ del problema afecta el comportamiento de los operadores gen éticos. En base a los experimentos se concluye que existe una combinación de operadores de cruzamiento y de mutación que genera el mayor promedio relativo de soluciones nodominadas. Tal combinación es la de cruzamiento Obx con mutación Insert. Además, se encontró que la mutación Switch es la peor de las mutaciones y que los operadores de cruzamiento Osx y Twopoint se comportan de manera similar. Para respaldar las conclusiones obtenidas en el presente trabajo, se realizó un análisis estadístico no-paramétrico utilizando la prueba de Kruskal-Wallis y la prueba de Wilcoxon de suma de rangos. This thesis deals with the experimental analysis of genetic operators for the multiobjective permutation flowshop problem. All combinations of four crossover and three mutation operators are analyzed. The aim of the work is to find which combination produces the best set of solutions (the best non-dominated front). However, deciding the best among two or more non-dominated fronts is not an easy task. Our approach is based on studying the dominance relationships among the sets to reach such decision. In fact, we propose a criterion for comparing non-dominated sets that overcome the limitations of current criteria which were thought of for continuous objective functions, while the multi-objective flowshop problem has discrete objective functions. Several of these criteria are analyzed and contrasted with our proposed criterion. The genetic operators were analyzed over three different genetic algorithms, to ensure that the supremacy of the winning combination is algorithm-independent. Two set of instances of different sizes were studied to assert the way problem size affects the behavior of the genetic operators. We conclude that there is a combination of crossover and mutation operators that outperforms the others. This combination is composed of the Obx crossover and the Insert mutation. Besides, we found that Switch mutation is the worst of all mutations and that Osx and Twopoint crossover operators have similar behavior. In order to support the conclusions attained, a statistical non-parametric analysis was performed applying the Kruskal-Wallis and the Wilcoxon’s sum of ranks tests. | |
| CICESE | |
| 2003 | |
| Tesis de maestría | |
| Español | |
| Aceves Pérez, R.2003.Estudio de operadores genéticos para un problema de calendarización multi-objetivo.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.109 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 159731.pdf | 2.57 MB | Adobe PDF | Visualizar/Abrir |