Progressive-Stepping-Based Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization

Progressive-Stepping-Based Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization

Akshay Baviskar (Indian Institute of Technology Madras, Chennai, India) and Shankar Krishnapillai (Indian Institute of Technology Madras, Chennai, India)
Copyright: © 2016 |Pages: 33
DOI: 10.4018/IJAEC.2016070102
OnDemand PDF Download:
List Price: $37.50


This paper demonstrates two approaches to achieve faster convergence and a better spread of Pareto solutions in fewer numbers of generations, compared to a few existing algorithms, including NSGA-II and SPEA2 to solve multi-objective optimization problems (MOP's). Two algorithms are proposed based on progressive stepping mechanism, which is obtained by the hybridization of existing Non-dominated Sorting Genetic Algorithm II (NSGA-II) with novel guided search schemes, and modified chromosome selection and replacement mechanisms. Progressive Stepping Non-dominated Sorting based on Local search (PSNS-L) controls the step size, and Progressive Stepping Non-dominated Sorting based on Utopia point (PSNS-U) method controls the number of divisions to generate better chromosomes in each generation to achieve faster convergence. Four multi-objective evolutionary algorithms (EA's) are compared for different benchmark functions and PSNS outperforms them in most cases based on various performance metric values. Finally a mechanical design problem has been solved with PSNS algorithms.
Article Preview

1. Introduction

Multi-objective Optimization is important in engineering optimization problems which often result in two or more conflicting objective functions. Multi-objective algorithms developed hitherto gives a set of optimal solution points from the feasible space forming a Pareto Optimal Front. Obtaining the Pareto Front (PF) and maintaining its accuracy comparable to the True Pareto Front while satisfying Convergence & Diversity are a key issue in the development of algorithms. Convergence implies the closeness of the solutions to the True Pareto-Optimal front, and Diversity implies the uniform spread of the solution points over the entire Pareto Front.

Over the past decades, many researchers proposed different multi-objective optimization algorithms. Evolutionary algorithms (EA's) became popular due to its applicability to solve complex real world problems with conflicting objective functions (Deb, 2001, Haupt & Haupt, 2004). Schaffer developed the first multi objective evolutionary algorithm (MOEA) which gives the trade-off between conflicting objective functions known as Pareto front (Schaffer, 1985). Zitzler and Thiele (1999) presented the Strength Pareto Evolutionary Algorithm (SPEA), it uses an archive population set to store previously generated non-dominated solutions and update it as and when new non-dominated solution found. After successful demonstration of external archives in SPEA, many researchers have tried to incorporate external archives with current population with their MOEAs. In SPEA, initial population is generated keeping the archive population empty and then the fitness is assigned to all the populations based on the domination criteria. Non-dominated populations, then sent to the archive and remaining in current populations. Mating pool is then filled by mating selection and binary tournament selection and finally recombination and mutation for the selected populations from the mating pool. Updated population is sent to the next generation only if the termination criteria is not yet achieved. This algorithm has its own fitness calculation methodology which is updated in its newer version known as SPEA2 (Zitzler, Laumanns, & Thiele, 2001). SPEA2 updated with a fine-grained fitness assignment strategy, a density estimation technique, and an enhanced archive truncation method in contrast to its predecessor. The density estimation technique used in SPEA2 is a modification of the k-th nearest neighbor technique (Silverman, 1986). In 1999, a MOEA called Pareto-Archived Evolution Strategy (PAES) (Knowles and Corne, 1999) was presented by Knowles and Corne. PAES (1 + 1) maintains an archive population of solutions from which individuals are selected for reproduction and fittest of the archive population replaces the current population. Ali et al. (2009 & 2011) extended the Modified Differential Evolution (MDE) used for solving single objective optimization problems and generalized it to MOPs. Their algorithm Multi-Objective Differential Evolution Algorithm (MODEA) adopts Opposition Based Learning (OBL) to produce an initial population. Furthermore, they incorporated the random localization concept in the mutation step.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing