Hybrid Genetic Algorithm: An Optimization Tool

Introduction

Optimization is an art of selecting the best alternative amongst a given set of options. It is central to any problem involving decision making in many disciplines such as engineering, mathematics, statistics, economics, and computer science. Now, more than ever, it is increasingly vital to have a firm grasp of the topic due to the rapid progress in computer technology, including the development and availability of user-friendly software, high-speed and parallel processors, and networks. Secondly, the problems, in general, arising in real life situations are highly complex and non-linear in nature. Some of them are unconstrained and some involve constraints. For such problems, it is a great challenge for the researchers to find the global optimal solution over many local optimal solutions. For example, a view of many local and single global minimum, is presented in Figure 1 for Ackley function (for n=2), which is a typical benchmark problem defined as

Figure 1.

Ackley Function: A 3D view for n=2

To handle such highly nonlinear problems with high complexity, the traditional methods become handicaped as it is a difficult task to check the auxiliary conditions like differentiability and continuity of the function in hand. Therefore, the evolutionary methods achieved enough popularity in recent years as they do not require any auxiliary conditions to be satisfied.

Genetic Algorithm (GA) (introduced by J. Holand in 1975) is one of such evolutionary methods, which is discussed briefly in section 2. GA operators are discussed in section 3. However, using simple GA sometimes puts the simulation suffering from getting trapped in local minima and sometimes results in premature convergence. To avoid such situations, researchers frequently use the hybrid versions of the GA. A case study on quadratic approximation based hybridization is described in section 4. In the same section, the effect of hybridization to simple GA is realized through a set of benchmark functions. Moreover, some real life applications are also presented. In section 5, some probable application areas in ‘Networking optimization’ are highlighted for researchers’ interest. Lastly, the conclusion of the chapter is drawn in section 6.

Genetic Algorithm

This section discusses the basics of Genetic Algorithm (GA). Holland is considered to be the father of GA. Later works on GA can be found in Goldberg (1989), Michalewicz (1992), Deb (1995, 2001), Mitchell (1996), Back (1996), Gen and Cheng (1997), Rajasekaran and Pai (2003) etc.

GA is based on the Darwin’s principle - ‘The survival of the fittest’. It works by evolving a population of individuals over a number of generations. A fitness value is assigned to each individual in the population, where the fitness computation depends upon the application. At each generation for the reproduction, individuals are selected from population according to their fitness values. Then the individuals are crossed to generate new individuals with some high crossover probability, and the new individuals are mutated with some low mutation probability. The individuals thus generated may completely replace the worse individuals in the old population. Since selection is based on more fit individuals, the average fitness of the population tends to improve from one generation to next generation. The fitness of best individuals is expected to improve over time, and the best individual may be chosen as a solution after several generations. GA uses two basic processes from evolution:

• •

  Inheritance or the passing of features from one generation to the next.

• •

  Competition or survival of the fittest.

The pseudo code of the Simple Genetic Algorithm comprises the following steps.