Introducción
LOGISPLAN está desarrollado utilizando técnicas de optimización basadas en algoritmos genéticos.
Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir para, de esta forma, dar solución a un problema específico.
Los algoritmos genéticos surgieron en los años 70 de la mano de John Henry Holland y David Goldberg. Desde entonces su aplicación en la resolución de problemas de búsqueda y optimización ha sido fuertemente contrastada.
Los algoritmos genéticos se llaman así porque se inspiran en la evolución biológica y su base genético-molecular.
Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas); así como también a una Selección, de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.
Acometen la solución de problemas de alta complejidad con una estructura intrínseca también de enorme complejidad potencial. Por así decirlo, sondean la complejidad con la complejidad. Por utilizar un símil, equivaldría a echar una malla de sondas sobre un paisaje de valles y cimas (mínimos y máximos de la función de evaluación), en lugar de proceder a mediciones secuenciales con determinados criterios, que es lo que suelen hacer los algoritmos específicos clásicos.
La aplicación de algoritmos genéticos en optimización, permiten resolver problemas del tipo NP-Completo. Este tipo de problemas necesitaría un tiempo prácticamente infinito para ser resueltos y, mediante las técnicas utilizadas por Evolution Algorithms, pueden resolverse en pocos minutos.
Ventajas
Los algoritmos genéticos tienen varias características que los hacen especialmente adecuados para la resolución de problemas de gran complejidad.
Resolución de problemas complejos
- Eliminan uno de los mayores obstáculos que entorpecen el diseño clásico de programas. Esto es la necesidad de la especificación por adelantado de todas las características y peculiaridades de un problema y de las acciones requeridas para atenderlas.
- Mediante los algoritmos genéticos es posible solucionar incluso problemas que se revelan de imposible definición en cuanto atañe a la prolija multiplicidad de sus variantes potenciales.
Paralelización
Todo el proceso evolutivo empleado por la naturaleza es un proceso que funciona con un altísimo grado de paralelismo. Todos los individuos contemporáneos de una población están sometidos a la vez a la función de evaluación del entorno (medio ambiente, depredadores, etc.). Estos sobreviven, se reproducen y mueren sin interferencias en cuanto a la simultaneidad de tales acontecimientos. Al utilizar un mecanismo similar, los algoritmos genéticos, aunque en general se instrumentan en los ordenadores de forma secuencial, obedecen por naturaleza intrínseca a un diseño muy apto para operar en proceso paralelo. En la actualidad podemos aprovecharnos de los sistemas con gran cantidad de procesadores en paralelo y, estos algoritmos resultan muy adecuados para su implementación en dichos sistemas, con el consiguiente beneficio en el rendimiento.
Adaptabilidad a cambios durante el proceso de optimización
Muchos algoritmos están diseñados para el caso en que los coeficientes que intervienen en el problema permanezcan fijos. Así, por ejemplo, en el caso del problema de las asignaciones, que trata de hacer corresponder por ejemplo personas a puestos de trabajo adecuando sus perfiles respectivos, el algoritmo húngaro (el método clásico empleado para su solución) supone la constancia de los coeficientes. Esto significa que si los valores empleados para el cálculo y las condiciones de entorno cambian durante el proceso, el método empleado debe suspenderse y reiniciarse nuevamente.
Los algoritmos genéticos, sin embargo, reorientan por su propio diseño intrínseco automáticamente el nuevo objetivo, y continúan el proceso de convergencia hacia el óptimo dictado por las nuevas condiciones. Podemos decir por lo tanto que los algoritmos genéticos son capaces de converger hacia las soluciones óptimas aun cuando los coeficientes varíen como consecuencia de la disposición de las asignaciones. En el problema de las asignaciones, el método húngaro no permite tener en cuenta el caso en que el coeficiente de asignación de una persona cambia en función del puesto que ocupa otra, como ocurre cuando una persona se asigna a un puesto en la misma sección en que trabaja su cónyuge, por ejemplo; el algoritmo genético se adapta igualmente bien a estas circunstancias del problema.
Funcionamiento
Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población.
Un esquema de funcionamiento básico se resume en los siguientes pasos:
Inicialización
Se genera aleatoriamente la población inicial. Esta se construye por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones. Es importante para tener una representación de la mayor parte de la población posible. Se debe evitar la convergencia prematura.
Evaluación
A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber qué tan «buena» es la solución que se está codificando.
Condición de término
El algoritmo genético se deberá detener cuando se alcance la solución óptima. Esta se desconoce generalmente, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el algoritmo genético un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:
- Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que se cruzarán en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
- Sobrecruzamiento: El cruzamiento es el principal operador genético. Representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
- Mutación: modifica al azar parte del cromosoma de los individuos. Se utilizan para permitir alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
- Reemplazo: una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.