Multi-Objective Genetic Algorithm with Strategies for Dying of Solution

Introduction

In biology and ecology, dying is the end of an organism. Dying is the permanent “cessation of all biological functions that sustain a living organism. Phenomena which commonly bring about death include biological aging (senescence), predation, malnutrition, disease, suicide, homocide and accidents or trauma resulting in terminal injury” (Wikipedia.com, n.d.a.). Contemporary evolutionary theory sees death as an important part of the process of natural selection. It is considered that organisms less adapted to their environment are more likely to die having produced fewer offspring, thereby reducing their contribution to the gene pool. “The gene pool of a species or a population is the variety of genetic information in its living members. A large gene pool (extensive genetic diversity) is associated with robust populations that can survive bouts of intense selection. Meanwhile, low genetic diversity … reduces the range of adaption possible. Replacing native with alien genes narrows genetic diversity within the original population, thereby increasing the chance of extinction” (Wikipedia.com, n.d.b.).

Algorithms based on strategies of evolution are called as evolutionary algorithms. Genetic Algorithm (GA) (Goldberg, 1989; Deb, 2001) is one such algorithm based on natural genetics and survival of fittest. Genetic algorithms are used to solve single-objective and multi-objective optimization problems. Genetic algorithm used for solving single-objective problem are simpleminded and return a single optimal solution whereas for solving multi-objective problem, genetic algorithm has to select appropriate solutions. The decision of selection of solution becomes complicated in presence of multiple conflicting objectives. Every multi-objective evolutionary algorithm has two goals; convergence and diversity, so they need two different mechanisms for fulfillment of these goals. Algorithms like NSGA-II use non-dominated sorting and crowding distance based selection strategies for convergence and diversity (Deb et al., 2000). Many such multi-objective evolutionary algorithms with explicit mechanism for convergence and diversity control are found in the literature (Corne et al., 2000; Schaffer, 1985).

Selection strategy uses Pareto-dominance based (Deb et al., 2000) selection or single scalar value based (Rahila Patel et al., 2011) selection to select a multi-objective solution. Selected solutions are passed to next generation and they become parents in that generation. Solutions which are not selected die out or discarded from population and never re-appear. Dying of solution is inherent part of evolutionary process and selection strategies given in literature performs dying or removal implicitly. Solutions having better fitness produce fitter offspring and selection strategies are likely to select both parent and their offspring. Solutions (parent solution) present in first generation inherit their properties to offspring solutions by using cross over operator. In subsequent generations good properties of parent solutions are carrying forward by offspring solutions generated by crossover operator. Problem with this selection strategy is that, after few generation whole population is dominated by presence of few solutions from initial population and their offspring i.e. trail of very few solutions from initial population reach to final generation and most of the solutions die out somewhere in between generations.

In analogy with nature, if GA introduces a mechanism to control the rate of dying of solutions then diversity in population can be maintained. If dying rate of solutions is low, number of solutions having variety of genetic material will contribute in the formation of next generation population by producing diverse offspring.

In this work dying of solution has been made explicit part of evolutionary process and three strategies for dying of solution have been proposed and implemented. A solution is deterministically removed from next generation population by using one of the three proposed dying strategies. Impact of dying rate of solutions on the performance of GA has been studied. Idea of gradual dying is modeled and a new framework of MOGA has been used to demonstrate the same.