Estratégias para Resolução de Problemas de Otimização com Muitos Objetivos: Um Estudo de Caso Aplicado a um Serviço de Transporte Reativo a Demanda
Otimização Multiobjetivo, Dial-a-Ride Problem, Algoritmos Evolutivos, Aná- lise do Fitness Landscape
Diversos problemas encontrados na ciência, engenharia, indústria, entre outros domínios do conhecimento, envolvem a otimização simultânea de dois ou mais objetivos frequen- temente conflitantes. Problemas com tal característica são conhecidos na literatura como Problemas de Otimização Multiobjetivo. Devido a existência de um certo nível de conflito entre os objetivos otimizados, para esta classe de problemas, não existe uma única solução ótima (global) como em problemas mono-objetivo, em vez disso produzem um conjunto de soluções que representam os possíveis trade-offs entre os objetivos. Geralmente, na otimização multiobjetivo, a relação de dominância Pareto é adotada para comparar soluções. Desta forma, as soluções ótimas para o problema são chamadas de soluções Pareto-Ótimo e a imagem deste conjunto no espaço de objetivo é intitulada fronteira Pareto-Ótimo. Ao longo dos últimos anos, pesquisas tanto experimentais quanto teóricas têm indicado que usualmente o aumento no número de objetivos otimizados promove novos e complexos desafios. Como por exemplo, o crescimento da proporção de soluções não-dominadas, o aumento exponencial do número de soluções necessárias para obtenção de uma completa aproximação da fronteira Pareto-Ótimo, ineficácia das técnicas tradicionais de visualização das soluções, dificuldade em garantir a manutenção da diversidade populacional, entre outros. Entretanto, é de conhecimento que um problema multiobjetivo não se torna necessa- riamente mais difícil quando novos objetivos são acrescentados. Outras propriedades do problema também podem contribuir no aumento de sua complexidade, como por exemplo as características dos problemas teste utilizados. Além disso, problemas combinatórios não têm recebido tanto atenção quanto problemas contínuos, portanto, ainda é uma área de pesquisa com questões a serem exploradas. Neste contexto, este trabalho tem como obje- tivo promover um melhor entendimento dos problemas combinatórios com muitos objetivos e propor estratégias de busca fundamentadas pelas propriedades de cada problema. Para esta finalidade foram realizadas duas análises utilizando uma formulação do Dial-a-Ride Problem (DARP) com muitos objetivos. Inicialmente, uma análise do fitness landscape foi realizada para prover um melhor entendimento sobre a geometria do problema e auxiliar na identificação de relacionamentos entre os objetivos. Posteriormente, uma análise de desem- penho envolvendo alguns dos principais algoritmos evolutivos multiobjetivo foi conduzida. Os resultados de ambas análises mostraram que para uma mesma formulação do problema, diferentes observações podem ser feitas tanto sobre as característica do problema quanto sobre o comportamento dos algoritmos quando utilizado diferentes conjuntos de teste. Por fim, estratégias de busca foram propostas com o objetivo de lidar com o acréscimo no número de objetivos, assim como outras propriedades associadas ao problema.