Programación de algoritmos genéticos - Genetic algorithm scheduling

El algoritmo genético es un método de investigación operativa que puede utilizarse para resolver problemas de programación en la planificación de la producción .

Importancia de la programación de la producción

Para ser competitivas, las empresas deben minimizar las ineficiencias y maximizar la productividad. En la fabricación, la productividad está intrínsecamente vinculada a qué tan bien la empresa puede optimizar los recursos disponibles, reducir el desperdicio y aumentar la eficiencia. Encontrar la mejor manera de maximizar la eficiencia en un proceso de fabricación puede resultar extremadamente complejo. Incluso en proyectos simples, hay múltiples entradas, múltiples pasos, muchas restricciones y recursos limitados. En general, un problema de programación con recursos limitados consiste en:

  • Un conjunto de trabajos que deben ejecutarse
  • Un conjunto finito de recursos que se pueden utilizar para completar cada trabajo.
  • Un conjunto de restricciones que deben cumplirse
    • Restricciones temporales: la ventana de tiempo para completar la tarea
    • Restricciones de procedimiento: el orden en que se debe completar cada tarea
    • Restricciones de recursos: ¿el recurso está disponible?
  • Un conjunto de objetivos para evaluar el desempeño de la programación.

Una configuración típica de piso de fábrica es un buen ejemplo de esto, donde es necesario programar qué trabajos deben completarse en qué máquinas, por qué empleados, en qué orden y en qué momento.

Uso de algoritmos en la programación

En problemas muy complejos como la programación no existe una forma conocida de llegar a una respuesta final, por lo que recurrimos a buscarla tratando de encontrar una "buena" respuesta. Los problemas de programación suelen utilizar algoritmos heurísticos para buscar la solución óptima. Los métodos de búsqueda heurísticos sufren a medida que las entradas se vuelven más complejas y variadas. Este tipo de problema se conoce en informática como problema NP-Hard . Esto significa que no se conocen algoritmos para encontrar una solución óptima en tiempo polinomial.

Fig. 1. Prioridad en la programación

Los algoritmos genéticos son adecuados para resolver problemas de programación de la producción porque, a diferencia de los métodos heurísticos, los algoritmos genéticos operan en una población de soluciones en lugar de una única solución. En la programación de la producción, esta población de soluciones consta de muchas respuestas que pueden tener diferentes objetivos, a veces contradictorios. Por ejemplo, en una solución podemos optimizar un proceso de producción para que se complete en una cantidad mínima de tiempo. En otra solución, podemos optimizar para una cantidad mínima de defectos. Al aumentar la velocidad a la que producimos, podemos encontrarnos con un aumento de defectos en nuestro producto final.

A medida que aumentamos el número de objetivos que estamos tratando de lograr, también aumentamos el número de restricciones sobre el problema y aumentamos de manera similar la complejidad. Los algoritmos genéticos son ideales para este tipo de problemas en los que el espacio de búsqueda es grande y la cantidad de soluciones factibles es pequeña.

Aplicación de un algoritmo genético

Fig.2 A. Ejemplo de genoma de programación

Para aplicar un algoritmo genético a un problema de programación, primero debemos representarlo como un genoma. Una forma de representar un genoma de programación es definir una secuencia de tareas y las horas de inicio de esas tareas en relación entre sí. Cada tarea y su hora de inicio correspondiente representa un gen.

Una secuencia específica de tareas y tiempos de inicio (genes) representa un genoma en nuestra población. Para asegurarnos de que nuestro genoma sea una solución viable , debemos tener cuidado de que obedezca nuestras limitaciones de precedencia. Generamos una población inicial usando tiempos de inicio aleatorios dentro de las restricciones de precedencia. Con algoritmos genéticos, tomamos esta población inicial y la cruzamos, combinando genomas con una pequeña cantidad de aleatoriedad (mutación). La descendencia de esta combinación se selecciona en función de una función de aptitud que incluye una o muchas de nuestras limitaciones, como minimizar el tiempo y minimizar los defectos. Dejamos que este proceso continúe durante un tiempo preasignado o hasta que encontremos una solución que se ajuste a nuestros criterios mínimos. En general, cada generación sucesiva tendrá una mayor aptitud promedio, es decir, tomará menos tiempo con mayor calidad que las generaciones anteriores. Al programar problemas, al igual que con otras soluciones de algoritmos genéticos, debemos asegurarnos de no seleccionar descendientes que no sean factibles, como descendientes que violen nuestra restricción de precedencia. Por supuesto, es posible que tengamos que agregar más valores de aptitud, como minimizar costos; sin embargo, cada restricción agregada aumenta en gran medida el espacio de búsqueda y reduce el número de soluciones que son buenas coincidencias.

Ver también

Bibliografía

  • Wall, M., Un algoritmo genético para la programación con restricciones de recursos (PDF)
  • Lim, C .; Sim, E., Planificación de la producción en entornos de fabricación / reacondicionamiento mediante algoritmo genético


enlaces externos