Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA Traveling Salesman Problems Based Assessment: Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA

Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA Traveling Salesman Problems Based Assessment: Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA

Victer Paul (Department of Computer Science and Engineering, Vignan's Foundation for Science, Technology & Research, Guntur, India), Ganeshkumar C (Indian Institute of Plantation Management (IIPM), Bangalore, India) and Jayakumar L (Pondicherry University, Pondicherry, India)
Copyright: © 2019 |Pages: 38
DOI: 10.4018/IJAMC.2019040103

Abstract

Genetic algorithms (GAs) are a population-based meta-heuristic global optimization technique for dealing with complex problems with a very large search space. The population initialization is a crucial task in GAs because it plays a vital role in the convergence speed, problem search space exploration, and also the quality of the final optimal solution. Though the importance of deciding problem-specific population initialization in GA is widely recognized, it is hardly addressed in the literature. In this article, different population seeding techniques for permutation-coded genetic algorithms such as random, nearest neighbor (NN), gene bank (GB), sorted population (SP), and selective initialization (SI), along with three newly proposed ordered-distance-vector-based initialization techniques have been extensively studied. The ability of each population seeding technique has been examined in terms of a set of performance criteria, such as computation time, convergence rate, error rate, average convergence, convergence diversity, nearest-neighbor ratio, average distinct solutions and distribution of individuals. One of the famous combinatorial hard problems of the traveling salesman problem (TSP) is being chosen as the testbed and the experiments are performed on large-sized benchmark TSP instances obtained from standard TSPLIB. The scope of the experiments in this article is limited to the initialization phase of the GA and this restricted scope helps to assess the performance of the population seeding techniques in their intended phase alone. The experimentation analyses are carried out using statistical tools to claim the unique performance characteristic of each population seeding techniques and best performing techniques are identified based on the assessment criteria defined and the nature of the application.
Article Preview
Top

1. Introduction

Genetic Algorithms (GAs) are bio-inspired and stochastic global optimization technique developed by John Holland in 1975 (Holland, 1975). GAs belong to the family of computational models inspired by biological evolution, natural selection and survival of the fittest in living organisms. The fundamental model of GA is to generate a population of feasible solutions and to manipulate using genetic operators to evolve the required optimal solution. Thus, GA can be referred as a type of search technique that operates on feature of a collection of solutions rather than feature of a single solution. This characteristic enables the GA as a powerful tool for solving search and optimization problems with large search space (Sivanandam & Deepa, 2008). GAs have been used to solve complex problems such as robot trajectory planning (Tian & Collins, 2004), gas pipeline control (Goldberg, 1987), traveling salesman problem (Majumdar & Bhunia, 2011), sequence scheduling (Manikas & Chang, 2009), routing (Xiang, Junzhou, Jievi, & Guangun, 1999), etc.,

The traditional GA consists of following steps initial population (population seeding), selection, crossover, mutation and termination constraint in which first step occurs once, and the rest of the steps are repeated until the termination condition is satisfied (Poland, Nugent, Wang, & Chen, 2012; Goldberg, 1998). The traditional GA takes more computation time (in terms of hundreds of years) to evolve an optimal solution, so each step in the traditional GA has been modified, using heuristics, in a problem specific manner to reduce the computation time and to improve the ability to evolve the optimal solution and thus resulting in Hybrid GA (Lurgi & Robertson, 2011; Poland et al., 2012; Marinakis & Marinaki, 2010; Chen & Chien, 2010; Chen & Chein, 2011; Jayalakshmi & Sathiamoorthy, 2001; Wei & Hu, 2007; Katayama, Sakamoto & Narihisa, 2000). In Okano et al., (1999), two classes of heuristics are discussed for Hybrid GA, namely construction heuristics and local improvement heuristics. The construction heuristics help to construct initial population of solutions for the problem start from an empty solution to a complete and feasible solution. The local improvement heuristics use a selective set of solutions and apply genetic operators iteratively. Thereby, it attempts to improve the quality of the solution and replace the current solution with the better optimal solution evolved. The amount of computation time required for construction heuristic is much less, though it returns the solution with lesser quality. Therefore, it is used in on-the-fly route optimization in the drilling of printed-circuit boards (PCB) and dynamic optimal routing in VANET, where the available computation time and power are quite limited. On requirement of near optimal solution at the cost of computation time and power, local improvement heuristics are preferred.

The population initialization is an essential step in GA because the quality of individual solutions generated in the initial population stage plays a critical role in determining the quality of final optimal solution (Maaranen, Miettinen, & Penttinen, 2007; Maaranen, Miettinen, & Makela, 2004; Rahnamayan, Tizhoosh, & Salama, 2007; Yang, Guohui, Liang, & Kun, 2009). If no prior knowledge about the optimal solution for the problem is available, then random population initialization is the most commonly used method to generate an initial population of solutions (Rahnamayan et al., 2007). The GA with random population initialization technique is simple and efficient; however, the population may contain poor quality individuals which take long time to converge to the optimal solution (Paul et al., 2014). Therefore, when a priori information about the optimal solution for the problem is available, then the initial population of solution can be generated so as to explore the areas of the high-quality solution regions more elaborately than other areas in the large search space. Thus, the problem specific initial population in GA has a unique role in the search space exploration and to find the near optimal solution.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing