Investigações sobre técnicas de arquivamento para otimizadores multiobjetivo

Multi-objective problems may have many optimal solutions, which together form the Pareto optimal set. A class of heuristic algorithms for those problems, in this work called optimizers, produces approximations of this optimal set. The approximation set kept by the optmizer may be limited or unlimited. The benefit of using an unlimited archive is to guarantee that all the nondominated solutions generated in the process will be saved. However, due to the large number of solutions that can be generated, to keep an archive and compare frequently new solutions to the stored ones may demand a high computational cost. The alternative is to use a limited archive. The problem that emerges from this situation is the need of discarding nondominated solutions when the archive is full. Some techniques were proposed to handle this problem, but investigations show that none of them can surely prevent the deterioration of the archives. This work investigates a technique to be used together with the previously proposed ideas in the literature to deal with limited archives. The technique consists on keeping discarded solutions in a secondary archive, and periodically recycle these solutions, bringing them back to the optimization. Three methods of recycling are presented. In order to verify if these ideas are capable to improve the archive content during the optimization, they were implemented together with other techniques from the literature. An computational experiment with NSGA-II, SPEA2, PAES, MOEA/D and NSGA-III algorithms, applied to many classes of problems is presented. The potential and the difficulties of the proposed techniques are evaluated based on statistical tests.

Problemas multiobjetivo, diferentes daqueles com um único objetivo, possuem, em geral, diversas soluções ótimas, as quais compõem o conjunto Pareto ótimo. Uma classe de algoritmos heurísticos para tais problemas, aqui chamados de otimizadores, produz aproximações deste conjunto. Devido ao grande número de soluções geradas durante a otimização, muitas delas serão descartadas, pois a manutenção e comparação frequente entre todas elas poderia demandar um alto custo de tempo. Como uma alternativa a este problema, muitos otimizadores lidam com arquivos limitados. Um problema que surge nestes casos é a necessidade do descarte de soluções não-dominadas, isto é, ótimas até então. Muitas técnicas foram propostas para lidar com o problema do descarte de soluções não-dominadas e as investigações mostraram que nenhuma delas é completamente capaz de prevenir a deterioração dos arquivos. Este trabalho investiga uma técnica para ser usada em conjunto com as propostas previamente na literatura, a fim de para melhorar a qualidade dos arquivos. A técnica consiste em reciclar periodicamente soluções descartadas. Para verificar se esta ideia pode melhorar o conteúdo dos otimizadores durante a otimização, ela foi implementada em três algoritmos da literatura e testada em diversos problemas. Os resultados mostraram que, quando os otimizadores já conseguem realizar uma boa otimização e resolver os problemas satisfatoriamente, a deterioração é pequena e o método de reciclagem ineficaz. Todavia, em casos em que o otimizador deteriora significativamente, a reciclagem conseguiu evitar esta deterioração no conjunto de aproximação.