[en] PSO+: A LINEAR AND NONLINEAR CONSTRAINTS-HANDLING PARTICLE SWARM OPTIMIZATION - MANOELA RABELLO KOHLER (2019)
[pt] O algoritmo de otimização por enxame de partículas (PSO, do inglês Particle Swarm Optimization) é uma meta-heurística baseada em populações de indivíduos na qual os candidatos à solução evoluem através da simulação de um modelo simplificado de adaptação social. Juntando robustez, eficiência e simplicidade, o PSO tem adquirido grande popularidade. São reportadas muitas aplicações bem-sucedidas do PSO nas quais este algoritmo demonstrou ter vantagens sobre outras meta-heurísticas bem estabelecidas baseadas em populações de indivíduos. Algoritmos modificados de PSO já foram propostos para resolver problemas de otimização com restrições de domínio, lineares e não lineares. A grande maioria desses algoritmos utilizam métodos de penalização, que possuem, em geral, inúmeras limitações, como por exemplo: (i) cuidado adicional ao se determinar a penalidade apropriada para cada problema, pois deve-se manter o equilíbrio entre a obtenção de soluções válidas e a busca pelo ótimo; (ii) supõem que todas as soluções devem ser avaliadas. Outros algoritmos que utilizam otimização multi-objetivo para tratar problemas restritos enfrentam o problema de não haver garantia de se encontrar soluções válidas. Os algoritmos PSO propostos até hoje que lidam com restrições, de forma a garantir soluções válidas utilizando operadores de viabilidade de soluções e de forma a não necessitar de avaliação de soluções inválidas, ou somente tratam restrições de domínio controlando a velocidade de deslocamento de partículas no enxame, ou o fazem de forma ineficiente, reinicializando aleatoriamente cada partícula inválida do enxame, o que pode tornar inviável a otimização de determinados problemas. Este trabalho apresenta um novo algoritmo de otimização por enxame de partículas, denominado PSO+, capaz de resolver problemas com restrições lineares e não lineares de forma a solucionar essas deficiências. A modelagem do algoritmo agrega seis diferentes capacidades para resolver problemas de otimização com restrições: (i) redirecionamento aritmético de validade de partículas; (ii) dois enxames de partículas, onde cada enxame tem um papel específico na otimização do problema; (iii) um novo método de atualização de partículas para inserir diversidade no enxame e melhorar a cobertura do espaço de busca, permitindo que a borda do espaço de busca válido seja devidamente explorada – o que é especialmente conveniente quando o problema a ser otimizado envolve restrições ativas no ótimo ou próximas do ótimo; (iv) duas heurísticas de criação da população inicial do enxame com o objetivo de acelerar a inicialização das partículas, facilitar a geração da população inicial válida e garantir diversidade no ponto de partida do processo de otimização; (v) topologia de vizinhança, denominada vizinhança de agrupamento aleatório coordenado para minimizar o problema de convergência prematura da otimização; (vi) módulo de transformação de restrições de igualdade em restrições de desigualdade. O algoritmo foi testado em vinte e quatro funções benchmarks – criadas e propostas em uma competição de algoritmos de otimização –, assim como em um problema real de otimização de alocação de poços em um reservatório de petróleo. Os resultados experimentais mostram que o novo algoritmo é competitivo, uma vez que aumenta a eficiência do PSO e a velocidade de convergência.