Article Preview
Top1. 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.