Tesis:
Surrogated Models for Metaheuristic Optimisation of Complex Problems
- Autor: SÁNCHEZ NAHARRO, Pablo
- Título: Surrogated Models for Metaheuristic Optimisation of Complex Problems
- Fecha: 2024
- Materia:
- Escuela: E.T.S DE INGENIEROS INFORMÁTICOS
- Departamentos: ARQUITECTURA Y TECNOLOGIA DE SISTEMAS INFORMATICOS
- Acceso electrónico: https://oa.upm.es/81774/
- Director/a 1º: TOHARIA RABASCO, Pablo
- Director/a 2º: PEÑA SÁNCHEZ, José María
- Resumen: Simulations are the cornerstone of many modern science and engineering fields. They allow experts to model a physical system using numerical equations that govern the dynamics among components, cause-effect interactions, and internal mechanics. The benefit of simulation-based science and engineering (SBES) is the potential to enable researchers to experiment in-silico alternative configurations, test computational models versus experimental data and estimate real-world systems performance.
A recurrent task in SBES consists of exploring different input parameters to analyse the resulting output and, later, choose the best configuration. This can be done using a manual adjustment or simple techniques such as grid search or random search. Nonetheless, applying a criterion is far more efficient than any brute-force method. In this context, heuristic optimisation is defined as a computational procedure that determines an optimal solution by iteratively trying to improve a candidate solution with regard to a given measure of quality and has become a popular tool for solving problems in these domains. These algorithms explore the search space by sampling solutions, evaluating their fitness, and biasing the search in the direction of promising solutions. However, in many cases such as engineering application problems, this fitness function involves executing expensive computational calculations or simulations, drastically reducing the reasonable number of evaluations. Hence, surrogate models have emerged as an excellent alternative to alleviate these computational problems.
There are many alternatives to the way that optimisation techniques and surrogate models can be applied. This makes it necessary to perform a tuning phase for selecting the best performing optimisation technique and the surrogates configuration that is going to be applied. When this is combined with the fact that the amount of fitness function evaluations is limited, a challenging problem arises as the action margin is limited.
In order to reduce the amount of preliminary work to achieve the correct surrogate con- figuration, different surrogate models have been evaluated, variating their type (regression and classification), their base model (regularised regression, neural networks, decision trees, boosting methods, and random forests) and the strategies used for creating the training dataset (encouraging diversity or relaxing prediction thresholds). For the case of classifiers, this work analyses a new proposal called pairwise surrogate models that align the model to how the optimiser uses its information. This approach can be directly exploited by some algorithms, such as Differential Evolution, certain Evolutionary Strategies or Tournament Selection in Genetic Algorithms, to name a few. In those, the fitness value is not actually needed to drive the search, and it is sufficient to know whether one solution is better than another one or not.
Further, the arguments described in the last two paragraphs lead me propose Best Performing Surrogate (BPS), an adaptive approach that dynamically selects the surrogate that is guiding the optimisation based on its performance. This research has shown that using an adaptive approach of surrogate models not only reduces the time to setup an optimisation algorithm by making decisions dynamically during the optimisation, but also improves the convergence in some of the fitness functions compared to its single surrogate approach.
The experimental part of this manuscript uses benchmark problems, that are similar to real- world problems according to some authors. However, although most of the experiments has been performed using the quick evaluating fitness function of benchmarks, some configurations have also been tested in two real-based simulation problems: hospital logistics and generative metamaterials design.
RESUMEN
Las simulaciones son la piedra angular de muchos campos en la ciencia moderna y la ingeniería ya que permiten a los expertos modelar un sistema físico usando ecuaciones numéricas que representan la dinámica entre los componentes, las relaciones causa-efecto y la mecánica interna de los componentes. Algunos de los beneficios de la ingeniería y la ciencia basada en simulación (SBES) es permitir a los investigadores experimentar in-silico configuraciones alternativas, testear los modelos computacionales frente a los experimentales y estimar el rendimiento de los sistemas en el mundo real.
Una tarea recurrente en SBES consiste en explorar los diferentes parámetros de entrada para analizar el resultado y, después, elegir la mejor configuración. Esto se puede hacer bien manualmente o aplicando técnicas simples como grid search o random search. Sin embargo, aplicar algún criterio es mucho más eficiente que cualquier mecanismo de fuerza bruta. En este contexto, podemos definir la optimización heurística como un proceso informático que determina una solución óptima mediante un proceso iterativo que intenta mejorar la solución candidata en relación a su medida de calidad. Además, este proceso se ha popularizado como herramienta para resolver problemas en este dominio.
Los algoritmos heurísticos y metaheurísticos exploran el espacio de búsqueda mediante el muestreo de soluciones, la evaluación de su valor objetivo y el sesgando la búsqueda hacia las soluciones más prometedoras. Sin embargo, en muchos problemas de ingeniería, la función objetivo implica ejecutar problemas con simulaciones computacionalmente costosas, lo que limita drásticamente la cantidad razonable de funciones objetivo que pueden ser evaluadas. Por ello, los modelos subrogados aparen como una excelente alternativa para solucionar estos problemas de cómputo.
Existen numerosas alternativas en la forma en la que los algoritmos de optimización y los modelos subrogados se pueden aplicar. Esto hace necesaria la existencia de una fase de ajuste para seleccionar la técnica con mejor rendimiento, así como el modelo subrogado que se va a aplicar. Lo cual, unido al hecho de que la función objetivo solo puede ser ejecutada un reducido número de veces, genera un problema debido a los límites en el margen de actuación.
Para reducir la cantidad de trabajo preliminar para elegir el subrogado apropiado, se han evaluado diferentes modelos subrogados variando su tipo (regresión y clasificación), su modelo base (regresión regularizada, redes neuronales, arboles de decisión, métodos de boosting y random forest), y las estrategias utilizadas para la creación del dataset de entrenamiento (promoviendo la diversidad de soluciones o relajando los límites de aceptación de soluciones). Además, para los clasificadores, se realiza una propuesta denominada pairwise surrogate models que alinea el modelo de predicción con la forma en la que el optimizador usa la información predicha. Esta aproximación puede ser usada directamente cuando se combina con algunas estrategias evolutivas de algoritmos genéticos y algunos algoritmos como Differential Evolution entre otros. En estos casos, el valor de fitness no es realmente necesario para guiar la búsqueda, sino que es suficiente con saber si una solución es mejor que otra o no.
Estos motivos me han conducido a proponer BPS (Best Performing Search), que es un modelo adaptativo de subrogados en el que se selecciona dinámicamente el modelo subrogado en función de su rendimiento. Esta investigación ha demostrado que usar una aproximación adaptativa de los modelos subrogados no solo reduce el tiempo de configuración de los algoritmos al reducir la fase preliminar de búsqueda de hiperparámetros, sino que también mejora la convergencia en algunas funciones objetivo comparado con una aproximación de subrogado único.
La parte experimental de este manuscrito usa problemas de benchmark, que son similares a los problemas de aplicación real según autores de la literatura. Sin embargo, aunque la mayoría de los experimentos se han realizado usando estas funciones de rápida ejecución, algunas configuraciones se han probado en dos problemas reales de simulación relacionados con la logística de hospitales y el diseño generativo de metamateriales.