APLICACIONES DE MÉTODOS HEURÍSTICOS EN LA INGENIERÍA.
TAXONOMÍA Y EJEMPLOS PRÁCTICOS

Fernando Gudiño-Peñaloza^*
Facultad de Estudios Superiores Cuautitlán, UNAM
^*ilciarmin@gmail.com

Resumen

En la actualidad la integración de la inteligencia artificial y las técnicas de aprendizaje máquina y aprendizaje profundo a la resolución de problemas múltiples de las diferentes áreas de la ingeniería ha significado un avance en el entendimiento y resolución de dichos problemas. Varias de estas técnicas se basan en la utilización de métodos heurísticos para su implementación. Uno de los problemas recurrentes de las técnicas de resolución tradicionales (métodos exactos) es el consumo de recursos necesarios para su implementación, así como una complejidad temporal y espacial elevada si se utilizan computadoras para su implementación. Es por ello por lo que la utilización de los métodos heurísticos resulta una alternativa adecuada para lidiar con estos problemas. Se califica de heurístico a un procedimiento para el que se tiene un alto grado de confianza en que encontrará soluciones de alta calidad con un coste computacional razonable, aunque no se garantice su optimalidad o su factibilidad, e incluso, en algunos casos, no se llegue a establecer lo cerca que se está de dicha situación. La idea subyacente es optimizar los recursos con los que se cuentan, a la par de la calidad de solución a implementar. En si se puede decir que se llega a una solución “buena” del problema, pero generalmente no la mejor. En este artículo se presenta una taxonomía de los métodos heurísticos poniendo énfasis en los métodos metaheurísticos utilizados de manera recurrente en procesos de optimización de tareas, por último, se dan ejemplos claros de las técnicas utilizadas actualmente en diferentes áreas de la ingeniería.

Palabras clave: Optimización, Aprendizaje Máquina, Aprendizaje Profundo, tecnología aplicada

Introducción

Actualmente los problemas que enfrentamos en diferentes ámbitos de nuestra vida laboral y personal tienden a ser muy complicados, esto debido a las grandes cantidades de información, el origen y la rapidez requerida para procesarla y entregar una solución a dichos problemas. Los sistemas computacionales han surgido como una herramienta útil para realizar las tareas de análisis y síntesis de la información y nos permiten tomar decisiones basadas en el conocimiento. Si bien en un principio los sistemas de apoyo a las decisiones (DSS) utilizaban métodos “exactos” desarrollados en otras áreas para dar solución a los problemas expuestos, con el tiempo se demostró que estas técnicas no eran capaces de dar soluciones viables a muchos de los problemas reales.

Incluso si se puede desarrollar un algoritmo exacto, su complejidad temporal (tiempo de procesamiento computacional) y espacial (espacio de almacenamiento) pueden resultar inaceptables (Desale, 2015). Sin embargo, en la realidad a menudo no es necesario tener una solución perfecta, basta con tener una solución aproximada o parcial. Tal flexibilidad en la respuesta nos permite tener un conjunto más amplio de técnicas para hacer frente a los problemas que enfrentamos.

Discutimos algoritmos heurísticos que sugieren algunas aproximaciones a la solución de problemas en Ingeniería. En tales problemas el objetivo es encontrar la óptima de todas las soluciones posibles, es decir, aquella que minimiza o maximiza una función objetivo. La función objetivo es una función utilizada para evaluar la calidad de la solución generada.

Objetivo

El objetivo del presente documento es demostrar la importancia que los métodos heurísticos tienen en las diferentes áreas de la ingeniería, en particular en aquellas impartidas dentro de la Fes Cuautitlán y hacer notar la necesidad de incluir el estudio de dichas técnicas en los planes de estudio.

Desarrollo del tema

Un problema de búsqueda.
El propósito final de todos los métodos de solución de problemas es encontrar una respuesta a un problema dado. En tales problemas el objetivo es encontrar la óptima de todas las soluciones posibles, es decir, aquella que minimiza o maximiza una función objetivo. La función objetivo es una función utilizada para evaluar la calidad de la solución generada. Muchos problemas del mundo real son fácilmente planteados como problemas de optimización. La recopilación de todas las posibles soluciones para un problema dado puede ser considerado como un espacio de búsqueda y algoritmos de optimización, a su vez, motivo por el cual se denominan algoritmos de búsqueda al hecho de tratar de encontrar dicha solución.

Por un lado, los algoritmos exactos son algoritmos que siempre resuelven un problema de optimización de forma óptima. Por ejemplo, si nosotros enfrentamos el problema de “la suma de dos números reales A y B” podemos decir que dicha suma es S=A+B, siendo S un valor en el conjunto de los números reales, así si Aes igual a 4 y B es igual a 2, la suma S es igual a 6. Nadie pone en duda dicha afirmación y el valor de la suma es exactamente seis, siempre lo ha sido y siempre lo será, es por tanto su valor exacto.

Ahora pongamos el ejemplo del área de un círculo está definido por “A=πr2”, en este caso el área A tomara diferentes valores de acuerdo con el número de decimales que se utilicen en el palor de pi. Este no es un valor exacto, sin embargo, es un valor próximo y podemos aceptarlo como valido aun cuando no estemos seguro del valor de dicha área.

De igual manera en los métodos de solución de problemas más complejos, no es necesario tener un valor exacto, nos basta con un valor aproximado. El en si se reduce entonces en encontrar aquel método que se acerque a dar una solución aceptable en el espacio de búsqueda adecuado (el de las técnicas de solución de dicho problema).

El conjunto de algoritmos que dan casi la respuesta correcta o proporcionar una solución no aplicable para todas las instancias del problema son llamados algoritmos heurísticos. Este grupo incluye un amplio espectro de métodos basados tanto en técnicas tradicionales como específicas. fundamentales de los algoritmos de búsqueda tradicionales.

Es difícil imaginar la variedad de problemas existentes, así como el número de algoritmos desarrollados para resolverlos. Sin embargo, los métodos aproximados los podemos clasificar en dos grandes categorías: Heurísticos y metaheurísticos.

La diferencia entre una y otra es que la primera trata de obtener una buena suposición de la solución de un problema, pero que realmente no sabes lo bueno que es (Nuha, 2018). El segundo se trata de obtener una solución para la que pueda demostrar lo cerca que está de la solución óptima. Por lo tanto, la heurística a menudo depende del problema, es decir, se define una heurística para un problema dado, por ello se les suele llamar heurísticas ad hoc. Las metaheurísticas son técnicas independientes de los problemas que se pueden aplicar a una amplia gama de problemas. Una metaheurística no sabe nada sobre el problema que se aplicará, puede tratar las funciones objetivo como cajas negras. En la Figura 1 se puede ver la taxonomía de los métodos de solución.

Técnicas Ad hoc.
Las técnicas ad hoc se dividen a su vez en subvariedades de búsquedas exhaustivas, es decir evalúan todas las posibles soluciones. estas técnicas se ordenan de la siguiente manera:

• Algoritmos de búsqueda local, es una versión de búsqueda exhaustiva que solo se enfoca en un área limitada del espacio de búsqueda. Tales algoritmos reemplazar constantemente la solución actual con lo mejor de sus vecinos si es mejor que el actual.
• Los algoritmos de divide y vencerás, intentan dividir un problema en problemas más pequeños que son más fáciles de resolver. Las soluciones de los pequeños problemas deben ser combinables para una solución para el original. Esta técnica es efectiva pero su uso es limitado, porque no hay una gran cantidad de problemas que se puedan particionar fácilmente y combinados de tal manera.
• Técnicas de branch-and-bound, es una enumeración crítica del espacio de búsqueda. Enumera, pero constantemente trata de descartar partes del espacio de búsqueda que no puede contener la mejor solución.
• La programación dinámica es una búsqueda exhaustiva que evita el recálculo almacenando las soluciones de los subproblemas. El punto clave para usar esta técnica está formulando el proceso de solución como una recursión.

Metaheurísticas.
De igual manera que dividimos a los métodos en exactos y heurísticos, y estos últimos en ad hoc y metaheurísticos, podemos dividir esta categoría en dos tipos: metaheurísticas basadas en trayectorias y basadas en poblaciones, tal como se ve en la Figura 1.

Una metaheurística basada en trayectoria mejora iterativamente una única solución y forma una trayectoria de búsqueda en el espacio de la solución. Los ejemplos de metaheurísticas basadas en trayectorias incluyen el recocido simulado (SA), la búsqueda tabú (TS), la búsqueda local iterada (ILS) y la búsqueda local guiada (GLS) (Hu,2018). En las metaheurísticas basadas en la población, varios operadores procesan una población de soluciones en cada iteración (generación). Los miembros de la población son reemplazados por otros nuevos para que se pueda explorar el espacio de solución. El algoritmo genético (GA), la optimización de colonias de hormigas (ACO), la optimización de enjambres de partículas (PSO) y la colonia de abejas artificiales (ABC) [4] son algunas metaheurísticas basadas en la población ampliamente utilizadas.

Ejemplos de aplicación en la ingeniería.
Enlistar los ejemplos de aplicación de métodos heurísticos en la ingeniería es por sí misma una labor ociosa. Por ello solamente pondremos algunos ejemplos utilizados en las carreras impartidas en la Facultad de Estudios Superiores Cuautitlán.

Metaheurística para la optimización de parámetros en biorreactores.
Un biorreactor es un recipiente o sistema que mantiene un ambiente biológicamente activo. Se puede definir como un sistema diseñado, desplegado para facilitar el crecimiento de la masa biológica a través de la transformación o degradación del material alimentado al reactor. Para ello se deben mantener condiciones estables de temperatura, ph, presión, etc. Hernández (2019) presentó un esquema computacional efectivo utilizando técnicas metaheurísticas para la optimización de un proceso integrado de producción de biodiesel a partir de la microalga Chlorella vulgaris. Se optimizaron diez variables de decisión, incluidas las temperaturas y presiones de los cinco reactores de proceso y el número de etapas y la etapa de alimentación de las tres columnas de destilación consideradas. El modelo es una formulación multiobjetivo que involucra objetivos económicos y ambientales. La función objetivo económica tiene como objetivo maximizar el ingreso anual total. La función objetivo asociada al impacto ambiental es minimizar los gases de efecto invernadero producidos. La herramienta de optimización que se utilizó en este artículo consiste en un algoritmo estocástico llamado I-MODE (evolución diferencial multiobjetivo mejorada).

Ensamblaje óptimo de tarjetas PCB en la industria de electrónicos.
En la industria electrónica, montaje automático de placas de circuito impreso (PCB) constituye un proceso de fabricación fundamental. El equipo utilizado para automatizar el montaje de electrónica supera con creces a otras máquinas en términos de capital inversión y complejidad en su programación de operaciones y control de máquinas.

Las desviaciones considerables entre las especificaciones proporcionadas por el diseñador y el resultado real pueden ser enormes, y el potencial de las configuraciones del sistema de montaje se vuelen enormes. Es por lo que se necesita un sistema que ayude a solucionar las configuraciones según los elementos a ensamblar. Métodos basados en la teoría de grafos, así como en modernos algoritmos de búsqueda numérica ayudaron a Grunow (Grunow, 2000) a reducir las pérdidas asociadas a la reconfiguración de los elementos. Para ello un sistema basado en grafos modelaba los puntos de ensamble de las piezas mientras que un algoritmo de recocido simulado optimizaba las rutas que debían de seguir las placas PBC para lograr reducir el tiempo en el que se dada el ensamble total de la placa electrónica.

Cálculo de orbitas satelitales para estaciones espaciales.
La misión de la estación espacial se está convirtiendo gradualmente en una tendencia floreciente de la industria en los últimos años, tanto como el mantenimiento de equipos, el suministro de combustible, el ensamblaje en órbita, etc. Muchos países comienzan a explorar el mantenimiento de la estación espacial, y vale la pena señalar que los satélites asociados a la estación han tenido éxito para completar las tareas en la estación espacial. Especialmente, la optimización de la trayectoria del satélite es crucial para las comunicaciones en órbita en la estación espacial. Se requiere la optimización de la trayectoria del satélite para reducir el consumo de combustible y acortar el tiempo de aproximación, sujeto a múltiples limitaciones. Hu (2018) propuso el uso de a model predictive control (MPC) una técnica exhaustiva para encontrar la trayectoria optima, pero dada la complejidad de las restricciones (espacio, combustible, velocidad, etc.) utiliza una corrección del modelo usando linealización, la cual es una técnica obtenida de la programación numérica, esto lo convierte en una técnica hibrida conocida como mate-heurísticas.

Reducción de maleza en plantíos de maíz.
El maíz (Zea mays L.) es uno de los principales cultivos de cereales del mundo y proporciona aproximadamente el 15% de las proteínas del mundo y el 20% de las calorías del mundo (Nuss, 2010). La escasez de proteínas y calorías en la gran proporción de la población mundial está provocando un crecimiento y desarrollo reducidos y un aumento de las enfermedades, especialmente entre los niños (Pimentel et al., 1975). Desafortunadamente la amapola mexicana (Argemone mexicana) es una maleza anual nociva generalizada asociada con cultivos como el maíz. Esta especie de maleza invasora debe controlarse incluso en la estación seca porque la amapola mexicana tiene un sistema de raíces de gran alcance, que extrae agua de las capas profundas del suelo. Sin embargo, cuando las malezas se controlan de manera uniforme en lugar de un método de agricultura de precisión o específico del sitio en los campos espacialmente variables, existen desafíos de contaminación ambiental. Las técnicas de control de malezas específicas en sitio han ganado interés en la comunidad de agricultura de precisión en los últimos años. En su estudio Moshia (2019) propone la utilización de técnicas de inteligencia artificial, Deep learning, para determinar las zonas de maleza para etiquetarlas y georeferenciarlas para su exterminio en sitio. Las técnicas de Deep learning en si se consideran técnicas metaheurísticas ya que dichas técnicas no ofrecen soluciones únicas, sino que ofrecen un Pareto de soluciones viables a un problema específico.

Conclusión

Las técnicas heurísticas han empezado a desplazar a las técnicas exactas en la solución de problemas, sobre todo en aquellos problemas en los cuales existen múltiples objetivos y gran cantidad de restricciones, ya que convierten el problema en una instancia de un problema de búsqueda de la solución óptima. Si bien las soluciones que ofrece no son perfectas, son lo suficientemente buenas para poder aceptarlas y además son desde un punto de vista de implementación más viables que un método tradicional.
Sin embargo, la enorme cantidad de técnicas existentes acarrea un nuevo problema ¿Cómo seleccionar la técnica adecuada para el problema que quiero resolver? La respuesta no es sencilla y dependerá en gran medida de la experiencia de quien decida usar este tipo de métodos. En ingeniería se ha visto que gran número de operaciones se refieren a la selección correcta de parámetros o configuraciones de operación, por lo cual, estos métodos nos brindan soluciones viables para su implementación.

Referencias

• Desale, S., Rasool, A., Andhale, S., & Rane, P. (2015). Heuristic and meta-heuristic algorithms and their relevance to the real world: a survey. Int. J. Comput. Eng. Res. Trends, 351(5): 2349-7084.
• Grunow, M., Günther, H.O., & Föhrenbach, A. (2000). Simulation-based performance analysis and optimization of electronics assembly equipment. International Journal of Production Research, 38(17): 4247-4259.
• Hernández, P.L.G., Sánchez, T.E., Ojeda, K.A., El-Halwagi, M.M., & Ponce, O.J.M. (2019). Optimization of microalgae-to-biodiesel production process using a metaheuristic technique. ACS Sustainable Chemistry & Engineering, 7(9): 8490-8498.
• Hu, Q., Xie, J., & Liu, X. (2018). Trajectory optimization for accompanying satellite obstacle avoidance. Aerospace Science and Technology, 82: 220-233.
• Moshia, M.E., & Newete, S.W. (2019). Mexican poppy (Argemone mexicana) control in cornfield using deep learning neural networks: A perspective. Acta Agriculturae Scandinavica, Section B—Soil & Plant Science, 69(3): 228-234.
• Nuha, H., Wati, P.E.D.K., & Widiasih, W. (2018). A comparison of exact method-metaheuristic method in determination for vehicle routing problem. In MATEC Web of Conferences, 204: 02017).

Quinto Congreso Nacional de Tecnología 19, 20 y 21 de octubre de 2022,
celebrado en formato virtual

---

Excepto donde se indique lo contrario esta obra está bajo una licencia Creative Commons Atribución No comercial, No derivada, 4.0 Internacional (CC BY NC ND 4.0 INTERNACIONAL).
https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es

FORMA SUGERIDA DE CITAR:

Gudiño-Peñaloza, F. (2022). Aplicaciones de métodos heurísticos en la ingeniería. Taxonomía y ejemplos prácticos. MEMORIAS DEL CONGRESO NACIONAL DE TECNOLOGÍA (CONATEC), Año 5, No. 5, septiembre 2022 - agosto 2023. Facultad de Estudios Superiores Cuautitlán. UNAM. https://tecnicosacademicos.cuautitlan.unam.mx/CongresoTA/memorias2022/mem2022_ExtensoPaper5.html

---