Desde antaño, la observación de la naturaleza ha sido una vía de innovación y creación de soluciones para el hombre. Da Vinci, por ejemplo, intentaba comprender el vuelo de las aves, Jorge de Mestral que analizó las semillas del cardo para la creación del velcro, hasta otras soluciones más recientes como la que presenta la empresa estadounidense PAX Scientific, la primera en crear hélices/impulsores basados en la piel de los moluscos que aprovechan los fluidos o gases con menor fricción, reduciendo hasta un 85% las necesidades energéticas y ruido.

Con la industria 4.0, la cantidad de datos disponibles hoy en día es enorme, lo que, computacionalmente hablando, ralentiza la ejecución de algoritmos de optimización, de predicción o clasificación. En este sentido, los tiempos y memoria de procesamiento se elevan a tal punto de incluso no encontrar soluciones en un tiempo razonable, perdiendo la real ventaja de un algoritmo, que es su rapidez para utilidad del hombre. Un ejemplo claro de esto es el procesamiento de datos en la inteligencia artificial y machine learning, ya sea para entrenar un modelo de regresión o para tareas más sofisticadas como la de detección de objetos mediante imágenes o video. Dependiendo de su resolución, cada imagen de estos modelos comprende un conjunto de datos de varios bits y en el caso de los videos es aún peor.

Charles Darwin

Algoritmos genéticos

Para resolver esta problemática, aparecieron los métodos metaheurísticos, que son algoritmos aproximados de optimización que exploran y explotan adecuadamente un espacio de soluciones, entregando un resultado aproximado y de calidad, pero en un tiempo más razonable en comparación a su respuesta exacta. Estas técnicas utilizan iteraciones con métodos de intensificación y diversificación como el esfuerzo empleado para la búsqueda de la solución, buscando un equilibrio entre ambas. En otras palabras, busca resultados aleatoriamente para diversificar o simplemente intensifica la búsqueda en puntos muy cercanos a la conclusión inicial encontrada. Una particularidad de estas técnicas es su fuente de inspiración natural, variando desde el comportamiento de las colonias de hormigas, movimientos de partículas, simulating annealing (proceso de forjado) o, incluso, al comportamiento de enjambres de abejas. Un método particular introducido por el Dr. John H. Holland son los llamados Algoritmos Genéticos (GA) como parte de las metaheurísticas inspiradas en métodos evolutivos o de población. Este método replica el proceso de selección natural propuesto por Darwin y que se resume en la famosa frase: “la supervivencia del más fuerte o el más adaptado.” El proceso se puede resumir de la siguiente forma:

Los individuos que se reproducen y dan lugar a una descendencia con sus genes, son los que están mejor adaptados, por lo que las generaciones se van adaptando cada vez mejor, pues son una combinación de los mejores genes de las generaciones anteriores.

Pero como en todo proceso, no existe la perfección, se deben simular mutaciones con cierta probabilidad de ocurrencia. Ahora, la pregunta clave es: ¿Cómo un algoritmo de programación lleva a la práctica estos conceptos bio-inspirados?

En estricto rigor, lo que hacen estos algoritmos es evolucionar poblaciones de soluciones hacia valores óptimos de un problema. Para esto, inicialmente se genera una población de individuos (o soluciones) generalmente de forma aleatoria, para luego evaluar cada uno de ellos con una función fitness o de adaptación, siendo este un indicador de cuán bien se está adaptando un individuo o cuán buena es la respuesta. Posteriormente, se seleccionan los mejores individuos para la reproducción, dando lugar a una nueva generación que sustituye a la anterior. Para simular mayor realidad, se integran mutaciones o pequeños cambios en ciertos individuos de la nueva población de forma aleatoria, iniciando así nuevamente el ciclo de la vida. Pero como esto no puede continuar infinitamente, se debe establecer un criterio de parado, que puede ser cuando se alcance un número predefinido de generaciones o cuando se alcance cierto valor de la función fitness. En la figura 1 se puede ver el ciclo descrito.

Figura 1: Flujo básico de un algoritmo genético (GA) (Wibisono et al, 2007)

Algo importante que señalar, es que para la representación de los individuos de la población se utiliza una codificación, que puede ser binaria como la que se ve en la figura 2, emulando un cromosoma único compuesto de genes.

Asimismo, y entrando en mayor detalle en cada una de las etapas del ciclo descrito, existen distintas estrategias a utilizar en la función de selección de individuos, tales como la selección por torneo, en donde se escogen aleatoriamente individuos de una porción de la población y se escoge al mejor de ellos; selección por ruleta, en donde se asigna una probabilidad de elección proporcional al valor fitness del cromosoma o, simplemente, estrategias aleatorias de la población general. La función de reproducción o cruce también es particular, ya que se generan operadores de cruce que corten el cromosoma en cierta posición, efectuando una mezcla de dos cromosomas en determinado punto y en cierto orden tal como se ve en la figura 2.

Figura 2: Composición de cromosoma (individuo).

Aplicación en construcción naval

Aplicaciones en esta área, son bastantes, de hecho si se busca en Youtube aplicaciones de GA, se encontrará desde cómo enseñarle a un computador a terminar, con mérito, una etapa del famoso videojuego Mario Bros, hasta simular rutas para vehículos eficientes como las que muestra Waze. Sin embargo, llevar a la práctica estos conceptos, suena algo extraño, ya que intentamos mezclar algoritmos informáticos con el ciclo biológico. Estos algoritmos bio-inspirados resuelven problemas de diversos tipos, como por ejemplo el planteado por Wibisono et al (2007), aplicado a la optimización de sistemas de división de bloques para construcción de embarcaciones, en donde el autor señala que la eficiencia de la construcción depende de los planes adecuados de división en bloque. Generalmente, este plan depende de un diseñador experto, quien a lo largo del tiempo, ha obtenido la experiencia y conocimiento en la construcción de buques, sin embargo, el número de estos talentosos ingenieros es cada vez menor, por lo que es necesario requerir apoyo por computadoras.

El problema planteado por los autores, consiste en la optimización de un proceso de construcción naval representado como un problema de assembling hierarchy o jerarquía de ensamblaje, donde todos los bloques deben ser conectados en un proceso de construcción. La jerarquía de ensamblaje permite establecer en una etapa temprana el correcto y adecuado ensamble de los bloques.

Figura 3: Ejemplo de cromosoma nivel-parte. (Wibisono et al, 2007)

El estudio realizado incluye una estructura objetivo como modelo gráfico, figura 3, la cual posee una numeración en cada arco o juntura. Este caso particular de cromosoma está compuesto por dos niveles de jerarquía: uno para niveles de conexión entre dos partes y otro para las partes o bloques. También los autores, ejecutan la evaluación del GA con una población de tamaño 100, reproducción de 50% de probabilidad entre dos individuos, mutación swap de un 30% de sus genes y estrategia de selección rejecting o descarte de soluciones infactibles sobre una función fitness que describe el total welding time como la que se muestra en la siguiente ecuación:

Donde:

f(x): Total welding time. (Función objetivo o fitness)

WT_i: Welding time en cada etapa. (minutos/m)

JL_ij: Largo de la junta en cada módulo. (m)

m: # De módulos en cada etapa de ensamble.

n: # De etapas de ensamble.

A esta función objetivo, Wibisono et al (2007) también señala que se le agregó restricciones y parámetros tales como el registro de niveles de etapas de ensamble, cada uno con tiempos de unión de soldadura, posición de juntas y tamaño de grúas, tamaño del bloque, como se puede ver en la figura 4.

Figura 4: Restricciones de producción (Wibisono et al, 2007)

El resultado se puede apreciar en la figura 5, donde se muestra que la función fitness se estabiliza en la generación 800 aproximadamente, con un valor total welding time de 60.000, aproximadamente. Como se puede apreciar, se obtiene un valor cercano al óptimo (57.127) en un tiempo de 127 horas, en comparación con el tiempo total que debería demorar un método exacto de optimización. Los atributos de la solución se pueden ver en la tabla de la figura 5.

Figura 5: Resultados (Wibisono et al, 2007)

Conclusiones

Los algoritmos metaheurísticos se caracterizan por tener una fuente de inspiración en los procesos de la naturaleza. Proveen soluciones aproximadas de manera mucho más rápida de lo que demoraría un método exacto. Los GA tienen una simpleza que permiten ser aplicados en todo ámbito, incluso en el área naval, constituyendo una herramienta eficiente para cualquier usuario.

Hoy en día, con la gran cantidad de información existente en la web, es necesario contar con herramientas que permitan procesar o analizar estos datos en un tiempo aceptable, que permitan hacer la vida del hombre más fácil y eficiente.

No obstante, si bien las aplicaciones más serias pueden parecer complicadas, vale la pena estudiarlas, y por qué no, jugar con ellas también es una alternativa constructiva.

&&&&&&&&&&

BIBLIOGRAFÍA:

1. Ohno, I. (1999). Systemization of Production Control in the Shipyard. Journal of the society of Naval Arquitects, Japan, 321-328.
2. Wibisono, et al (2007). Optimization system of block Division Using Genetic Algorithm and Product Model.
3. Talbi, El-Ghazali. Metaheuristics: from design to implementation. University of Lille. John Wiley & sons, EE.UU.