Melhoria do algoritmo de colônia artificial de abelhas para problemas binários

Resumo

A natureza tem sido fonte de inspiração para vários algoritmos no ramo da Computação Natural (CN). Esses algoritmos se inspiram em comportamentos sociais de indivíduos pertencentes a sociedades presentes na natureza como por exemplo o algoritmo de Otimização por Enxame de Partículas (PSO) que se inspira no comportamento de enxame de pássaros e cardumes (KENNEDY, 1995), o algoritmo de Colônia Artificial de Abelhas (ABC) que foi inspirado no comportamento das abelhas dentro de uma colônia (MARJAN, 2015), etc. Por possuírem alta capacidade de exploração e refinamento de solução, esses algoritmos vêm sendo aplicado em problemas de otimização em diversas áreas. Embora grande parte desses algoritmos tenha sido criado para problemas de otimização contínuo, a aplicação ou criação desses algoritmos em problemas de natureza binária também é encontrado na literatura. Neste trabalho é apresentada uma proposta de melhoria do ABC visando aplicações em problemas de natureza binária chamado NBABC. Na versão proposta, ao invés de fazer um mapeamento das posições das abelhas em um espaço contínuo para o binário, as posições das abelhas e as operações sobre elas são feitas no espaço binário. Além disso, para evitar a convergência prematura, foi definido um limite de máximo de dimensões que a abelha pode mudar para gerar uma nova posição. Para analisar o desempenho do algoritmo proposto, foram implementados os seguintes algoritmos binários: BFSS, BPSO, BGA, BCSO, BABC, XBABC, BitABC e GBABC. Como funções de teste foram escolhidas a Chuang F1 e a função 0/1 Knapsack, ambas com 100, 500, 800 e 1000 dimensões. Cada experimento foi executado 30 vezes usando como critério de parada 3000 avaliações de fitness e uma população de 30 indivíduos. Os resultados obtidos para a função Chuang F1 mostram que o NBABC só teve resultados inferiores ao GBABC e o BFSS em 100 dimensões. Nesse caso os valores foram 96,733 ±1,788, 98,033 ±0,407 e 100,0 ±0,0 respectivamente. Entretanto, para 600, 800 e 1000 dimensões, ele foi superior a todos os algoritmos analisados. Resultados ainda mais promissores foram obtidos com a função 0/1 Knapsack, na qual o algoritmo proposto obteve resultados superiores que os demais algoritmos em todas as dimensões. Além disso, o teste não-paramétrico de Wilcoxon foi aplicado nas amostras do NBABC e dos demais algoritmos e mostrou que existe diferença entre elas com intervalo de confiança de 95%.