Otimização por Enxame de Partículas Discretas Baseada em Conjunto e Decomposição para Problemas Combinatórios Multiobjetivos Baseados em Permutação

Este artigo estuda uma classe específica de problemas de otimização combinatória multiobjetivos (MOCOPs), a saber, os MOCOPs baseados em permutação. Muitos MOCOPs comumente vistos, por exemplo, o problema do vendedor viajante multiobjetivo (MOTSP) e o problema de agendamento de projetos multiobjetivos (MOPSP), pertencem a essa classe de problemas e podem ser muito diferentes. No entanto, como os MOCOPs baseados em permutação compartilham a semelhança inerente de que a estrutura de seu espaço de busca geralmente tem a forma de uma árvore de permutação, este artigo propõe uma metodologia genérica de otimização por enxame de partículas baseada em conjunto e decomposição, denominada MS-PSO/D. Para coordenar com a propriedade dos MOCOPs baseados em permutação, o MS-PSO/D utiliza uma representação baseada em elementos e uma abordagem construtiva. Através disso, soluções viáveis sob restrições podem ser geradas passo a passo seguindo a estrutura em forma de árvore de permutação. E informações heurísticas relacionadas ao problema são introduzidas na abordagem construtiva para eficiência. Para abordar as questões de otimização multiobjetiva, a estratégia de decomposição é empregada, na qual o problema é convertido em múltiplos subproblemas de objetivo único de acordo com um conjunto de vetores de peso. Além disso, um mecanismo flexível para controle de diversidade é fornecido no MS-PSO/D. Extensos experimentos foram realizados para estudar o MS-PSO/D em dois MOCOPs baseados em permutação, a saber, o MOTSP e o MOPSP. Resultados experimentais validam que a metodologia proposta é promissora.