HYBRID GENETIC ALGORITHMS AND THEIR APPLICATIONS

Abstract

Optimization problems arise in several fields such as system engineering, telecommunication, agriculture, biochemical engineering, business management, engineering design and manufacturing systems etc. In fact the newly developed optimization techniques are now being extensively used in various spheres of human activity where decisions have to be taken in some complex situations that can be represented by mathematical models. Optimization can thus be viewed as a kind of decision making, or more specifically, as one of the major quantitative tools in the network of decision making, 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. It is desired by most of the users to design optimization techniques which determine the global optimal solution rather than the local optimal solution of nonlinear optimization problems. With the advent of computers, population based heuristics are becoming popular day by day, not only because of their ease of implementation, but also due to their wide applicability. Evolutionary Algorithms, particularly Genetic Algorithms (GAs) are the most commonly used heuristics for solving real life problems. Binary GAs are found to be robust search techniques to avoid local optimum but the computational cost is usually very high as compared to deterministic ii optimization technique. A major drawback of binary GAs is that they face difficulties when applied to problems having large 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. Goldberg (1989) has shown that for large string lengths, larger population size is required which in turn increase the computational cost. One way to overcome these difficulties related to binary encoding of continuous parameter optimization problems is to hybridize GA by incorporating local searches which usually work in the real space. This way the good traits of binary as well as real encoding can be exploited and the chance to achieve the global optimum increases. Such methods are called Hybrid GAs or MAs. The major contribution of this thesis is the design of new hybrid GAs for obtaining the global optimal solution of nonlinear optimization problems. Three hybrid GAs are designed in this thesis.' One is hybridized with a deterministic local search method and the other two are hybridized with a population based stochastic search technique. A variant of MA is designed to implement the most commonly used deterministic local search called Hookes and Jeeves with the binary GA. The local search is applied only after a specified number of generations and only to a partial subset of the population. The numerical experiments are performed on 5 of the most challenging benchmark problems in global optimization literature. These 5 problems are particularly selected as their nature is conflicting and they are scalable, that is their dimension can be increased. Problems of size 10, 30 and 50 are analyzed in iii terms of function evaluations, percentage of success and mean value of the objective function. Based on the extensive numerical and graphical results, it is concluded that although this approach has a high percentage of success in comparison to GA, the number of function evaluations are very high. The next milestone is the design of new hybrid GA. The Binary GA is hybridized with the real coded Self Organizing Migrating Algorithm in a way that maximum benefits of both the approaches are reaped. The new hybridized algorithm is called the Self Organizing Migrating Genetic Algorithm (SOMGA). The main feature of this algorithm is that it works with a very less population size. A wide variety of 25 benchmark test problems are selected and analyzed including the previous 5 problems. All the problems are purposefully selected since they are scalable and have varying complexity levels. Based on the extensive numerical and graphical analysis it is found that SOMGA is an efficient algorithm which can attain .4J the global optima efficiently in less function evaluations and with a better precision.,. A well known constraint handling technique, called the parameter free constrained handling technique is implemented into SOMGA and a new algorithm called C-SOMGA is designed which can be used to determine the global optimal solution of nonlinear constrained optimization problems. A set of 10 well known benchmark constrained test problems are used to evaluate its performance. The results obtained by C-SOMGA are compared with GA and SOMA. For the fair comparison same constraint handling technique is implemented on GA and SOMA and these algorithms are called as C-GA and C-SOMA respectively. Based on the numerical iv and graphical results it is concluded that the newly defined hybrid GA for constraint optimization, namely, C-SOMGA outperform the C-GA as well as C-SOMA. The utility of the algorithms SOMGA for unconstrained optimization and C-SOMGA for constrained optimization is exhibited on a number of real life optimization problems. The first family of problems is from the field of electrical engineering. The Directional Overcurrent Relay Times are to be minimized in order to identify the faulty lines in IEEE 3-bus model, IEEE 4-bus model and IEEE 6-bus model. Based on the results it is concluded that C-SOMGA is able to provide better results as compared to the earlier published results. The second family of real life problems deals with three models of reliability based optimization problems. These models are life support system in a space capsule, complex bridge-network and n-stage mixed system. Results obtained are shown to provide comparable results to the previously quoted results. Further, a set of 8 real life optimization problems, two unconstrained and six constrained arising in various fields of engineering design are solved using SOMGA and C-SOMGA respectively. The problems are of various difficulty levels, including Geometric Programming Problems. The numerical results clearly demonstrate the effectiveness of SOMGA and C-SOMGA in solving these real life problems as well, since the results are either better than or comparable to the previously quoted results. Finally, the behavior of the SOMGA algorithm is investigated on a set of 13 large scale optimization problems. The results of problem size upto 200 are analyzed. It is observed that SOMGA can solve large scale problems with considerable ease. This is so because SOMGA and C-SOMGA work with a small population size and hence require very few function calls. Finally based on the results, SOMGA is recommended for determining the global optimal solution of nonlinear unconstrained optimization problems. Also, C-SOMGA is recommended for determining the global optimal solution of nonlinear constrained optimization problems. These algorithms are efficient, reliable and robust not only for benchmark test problems taken from literature but also for a wide variety of real life optimization problems arising in engineering applications.