Saturday , August 18 2018

A Hybrid Particle Swarm Optimization – Simulated Annealing Algorithm for the Probabilistic Travelling Salesman Problem

Guillermo CABRERA G.1, Silvana RONCAGLIOLO D.1, Juan P. RIQUELME1, Claudio CUBILLOS1, Ricardo SOTO1,2
1 Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso,
Av. Brasil 2241, Chile

2 Universidad Autónoma de Chile,
Pedro de Valdivia 641, Santiago, Chile

Abstract: The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the well known Traveling Salesman Problem (TSP). This problem arises when the information about customers demand is not available at the moment of the tour generation and/or the tour re-calculating cost is too elevated. In this article, a Hybrid Algorithm combining Particle Swarm Optimization (PSO) and Simulated Annealing (SA) is proposed, in order to solve the PTSP. The PSO heuristic offers a simple structured algorithm which supplies a high level of exploration and fast convergence, compared with other evolutionary algorithms. The SA algorithm is used to improve the particle diversity and to avoid the algorithm being trapped into local optimum. Two well-known benchmarks of the literature are used and the proposed PSO-SA algorithm obtains acceptable results. In fact, the hybrid algorithm improves the performance of simple PSO algorithm for all instances.

Keywords: Hybrid Algorithm, Metaheuristics, Routing Problems, Stochastic Optimization, Swarm Intelligence.

>>Full text
CITE THIS PAPER AS:
Guillermo G. CABRERA, Silvana D. RONCAGLIOLO, Juan P. RIQUELME, Claudio CUBILLOS, Ricardo SOTO, A Hybrid Particle Swarm Optimization – Simulated Annealing Algorithm for the Probabilistic Travelling Salesman Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 21 (1), pp. 49-58, 2012.

1. Introduction and Literature Review

The Travelling Salesman Problem (TSP) has several different variations. One of them is the stochastic variant called Probabilistic Traveling Salesman Problem (PTSP), which can be classified as a Stochastic Combinatorial Optimization Problem (SCOP). PTSP was proposed by Jaillet [19] and several authors have solved this model using different approaches. In [19] the PTSP is described as follows: Consider a set of n points which must be visited with probability p. On any given instance of the problem only a subset consisting of k out of the n points (0<k<n) have to be visited. The k number is determined according to a known probability distribution (such as the binomial). An a priori tour through all n points has to be found. Each point must be included only once in the a priori tour. On any given instance of the problem, the present k points will then be visited in the same order as they appear in the a priori tour. The PTSP is usually tackled by an a priori optimization phase [4] which comprises two stages: First, as said above, an a priori solution is found. In the second stage, the a posteriori solution is derived from the a priori solution. For a posteriori solution, the edges are visited in the same order as in the a priori solution, but excluding the edges that do not require to be visited. Fig. 1 shows both different a priori and a posteriori tours. In the example only odd edges are visited in the a posteriori tour. The problem of finding such an a priori tour which is of minimum length in the expected value sense is defined as a PTSP.

fig1art6-2012-1-6

Figure 1. a) A priori tour for 16 edges. (b) A posteriori tour after a realization.

The problem appears when the information about customers demand is not available at the moment of tour generation and/or the tour re-calculating cost is too elevated. In [19] the proposed model was solved by a well-known “hill climbing” algorithm. hereafter, several authors have used different stochastic approaches in order to solve this optimization problem, e.g., in [5, 6] the authors solved the homogeneous PTSP using an Ant Colony Optimization (ACO) approach. In there, a variation of traditional ACO algorithm, called probabilistic Ant Colony System (pACS), raised very good solution for the PTSP, being as one of the more efficient strategies for stochastic routing problems. The most important difference between pACS and ACS is the set of arcs on which the pheromone is globally increased. One of the main conclusions of these works is that the pACS algorithm is very competitive when the probabilities of the cities are far from 1. In this case (probabilities close to 1) the well-known ACS algorithm raised better solutions than pACS. In [26] the Expanding Neighborhood Search (ENS) is proposed for the resolution of the PTSP. The ENS is a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP) which obtained a very good solution for a theoretical dataset. In [25] the author proposed a set of initial solution generators under a genetic algorithm (GA) framework for solving the PTSP. These three initial solution generators allow the GA to reduce computational time without decreasing the quality of the best reached solution. In [2, 3], the authors present an Estimation-Based algorithm involving local search strategies. In both, the authors experiment with different metaheuristics applying an estimation-based customization strategy, to evaluate the solution cost of different PTSP instances, obtaining excellent results. In [27] an hybrid algorithm – nature inspired – based on PSO, GRASP and ENS strategy is proposed, for a solution of the PTSP. The GRASP and ENS strategies are used in order to improve the quality of initial solutions for the PSO algorithm, which have as main characteristic the use of multiple swarms, reducing considerably the required computational time.

Finally, in [1] the authors describe a variant of particle swarm, called hybrid swarms, that incorporates an explicit selection mechanism similar to that used in more traditional evolutionary computations. The main author’s conclusion is that the addition of selection supplies some advantage to particle swarm on certain functions.

The main contribution of this article is the application of an hybrid technique on a SCOP, using a simple but effective sort algorithm which improves considerably the solution reached by the hybrid algorithm in a reasonable computational time.

REFERENCES:

  1. ANGELINE, P. J., Using Selection to Improve Particle Swarm Optimization. IEEE Int. Conf. on Computational Intelligence (ICEC’98), 1998, pp. 84-89.
  2. BALAPRAKASH, P., M. BIRATTARI, T. Stützle, M. Dorigo, Estimation-based Metaheuristics for the Probabilistic Traveling Salesman Problem. Computers & Operations Research, vol. 37, no. 11, 2010, pp. 1939-1951.
  1. BALAPRAKASH, P., M. BIRATTARI, T. STÜTZLE, Z. YUAN, M. DORIGO, Estimation-based Ant Colony Optimization and Local Search for the Probabilistic Traveling Salesman Problem. Swarm Intelligence, vol 3, 2009, pp. 223-242.
  2. BERTSIMAS, D., P. JAILLET, A. ODONI, A Priori Optimization. Operations Research, vol. 38, no. 6, 1990, pp. 1019-33.
  3. BIANCHI, L., L. M. GAMBARDELLA, M. DORIGO, Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic. Ant Algorithms (ANTS’02) LNCS vol. 2463, 2002, pp. 176-187.
  4. BIANCHI, L., L. M. GAMBARDELLA, M. DORIGO, An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem. International Conference on Parallel Problem Solving from Nature (PPSN’02), 2002, pp. 883-892.
  5. BOWLER, N. E., T. M. A. FINK, R.C. BALL, Characterization of the Probabilistic Traveling Salesman Problem. Physical Review part E, vol. 68, 2003, pp. 36703-36710.
  6. BRANKE, J., M. GUNTSCH, Solving the Probabilistic TSP with Ant Colony Optimization. J. of Mathl. Modelling and Algorithms, vol. 3, 2004, pp. 403-425.
  7. CEMY, V., Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm, Journal of Optimisation Theory and Applications, vol. 45, 1985, pp. 41-51.
  8. EBERHART, R. C., R. W. DOBBINS, P. SIMPSON, Computational Intelligence PC Tools. Boston: Academic Press. ISBN: 0-12-228630-8. 1996.
  9. EBERHART, R.C., J. KENNEDY, A New Optimizer Using Particle Swarm Theory. Proceedings Sixth International Symposium on Micro Machine and Human Science (MHS’95), 1995, pp. 39-43.
  10. EGLESE, R. W., Simulated Annealing: A Tool for Operational Research. European Journal of Operational Research, vol. 46, 1990, pp. 271-281.
  11. DURÁN O., N. RODRIGUEZ, L. CONSALTER, Collaborative Particle Swarm Optimization with a Data Mining Technique for Manufacturing Cell Design. Expert Systems with Applications, vol. 37, 2010, pp. 1563-1567
  12. FANG, L., P. CHEN, S. LIU., Particle Swarm Optimization with Simulated Annealing for TSP. Proc. of the 6th Intl. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases, (WSEAS ’07), 2007, pp. 206-210.
  13. FAN, X., X. FANG, On Optimal Decision for QoS-Aware Composite Service Selection. Information Technology Journal, vol. 9, no. 6, 2010, pp. 1207-1211
  14. XIA, Y., G. ZHANG, S. NIE, Y. BU, Z. ZHANG, Optimal Control of Cobalt Crust Seabed Mining Parameters Based on Simulated Annealing Genetic Algorithm. Journal of Central South University of Technology, vol. 18, no. 3, pp. 650-657
  15. HENDERSON, D., S. H. JACOBSON, A. W. JOHNSON, The Theory and Practice of Simulated Annealing. Handbook on Metaheuristics, F. Glover and G. Kochenberger, Editors, Kluwer Academic Publishers, Norwell MA: 287-320. ISBN: 1-4020-7263-5. 2003.
  16. INGBER, L., Simulated Annealing: Practice Versus Theory. Mathl. Comput. Modelling, vol. 18, no. 11, 1993, pp. 29-57.
  17. JAILLET, P., A Priori Solution of a Traveling Salesman Problem in which a Random Subset of the Customers are Visited. Operations Research, vol. 36, no. 6, 1988, pp. 929-936.
  18. KENNEDY, J., R. C. EBERHART, Particle Swarm Optimization. Proc. of the IEEE Intl. Conf. on Neural Networks, vol. 4, 1995, pp. 1942-1948.
  19. KENNEDY, J., R. C. EBERHART, Y. SHI, Swarm Intelligence. The Morgan Kaufmann Series in Artificial Intelligence, Morgan Kaufmann, San Francisco-California. 2001.
  20. KENNEDY, J., The particle swarm: social adaptation of knowledge. Proc. IEEE Intl. Conf. on Evolutionary Computation (CEC’97), 1997, pp. 303-308.
  21. KIRKPATRICK, S., C. D. GELATT, M. P. VECCHI, Optimization by simulated annealing, Science, vol. 220, 1983, pp. 671-680.
  22. KULIC, F., D. MATIC, B. DUMNIC, V. VASIC, Optimal Fuzzy Controller Tuned by TV-PSO for Induction Motor Speed Control. Advances in Electrical and Computer Engineering, vol. 11, no.1, 2011, pp. 49-54.
  23. LIU, Y., Different Initial Solution Generators in Genetic Algorithms for Solving the Probabilistic Traveling Salesman Problem. Applied Mathematics and Computation, vol. 216, no. 1, 2010, pp. 125-137.
  24. MARINAKIS, Y., A. MIGDALAS, P. M. PARDALOS, Expanding Neighborhood search-GRASP for the Probabilistic Traveling Salesman Problem. Optimization Letters, vol. 2, no. 3, 2008, pp. 351-361.
  25. MARINAKIS, Y., M. MARINAKI, A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman Problem. Computers & Operations Research, vol. 37, no. 3, 2010, pp. 432-442.
  26. METROPOLIS, N., A. ROSENBLUTH, M. ROSENBLUTH, A. TELLER, E. TELLER, Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, vol. 21, 1953, pp. 1087-1092.
  27. NIKNAM, T., An Approach Based on Particle Swarm Optimization for Optimal Operation of Distribution Network Considering Distributed Generators. IEEE 32nd Annual Conf. on Industrial Electronics (IECON’ 06), 2006, pp. 633-637.
  28. NIKNAM, T., J. OLAMAEI, B. AMIRI, A Hybrid Evolutionary Algorithm Based on ACO and SA for Cluster Analysis. Journal of Applied Sciences, vol. 8, 2008, pp. 2695-2702.
  29. RAHMANI, K., M. MOLAVI, B. NADERI, M. SOLTANI, A Hybridization of Simulated Annealing and Electromagnetic Algorithms for Flowshop Problems with Skipping Probability. Journal of Applied Sciences, vol. 9, 2009, pp. 2438-2444.
  30. SAADI , M. BETTAYEB, A. GUESSOUM, Optimal Approach for Neutron Images Restoration using Particle Swarm Optimization Algorithm with Regularization. Journal of Applied Science, vol. 10, no. 7, 2010, pp. 517-525.
  31. SHI, X. H., Y. C. LIANG, H. P. LEE, C. LU, Q. X. WANG, Particle Swarm Optimization-based Algorithms for TSP and Generalized TSP. Information Processing Letters, vol. 103, 2007, pp. 169-176.
  32. SHI, Y., R. C. EBERHART, Empirical Study of Particle Swarm Optimization. Proc. of the IEEE Congress on Evolutionary Computation (CEC’99), 1999, pp. 1945-1950.
  33. WANG, Q., L. XIONG, H. LIU, J. LIANG, Improved PSO for TSP based on the Information Communication and Dynamic Work Allocation. Asian Journal of Information Technology, vol. 5, no.11, 2006, pp. 1191-119.
  34. BOUKEF, H., M. BENREJEB, P. BORNE, Flexible Job-shop Scheduling Problems Resolution Inspired from Particle Swarm Optimization. Studies in Informatics and Control, vol 17, no. 3, 2008, pp. 241-252.
  35. TSPLIB:http://www2.iwr.uni-heidelberg.de /groups/comopt/software/TSPLIB95/index.html, 2011

https://doi.org/10.24846/v21i1y201206