Document Type : Research Paper
Author
University of Anbar- College of Computer Science and Information Technology
Abstract
Multi-parent crossover has been proven its ability to address many of combinatorial optimization problems such as the traveling salesman problem and the vehicle routing problem with time windows. The successful use of multi-parent crossover arises from its abilities to enhance the search performance via utilizing information exchanged by more than two parents and inheriting by offspring. These parents are selected according to one of the selection mechanisms. Selecting the most appropriate parents for a crossover process might leads to improving the effectiveness of genetic algorithm. Therefore, this work investigates the effect of selection mechanism on the efficiency of multi-parent crossover. To test this, seven selection mechanisms have been used; random selection mechanism, roulette wheel mechanism, stochastic universal sampling mechanism, tournament selection mechanism, best selection mechanism, single best-couple random selection mechanism and couple best- single random selection mechanism. The performance of the proposed algorithm is tested using Solomon VRPTW benchmark. The experimental results show the superiority of multi-parent crossover that employs the selection mechanism which selects the outstanding individuals to form most of parents over multi-parent crossover that employ other selection mechanisms. This demonstrates the efficiency of employing best parents in a crossover process that can assist the search process to attain a better solution.
Keywords
Main Subjects
[1] O. Bräysy and M. Gendreau, "Vehicle routing problem with time windows, Part I: Route construction and local search algorithms," Transportation science, vol. 39, pp. 104-118, 2005a.
[2] G. B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management science, pp. 80-91, 1959.
[3] J.-F. Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon, and F. Soumis, "VRP with time windows," The vehicle routing problem, vol. 9, pp. 157-193, 2001.
[4] E. T. Yassen, M. Ayob, M. Z. A. Nazri, and N. R. Sabar, "Meta-harmony search algorithm for the vehicle routing problem with time windows," Information Sciences, vol. 325, pp. 140-158, 2015.
[5] Y. J. Gong, J. Zhang, O. Liu, R. Z. Huang, H. S. H. Chung, and Y. H. Shi, "Optimizing the Vehicle Routing Problem With Time Windows: A Discrete Particle Swarm Optimization Approach," IEEE Transactions on Systems Man and Cybernetics-Part C-Applications Reviews, vol. 42, p. 254, 2012b.
[6] E. T. Yassen, M. Ayob, M. Z. Ahmad Nazri, and N. R. Sabar, "A hybrid meta-heuristic algorithm for vehicle routing problem with time windows," International Journal on Artificial Intelligence Tools, vol. 24, p. 1550021, 2015.
[7] Y. Rochat and É. D. Taillard, "Probabilistic diversification and intensification in local search for vehicle routing," Journal of heuristics, vol. 1, pp. 147-167, 1995.
[8] R. A. Russell and W. C. Chiang, "Scatter search for the vehicle routing problem with time windows," European Journal of Operational Research, vol. 169, pp. 606-622, 2006.
[9] H. Nazif and L. Lee, "Optimized crossover genetic algorithm for vehicle routing problem with time windows," American journal of applied sciences, vol. 7, pp. 95-101, 2010.
[10] Y. Wang, "A Hybrid Approach Based on Ant Colony System for the VRPTW," 2012, pp. 327-333.
[11] J. H. Holland, Adaptation in natural and artificial systems: University of Michigan press, 1975.
[12] W. Gong, Á. Fialho, Z. Cai, and H. Li, "Adaptive strategy selection in differential evolution for numerical optimization: an empirical study," Information Sciences, vol. 181, pp. 5364-5386, 2011b.
[13] G. Zapfel, R. Braune, and M. Bogl, Metaheuristic search concepts: Springer, 2010.
[14] B. Kallehauge, J. Larsen, O. B. G. Madsen, and M. M. Solomon, "Vehicle routing problem with time windows," Column generation, pp. 67-98, 2005.
[15] K. Tan, T. Lee, K. Ou, and L. Lee, "A messy genetic algorithm for the vehicle routing problem with time window constraints," in Evolutionary Computation, 2001. Proceedings of the 2001 Congress on, 2001c, pp. 679-686.
[16] S. R. Thangiah, Vehicle routing with time windows using genetic algorithms: Citeseer, 1993.
[17] S. R. Thangiah, "An adaptive clustering method using a geometric shape for vehicle routing problems with time windows," in Proceedings of the 6th International Conference on Genetic Algorithms, 1995, pp. 536-545.
[18] E. G. Talbi, Metaheuristics from design to implementation: Wiley Online Library, 2009.
[19] I. Oliver, D. Smith, and J. Holland, "C, 1987. A Study of Permutation Crossover Operators on the Travelling Salesman Problem," in Genetic Algorithms and their Application:Proceedings of the 2nd International Conference on Genetic Algorithms.
[20] Y. Nagata, "Edge assembly crossover for the capacitated vehicle routing problem," Evolutionary Computation in Combinatorial Optimization, pp. 142-153, 2007.
[21] Z. Lü, J. K. Hao, and F. Glover, "A Study of Memetic Search with Multi-parent Combination for UBQP," Evolutionary Computation in Combinatorial Optimization, pp. 154-165, 2010.
[22] Y. Wang, Z. Lü, and J. K. Hao, "A study of multi-parent crossover operators in a memetic algorithm," Parallel Problem Solving from Nature–PPSN XI, pp. 556-565, 2011.
[23] E. T. Yassen, M. Ayob, M. Z. A. Nazri, and N. R. Sabar, "Multi-parent insertion crossover for vehicle routing problem with time windows," in Data Mining and Optimization (DMO), 2012 4th Conference on, 2012, pp. 103-108.
[24] J. Berger, M. Barkaoui, and O. Braysy, "A route-directed hybrid genetic approach for the vehicle routing problem with time windows," Infor-Information Systems and Operational Research, vol. 41, pp. 179-194, 2003.
[25] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning vol. 412: Addison-wesley Reading Menlo Park, 1989.
[26] K. C. Tan, L. L. Hay, and O. Ke, "Hybrid genetic algorithms in solving vehicle routing problems with time window constraints," Asia-Pacific Journal of Operational Research, vol. 18, pp. 121-131, 2001b.
[27] S. Jung and B. R. Moon, "A Hybrid Genetic Algorithm For The Vehicle Routing Problem With Time Windows," in GECCO, 2002, pp. 1309-1316.
[28] G. B. Alvarenga and G. R. Mateus, "Hierarchical tournament selection genetic algorithm for the vehicle routing problem with time windows," in Hybrid Intelligent Systems, 2004. HIS'04. Fourth International Conference on, 2004, pp. 410-415.
[29] B. Minocha and S. Tripathi, "Solution of Time Constrained Vehicle Routing Problems using Multi-Objective Hybrid Genetic Algorithm," Int. J. Comput. Sci. Inf. Technol., vol. 2, pp. 2671-2676, 2011.
[30] Y.-J. Shi, F.-W. Meng, and G.-J. Shen, "A modified artificial bee colony algorithm for vehicle routing problems with time windows," Information Technology Journal, vol. 11, p. 1490, 2012.
[31] T. Vidal, T. Gabriel Crainic, M. Gendreau, and C. Prins, "A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows," Computers & Operations Research, 2013.
[32] J.-Y. Potvin and S. Bengio, "The vehicle routing problem with time windows part II: genetic search," INFORMS Journal on computing, vol. 8, pp. 165-172, 1996.
[33] A. Le Bouthillier and T. G. Crainic, "A cooperative parallel meta-heuristic for the vehicle routing problem with time windows," Computers & Operations Research, vol. 32, pp. 1685-1708, 2005.
[34] H. Wee-Kit , J. C. Ang, and A. Lim, "A HYBRID SEARCH ALOGRITHM FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS," International Journal on Artificial Intelligence Tools, vol. 10, pp. 431-449, 2001.
[35] H. Gehring and J. Homberger, "A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows," in Proceedings of EUROGEN99, 1999, pp. 57-64.
[36] H. Gehring and J. Homberger, "Parallelization of a two-phase metaheuristic for routing problems with time windows," Journal of Heuristics, vol. 8, pp. 251-276, 2002.
[37] D. Mester, "An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions," in Conf. Mathematical and Population Genetics, University of Haifa, Israel, 2002.
[38] G. Zapfel, R. Braune, M. Bogl, and E. Corporation, Metaheuristic Search Concepts: Springer, 2010.
[39] H. M. Pandey, A. Shukla, A. Chaudhary, and D. Mehrotra, "Evaluation of genetic algorithm’s selection methods," in Information Systems Design and Intelligent Applications, ed: Springer, 2016, pp. 731-738.
[40] C.-K. Ting, C.-H. Su, and C.-N. Lee, "Multi-parent extension of partially mapped crossover for combinatorial optimization problems," Expert systems with applications, vol. 37, pp. 1879-1886, 2010.
[41] Y. W. Foo, C. Goh, H. C. Lim, and Y. Li, "Evolutionary Neural Network Modeling for Energy Prediction of Cloud Data Centers," in International Symposium on Grids and Clouds, 2015.
[42] A. J. Kulkarni, G. Krishnasamy, and A. Abraham, "Cohort Intelligence for Solving Travelling Salesman Problems," in Cohort Intelligence: A Socio-inspired Optimization Method, ed: Springer, 2017, pp. 75-86.
[43] B. B. Akay and D. Karaboga, "Artificial Bee Colony Algorithm Variants on Constrained Optimization," An International Journal of Optimization and Control: Theories & Applications (IJOCTA), vol. 7, pp. 98-111, 2017.
[44] J. E. Baker, "Reducing bias and inefficiency in the selection algorithm," in Proceedings of the second international conference on genetic algorithms, 1987, pp. 14-21.
[45] W. La Cava, S. Silva, L. Vanneschi, L. Spector, and J. Moore, "Genetic programming representations for multi-dimensional feature learning in biomedical classification," Spring, Amsterdam, e Netherlands. To Appear, 2017.
[46] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations research, pp. 254-265, 1987.
[47] C. Yang, Z.-x. Guo, and L.-y. Liu, "Comparison Study on Algorithms for Vehicle Routing Problem with Time Windows," in Proceedings of the 21st International Conference on Industrial Engineering and Engineering Management 2014, 2015, pp. 257-260.
[48] S. García, A. Fernández, J. Luengo, and F. Herrera, "Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power," Information Sciences, vol. 180, pp. 2044-2064, 2010.
[49] N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, "A Dynamic Multi-Armed Bandit-Gene Expression Programming Hyper-Heuristic for Combinatorial Optimization Problems," IEEE transactions, vol. 45, pp. 217 - 228, 2014
)
