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 .
Para ser competitivas, las corporaciones deben minimizar las ineficiencias y maximizar la productividad. En la industria manufacturera, la productividad está inherentemente vinculada a la capacidad de la empresa para optimizar los recursos disponibles, reducir los desechos y aumentar la eficiencia. Encontrar la mejor manera de maximizar la eficiencia en un proceso de fabricación puede ser extremadamente complejo. Incluso en proyectos simples, hay múltiples insumos, múltiples pasos, muchas restricciones y recursos limitados. En general, un problema de programación con recursos limitados consiste en:
Un buen ejemplo de esto es una típica configuración de una fábrica, donde es necesario programar qué trabajos deben completarse en qué máquinas, por qué empleados, en qué orden y a qué hora.
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 para intentar 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ística sufren a medida que las entradas se vuelven más complejas y variadas. Este tipo de problema se conoce en informática como un problema NP-Hard . Esto significa que no existen algoritmos conocidos para encontrar una solución óptima en tiempo polinómico.
Los algoritmos genéticos son muy 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 sobre una población de soluciones en lugar de sobre una única solución. En la programación de la producción, esta población de soluciones consta de muchas respuestas que pueden tener objetivos diferentes y, a veces, contradictorios. Por ejemplo, en una solución podemos estar optimizando un proceso de producción para que se complete en un tiempo mínimo. En otra solución podemos estar optimizando 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 intentamos alcanzar, también aumentamos el número de restricciones del problema y, de manera similar, aumentamos la complejidad. Los algoritmos genéticos son ideales para este tipo de problemas en los que el espacio de búsqueda es grande y el número de soluciones factibles es pequeño.
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 los tiempos de inicio de esas tareas en relación con las demás. Cada tarea y su tiempo de inicio correspondiente representan 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 factible, debemos asegurarnos de que obedezca nuestras restricciones de precedencia. Generamos una población inicial utilizando tiempos de inicio aleatorios dentro de las restricciones de precedencia. Con algoritmos genéticos, luego tomamos esta población inicial y la cruzamos, combinando genomas junto 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 restricciones, 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 aptitud promedio mayor, es decir, tomará menos tiempo con mayor calidad que las generaciones anteriores. En los problemas de programación, como con otras soluciones de algoritmos genéticos, debemos asegurarnos de no seleccionar descendencia que no sea factible, como la descendencia que viola nuestra restricción de precedencia. Por supuesto, es posible que tengamos que agregar más valores de aptitud, como minimizar los costos; Sin embargo, cada restricción agregada aumenta enormemente el espacio de búsqueda y reduce el número de soluciones que coinciden bien.