Heurística híbrida para o problema de localização de regeneradores

Com o crescente utilização da Internet, novas tecnologias precisaram ser desenvolvidas para atender a essa demanda. A fibra ótica surge como uma solução, pois possui capacidade de banda superior às tecnologias antecessoras. Entretanto, o sinal ótico perde confiabilidade ao percorrer grandes distâncias, de forma que é necessário posicionar regeneradores de sinal para garantir a qualidade de comunicação. Como esses regeneradores são equipamentos caros, é necessário minimizar sua quantidade. Portanto, o Problema de Localização de Regeneradores (PLR) visa posicionar o menor número possível de regeneradores em uma rede de forma que todos possam se comunicar com confiabilidade. Metaheurísticas são técnicas que têm como objetivo obter soluções de boa qualidade em tempo computacional viável para problemas difíceis da ciência da computação e otimização matemática, os quais algoritmos exatos não conseguem resolver eficientemente. Uma tendência na área de otimização é a hibridização de metaheurísticas, que tem como objetivo utilizar técnicas de outras áreas para ajuda-las a obter resultados melhores. Como exemplo, podemos citar o DM-GRASP e MDM-GRASP, hibridizações do GRASP com técnicas de mineração de dados. Sendo o PLR um problema NP-Difícil, metaheurísticas são úteis para obtenção de boas soluções em tempos computacionais viáveis. O presente trabalho tem como objetivo construir uma versão do MDM-GRASP para o PLR e estudar o impacto da hibridização nos resultados. A inserção de padrões antes da construção, que é como comumente o processo ocorre, não levou a bons resultados. Dessa forma são propostas formas alternativas para inserir o padrão na solução. Essas técnicas se mostraram eficientes e conseguiram melhorar o GRASP tanto em relação a qualidade da solução como reduzindo seu tempo de execução.With the increasing use of the Internet, new technologies needed to be developed to meet this demand. Optical fiber comes as a solution, as it has superior bandwidth capacity to its predecessors. However, the optical signal looses reliability when traveling long distances, so it is necessary to position signal regenerators to assure communication. Since these regenerators are expensive equipments, it is necessary to minimize their quantity. Therefore, the Regenerator Location Problem (RLP) aims to position as few regenerators as possible in a network so that everyone can communicate reliably. Metaheuristics are techniques that aim to obtain good quality solutions in feasible computational time for difficult problems in computer science and mathematical optimi- zation, which exact algorithms can not solve efficiently. A trend in the area of optimization is the hybridization of metaheuristics, which aims to use techniques from other area to help them achieve better results. As an example, we can mention the DM-GRASP and MDM-GRASP, which are GRASP hybridizations with data mining techniques. Since RLP is an NP-Difficult problem, metaheuristics are useful for obtaining good solutions in feasible computional time. The present work aims to build a version of MDM-GRASP for PLR and to study the impact of hybridization on the results. The insertion of patterns before construction, which is how the process commonly occurs, did not lead to good results. So two alternative ways are proposed to insert the pattern into the solution. These new techniques proved to be efficient and improved GRASP both in terms of solution quality as reducing execution time.38 p