International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 7, No. 3, 8 Feb. 2015
Cover page and Table of Contents: PDF (size: 512KB)
Producer-Scrounger Method to Solve Traveling Salesman Problem
Full Text (PDF, 512KB), PP.29-36
Views: 0 Downloads: 0
Author(s)
M. A. H. Akhand
1,*
Pintu Chnadra Shill
1
Forhad Hossain
1
A. B. M. Junaed
1
Kazuyuki Murase
2
Index Terms
Traveling Salesman Problem, Animal Group Living, Swap Sequence, Swap Operator
Abstract
Algorithms inspired from natural phenomena are seem to be efficient to solve various optimization problems. This paper investigates a new technique inspiring from the animal group living behavior to solve traveling salesman problem (TSP), the most popular combinatorial optimization problem. The proposed producer-scrounger method (PSM) models roles and interactions of three types of animal group members: producer, scrounger and dispersed. PSM considers a producer having the best tour, few dispersed members having worse tours and scroungers. In each iteration, the producer scans for better tour, scroungers explore new tours while moving toward producer’s tour; and dispersed members randomly checks new tours. For producer’s scanning, PSM randomly selects a city from the producer’s tour and rearranges its connection with several near cities for better tours. Swap operator and swap sequence based operation is employed in PSM to update a scrounger towards the producer. The proposed PSM has been tested on a large number of benchmark TSPs and outcomes compared to genetic algorithm and ant colony optimization. Experimental results revealed that proposed PSM is a good technique to solve TSP providing the best tours in most of the TSPs.
Cite This Paper
M. A. H. Akhand, Pintu Chnadra Shill, Md. Forhad Hossain, A. B. M. Junaed, K. Murase, "Producer-Scrounger Method to Solve Traveling Salesman Problem", International Journal of Intelligent Systems and Applications(IJISA), vol.7, no.3, pp.29-36, 2015. DOI:10.5815/ijisa.2015.03.04
Reference
[1]D. E. Goldberg, Genetic Algorithms, Addison-wesley, 1998.
[2]D. Whitely, “A genetic algorithm tutorial,” Statistics and Computing 4, pp. 65-85,1994.
[3]J. Brownlee, Clever Algorithms: Nature-Inspired Programming Recipes, 2011.
[4]S. K. Pal, C. S. Rai and A. P. Singh, “Comparative Study of Firefly Algorithm and Particle Swarm Optimization for Noisy Non-Linear Optimization Problems,” International Journal of Intelligent Systems and Applications (IJISA), vol. 4, no. 10, pp. 50-57, 2012.
[5]K. Khan and A. Sahai, “A Glowworm Optimization Method for the Design of Web Services,” International Journal of Intelligent Systems and Applications (IJISA), vol. 4, no. 10, pp. 89-102, 2012.
[6]C. H. V. Raghavendran, G. N. Satish and P. S.Varma, “Intelligent Routing Techniques for Mobile Ad hoc Networks using Swarm Intelligence,” International Journal of Intelligent Systems and Applications (IJISA), vol. 5, no. 1, pp. 81-89, 2013.
[7]E. Bonabeau, M. Dorigo and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, Oxford, 1999.
[8]O. Cordon, F. Herrera, T. Stutzle, “A review on the ant colony optimization metaheuristic: basis, models and new trends”, Mathware and Soft Computing, vol. 9, pp. 141-175, 2002.
[9]R. Eberhart and J. Kennedy, “A New Optimizer Using Particles Swarm Theory”, Roc Sixth International Symposium on Micro Machine and Human Science (Nagoya, Japan) IEEE Service Center, Piscataway, NJ:39-43, 1995.
[10]K. P. Wang, L. Huang, C. G. Zhou, W. Pang. “Particle swarm optimization for traveling salesman problem”, International Conference on Machine Learning and Cybernetics, Xi’an, pp. 1583–1585, 2003.
[11]L. Wong, M. Y. H. Low and C. S. Chong, “A Bee Colony Optimization Algorithm for Traveling Salesman Problem,” Second Asia International Conference on Modeling & Simulation, no. 978-0-7695-3136-6/08, 2008. IEEE DOI 10.1109/AMS.2008
[12]R. Matai, S. P. Singh and M. L. Mittal, “Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches,” Traveling Salesman Problem, Theory and Applications, Edited by D. Davendra, InTech, pp 1-24, 2010.
[13]J. Krause and G. D. Ruxton, Living in Groups. Oxford Series in Ecology and Evolution. Oxford University Press, 2002.
[14]S. He, Q. H. Wu and J. R. Saunders, “A novel group search optimizer inspired by animal Behavioral ecology,” in Proc. 2006 IEEE Congr. Evol. Comput., Vancouver, BC: Sheraton Vancouver Wall Center, pp. 1272–1278, Jul. 2006.
[15]S. He, Q. H. Wu and J. R. Saunders, “Group Search Optimizer: An Optimization Algorithm Inspired by Animal Searching Behavior,” IEEE Transactions On Evolutionary Computation, vol. 13, no 5, pp. 973-990, October 2009.
[16]S. L. Lima and P. A. Zollner, “Towards a behavioral ecology of ecological landscapes”, Trends in Ecology and Evolution,vol. 11, issue 3, pp. 131-135, March 1996.
[17]H. J. Brockmann, C. J. Barnard “Kleptoparasitism in birds”, Animal Behaviour, vol 27, part 2, pp. 487–514, May 1979.
[18]N. G. Blurton Jones, “A selfish origin for human food-sharing: tolerated theft”, Ethology and Sociobiology, vol 5, issue 1, pp. 1-3, 1984.
[19]L. A. Giraldeau and G. Beauchamp, “Food exploitation: Searching for the optimal joining policy”, Trends Ecology & Evolution, vol. 14, no. 3, pp. 102–106, March 1999.
[20]C. W. Clark and M. Mangel, “Foraging and flocking strategies: Information in an uncertain environment,” Amer. Naturalist, vol. 123, pp. 626–641, 1984.
[21]C. J. Barnard and R. M. Sibly, “Producers and scroungers: A general model and its application to captive flocks of house sparrows,”Animal Behavior, vol. 29, pp. 543–550, 1981.
[22]J. W. Bell, “Searching Behavior–The Behavioral Ecology of Finding Resources”, Chapman and Hall Animal Behavior Series. London, U.K.: Chapman and Hall, 1990.
[23]W. L. Vickery, L. G. Deau, J. J. Templeton, D. L. Kramer and C. A. Chapman “Producers, scroungers and group foraging”, The American Naturalist, vol. 137, no. 6, pp. 847-863, June 1991.
[24]TSPLIB - A library of sample instances for the TSP. Available: http://www.iwr.uni-heidelberg.de/groups/ comopt/software/TSPLIB95/tsp.
[25]P. Larrañaga, C. M. H. Kuijpers, R. H. Murga, I. Inza and S. Dizdarevic, “Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators”, Artificial Intelligence Review, vol. 13, no. 2, pp. 129−170, April 1999.