DEMORS: A hybrid multi-objective optimization algorithm using differential evolution and rough set theory for constrained problems

https://doi.org/10.1016/j.cor.2009.02.006Get rights and content

Abstract

The aim of this paper is to show how the hybridization of a multi-objective evolutionary algorithm (MOEA) and a local search method based on the use of rough set theory is a viable alternative to obtain a robust algorithm able to solve difficult constrained multi-objective optimization problems at a moderate computational cost. This paper extends a previously published MOEA [Hernández-Díaz AG, Santana-Quintero LV, Coello Coello C, Caballero R, Molina J. A new proposal for multi-objective optimization using differential evolution and rough set theory. In: 2006 genetic and evolutionary computation conference (GECCO’2006). Seattle, Washington, USA: ACM Press; July 2006], which was limited to unconstrained multi-objective optimization problems. Here, the main idea is to use this sort of hybrid approach to approximate the Pareto front of a constrained multi-objective optimization problem while performing a relatively low number of fitness function evaluations. Since in real-world problems the cost of evaluating the objective functions is the most significant, our underlying assumption is that, by aiming to minimize the number of such evaluations, our MOEA can be considered efficient. As in its previous version, our hybrid approach operates in two stages: in the first one, a multi-objective version of differential evolution is used to generate an initial approximation of the Pareto front. Then, in the second stage, rough set theory is used to improve the spread and quality of this initial approximation. To assess the performance of our proposed approach, we adopt, on the one hand, a set of standard bi-objective constrained test problems and, on the other hand, a large real-world problem with eight objective functions and 160 decision variables. The first set of problems are solved performing 10,000 fitness function evaluations, which is a competitive value compared to the number of evaluations previously reported in the specialized literature for such problems. The real-world problem is solved performing 250,000 fitness function evaluations, mainly because of its high dimensionality. Our results are compared with respect to those generated by NSGA-II, which is a MOEA representative of the state-of-the-art in the area.

Introduction

Multi-objective programming (MOP) is a research field that has raised great interest over the last 30 years, mainly because of the many real-world problems which naturally have several (often conflicting) criteria to be simultaneously optimized [9], [21].

In recent years, a wide variety of multi-objective evolutionary algorithms (MOEAs) have been proposed in the specialized literature [5], [6], [7]. However, the study of hybrids of MOEAs with other types of techniques is still relatively scarce (see [10] as a suitable reference to hybrid methods also for combinatorial problems). This paper presents a study of the combination of a MOEA and a local search method inspired by rough set theory as a viable way of obtaining a good approximation, both in quality and in diversity, of the Pareto front of a constrained multi-objective optimization problem. Our main motivation for such a hybrid approach is to reduce the overall number of fitness function evaluations performed to approximate the Pareto front of a problem. For this aim, we consider one of the fastest MOEAs in the literature, differential evolution (DE) [27], [32], and improve its performance by using a local search method inspired by rough set theory. This kind of hybrid approach (DE and rough set theory) has been already used and tested to solve box-constrained multi-objective optimization problems showing a high performance [12] when compared with highly competitive methods, and this is the main reason to approach its adaptation to constrained problems here. We opted to implement such an adaptation also taking into account the increase in the demand of multi-objective solvers for real cases, where most of the problems are (hard) constrained. It is worth noting, however, that in spite of this demand, the number of multi-objective metaheuristics developed with a particular emphasis on reducing the number of objective function evaluations that they perform is very scarce. Taking into account these last facts, we adapted and tested this hybrid method in order to validate it to be used for constrained multi-objective optimization problems.

The remainder of this paper is organized as follows: Section 2 provides some basic concepts required to understand the rest of this paper. In Section 3, we introduce DE, which is the approach adopted as our search engine. An introduction to rough set theory is provided in Section 4. Section 5 describes the relaxed form of Pareto dominance adopted for our secondary population (called Pareto-adaptive ε-dominance). Our proposed hybrid is described in Section 6. The experimental setup adopted to validate our approach and the corresponding discussion of results are provided in Section 7. Finally, our conclusions and some possible paths for future research are provided in Section 8.

Section snippets

Basic concepts

We are interested in solving problems of the type2Minimize f(x)(f1(x),f2(x),,fk(x))subject togj(x)0,j=1,2,,mhk(x)=0,k=1,2,,pwhere x=(x1,x2,,xn)T is the vector of decision variables, fi:RnR, i=1,,k are the objective functions and gj,hk:RnR, j=1,,m, k=1,,p are the constraint functions of the problem. Let us denote by X the set of all feasible solutions, that is, the set of all xRn satisfying constraints (2), (3)

Differential evolution

DE [27], [32] is a relatively recent heuristic designed to optimize problems over continuous domains. DE has been shown to be not only very effective as a global optimizer, but also very robust producing in many cases a minimum variability of results from one run to another. DE has been extended to solve multi-objective problems by several researchers (see e.g., [1], [2], [14], [16], [19], [20], [24], [29], [34]). However, in such extensions, DE has been found to be very good at converging

Rough set theory

Rough set theory is a new mathematical approach to imperfect knowledge. The problem of imperfect knowledge has been tackled for a long time by philosophers, logicians and mathematicians. Recently, it also became a crucial issue for computer scientists, particularly in the area of artificial intelligence (AI). There are many approaches to the problem of how to understand and manipulate imperfect knowledge. The most used one is the fuzzy set theory proposed by Zadeh [35]. Rough set theory was

Pareto-adaptive ε-dominance

One of the concepts that has raised more interest within evolutionary multi-objective optimization in the last few years is, with no doubt, the use of relaxed forms of Pareto dominance that allow us to control the convergence of a MOEA. From such relaxed forms of dominance, ε-dominance [17] is certainly the most popular. ε-dominance has been mainly used as an archiving strategy in which one can regulate the resolution at which our approximation of the Pareto front will be generated. This allows

The hybrid method: DEMORS

Our proposed approach, called DEMORS (DE for multi-objective optimization with local search based on rough set theory) [12], is divided in two different phases, and each of them consumes a fixed number of fitness function evaluations. During Phase I, our DE-based MOEA performs the greatest effort for obtaining a good Pareto front approximation. For that reason, this phase consumes 65% of the total number of evaluations. During Phase II, a local search procedure based on rough set theory is

Computational experiments

In order to validate our proposed approach, our results are compared with respect to those generated by NSGA-II [8], which is a MOEA representative of the state-of-the-art in the area.

The first phase of our approach uses four parameters: crossover probability (pc), elitism (sel2), population size (P), and the amplification value (F). On the other hand, the second phase uses four more parameters: the number of points randomly generated inside each atom (Offspring), the number of atoms per

Conclusions

We have presented a new hybrid multi-objective optimization algorithm for constrained MOPs based on the use of a fast DE algorithm and a local search engine based on rough set theory. The proposed approach was found to provide very competitive results with respect to other previous approaches, in a variety of bi-objective test problems, in spite of the fact that it performed only 10,000 fitness function evaluations. Within this number of evaluations, both DEMORS and NSGA-II (which is a highly

Acknowledgements

The authors thank the two anonymous reviewers for the comments which greatly helped them to improve the contents of this paper.

The first author acknowledges support from CONACyT through a scholarship to pursue graduate studies at the Computer Science Department at CINVESTAV-IPN. The fourth author acknowledges support from CONACyT project number 45683-Y.

References (37)

  • L.A. Zadeh

    Fuzzy sets

    Information and Control

    (1965)
  • Abbass HA. The self-adaptive Pareto differential evolution algorithm. In: Congress on evolutionary computation...
  • Babu BV, Mathew Leenus Jehan M. Differential evolution for multi-objective optimization. In: Proceedings of the 2003...
  • Binh TT, Korn U. MOBES: a multiobjective evolution strategy for constrained optimization problems. In: The third...
  • Cobacho B. Planificación de la inversión pública federal en México mediante técnicas de análisis multicriterio. PhD...
  • C.A. Coello Coello et al.

    Evolutionary algorithms for solving multi-objective problems

    (2002)
  • C.A. Coello Coello et al.

    Evolutionary algorithms for solving multi-objective problems

    (2007)
  • K. Deb

    Multi-objective optimization using evolutionary algorithms

    (2001)
  • K. Deb et al.

    A fast and elitist multiobjective genetic algorithm: NSGA–II

    IEEE Transactions on Evolutionary Computation

    (2002)
  • M. Ehrgott

    Multicriteria optimization

    (2005)
  • M. Ehrgott et al.

    Hybrid metaheuristics for multi-objective combinatorial optimization

  • D.E. Goldberg

    Genetic algorithms in search, optimization and machine learning

    (1989)
  • Hernández-Díaz AG, Santana-Quintero LV, Coello Coello C, Caballero R, Molina J. A new proposal for multi-objective...
  • A.G. Hernández-Díaz et al.

    Pareto adaptive—ε-dominance

    Evolutionary Computation

    (2007)
  • Iorio AW, Li X. Solving rotated multi-objective optimization problems using differential evolution. In: AI 2004:...
  • H. Kita et al.

    Multi-objective optimization by means of the thermodynamical genetic algorithm

  • Kukkonen S, Lampinen J. An extension of generalized differential evolution for multi-objective optimization with...
  • M. Laumanns et al.

    Combining convergence and diversity in evolutionary multi-objective optimization

    Evolutionary Computation

    (2002)
  • Cited by (70)

    • A new multi-objective optimization algorithm combined with opposition-based learning

      2021, Expert Systems with Applications
      Citation Excerpt :

      The idea of HOA is to increase the quality of the solution using the features of two or more optimization algorithms, but in MOP there is not a single solution to optimize, the entire Pareto set is modified by the selected operators to find the PF. An example of HOA for MOP is the hybrid evolutionary immune algorithm (HEIA) proposed by Lin et al. (2016) or the DEMORS that used the DE and the rough set theory for MOP (Santana-Quintero, Hernández-Díaz, Molina, Coello, & Caballero, 2010). Meanwhile, (Lin et al., 2015) proposed the hybridization of the multi-objective immune algorithm with an adaptive DE to generate the ADE-MOIA that improved the convergence and the population diversity.

    View all citing articles on Scopus
    1

    The author is also associated to the UMI-LAFMIA 3175 CNRS.

    View full text