- Title
- Comparing a hybrid branch and bound algorithm with evolutionary computation methods, local search and their hybrids on the TSP
- Creator
- Jiang, Yan; Weise, Thomas; Lässig, Jörg; Chiong, Raymond; Athauda, Rukshan
- Relation
- 2014 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS 2014). Proceedings of 2014 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (Orlando, FL 9-12 December, 2014) p. 148-155
- Publisher Link
- http://dx.doi.org/10.1109/CIPLS.2014.7007174
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2014
- Description
- Benchmarking is one of the most important ways to investigate the performance of metaheuristic optimization algorithms. Yet, most experimental algorithm evaluations in the literature limit themselves to simple statistics for comparing end results. Furthermore, comparisons between algorithms from different 'families' are rare. In this study, we use the TSP Suite - an open source software framework - to investigate the performance of the Branch and Bound (BB) algorithm for the Traveling Salesman Problem (TSP). We compare this BB algorithm to an Evolutionary Algorithm (EA), an Ant Colony Optimization (ACO) approach, as well as three different Local Search (LS) algorithms. Our comparisons are based on a variety of different performance measures and statistics computed over the entire optimization process. The experimental results show that the BB algorithm performs well on very small TSP instances, but is not a good choice for any medium to large-scale problem instances. Subsequently, we investigate whether hybridizing BB with LS would give rise to similar positive results like the hybrid versions of EA and ACO have. This turns out to be true - the 'Memetic' BB algorithms are able to improve the performance of pure BB algorithms significantly. It is worth pointing out that, while the results presented in this paper are consistent with previous findings in the literature, our results have been obtained through a much more comprehensive and solid experimental procedure.
- Subject
- ant colony optimisation; evolutionary computation; software algorithms; public domain software; search problems; travelling salesman problems; tree searching; algorithm design and analysis; benchmark testing; complexity theory; optimization
- Identifier
- http://hdl.handle.net/1959.13/1067839
- Identifier
- uon:18495
- Identifier
- ISBN:9781479945016
- Language
- eng
- Reviewed
- Hits: 2974
- Visitors: 2938
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|