Evolutionary computation strategies applied to the ua-flp

Resumen

1. Introducción o motivación de la tesis. El problema de distribución en planta, comúnmente conocido como Facility Layout Problem (FLP), trata de determinar la mejor ubicación para los departamentos o instalaciones que componen una planta industrial [1]. Para ello, han de tenerse en consideración ciertos criterios y restricciones. Una buena distribución de las instalaciones que componen la planta industrial puede reducir entre un 20% y un 50% los costes totales de producción [2]. La forma en la que se distribuyen las instalaciones en una planta industrial afecta directamente a los costes de producción, eficiencia de la planta y productividad [3]. Aunque el flujo de material entre las diferentes instalaciones que conforman la planta es el criterio más considerado a la hora de resolver el problema que nos atañe [4], existen otras características que pueden tenerse en cuenta. Estas pueden ser de tipo cuantitativo o cualitativo [5]. En el primer caso, podemos hablar de requerimientos de cercanía o proximidad entre dos instalaciones, satisfacer alguna restricción de forma, etc. En el segundo caso, hablamos de otro tipo de preferencias, que pueden ser útiles o necesarias cuando realizamos el diseño de la planta industrial [6], como por ejemplo: deseo de una concreta ubicación de una instalación en particular, necesidad de evitar la localización para cierto departamento, la seguridad, el ruido, la flexibilidad, etc. Las características cualitativas son difíciles de considerar, ya que no pueden ser modeladas como una función clásica de optimización, pueden variar durante el proceso de diseño, son específicas para cada problema en particular, y pueden ser desconocidas a priori [7]. Para solucionar esta problemática, se requiere el conocimiento del diseñador experto, incluyendo sus preferencias a la hora de buscar la mejor solución de diseño. Por lo tanto, se considera necesario investigar nuevos enfoques que permitan evitar sobrecargar al diseñador experto durante la ejecución del algoritmo interactivo, siendo esencial preservar la diversidad de la población al mismo tiempo que se evite evaluar diseños repetidos. Por otro lado, uno de los principales problemas con el que nos encontramos a la hora de afrontar el FLP es la búsqueda de soluciones diversas, ya que cuanta mayor diversidad podamos mantener, mayor probabilidad tendremos de encontrar buenas soluciones. La adopción de un enfoque paralelo puede considerarse como una forma de mejorar la diversificación de la búsqueda y retrasar la convergencia prematura [8], características clave para explorar un espacio de búsqueda más amplio y obtener mejores soluciones. Es por ello que, a la vista de los primeros estudios publicados, consideramos que los algoritmos genéticos paralelos (PGA) pueden ser una herramienta prometedora para el mantenimiento de la diversidad de la población y, por consecuencia, para la obtención de mejores y diversas soluciones para el FLP. 2. Contenido de la investigación. El objetivo principal de esta tesis doctoral es mejorar los enfoques existentes para la resolución del Unequal Area Facility Layout Problem (UA-FLP), mediante el desarrollo de propuestas basadas en algoritmos genéticos. Estas nuevas propuestas exploran dos líneas de investigación prometedoras: a) la resolución del problema teniendo en cuenta los aspectos cualitativos para ayudar al diseñador experto, y b) la aplicación de nuevas técnicas para el mantenimiento de la diversidad de la población, que permita explorar un amplio espacio de búsqueda con mayores probabilidades de obtener mejores soluciones. La consideración de aspectos cualitativos en el diseño de distribución en planta enriquece enormemente las soluciones obtenidas. Sin embargo, tiene el inconveniente que la presentación de soluciones al diseñador experto para que este las evalúe puede provocarle cansancio, ya que, a menudo, se le presentan soluciones similares a las ya evaluadas [9]. Para intentar solucionar este problema, se han evaluado diferentes técnicas para preservar las soluciones. Como resultado de este estudio, se ha desarrollado una propuesta en la que se aplican técnicas de clustering para mostrar al diseñador únicamente las soluciones representativas, y métodos de niching para preservar múltiples nichos estables de posibles soluciones. Por otro lado, en esta tesis se trata de resolver los inconvenientes clásicos de los algoritmos genéticos (quedar atrapado en los óptimos locales, la convergencia prematura y el tiempo de ejecución) [10]. En la presente tesis se ha desarrollado una propuesta denominada Island Model Genetic Algorithm (IMGA), basada en un PGA de grano grueso con múltiples poblaciones o islas. Debido al grado de independencia que suponen las islas, y al intercambio de individuos a través de la migración, es posible explorar diferentes regiones del espacio de búsqueda [11], mejorando así la calidad de las soluciones en un menor número de iteraciones y manteniendo la diversidad de la población [12]. 3. Conclusión. Se han desarrollado dos propuestas para resolver el problema FLP. Con ambas propuestas en se han realizado experimentos que han arrojado resultados muy satisfactorios. Estos buenos resultados han permitido la publicación de dos artículos indexados en el primer decil del ranking JCR. La introducción de las preferencias subjetivas de un usuario experto enriquece el conjunto de soluciones obtenidas, permitiendo tener en cuenta aspectos difíciles de considerar en una función objetivo tradicional. Para reducir la fatiga física y visual de la intervención humana se ha recurrido a agrupar las soluciones que componen la población en grupos más o menos homogéneos, a través de un procedimiento de clustering. Por otro lado, las dos carencias fundamentales de los métodos de computación evolutiva son: a) el peligro de caer rápidamente en óptimos locales, con una convergencia prematura hacia soluciones alejadas del óptimo global, y b) la falta de diversidad de la población, aspectos ambos que están íntimamente relacionados. Para incrementar la variabilidad de la población y evitar la convergencia prematura, se han propuesto dos técnicas: en primer lugar el uso de técnicas de niching y, en segundo lugar, un nuevo enfoque consistente en la evolución de la población por islas independientes. Estos nuevos enfoques aplicados al FLP han sido probados sobre un amplio conjunto de problemas bien conocidos en la bibliografía, obteniendo soluciones aptas y mejores que las aportadas hasta el momento por otras propuestas, incluso con coste computacional inferior. 4. Bibliografía. [1] S. Heragu, Facilities Design. CRC Press, 2018, ISBN: 9781498732901. [2] J. Tompkins, J. White, Y. Bozer y J. Tanchoco, Facilities Planning, 4rd ed. New York: Wiley, 2010. [3] P. Kouvelis, A. A. Kurawarwala y G. J. Gutierrez, «Algorithms for robust single and multiple period layout planning for manufacturing systems», European Journal of Operational Research, vol. 63, nº 2, págs. 287-303, 1992. [4] A. Drira, H. Pierreval y S. Hajri-Gabouj, «Facility layout problems: A survey», Annual Reviews in Control, vol. 31, nº 2, págs. 255-267, 2007. [5] A. M. Brintup, J. Ramsden y A. Tiwari, «An interactive genetic algorithm-based framework for handling qualitative criteria in design optimization», Computers in Industry, vol. 58, págs. 279-291, 2007. [6] B. Malakooti y A. Tsurushima, «An expert system using priorities for solving multiple-criteria facility layout problems», International Journal of Production Research, vol. 27, nº 5, págs. 793-808, 1989. [7] L. García-Hernández, H. Pierreval, L. Salas-Morera y A. Arauzo-Azofra, «Handling qualitative aspects in Unequal Area Facility Layout Problem: An Interactive Genetic Algorithm», Appl. Soft Comput., vol. 13, nº 4, págs. 1718-1727, 2013. [8] M. Kurdi, «An effective new island model genetic algorithm for job shop scheduling problem», Computers & Operations Research, vol. 67, págs. 132 -142, 2016. [9] L. García-Hernández, A. Arauzo-Azofra, L. Salas-Morera, H. Pierreval y E. Corchado, «Recycling Plants Layout Design by Means of an Interactive Genetic Algorithm», Intelligent Automation & Soft Computing, vol. 19, nº 3, págs. 457-468, 2013. [10] D. B. Fogel, «An introduction to simulated evolutionary optimization», IEEE transactions on neural networks, vol. 5, nº 1, págs. 3-14, 1994. [11] D. Whitley, S. Rana y R. Heckendorn, «The Island Model Genetic Algorithm: On Separability, Population Size and Convergence», Journal of Computing and Information Technology, vol. 7, 1998. [12] T. Starkweather, D. Whitley y K. Mathias, «Optimization using distributed genetic algorithms», en Parallel Problem Solving from Nature, H.-P. Schwefel y R. Manner, eds., Berlin, Heidelberg: Springer Berlin Heidelberg, 1991, págs. 176-185, ISBN: 978-3-540-70652-6.