Incorporação de restrições no processo de busca em algoritmo de inteligência de enxames da família do Fish School Search (FSS)

##plugins.themes.bootstrap3.article.main##

João Paulo Martins Alcântara
Fernando Buarque de Lima Neto
Marcelo Gomes Pereira de Lacerda

Resumo

O processo de otimização consiste em ajustar um conjunto de parâmetros do sistema para obter a melhor saída possível. O ser humano realiza diariamente otimizações nas mais diversas áreas. No entanto, à medida que a complexidade da otimização aumenta, torna-se mais difícil e custoso lidar com esses problemas. Em tais ocasiões, muitas vezes encontrar uma solução ótima já é suficiente, não sendo necessário obter obrigatoriamente a melhor. Quando esse é o caso, técnicas de metaheurísticas (Anupriya Gogna & Akash Tayal, et al., 2013) podem ser utilizadas. Muitos problemas de otimização do mundo real possuem restrições (A. R. Jordehi, et al., 2015). Por exemplo, ao comprar um automóvel, o cliente pode querer escolher um carro de menor preço que atenda à uma certa faixa de potência do motor ou que possua um limite máximo de consumo de combustível. Essas restrições podem ser de desigualdade, onde um uma função pode assumir valores em uma janela de valores, ou de igualdade, onde a função precisa assumir um determinado valor. Geralmente as restrições de igualdade são transformadas em restrições de desigualdade acrescentando-se uma tolerância muito pequena. O Fish School Search (FSS) é um algoritmo de metaheurística baseado em população inspirado no comportamento de peixes que se movimentam à procura de alimento (Bastos & Lima Neto, et al., 2008). Cada localização n-dimensional do peixe representa uma possível solução para o problema de otimização. O processo de busca do FSS consiste em movimentos individuais de cada peixe, movimentos coletivos de todo o cardume, e alimentação. Durante o movimento individual, cada peixe seleciona aleatoriamente uma nova posição para se deslocar e se movimenta apenas se a função objetivo (no exemplo citado da compra do carro, seria o preço) da posição candidata apresentar melhor valor (menor valor para problemas de minimização ou maior valor para problemas de maximização).Em seguida os peixes se alimentam proporcionalmente ao valor de suas funções objetivo. Peixes quese encontram regiões promissoras se alimentam mais, sendo o peso do peixe a medida de sucesso do algoritmo. Por último os peixes se movimentam coletivamente, tendendo a seguir a direção dos peixes mais pesados. Desde que a primeira versão do FSS foi apresentada, várias variações do algoritmoforam desenvolvidas para atacar diferentes tipos de problemas, como otimizações multimodais (Weight-based Fish School Search) e otimizações com vários objetivos (Many Objective Fish School Search). O presente trabalho apresenta uma nova versão do FSS capaz de incorporar restrições ao processo de busca dos melhores parâmetros, denominada de rFSS. Para se tornar apto a resolver problemas com restrições, no início de cada iteração do processo de busca, o algoritmo decide se irá otimizar a função objetivo ou uma função de agregação das restrições. A decisão de qual função otimizar é feita de acordo com a proporção de indivíduos viáveis em relação à população total. Indivíduos viáveis são aqueles que estão em regiões que não infringem nenhuma das restrições definidas para o problema. Isso significa que, se a proporção viável da população for maior do que um limite definido pelo usuário, a busca será realizada otimizando-se a função objetivo, caso contrário utiliza-se a otimização da função de agregação de restrições. O procedimento descrito foi aplicado para dividir o processo de busca em duas fases diferentes e permitir que o algoritmo na: fase 1 - encontre várias regiões viáveis; fase 2 - otimize o valor da função objetivo dentro das regiões viáveis. Com o objetivo de avaliar o algoritmo proposto em problemas com restrições variadas, foram utilizados dois conjuntos de funções de benchmark: um subconjunto do conjunto de funções restritas do CEC 2010 (Mallipeddi, & Suganthan, et al., 2010), que contém restrições moderadas, e um subconjunto do CEC 2020 (Kumar, Wu, Mallipeddi, & Suganthan, et al., 2020), contendo espaços de busca com grandes restrições. O rfSS foi comparado com os melhores algoritmos da competição do CEC 2010 e do CEC 2020 e os resultados mostram que o rFSS é capaz de lidar com problemas de busca com restrições moderadas e alcançar resultados comparáveis a alguns dos melhores algoritmos do estado-da-arte. Entretanto, também foi possível observar que o desempenho do algoritmo cai consideravelmente quando o problema proposto apresenta uma grande quantidade de restrições de igualdade

Downloads

Não há dados estatísticos.

##plugins.themes.bootstrap3.article.details##

Seção
Engenharia da Computação e Sistemas