An Efficient Framework Using Normalized Dominance Operator for Multi-Objective Evolutionary Algorithms

An Efficient Framework Using Normalized Dominance Operator for Multi-Objective Evolutionary Algorithms

Muneendra Ojha (DSPM International Institute of Information Technology - Naya Raipur, Atal Nagar, India), Krishna Pratap Singh (Indian Institute of Information Technology - Allahabad, Allahabad, India), Pavan Chakraborty (Indian Institute of Information Technology - Allahabad, Allahabad, India) and Shekhar Verma (Indian Institute of Information Technology - Allahabad, Allahabad, India)
Copyright: © 2019 |Pages: 23
DOI: 10.4018/IJSIR.2019010102

Abstract

Multi-objective optimization algorithms using evolutionary optimization methods have shown strength in solving various problems using several techniques for producing uniformly distributed set of solutions. In this article, a framework is presented to solve the multi-objective optimization problem which implements a novel normalized dominance operator (ND) with the Pareto dominance concept. The proposed method has a lesser computational cost as compared to crowding-distance-based algorithms and better convergence. A parallel external elitist archive is used which enhances spread of solutions across the Pareto front. The proposed algorithm is applied to a number of benchmark multi-objective test problems with up to 10 objectives and compared with widely accepted aggregation-based techniques. Experiments produce a consistently good performance when applied to different recombination operators. Results have further been compared with other established methods to prove effective convergence and scalability.
Article Preview
Top

1. Introduction

Evolutionary Multi-objective Optimization (EMO) method is a population-based approach to solve Multi-objective Optimization Problem (MOP). A significant amount of work has been done in recent past, wherein researchers developed a number of efficient algorithms such as SPEA2 (Zitzler, Laumanns, & Thiele, 2001), NSGA-II (Deb, Pratap, Agarwal, & Meyarivan, 2002), PESA-II (Corne, Jerram, Knowles, Oates, & Martin, 2001), IJSIR.2019010102.m01-EMO (Deb, Mohan, & Mishra, 2005) and MOEA/D (Q. Zhang & Li, 2007), and NSGA-III (Deb & Jain, 2014). The foremost reason for using Evolutionary Algorithm's (EA) in solving MOP is the unique feature of population-based approach where each individual is a possible solution candidate exploring a number of solution space in single simulation run, giving rise to a good approximation of complete Pareto set and consequently the Pareto front. Primarily, there are two aspirations that generic MOEA sets to achieve while solving MOPs (Deb, 1999): first, converge the search onto the true global Pareto front, and second, produce a diversified set of Pareto points in the generated approximate Pareto front. However, a major problem in EMO appears in the form of Dominance Resistance (DR) phenomenon (Li, Li, Tang, & Yao, 2015), wherein an exponentially increasingly fraction of the generated population becomes nondominated, thus adversely affecting the generation of the better population. Under such circumstances where dominance based primary criterion fails to define preference among solutions, a relaxed dominance criterion such ε-dominance (Laumanns, Thiele, Deb, & Zitzler, 2002) is applied. Additionally, in order to counter the effect of DR, and enhance the selection pressure towards the Pareto front, a density-based secondary criterion, called Active Diversity Preservation mechanism (ADP) is applied. However, computing the density or extent of crowding of solutions in a population and identification of neighbors becomes computationally expensive in a large-dimensional space. It has been shown that purely Pareto based approaches like NSGA-II and SPEA2 have deteriorated due to DR and ADP effects (Purshouse & Fleming, 2007) on Many objective Optimization Problems (MaOPs) where a number of objective functions are greater than 2. An approximation of diversity estimates the computations faster may cause an unacceptable distribution of solutions at the end (Deb & Jain, 2014). Additionally, in some cases, the final solution set might not even converge to the true Pareto front (Wagner, Beume, & Naujoks, 2007).

In view of the above discussion, both issues of convergence as well as diversity preservation have been addressed in the present work. In the present approach, both the Pareto based concept with the aggregation based concept is combined to use merits of both and to reduce the computational cost. A new Normalized Dominance IJSIR.2019010102.m02 operator is proposed with Pareto dominance-based vector optimization method to counter the DR phenomenon. An external elitist archive is maintained in parallel which generates an evenly distributed global Pareto front while reducing the overall computational cost. A concept of merger probability is also implemented to enforce restricted mating and a fair chance selection mechanism. It is shown that the present framework works fairly well on different pairs of crossover and mutation operators. Furthermore, it can be scaled up to at least 10 objective problems. Remainder of this paper is organized as follows: next, in this section, the multi-objective optimization problem definition is defined in brief followed by a section where a thorough literature review is presented. Section 2 introduces the details of the proposed Normalized Dominance operator IJSIR.2019010102.m03, an efficient binary ranking method along with modifications introduced in GA methods. Section 3 details the experimental setup and description of simulations performed on 2-objectives followed by 3, 5, 8 and 10-objective benchmark test problems. The results obtained are discussed in section 4 with final conclusion provided in section 5.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
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