DEMORS: A hybrid multi-objective optimization algorithm using differential evolution and rough set theory for constrained problems
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 type2subject towhere is the vector of decision variables, , are the objective functions and , , are the constraint functions of the problem. Let us denote by the set of all feasible solutions, that is, the set of all 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 , elitism , population size , and the amplification value . On the other hand, the second phase uses four more parameters: the number of points randomly generated inside each atom , 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)
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...
- et al.
Evolutionary algorithms for solving multi-objective problems
(2002) - et al.
Evolutionary algorithms for solving multi-objective problems
(2007) Multi-objective optimization using evolutionary algorithms
(2001)- et al.
A fast and elitist multiobjective genetic algorithm: NSGA–II
IEEE Transactions on Evolutionary Computation
(2002) Multicriteria optimization
(2005)
Hybrid metaheuristics for multi-objective combinatorial optimization
Genetic algorithms in search, optimization and machine learning
Pareto adaptive—-dominance
Evolutionary Computation
Multi-objective optimization by means of the thermodynamical genetic algorithm
Combining convergence and diversity in evolutionary multi-objective optimization
Evolutionary Computation
Cited by (70)
Dynamic space reduction optimization framework and its application in hull form optimization
2021, Applied Ocean ResearchA new multi-objective optimization algorithm combined with opposition-based learning
2021, Expert Systems with ApplicationsCitation 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.
Handling multi-objective optimization problems with unbalanced constraints and their effects on evolutionary algorithm performance
2020, Swarm and Evolutionary ComputationTwo-stage storage assignment to minimize travel time and congestion for warehouse order picking operations
2020, Computers and Industrial Engineering
- 1
The author is also associated to the UMI-LAFMIA 3175 CNRS.