Algoritmo Colônia de Vaga-lumes Aplicado na Otimização de Funções N-dimensionais

Authors

  • Deylon Carlo Fidelis Couto
  • Carlos Alexandre Silva

DOI:

https://doi.org/10.5540/03.2015.003.02.0109

Keywords:

Algoritmos de Inteligência por Enxame, Otimização, Colônia de Vagalumes. Agradecimentos Agradecemos a Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG) pelo apoio financeiro despendido a esta pesquisa.

Abstract

Neste artigo os autores propõem a aplicação de um algoritmo baseado em inteligência por enxame, mais especificamente o Algoritmo Colônia de Vagalume (ACV), na otimização de funções ndimensionais e multimodais. Algoritmos baseados em inteligência por enxame são bastante estudados na literatura por serem algoritmos eficientes para resolver problemas reais em diversas áreas. A computação bio-inspirada tem crescido bastante nos últimos anos, especialmente nas últimas duas décadas. Muitos dos recém algoritmos bio-inspirados, e em especial os algoritmos baseados em inteligência por enxame, são desconhecidos por uma grande parte de estudantes, professores e profissionais do mercado de trabalho que lidam com otimização. Dentre estes algoritmos pode-se citar: Colônia de Vaga-lume [6], Colônia de Bactérias [5], Otimizador da Formiga-Leão [4], entre outros. A metaheurística ACV tem sido recentemente explorada na otimização de problemas reais tais como: reconfiguração de antenas para telecomunicação [1] e sequenciamento de tarefas [3]. Problemas de otimização podem ser facilmente associados a problemas reais e de relevante impacto social e/ou econômico, como a obtenção de maiores ganhos de um dado investimento ou maior produção de um produto industrial, o que caracterizam problemas de maximização. A obtenção de menores custos para determinar rotas de transporte público ou menores desperdícios no corte de chapas metálicas de uma siderúrgica caracterizam problemas de minimização. Em geral, a modelagem matemática de um problema de otimização tem como ındice de desempenho uma função que é responsável pela qualificação de uma solução. Esta função, chamada de função objetivo, pode ser linear ou não linear, além de admitir uma, duas ou n variáveis. Neste trabalho implementamos a metaheurística ACV para encontrar pontos de máximo ou mınimo de um conjunto de funções ndimensionais e com particularidades como a multimodalidade, ou seja, a função possui várias inflexões de sua superfície caracterizando múltiplos pontos de mınimo ou máximo. As metaheurísticas representam métodos eficientes e alternativos aos métodos exatos, quando estes não são capazes de solucionar o problema de otimização. O funcionamento do ACV baseia-se no comportamento social de vaga-lumes ou pirilampos. Cada espécie de vaga-lume produz um padrão único de lampejos rítmicos. No algoritmo, a intensidade e lampejos da luz estão associados com o valor da função objetivo a ser otimizada. Três importantes características são consideradas na elaboração do programa: (i) os vagalumes são unissex; (ii) a atração entre os vaga-lumes é proporcional à intensidade de sua luz e decresce à medida que a distância aumenta; e (iii) a intensidade do lampejo é determinado pelo valor da função objetivo a ser otimizada. 1deyloncarlo@gmail.com 2carlos.silva@ifmg.edu.br 2 O movimento do vaga-lume i no tempo discreto t, atráıdo pelo vaga-lume j, é dado pela equação (1): xt1i  x t i  β(x t j  xti)  α(rand 0, 5), (1) sendo β o parâmetro de atratividade e α um parâmetro de aleatoriedade. Em [2] é feita uma abordagem completa sobre o desempenho de métodos computacionais, incluindo uma versão de um algoritmo baseado no comportamento dos vaga-lumes (Glowworm Swarm Optimization Algorithm) na otimização de funções ndimensionais e multimodais. Como diferencial a este e demais trabalhos encontrados na literatura, constrúımos um benchmark contendo uma quantidade significativa de funções multimodais de acordo com sua dimensionalidade, e ampliamos a análise estatística sobre a performance do método, como por exemplo analisando a correlação entre os parâmetros de ajuste do método. Os resultados mostram que o ACV apresenta um bom desempenho diante da classe de funções testes utilizadas, além disso há indícios de correlação entre alguns parâmetros do algoritmo. O próximo passo do trabalho é compará-lo com outras metaheurísticas como o algoritmo da alcateia de lobos que se encontra em fase de implementação.

Downloads

Download data is not yet available.

Published

2015-11-18

Issue

Section

Otimização