Genetic Search Algorithms

The extension of genetic search algorithms to MOO problems requires new concepts, such as Pareto domination ranking and fitness sharing. The goal is to maintain the diversity in the population of solutions through successive generations. Niching methods were introduced to reduce the effect of “random genetic drift,” and to preserve the genetic diversity of optimal solutions. The NPGA algorithm illustrates this approach with application to the Binh-Korn test function. The software NSGA-II can handle real-world complex constrained MOO problems. This software package is a fast and elitist algorithm sorting the population of parents and offspring on different ranked fronts. A non-domination order relation prevails. An elitist search procedure guarantees the diversity and spread of solutions. The constraint handling method differs from the conventional methods by using a modified definition of dominance rather than penalty parameters. NSGA-II can solve several test functions. These applications are unconstrained test functions such as ZDT1, UF1, Kursawe and Viennet, and constrained test functions such as SRN, Deb, and Tanaka. For these problems, we decided to illustrate the progression of calculation at the different steps of the iteration path.

Keywords: Crowded-comparison operator, Crowding distance, Elitist search procedure, Kursawe’s test function, MOEA Framework, NPGA software, Niching methods, Niche radius, NSGA-II software, Ranking process, Pareto domination ranking, SciLab software, Selection operator, Sharing function, SRN test problem, Tournament competition, Tanaka’s test function, UF1 test function, Viennet’s test function.