Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T22:52:02Z (GMT). No. of bitstreams: 1
Pureza_VitoriaM.M_D.pdf: 9869285 bytes, checksum: 3d30f5f94e19c47fb41416cb14190a97 (MD5)
Previous issue date: 1996 / Resumo: A Busca Tabu é um procedimento heurístico de orientação da busca com vistas à obtenção de boas soluções em problemas de dificil tratamento. Fundamentalmente, ela é caracterizada por mecanismos que promovem a superação da otimalidade local. Esses mecanismos geralmente tomam a forma de parâmetros que impõem restrições à seleção de movimentos. Como a calibragem desses elementos restritivos tem um impacto fundamental no desempenho do algoritmo, algumas implementações utilizam estratégias que provocam alterações sistemáticas nos valores de determinados parâmetros. Estas estratégias procuram intensificar a exploração de regiões promissoras e o abandono de regiões onde possibilidades de melhoria parecem mínimas. As alterações nos valores dos parâmetros são normalmente acionadas por fases de busca caracterizadas pela ausência de movimentos de atualização da solução incumbente. O objetivo principal deste trabalho é o de propor uma nova abordagem adaptativa de metaheurísticas Tabu. A abordagem HTA, aqui considerada, propõe que a alteração de parâmetros seja determinada a partir da identificação de padrões da trajetória de busca recentemente traçada. Estes padrões fornecem indicações, ainda que limitadas, acerca da topologia do espaço de soluções. Para cada padrão, são aplicadas perturbações nos valores de parâmetros tabu selecionados, como forma de adaptar a busca às diferentes condições encontradas. A abordagem HTA foi desenvolvida a partir de extensos experimentos com o Problema do Caixeiro Viajante Simétrico e Euclideano (PCV). Testes envolveram 12 instâncias clássicas e verificaram ganhos significativos em relação à versão não-adaptativa, mesmo sob condições operacionais estressantes impostas por parâmetros mantidos fora de controle. A seguir, a mesma abordagem foi aplicada ao Problema de Roteamento de Veículos (PRV). Neste trabalho, apresentamos os resultados obtidos com 14 instâncias clássicas caracterizadas por diferentes restrições. Os resultados foram comparados com os de três algoritmos altamente competitivos e indicaram que HTA produz soluções de qualidade comparável aos demais. São também apresentados os resultados obtidos com uma implementação adaptativa HTA para o Problema de Agrupamento Capacitado (PAC). Os resultados, mais uma vez, sugerem que a introdução de mecanismos adaptativos baseados em padrões da trajetória da busca é uma estratégia robusta e promissora / Abstract: Tabu Search (TS) is a general heuristic procedure for guiding search to obtain good solutions in complex solution spaces. Fundamentally, it is characterized by mechanisms that allow the exploration of the solution space beyond local optimality. These mechanisms are generally implemented by means of parameters which impose restrictions to move selection. Since the calibration of such restrictive elements has a major impact on the algorithm's performance, some implementations use strategies for altering the values of these parameters whenever non-improving search phases are verified. Essentially, these strategies seek to intensify the exploration of promising regions of the solution space, and to abandon the search in regions where improvement possibilities seem to be minimal. The main purpose ofthis work is to propose a new adaptive Tabu metaheuristic approach. The HTA approach, considered here, assumes that the alteration of the parameters values should be defined first by identifying specific pattems in the search trajectory recently described. These pattems provide indications of the solution space topology. For each pattem, perturbation on the values of selected tabu parameters is applied, as means to adapt the search to the different conditions found. The HTA approach was developed from extensive experiments with the Symmetric and Euclidean Traveling Salesman Problem (TSP). Tests involved 12 benchmark instances and verified improvements with respect to a non-adaptive implementation, even under stressing operational conditions provided by free-Junning parameters. HTA was also applied to the Vehicle Routing Problem (VRP). We present the results obtained for 14 benchmark instances characterized by different restrictions. Our adaptive implementation is compared to three highly competitive algorithms. The results indicate that HTA is able to provide solution quality levels comparable to the other algorithms. We also present the results provided by an HTA implementation for the Capacitated Clustering Problem (CCP). They also suggest that introducing adaptive mechanisms based on the pattems of search trajectories is a robust and promising strategy / Doutorado / Doutor em Engenharia Elétrica
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/261048 |
| Date | 17 December 1996 |
| Creators | Pureza, Vitoria M. M |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, França, Paulo Morelato, 1949- |
| Publisher | [s.n.], Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e de Computação, Programa de Pós-Graduação em Engenharia Elétrica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 115f. : il., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0028 seconds