“Inteligência Artificial: A Nova Fronteira da Ciência Brasileira”
19 a 24 de outubro de 2020
Trabalho 14089
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da computação |
| Setor | Instituto de Ciências Exatas e Tecnológicas - Campus Florestal |
| Conclusão de bolsa | Não |
| Primeiro autor | Daniel Freitas Martins |
| Orientador | MARCUS HENRIQUE SOARES MENDES |
| Título | Simple Binary Firefly Algorithm With Influencers: Uma variação da meta-heurística Firefly Algorithm aplicada à resolução do Problema da Mochila 0-1 |
| Resumo | A meta-heurística Firefly Algorithm, desenvolvida inicialmente para a resolução de problemas contínuos, foi construída tendo como base as características relacionadas à bioluminescência dos vagalumes. As luzes emitidas pelos vagalumes podem servir como um mecanismo de proteção contra possíveis predadores e até mesmo para atrair parceiros para acasalamento ou presas em potencial. De modo a abstrair estes conceitos e representar computacionalmente o comportamento dos vagalumes, algumas considerações foram adotadas: I - Todos os vagalumes podem ser atraídos igualmente por qualquer outro; II - Atratividade é proporcional ao seu brilho, isto é, o vagalume menos brilhante deve se mover em direção ao vagalume com brilho mais intenso; e III - A intensidade do brilho de um vagalume é afetada ou determinada pelo landscape da função objetivo considerada. Neste trabalho é proposto uma variação dessa meta-heurística para a resolução de problemas discretos binários, em especial o Problema da Mochila 0-1. O Problema da Mochila 0-1 é um problema NP-Difícil de otimização combinatória e consiste em, dado um conjunto de itens representados por pares <peso, valor>, determinar quais itens devem ser adquiridos de maneira que a soma dos valores individuais de cada item seja a maior possível, respeitando a restrição do peso total que a mochila pode suportar. O algoritmo proposto neste trabalho, denominado Simple Binary Firefly Algorithm With Influencers (SBFAWI), consiste na divisão da população de vagalumes em dois grupos: um grupo geral e um grupo especial. Os vagalumes do grupo especial são chamados de influencers e possuem pelo menos uma característica especial que os diferenciam do restante do grupo e os tornam uma referência diante da população. Na natureza, tal característica pode estar relacionada à espécie, sexo, tamanho ou idade, por exemplo. Assim, os vagalumes têm 5% a mais de chance de seguirem um influencer do que seguir qualquer outro vagalume. Outras características de SBFAWI incluem o modo de inicialização e o movimento dos influencers: a inicialização leva em consideração a distância de hamming e a razão lucro/peso dos itens do problema; o movimento foi definido de forma que os influencers nunca pioram em termos da função objetivo e da factibilidade. O desempenho do SBFAWI foi avaliado a partir de 14 instâncias de benchmark do Problema da Mochila 0-1. Metade dessas instâncias possuem alta Correlação de Pearson entre os dados de entrada. Uma instância com uma alta correlação de dados indica que ela é mais difícil de se resolver, uma vez que a troca de itens próximos é dificultada. A menor instância utilizada teve um total de 4 itens, enquanto que a maior delas teve 200 itens. O algoritmo proposto se mostrou capaz de resolver este tipo de problema em tempo razoável, alcançando o ótimo em todas as execuções para todas as instâncias. Futuramente pretende-se reduzir o custo computacional exigido pelo algoritmo e aplicá-lo a um problema real. |
| Palavras-chave | Firefly Algorithm, Problema da Mochila 0-1, Otimização Combinatória |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|