Use este identificador para citar ou linkar para este item:
https://repositorio.ufms.br/handle/123456789/6812
Tipo: | Outros |
Título: | Uma abordagem alternativa para aplicação do Algoritmo de Colônia de Abelhas Artificial no problema da Mochila Multidimensional Binária. |
Autor(es): | LUIZ EDUARDO BATISTA GARCIA AMANDA AYUMI YAMASHITA |
Primeiro orientador: | BIANCA DE ALMEIDA DANTAS |
Resumo: | Análise de uma abordagem diferente do conceito de "vizinhança de uma solução" a ser aplicado no Algoritmo de Colônia de Abelhas Artificial. |
Abstract: | A mochila multidimensional binária é um problema de otimização muito explorado no âmbito da computação. Mesmo sendo um problema conhecido de maneira abrangente, sua solução não é trivial, uma vez que pertence à classe dos problemas $\mathcal{NP}$-difíceis, isto é, não há um algoritmo que forneça uma solução que possa ser verificada em tempo polinomial. Assim, a fim de buscar soluções aproximadas em menor tempo, faz-se uso das meta-heurísticas. Neste trabalho, utilizou-se a meta-heurística do Algoritmo Colônia de Abelhas Artificiais (ABC - do inglês {\itshape Artificial Bee Colony}). Nesse algoritmo iterativo, a colônia é simplificada em três classes de abelhas: as empregadas, as observadoras e as escoteiras. Durante as iterações, elas procuram a melhor solução alcançável, que se refere à fonte de alimento procurada pela colônia. Com base nessa meta-heurística, desenvolveu-se um algoritmo ABC discreto, visto que a mochila multidimensional é de ordem binária e o ABC foi proposto inicialmente para ser aplicado a problemas contínuos, a fim de tentar alcançar bons resultados para a questão proposta. O algoritmo apresentado foi avaliado com base na resolução de problemas de otimização encontrados na literatura. Os resultados obtidos foram armazenados e processados para realizar comparações quantitativas quanto à aplicabilidade do algoritmo no problema proposto. Para comprovar a eficiência, foram calculados as médias e os desvios-padrões dos resultados, a fim de validá-los. Por fim, pode-se dizer que o algoritmo obteve resultados promissores na maioria dos casos testados, aproximando-se de outras meta-heurísticas aplicáveis existentes. |
Palavras-chave: | meta-heurística otimização combinatória mochila multidimensional binária algoritmo colônia de abelhas |
País: | |
Editor: | Fundação Universidade Federal de Mato Grosso do Sul |
Sigla da Instituição: | UFMS |
Tipo de acesso: | Acesso Aberto |
URI: | https://repositorio.ufms.br/handle/123456789/6812 |
Data do documento: | 2023 |
Aparece nas coleções: | Engenharia de Computação - Bacharelado (FACOM) |
Arquivos associados a este item:
Arquivo | Tamanho | Formato | |
---|---|---|---|
6559.pdf | 219,73 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.