DESIGN AND APPLICATIONS OF HYBRID GENETIC ALGORITHMS FOR FUNCTION OPTIMIZATION

Abstract

"Optimization" can be viewed as a kind of decision making tool, in which decisions have to be taken to optimize one or more objectives in some prescribed set of circumstances. A real life optimization may have a number of local as well as global optimal solutions. Often it is desired to design optimization techniques which attempt to determine the global optimal solution of nonlinear optimization problems. Due to easy implantation and wide applicability, population based heuristics are becoming popular day by day, which takes the advent of computers. Evolutionary Algorithms, particularly Genetic Algorithms (GAs) are the most commonly used heuristics for solving real life problems for function optimization. Binary GAs are found to be robust search techniques, but a major drawback of binary GAs is that they face difficulties when applied to problems having lrge search space and seeking high precision. In binary coded GAs string length must be chosen a priori to get a desired degree of precision in the final solution. Larger string length results in more precise solution. It is shown in literature that for large string lengths, larger population size is required which in turn increase the computational cost. Another drawback in binary coded GA is the "Hamming-Cliff' problem which arises when the hamming distance (in binary coding) between two adjacent integers (in decimal code) is very large. A large number of bits are to be altered to change an integer to the adjacent one which causes the reduction in the efficiency of Binary GA. The Gray-coded GAs overcome the hamming-cliff problem of Binary Coded GAs. However, it is found that it still requireja large amount of computations. To overcome these difficulties related to binary encoding of continuous parameter optimization problems, real-encoding of chromosomes is used. GAs which make use of the real- encoding of chromosomes are termed as Real Coded GAs. This representation seems quite natural to deal with problems having continuous search space. This Thesis aims to improve the efficiency and reliability of Binary Coded Genetic Algorithms and Real Coded Genetic Algorithms by hybridizing them with a strong operator called Quadratic Approximation (QA). It is found that QA gives faster result, but there are more chances to get struck in local optima. But GA servers the purpose and finds a better result in the sense of reaching objective function value closer towards the global optima. Hence both the qualities namely better from GA and faster from QA are picked for hybridization. The main contribution of this Thesis is to design new hybrid GAs for determining the global optimal solution of unconstrained and constrained nonlinear optimization problems. After testing them on benchmark problems they are used to solve three real life nonlinear optimization problems. The first problem is a continuous unconstrained problem which concerns the optimization of infiltration parameters. The second problem is a continuous constrained nonlinear optimization problem on optimization of hydropower generations . The third problem is to design a specialized Genetic Algorithm for discrete optimization problem for solving a popular game called the "Sudoku". The chapter — wise summary of the Thesis is as follows. Chapter 1 is introductory in nature. Besides explaining the fundamentals it discusses the literature review on GA operators, hybrid GAs and constraint handling techniques. In Chapter 2, exhibits the detailed performance of four versions of binary coded GA both with and without elitism on a set of 5 most typical and hence challenging test examples in literature. They are Ackley, Griewank, Rastrigin, Rosenbrock and Schwefel functions. The four combinations of GA are based on the most popular operators like tournament selection (TS), roulette-wheel selection (RS), single point crossover (SC) and uniform crossover (UC). ii Depending upon the different pair-wise combinations of selection and crossover operators, we name the four proposed GA versions as V1 (uses TS & SC), V2 (uses TS & UC), V3 (uses RS and SC) and V4 (RS & UC). An exhaustive study is made based on generation—wise convergence, success rate, fine tuning of probability of crossover and probability of mutation. The quality of the final optimal value obtained is analyzed by varying problem dimension. It is i s concluded that the version V3 and V4 those use tournament selection, performance better. A In Chapter 3, we rename the four simple GA versions V1, V2, V3 and V4 as GAl, GA2, GA3 and GA4 respectively. In this chapter, an attempt is made to hybridize the four simple binary encoded GAs, described in Chapter 2, with the Quadratic Approximation (QA) as an additional operator after each cycle of GA. The four resultant hybrid GAs called HGA1(=GA1+QA), HGA2(=GA2+QA), HGA3(=GA3+QA) and HGA4(=GA4+QA). The comparison between the four simple GAs and corresponding hybrid GAs is done using a set of 22 benchmark problems that includes the 5 challenging test problems considered in Chapter 1. We conclude the results under three different cases. Case 1: Taking all versions that useb TS: HGA 1>HGA2>G442>GA 1. Case 2: Taking all versions that uses RS: HGA3>HGA4>GA4>GA3. Case 3: Taking all hybrid versions together HGA3>HGA4>HGA2>HGA1. Hence we left with two final the conclusions. Firstly, each hybrid version really outperforms their respective simple version. Secondly, among the hybrids, the HGA3 i.e. the version that uses RS and SC, performs better over all rest 7 versions in terms of reliability, efficiency and accuracy. Further for the particular problem suite, the depth and frequency of the QA that should be applied for better performance, is investigated. Due to their diversity preserving mechanism, real coded genetic algorithms are extremely popular in solving complex non-linear optimization problems. In recent literature, Deep and 111 Thakur (2007a, 2007b) proved that the new real coded genetic algorithm (called LX-PM that uses Laplace Crossover and Power Mutation), is more efficient than the existing genetic algorithms that use combinations of Heuristic Crossover along with Non-Uniform or Makinen, Periaux and Toivanen Mutation. However there are some instances where LX-PM needs improvement. Hence, in Chapter 4, an attempt is made to improve the efficiency and reliability of this existing LX-PM, by hybridizing it with quadratic approximation (called H-LX-PM). To realize the improvement, the same set of 22 benchmark problems as considered in Chapter 3. The numerical and graphical results confirm that H-LX-PM really exhibits improvement over LX-PM in terms of efficiency, reliability and stability. In Chapter 5, the Binary GA and the Hybrid Binary GA are extended to solve constrained nonlinear optimization problems. The penalty technique is incorporated as a constraint handling mechanism in which the bracket operator penalty term is SI=R (g(42, where R is the penalty parameter and g(x) represents the constraints. A set of 25 benchmark problems are used to evaluate the performance of constraint! versions of the Binary GA recommended in chapter 2 and the Hybrid Binary GA recommended in chapter 3. The numerical and graphical results confirm the superiority of the hybridization of binary GA. In Chapter 6, the Real coded GA and the Hybrid Real Coded GA are extended to solve constrained nonlinear optimization problems. The penalty technique is incorporated as a constraint handling mechanism. The same set of 25 benchmark problems as considered in chapter 5 are used to evaluate their performance. The extensive numerical and graphical results confirm the superiority of the real coded hybridization. The next task is to solve real life optimization problems. The first problem discussed in Chapter 7 is from the field of hydrology. This is an unconstrained nonlinear optimization problem. The movement of water into the soil under specific conditions is called infiltration. iv The study of infiltration is one of the most important necessities in irrigation and drainage engineering. Two popular infiltration models called Kostiakov and Modified Kostiakov, which are largely used in the fields, are considered for analysis. The problem is modeled as a least sum of squares of the differences in observed infiltration rates and computed infiltration rates over a specified time interval. In this Chapter, the comparative performance of the optimization methods developed in this Thesis is displayed for obtaining the infiltration parameters for the datasets (two each) of popular soils, namely Plain Field Sand (PFS) and Columbia Sandy Loam (CSL). To test model performance, the Nash-Sutcliffe efficiency is employed in this study. It is concluded that the hybrid binary GA performs better than binary GA and hybrid real coded GA performs better than real coded GA. Hydropower generation is of given importance as it saves precious hydrocarbon fuel deposits and does not adversely disturb ecological balance. In Chapter 8, the problem of hydropower generation is modeled as a constrained nonlinear optimization problem. The objective function to be maximized is the sum of the product of the release through power house and corresponding operating head during a certain period of time over the "'entire operation horizon. This is subject to the constraints on reservoir water mass balance, bounds on storage, irrigation and other water requirement and channel capacity thus ensuring that irrigation, domestic, industrial and environmental water requirements of the basin population are fully met. Two reservoirs from Orrisa state (namely Rengali and Derjang) are considered-and the model is developed with the data available at Water Resource Department, Orissa. The Hybrid Genetic Algorithms developed in Chapters 5 and 6 are used to solve the models. The extensive numerical and graphical results confirm the superiority of the binary and real coded hybrid versions over their original counterparts. The popular Japanese number puzzle Sudoku is interesting but challenging due to its easy rules and difficult phenomenon to solve it. Although a number of approaches exist for solving a given Sudoku puzzle, very few papers with heuristic approaches are available for obtaining its solution. As this is a discrete optimization problem, in Chapter 9 a Retrievable Genetic Algorithm is presented to solve a given Sudoku puzzle. Here the fitness function is modeled in a new way considering puzzle-character-dependent constraints. The GA is named as Retrievable, since the population is reinitialized after a certain number of generations in order to escape the local minima and retrieve the solution in least computational time. A set of 9 sample puzzles have been considered for comparison with the previously published results by GA and it is concluded that Retrievable GA outperforms GA. In addition we consider 6 newly generated puzzles namely Easy, Medium and Hard (two of each type) to conclude that the problem which is hard for the human beings is also hard for the Retrievable GA to solve. Finally in Chapter 10 conclusions based on the present study are outlined and suggestions for further work in this direction are mentioned.