Meta-Heurísticas em Pesquisa Operacional – Capítulo 24

  • Título: Um Estudo Comparativo de Algoritmos Genéticos e Beam Search para o Problema de Alocação de Células de Telefonia Celular
  • Autores: Anibal Tavares de Azevedo e Cassilda Maria Ribeiro
  • DOI:10.7436/2013.mhpo.24
  • Resumo: Este capítulo apresenta o problema de atribuição de células às centrais de telefonia móvel. Este problema é conhecido como um problema de otimização NP-completo. Isto significa que ainda não se encontrou um método de otimização exato que seja capaz de encontrar a solução ótima do problema num tempo computacional razoável. Uma alternativa para a solução deste tipo de problema é a utilização de métodos heurísticos, pois eles permitem que se encontre uma solução de boa qualidade num tempo computacional bastante satisfatório. Três heurísticas são apresentadas para resolver este problema, sendo duas baseadas em Algoritmos Genéticos e uma relacionada ao Beam Search. Os resultados mostram a qualidade das soluções produzidas por cada método tanto em termos numéricos como através de uma análise gráfica da alocação de células para cada central. É observado o  melhor desempenho do Beam Search devido a capacidade deste método em lidar com problemas cujas soluções devem atender muitas restrições.
  • Palavras-chave: Rede de telefonia celular, Otimização combinatória, Beam search, Algoritmo genético.
  • Abstract: This chapter presents the optimization problem of cell assignment to switches in a cellular mobile network. This optimization problem is known to be NP-Complete. It means, until now, it can not be solved by exact optimization algorithms, so the alternative is the heuristic methods, which can practically lead to good feasible solutions to problems of a certain size in a satisfactory computational time. Three heuristics are presented to solve these problems such that two of them are based on Genetic Algorithms and one is the Beam Search. It is also presented the solutions for each approach in terms of numerical and visualization of the cellular allocation for each central. We observed that the Beam Search Method always produces the best solutions. A possible explanation is the fact that the Beam Search Method is especially designed to deal with severely constrained problems.
  • Keywords: Cellular mobile network, Combinatorial optimization, Beam search, Genetic algorithm.
PDF do capítulo (1,927 MB):
BIBTEX do capítulo:

 

Os comentários estão encerrados.