Algorithm Selection for Multi-Objective Optimization

Abstract

Multi-objective optimization problems, which consider multiple objective functions to be optimized, can arise in many real-life scenarios, e.g., when trying to minimize both the cost and the time needed for traveling between two locations. In the last few decades, several algorithms have been proposed to solve multi-objective optimization problems. These algorithms can have very distinct behaviors, and their performance is often significantly affected by the problem instance to be solved, the time budget available, or the desirable solution quality. As such, which algorithm performs best often depends on the scenario that is being considered.This gives rise to the algorithm selection problem, which is concerned with the automatic selection of the best algorithm for a given scenario. In this thesis, we investigate the case of automatically selecting the best multi-objective optimization algorithm to solve a previously unseen problem instance, taking into account that the available time budget and desirable solution quality may be uncertain, and are only known when selecting the algorithm. We make several contributions in this line.First, we propose theoretical and empirical models to characterize the anytime performance of an algorithm, i.e., how solution quality improves over time, for previously unseen problem instances. Then, considering these models, we develop an offline selection methodology to select the best algorithm for a previously unseen problem instance given a utility function that describes the desirable time budget and solution quality. We also propose an online selection methodology that can swap between multi-objective branch and bound strategies to improve anytime performance. Lastly, we propose a scalarization technique and a branch and bound search strategy for multi-objective optimization problems to achieve a better anytime performance than previous approaches. Each contribution is backed by an experimental study on a multi-objective knapsack problem, and the results highlight the quality of the proposed models, selection methodologies, and algorithms.

Problemas de otimização multi-objetivo, que consideram múltiplas funções objetivo a otimizar, podem surgir em diversos cenários reais, por exemplo, quando se quer minimizar tanto o custo como o tempo de uma viagem entre dois locais. Nas últimas décadas, vários algoritmos foram propostos para resolver problemas multi-objetivo. Estes algoritmos podem ter comportamentos distintos, e o seu desempenho é tipicamente afetado pela instância do problema a resolver, o tempo disponível para resolver o problema, e a qualidade da solução desejada. Como tal, qual o algoritmo que tem melhor desempenho depende do cenário em consideração.Isto dá origem ao problema de seleção de algoritmos, que considera a escolha automática do algoritmo com melhor desempenho para um dado cenário. Nesta tese, investigamos a seleção automática do melhor algoritmo para resolver instâncias do problema nunca antes vistas, tendo em conta que o tempo disponível e a qualidade da solução desejada podem ser incertos, e apenas conhecidos aquando da seleção. Fazemos várias contribuições nesta direção.Em primeiro lugar, propomos modelos teóricos e empíricos para caracterizar o desempenho de algoritmos anytime, ou seja, modelos que caracterizem a evolução da qualidade da solução devolvida pelo algoritmo ao longo do tempo, para instâncias do problema nunca antes vistas. Em segundo lugar, tendo em conta os modelos propostos, desenvolvemos uma metodologia de seleção offline para selecionar o melhor algoritmo para uma instância do problema nunca antes vista, dada uma função de utilidade que descreve o tempo disponível e a qualidade da solução desejada. Também propomos uma metodologia de seleção online capaz de mudar de estratégias branch and bound multi-objetivo de forma a melhorar o desempenho do algoritmo ao longo do tempo. Por fim, propomos uma técnica de escalarização e uma estratégia de branch and bound para problemas de otimização multi-objetivo para obter um melhor desempenho ao longo do tempo comparativamente a abordagens já existentes. Cada contribuição é acompanhada por um estudo experimental de um problema knapsack multi-objetivo, sendo que os resultados destacam a qualidade dos modelos, metodologias de seleção, e algoritmos propostos.