A Fast Two-objective Differential Evolutionary Algorithm based on Pareto-optimal Set

A Fast Two-objective Differential Evolutionary Algorithm based on Pareto-optimal Set

Xu Yu-long (Institute of Information and Technology, Henan University of Traditional Chinese Medicine, Zheng Zhou, China) and Zhao Ling-dong (School of Electronics & Information, Nantong University, NanTong, China)
DOI: 10.4018/IJSSCI.2016010104
OnDemand PDF Download:


The two-objective differential evolution with Pareto-optimal set, which is researched in this paper. Firstly, it is found that there are some redundant computations in the classic multi-objective evolutionary algorithm, such as the NSGA-II. Then, based on the concept of Pareto-optimal set, the non-dominated solution sorted and its potential features, the authors propose a ranking method for solution that only handles the highest rank individuals in current population. The highlight of the proposed method is that during the ranking process, the individuals can be chosen into the next generation meanwhile. When the individuals of next generation population are obtained the algorithm is broken out. Both the number of individuals for sorting process and the time complexity are reduced. Furthermore, a method of uniform crowding distance calculation is provided in this work. Finally, the authors incorporate the introduced ranking method and uniform crowding distance method into differential evolution, a fast two-objective differential evolution algorithm is obtained. For verifying the proposed method, they use the classical optimal problems ZDTl~ZDT4 and ZDT6 for tesing. Simulation results show that the authors' method has greatly improved in terms of time complexity and performance than other algorithms.
Article Preview

1. Introduction

In the optimization problem, the number of objective function more than two is called multi-objective optimization. For the multi-objective optimization problems, a solution for one target may be good, but for other targets may be poor. Thus, there is a compromise solution collection, which is called the Pareto-optimal set or Non-dominated set. Multi-objective optimization problems are often converted into single objectives by weighting, and then using the mathematical programming method to solve them. This method only can get an optimal solution in case of a certain weight at each run. However, the traditional mathematical programming is inefficiency, and more sensitive to the weight value or the order given by target (Deb, 2001).

Multi-objective evolutionary algorithms (MOEAs) began in the1980s. During the research results, the NSGA-II algorithm (Deb, 2002) proposed by Deb and the SPEA-II algorithm (Zitzler, 1999; Zitzler, 2002) proposed by Zitzler are the most famous, which all pursue two optimizations convergence and diversity index, and such algorithms are used the following two strategies:ÿ By constructing Pareto candidate solution set to retain the Pareto solutions, and through the appropriate ways to maintain the diversity of solution;ÿ Based on the Pareto dominance relation and spatial density to determine the merits of the individual. Chinese scholars reviewed the development history of MOEAs, and the main technology, theoretical results of multi-objective evolutionary algorithm and the direction of further study (Tao, 2003; Cui, 2001; Gong, 2009; Geng, 2013).

Since Storn proposed the differential evolution (DE) algorithm (Das, 2011), many scholars have devoted to extend to their research of multi-objective optimization. (Abbass, 2002) introduced the PDE algorithm, which early using of DE combined with Pareto dominance relationship to solve multi-objective optimization problem. Subsequently, an improved differential evolution algorithm for solving multi-objective problems in power system PEDA (Yang, 2008) has been proposed. Xue according to the improved individual density calculations, based on Pareto dominance, multi-objective differential evolution algorithm MODE was proposed, and achieved a good result (Xue, 2005). The most famous algorithm using DE for solving multi-objective problem named DEMO was put forward by (Robic, 2005). The biggest difference between DEMO and other algorithms is that it is not in accordance with an individual level to select the next generation, but compared with offspring and parent individual directly, if the offspring dominate parent, choose the offspring enter the next generation directly, otherwise discarded. If the parent and offspring's relationship is non-dominated solution, it will put the offspring in extra population to archive, which has significantly improved over NSGAII on convergence and diversity index.

Complete Article List

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