Portfolio Selection in Evolutionary Algorithms

Abstract

Evolutionary Algorithms (EAs) are algorithms inspired in the process of natural selection, and are among the most popular methods in multiobjective optimization. As objectives are typically conflicting with one another, instead of a single optimal solution, there is usually a set of optimal solutions which, together, form a trade-off surface. The choice of the best solution depends on the preferences of a Decision Maker (DM), which arise from subjective information not contained in the multiobjective optimization problem formulation itself. In the absence of such preference information, an optimization algorithm should be able to cover the optimal trade-off surface as well as possible, in order to increase the chance that at least one satisfactory solution is presented to the (unknown) DM. One of the main steps of an EA is selection which is aimed at focusing on the best solutions, but must also maintain a sufficient level of diversity in the population. A very successful selection approach consists in optimizing a measure of the quality of the population as a whole, accounting simultaneously for individual quality and population diversity. Such EAs are called indicator-based EAs, as they rely on set-quality indicators to perform selection. Indicator-based EAs are currently state-of-the-art algorithms in Evolutionary Multiobjective Optimization (EMO). More recently, the notion of selection in EAs has been linked to the Portfolio Selection Problem (PSP), which is well known in Finance. In this analogy, individuals are seen as assets whose returns are random variables that are characterized by their expected values and covariance matrix. Balancing between good and diverse solutions in a population becomes analogous to balancing expected return and risk, respectively, in financial portfolios. In particular, it has been empirically shown that such a balance in EMO selection can be achieved using the risk-adjusted performance index known as Sharpe Ratio, without modification, as a new quality indicator in the context of a particular formulation of random individual return related to the concept of dominated hypervolume. The focus of the thesis is the subset selection problem at the core of selection in EMO algorithms, but from the more general point of view of Portfolio Selection. Two lines of work are followed. The first one consists in improving those state-of-the-art algorithms that are based on the hypervolume indicator, which is a well known and theoretically supported, but computationally expensive, quality indicator. The second line of work goes beyond subset selection: a new type of indicators based on the Sharpe Ratio is studied, both theoretically and experimentally, shedding new light on selection, fitness assignment and preference integration in EMO algorithms.

Os Algoritmos Evolutivos (AEs) são algoritmos inspirados no processo de selecção natural e estão entre os métodos mais utilizados em optimização multiobjectivo. Como tipicamente os objectivos são contraditórios entre si, em vez de existir uma única solução óptima, existe um conjunto de soluções óptimas que, juntas, formam uma superfície de trade-off. A escolha da melhor solução depende das preferências do decisor, que resultam de informação subjectiva não contida na formulação do problema multiobjectivo. Na ausência desta informação sobre preferências, um algoritmo de optimização deve ser capaz de cobrir a superfície de trade-off o melhor possível, de modo a aumentar as hipóteses de que, pelo menos, uma solução satisfatória seja apresentada ao decisor (desconhecido). Um dos principais passos de um AE é a selecção, que visa priveligiar as melhores soluções mas deve também manter um nível suficiente de diversidade na população. Uma abordagem bem sucedida para selecção consiste em optimizar uma medida de qualidade da população como um todo, tendo simultaneamente em conta a qualidade de cada indivíduo e a diversidade da população. A estes AEs dá-se o nome de AEs baseados em indicadores, e estão actualmente entre o estado da arte em Optimização Multiobjectivo Evolutiva (OME). Recentemente, a noção de selecção em AEs tem sido ligada ao Problema de Selecção de Portfólios (PSP), que é muito conhecido em Finanças. Nesta analogia, os indivíduos são vistos como activos cujos retornos são variáveis aleatórias caracterizadas pelo seus valores esperados e por uma matriz de covariância. Balancear entre boas soluções e soluções diferentes numa população torna-se análogo a balancear retorno esperado e risco, respectivamente, em portfólios financeiros. Em particular, já foi mostrado empiricamente que este balanceamento na selecção em OME pode ser obtido usando, sem qualquer modificação, um índice de desempenho que tem em conta o risco e que é conhecido como rácio de Sharpe, como um novo indicador de qualidade no contexto de uma determinada formulação de retorno individual aleatório relacionado com o conceito de hipervolume dominado. O foco desta tese é o problema de selecção de subconjuntos que está no cerne da selecção em algoritmos de OME, mas do ponto-de-vista mais geral de Selecção de Portfólios. Foram seguidas duas linhas de trabalho. A primeira consiste em melhorar os algoritmos estado da arte baseados no indicador de hipervolume, que é um indicador muito conhecido e com bases teóricas, mas cujo cálculo é computacionalmente dispendioso. A segunda linha de trabalho vai além da selecção de subconjuntos: estudar um novo tipo de indicadores baseados no rácio de Sharpe, tanto teórica como experimentalmente, abrindo uma nova perspectiva sobre a selecção, atribuição de aptidão e integração de preferências em algoritmos de OME.