Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/330855
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Um algoritmo imuno-inspirado para o problema quadrático de alocação
Title Alternative: An immune-inspired algorithm for the quadratic assignment
Author: Oliveira Neto, Luiz Gonzaga de, 1991-
Advisor: Boccato, Levy, 1986-
Abstract: Resumo: O problema quadrático de alocação (QAP, do inglês quadratic assignment problem) é um dos problemas de otimização combinatória mais estudados devido à sua dificuldade inerente e a uma grande gama de aplicações. Instâncias de tamanho médio e grande do QAP já apresentam custos proibitivos para algoritmos exatos, motivando assim o uso de heurísticas. Em particular, sistemas imunológicos artificiais vêm ganhando espaço na última década, especialmente devido a sua capacidade de identificar e manter ótimos locais na população. Neste trabalho, é proposto um algoritmo imuno-inspirado para a solução do QAP. O método, chamado de copt-aiNet[QAP], combina elementos de outros dois algoritmos para otimização combinatória ¿ copt-aiNet e cop-aiNet[C] ¿ e explora novos operadores de busca local e inserção de novos indivíduos. A performance do algoritmo foi analisada em detalhes para diversas instâncias do QAP, e os resultados obtidos mostram que o algoritmo proposto é competitivo em relação à qualidade da melhor solução encontrada, quando comparado com o estado da arte para o QAP, e também do ponto de vista de preservação da diversidade da população

Abstract: The quadratic assignment problem (QAP) is one of the most studied in the combinatorial optimization literature due to its inherent difficulty and wide scope of applications. Medium and large-sized QAP instances are not yet practically solvable to optimality, which motivates the use of heuristic methods. In particular, artificial immune systems have gained space in the last decade, especially in view of their intrinsic capability of simultaneously identifying and maintaining local optima in the population. In this work, we propose an immune-inspired algorithm especially tailored for solving the QAP. The method, named copt-aiNet[QAP], combines elements of two other immune algorithms for combinatorial optimization ¿ copt-aiNet and cob-aiNet[C] ¿ and explores new local search and insertion operators. A detailed performance analysis is carried out considering several instances of the QAP, and the obtained results show that the proposed method is competitive with respect to the best solution found, when compared with state-of-the-art QAP algorithms, and also in preserving the population diversity
Subject: Otimização combinatória
Sistema imunológico
Algoritmos
Language: Português
Editor: [s.n.]
Citation: OLIVEIRA NETO, Luiz Gonzaga de. Um algoritmo imuno-inspirado para o problema quadrático de alocação. 2017. 1 recurso online (69 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/330855>. Acesso em: 2 set. 2018.
Date Issue: 2017
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
OliveiraNeto_LuizGonzagaDe_M.pdf1.36 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.