Geração de diversidade na otimização dinâmica multiobjetivo evolucionária por paisagens de não-dominância

Abstract

A geração e manutenção de soluções distintas em Algoritmos Evolucionários Multiobjetivo (MOEAs), sobretudo em ambientes dinâmicos nos quais os critérios de avaliação das soluções podem variar ao longo do tempo, é um problema em aberto, em que há poucos estudos sobre a influência das diferentes maneiras de gerar diversidade na qualidade do conjunto de soluções ótimas. A inclusão de geradores de diversidade em MOEAs pode aumentar o custo do processo evolucionário e prejudicar seu desempenho. Surge, então, a necessidade de buscar meios para atenuar a repercussão negativa do aumento dos níveis de dispersão da população de soluções candidatas no caminhamento à superfície onde se situam os pontos ótimos, conhecida como a Frente de Pareto (PF). Em sistemas biológicos, regimes de imigração aumentam as possíveis combinações de trocas genéticas, promovendo diversidade de caminhos evolucionários. Inspirada na modelagem de imigração natural, esta pesquisa investiga a inserção de soluções atípicas (imigrantes) em populações de soluções candidatas como forma de gerar diversidade em MOEAs aplicados à otimização dinâmica multiobjetivo. A dissertação também propõe e formaliza as Paisagens de Não-Dominância (NDL) para guiar a inserção dos imigrantes gerados na população. As NDLs proveem os MOEAs das probabilidades dos imigrantes serem não-dominados em uma população a partir da estimação de funções densidade de probabilidade e de estatísticas de ordem multivariadas no espaço de objetivos. Após caracterizar a influência da diversidade na dinâmica de aproximação da PF em MOEAs, incorporaram-se as NDLs a geradores de imigrantes. A validação experimental do Gerador de Diversidade baseado em NDL (NDL-DG) expressa o potencial da abordagem proposta no aumento da qualidade média dos conjuntos de soluções não-dominadas evoluídas. A análise dos resultados da incorporação do NDL-DG ao algoritmo NSGA2 revela a obtenção de soluções de maior qualidade média com significância estatística em 79% dos cenários de otimização dinâmica estudados, em termos do indicador de Hipervolume offline, quando comparado com populações evoluídas sem o uso das NDLs. Em seguida, identificaram-se os cenários de otimização em que o NDL-DG se mostra mais promissor. Finalmente, indicaram-se direções de pesquisa para ampliar o alcance da aplicação das NDLs para outros problemas em aberto na otimização multiobjetivo evolucionária