Incorporation of Preferences, Adaptive Operators and Hybridization in Multi-Objective Evolutionary Algorithms

Abstract

The resolution of a multi-objective optimization problem involves, in general, not only a search phase adequate to provide a representative set of the Pareto-optimal front, but also a decision phase consisting in the identification of a solution (or a set of solutions) acceptable as a final recommendation having in mind practical implementation. The incorporation of preferences during the evolutionary process allows focusing the search according to the preference information elicited from the decision maker, avoiding the exploration of irrelevant solutions (thus minimizing the computational time) and facilitating the integration of knowledge in the search process (minimizing the cognitive effort). These aspects are particularly important in combinatorial problems, when the number of objective functions is large and/or their nature is conflicting, since the size of the search space as well as the number of non-dominated solutions tends to be very high. The evolutionary approach, called EvABOR (Evolutionary Algorithm Based on an outranking Relation), presented in this work incorporates the decision maker’s preferences to guide the search for regions of the space more in accordance with the elicited preferences. These are captured and made operational using the principles and parameters of the ELECTRE TRI method. The outranking relation in the ELECTRE TRI method is used to replace/complement the non-dominance relation in the usual evolutionary algorithm operators (crossover, mutation and selection). Since the quality of the initial solutions may influence the performance of an evolutionary algorithm a methodology based on GRASP (Greedy Randomized Adaptive Search Procedure) is proposed for the construction of initial solutions. This procedure is particularly relevant when knowledge about the problem at hand exists, which happens, in general, in real-world problems. Additionally, the need to exploit regions of the search space more efficiently led to the implementation of a local search procedure based on Simulated Annealing, in which the preferences elicited from a decision maker are taken into account. This motivated the development of a new approach for multi-objective optimization problems in which GRASP and Simulated Annealing are hybridized, incorporating preferences in the construction phase or/and the local search phase. The proposed algorithms are applied to provide decision support in the resolution of two real-world problems: a reactive power compensation problem in electrical distribution networks, using the EvABOR algorithm, and a direct load control problem, using the hybrid algorithm.

A resolução de um problema de optimização multiobjectivo envolve, em geral, não apenas uma fase de pesquisa, capaz de fornecer um conjunto representativo da frente óptima de Pareto, mas também uma fase de decisão, consistindo na escolha da solução (ou conjunto de soluções) aceitável como recomendação final tendo em vista a sua aplicação prática. Neste sentido, a incorporação de preferências durante o processo evolutivo permite focar a pesquisa evitando a exploração de soluções irrelevantes (minimizando assim o tempo de computação) e facilita a integração de conhecimento do decisor no processo de pesquisa (minimizando o esforço cognitivo). Estes aspectos são particularmente importantes quando o número de funções objectivo é grande e/ou a sua natureza é conflituante, uma vez que a dimensão do espaço de pesquisa assim como o número de soluções não-dominadas admissíveis tende a ser elevado. A proposta de uma abordagem evolutiva, designada por EvABOR (Evolutionary Algorithm Based on an Outranking Relation), apresentada neste trabalho incorpora as preferências de um decisor de modo a guiar a pesquisa para regiões do espaço mais de acordo com as preferências explicitadas. Estas são captadas e tornadas operacionais recorrendo aos parâmetros e princípios do método ELECTRE TRI. A relação de prevalência (outranking), na qual o ELECTRE TRI se baseia, é usada para substituir/complementar a relação de não dominância nos habituais operadores do algoritmo evolutivo (cruzamento, mutação e selecção). Dado que a qualidade das soluções iniciais pode influenciar o desempenho de um algoritmo evolutivo, e existindo conhecimento sobre o problema em causa, nomeadamente ao lidar com problemas reais, propõe-se uma metodologia de construção de soluções iniciais baseada no GRASP (Greedy Randomized Adaptive Search Procedure) permitindo também a incorporação de preferências. Adicionalmente, a necessidade de explorar as regiões do espaço de pesquisa de forma mais eficiente, levou à implementação de um procedimento de pesquisa local, baseado no Simulated Annealing, onde as preferências explicitadas pelo decisor são tidas em conta, sendo também incorporadas numa versão multiobjectivo do Simulated Annealing. Este trabalho teve como resultado um novo algoritmo onde se explora a hibridização do GRASP com o Simulated Annealing, incorporando as preferências tanto na fase de construção como na fase de pesquisa local. Os algoritmos propostos foram aplicados na resolução de dois problemas recorrendo a dados reais: um problema de compensação de energia reactiva em redes de distribuição de energia eléctrica, no caso do EvABOR, e um problema de controlo remoto de cargas, no caso do algoritmo híbrido.