Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP

The travelling salesman problem (TSP) is a NP-hard problem. Techniques as either Branch and Bound or Dynamic Programming supplied the global optimum solution for instances with more than 7000 cities. But, ther needed more than 4 years of CPU time. Fortunately, faster algorithms (simulated annealing,...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bermúdez, Carlos, Minetti, Gabriela F., Alfonso, Hugo, Gallard, Raúl Hector
Formato: Objeto de conferencia
Lenguaje:Español
Publicado: 2001
Materias:
Ciencias Informáticas
TSP
hybridization
multirecombination
tabu search
evolutionary algorithm
Algorithms
ARTIFICIAL INTELLIGENCE
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/23412
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-23412
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
TSP
hybridization
multirecombination
tabu search
evolutionary algorithm
Algorithms
ARTIFICIAL INTELLIGENCE
spellingShingle Ciencias Informáticas
TSP
hybridization
multirecombination
tabu search
evolutionary algorithm
Algorithms
ARTIFICIAL INTELLIGENCE
Bermúdez, Carlos
Minetti, Gabriela F.
Alfonso, Hugo
Gallard, Raúl Hector
Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
topic_facet Ciencias Informáticas
TSP
hybridization
multirecombination
tabu search
evolutionary algorithm
Algorithms
ARTIFICIAL INTELLIGENCE
description The travelling salesman problem (TSP) is a NP-hard problem. Techniques as either Branch and Bound or Dynamic Programming supplied the global optimum solution for instances with more than 7000 cities. But, ther needed more than 4 years of CPU time. Fortunately, faster algorithms (simulated annealing, tabu search, neural networks, and evolutionary computation) exist although they do not guarantee to find the global optimum. Recently an EA based on a operator inver-over [4], provides optimal or near-optimal solutions in a very short time. A latest approach included a variant of inver-over called multi-inver-over [6]. The corresponding results showed advances when compared with other search techniques. This work shows a further enhancement, the Hybrid Multi-inver-over Evolutionary Algorithms (HMEAs), which consists in hybridizing multirecombined evolutionary algorithms with Tabu Search. In these algorithms local search is inserted in different stages of the evolutionary process as in [7 and 8]. They were tested on the hardest set of the test suite chosen in previous works. Details on implementation, experiments and results are discussed.
format Objeto de conferencia
Objeto de conferencia
author Bermúdez, Carlos
Minetti, Gabriela F.
Alfonso, Hugo
Gallard, Raúl Hector
author_facet Bermúdez, Carlos
Minetti, Gabriela F.
Alfonso, Hugo
Gallard, Raúl Hector
author_sort Bermúdez, Carlos
title Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
title_short Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
title_full Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
title_fullStr Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
title_full_unstemmed Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
title_sort hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric tsp
publishDate 2001
url http://sedici.unlp.edu.ar/handle/10915/23412
work_keys_str_mv AT bermudezcarlos hybridizingmultiinveroverevolutionaryalgorithmswithtabusearchforthesymmetrictsp
AT minettigabrielaf hybridizingmultiinveroverevolutionaryalgorithmswithtabusearchforthesymmetrictsp
AT alfonsohugo hybridizingmultiinveroverevolutionaryalgorithmswithtabusearchforthesymmetrictsp
AT gallardraulhector hybridizingmultiinveroverevolutionaryalgorithmswithtabusearchforthesymmetrictsp
bdutipo_str Repositorios
_version_ 1764820465894817792

Ejemplares similares