Estrategias de computación evolutiva aplicadas al UA-FLP

Abstract

En la presente tesis doctoral se desarrollan dos aproximaciones distintas al problema de distribución en planta de áreas desiguales (UA-FLP). En primer lugar, se trata de incorporar el conocimiento del diseñador experto a los algoritmos clásicos de optimización, de forma que, además de buscar buenas soluciones desde el punto de vista cuantitativo, por ejemplo minimizando el flujo de materiales, se introduzca la posibilidad de que el diseñador aporte su experiencia y preferencias personales. Para facilitar la intervención humana en el proceso de búsqueda de soluciones, se ha utilizado un procedimiento de clustering, el cual permite clasificar las soluciones subyacentes en el conjunto de búsqueda, de forma que se presente al diseñador un número suficientemente representativo y, a la vez, evitándole una fatiga innecesaria. Además, en esta primera propuesta se han implementado dos técnicas de niching, denominadas Deterministic Crowding y Restricted Tournament Selection. Estas técnicas tienen la capacidad de mantener ciertas propiedades dentro de la población de soluciones, preservar múltiples nichos con soluciones cercanas a los óptimos locales, y reducir la probabilidad de quedar atrapado en ellos. De esta manera el algoritmo se enfoca simultáneamente en más de una región (nicho) en el espacio de búsqueda, lo cual es esencial para descubrir varios óptimos en una sola ejecución. Por otro lado, en la segunda aproximación al problema, se ha implementado una estrategia evolutiva paralela, muy útil para los problemas de alta complejidad en los que el tiempo de ejecución con un enfoque evolutivo secuencial es prohibitivo. La propuesta desarrollada, denominada IMGA, está basada en un algoritmo genético paralelo de grano grueso con múltiples poblaciones o islas. Este enfoque se caracteriza por evolucionar varias subpoblaciones independientemente, entre las que se intercambian individuos, haciendo posible explorar diferentes regiones del espacio de búsqueda, al mismo tiempo que se mantiene la diversidad de la población, permitiendo la obtención de buenas y diversas soluciones. Con ambas propuestas se han realizado experimentos que han arrojado resultados muy satisfactorios, encontrando buenas soluciones para un conjunto de problemas bien conocidos en la bibliografía. Estos buenos resultados han permitido la publicación de dos artículos indexados en el primer decil del ranking JCR (Journal Citation Reports).

The present doctoral thesis develops two different approaches to the Unequal Area Facility Layout Problem (UA-FLP). The first approach encompasses the designer’s knowledge on classic optimization of algorithms in pursuance of good quantitative solutions (e.g. minimizing the materials flow) and also opens the possibility to include the contribution of the designer by means of his expertise and personal preferences. A clustering procedure has been used to facilitate human intervention in the process of finding solutions. This allows the underlying solutions to be classified in the search in order to present the designer with sufficiently representative solutions and, at the same time, avoiding unnecessary fatigue. In addition, two niching techniques have been implemented, called Deterministic Crowding and Restricted Tournament Selection. These techniques have the ability to maintain certain properties within the solutions space, preserve multiple niches with solutions close by local optimums, and reduce the probability of being trapped in them. In this way, the algorithm focuses simultaneously on more than one region (niche) in the search space, which is essential to discover several optimums in a single execution. The second approach to the problem comprises the implementation of a parallel evolutionary strategy. This method is useful for problems of high complexity in which the execution time using a sequential evolutionary approach is prohibitive. The proposal developed, called IMGA (Island Model Genetic Algorithm), is based on a parallel genetic algorithm of multiple-population coarse-grained. This is characterized by evolving several subpopulations independently among which individuals are exchanged. Different regions of the search space can be explored while the diversity of the population is maintained. Satisfactory and diverse solutions have been obtained as a result of this method. Experiments with both proposals have been carried out with satisfactory results, providing good solutions for a set of problems well known in the literature. These results were already published in two papers indexed in the first decile of the JCR (Journal Citation Reports) ranking.