TY - GEN
T1 - Comparison of a memetic algorithm and a tabu search algorithm for the traveling salesman problem
AU - Osaba, Eneko
AU - Diaz, Fernando
PY - 2012
Y1 - 2012
N2 - The traveling salesman problem, or TSP, is one of the most famous and well studied problems in combinatorial optimization. There are many studies with the objective of finding an optimal solution for this problem. These studies have not been successful, since it is considered to be an NP-Hard problem. This means that is not possible to find a method that ensures an optimal solution for all instances of this problem. In this paper we present two techniques to solve this problem, a tabu search based algorithm and a memetic algorithm. The results of both techniques are shown and compared to decide which one of the two alternatives gets better results. Apart from this, several studies are performed to determine certain aspects of the algorithms, such as the crossover function for the memetic algorithm or the size of the tabu list.
AB - The traveling salesman problem, or TSP, is one of the most famous and well studied problems in combinatorial optimization. There are many studies with the objective of finding an optimal solution for this problem. These studies have not been successful, since it is considered to be an NP-Hard problem. This means that is not possible to find a method that ensures an optimal solution for all instances of this problem. In this paper we present two techniques to solve this problem, a tabu search based algorithm and a memetic algorithm. The results of both techniques are shown and compared to decide which one of the two alternatives gets better results. Apart from this, several studies are performed to determine certain aspects of the algorithms, such as the crossover function for the memetic algorithm or the size of the tabu list.
UR - https://www.scopus.com/pages/publications/84872586538
M3 - Conference contribution
AN - SCOPUS:84872586538
SN - 9781467307086
T3 - 2012 Federated Conference on Computer Science and Information Systems, FedCSIS 2012
SP - 131
EP - 136
BT - 2012 Federated Conference on Computer Science and Information Systems, FedCSIS 2012
T2 - 2012 Federated Conference on Computer Science and Information Systems, FedCSIS 2012
Y2 - 9 September 2012 through 12 September 2012
ER -