A New Heuristic for Improving the Performance of Genetic Algorithm

Authors: Warattapop Chainate, Peeraya Thapatsuwan, Pupong Pongcharoen

Abstract:

The hybridisation of genetic algorithm with heuristics has been shown to be one of an effective way to improve its performance. In this work, genetic algorithm hybridised with four heuristics including a new heuristic called neighbourhood improvement were investigated through the classical travelling salesman problem. The experimental results showed that the proposed heuristic outperformed other heuristics both in terms of quality of the results obtained and the computational time.

Keywords: Genetic Algorithm, Hybridisation, Metaheuristics, Travelling Salesman Problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1083721

References:

[1] A. Syarif, Y. Yun, and M. Gen, "Study on multistage logistic chain network: a spanning tree-based genetic algorithm approach," Computer & Industrial Engineering, vol. 43, no. 1-2, pp. 299-314, 2002.
[2] D. E. Goldberg, Genetic Algorithms in Search, Optimisation and Machine Learning. Massachusetts: Addison-Wesley, 1989.
[3] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design. New York: John Wiley and Sons, 1997.
[4] H. Aytug, M. Khouja, and F. E. Vergara, "Use of genetic algorithm to solve production and operation management problems: a review," International Journal of Production Research, vol. 41, no. 17, pp. 3955-4009, 2003.
[5] S. S. Chaudhry and W. Luo, "Application of genetic algorithms in production and operation management: a review," International Journal of Production Research, vol. 43, no. 19, pp. 4083-4101, 2005.
[6] P. Pongcharoen, C. Hicks, P. M. Braiden, and D. J. Stewardson, "Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products," International Journal of Production Economics, vol. 78, no. 3, pp. 311-322, 2002.
[7] T. Yamada and C. R. Reeves, "Solving the Csum permutation flowshop scheduling problem by genetic local search," in Proceedings of IEEE International Conference on Evolutionary Computation, 1998, pp. 230-234.
[8] L. Wang, "A hybrid genetic algorithm-neural network strategy for simulation optimisation," Applied Mathematics and Computation, vol. 170, no. 2, pp. 1329-1343, 2005.
[9] T. Kido, H. Kitano, and M. Nakanishi, "A Hybrid Search for Genetic Algorithms: Combining Genetic Algorithms, TABU Search, and Simulated Annealing," in Proceedings of the 5th International Conference on Genetic Algorithms, San Mateo, CA, 1993, p. 641.
[10] B. Freisleben and P. Merz, "A genetic local search algorithm for solving symmetric and asymmetric travelling salesman problems," in Proceedings of IEEE International Conference on Evolutionary Computation, 1996, pp. 159-164.
[11] T. Murata, H. Ishibuchi, and H. Tanaka, "Genetic algorithms for flowshop scheduling problems," Computer & Industrial Engineering, vol. 30, no. 4, pp. 1061-1071, 1996.
[12] A. Roach and R. Nagi, "A hybrid GA-SA algorithm for just-in-time scheduling of multi-level assemblies," Computers & Industrial Engineering, vol. 30, no. 4, pp. 1047-1060, 1996.
[13] C. A. Glass and C. N. Potts, "A comparison of local search methods for flow shop scheduling," Annals of Operations Research, vol. 63, pp. 489-509, 1996.
[14] W. Chainate, P. Thapatsuwan, S. Kaitwanidvilai, P. Muneesawang, and P. Pongcharoen, "Improving Hopfield neural network performance and parameters investigation," KMITL Science Journal, vol. 6, no. 2, 2006.
[15] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. New York: Freeman, 1979.
[16] J. Holland, Adaptation in Natural and Artificial Systems: University of Michigan Press: Ann Habor, 1975.
[17] C. L. Huntley and D. E. Brown, "Parallel Genetic Algorithms with Local Search," Computers Operation Research, vol. 23, no. 6, pp. 559-571, 1996.
[18] P. Merz and B. Freisleben, "Genetic local search for the tsp: new results," in Proceedings of IEEE International Conference on Evolutionary Computation, 1997, pp. 159-164.
[19] T. Murata, H. Ishibuchi, and H. Tanaka, "Multi-objective genetic algorithm and its applications to flowshop scheduling," Computer & Industrial Engineering, vol. 30, no. 4, pp. 957-968, 1996.
[20] I. H. Osman and G. Laporte, "Metaheuristics: A bibliography," Annals of Operations Research, vol. 63, no. 1, pp. 513-623, 1996.
[21] W. Chainate, "A hybridisation of genetic algorithm and neural network for solving the travelling salesman problem," Master thesis, Faculty of Science., Naresuan Univ., Phitsanulok, Thailand, 2005.