Tesis de maestría
Solución al Problema de Programación de Tareas mediante Algoritmos Genéticos Cooperantes-Edición Única
Fecha
2002-05-01Autor
Flores Flores, José Maximiliano
Institución
Resumen
Este trabajo de tesis aborda el problema de programación de tareas minimizando el criterio de justo a tiempo, mediante la combinación de algoritmo genético cooperante con una heurística llamada dinámica de cuello de botella. La solución que se propone en este trabajo es el uso de un algoritmo genético medicado, llamado algoritmo genético cooperante, en donde la representación de las tareas del problema se lleva a cabo mediante particiones del problema completo en varias poblaciones independientes. Cada una de estas poblaciones pertenecen a un algoritmo genético completo. Mediante un mecanismo de intercambio de información, cada uno de los algoritmos genéticos independientes utilizan la información generada por los individuos de las demás poblaciones para encontrar una mejor solución que la que se encontraría con una sola población, con el mismo número de evaluaciones totales de la función objetivo. La aplicación del algoritmo genético cooperante que se propone incluye un método para construirlas particiones iniciales y un método de reinicialización para migrar tareas entre particiones, así como una forma de representar algunas tareas en dos poblaciones distintas. La proposición del uso de un algoritmo genético cooperante se basa en la hipótesis de que, en un conjunto de tareas a programar, existen tareas que están fuertemente relacionadas entre sí, al igual que existen tareas que no tienen relación alguna en el resultado final de la programación. Con este enfoque, se pretende explotar la idea de independencia entre tareas para optimizar la representación de la solución y mejorar considerablemente el tiempo de respuesta de un algoritmo genético a los problemas de programación de tareas en una máquina. Los resultados de esta tesis son comparados con investigaciones anteriores donde se utilizaron algoritmos genéticos simples para resolver este mismo problema y objetivo de producción. El uso del algoritmo genéticos cooperante obtuvo de manera consistente mejores resultados que los algoritmos contra los que se comparó