Accelerating convergence using rough sets theory for multi-objective optimization problems

ABSTRACT

We propose the use of rough sets theory to improve the first approximation provided by a multi-objective evolutionary algorithm and retain the nondominated solutions using a new adaptive grid based on the ε-dominance concept that tries to overcome the main limitation of ε-dominance: the loss of several nondominated solutions from the hypergrid adopted in the archive because of the way in which solutions are selected within each box. We decided to use a multi-objective version of differential evolution to build a first approximation of the Pareto front and in a second stage, we use the rough sets theory in order to improve the spread of the solutions found so far. To assess our proposed hybrid approach, we adopt a set of standard test functions and metrics taken from the specialized literature. Our results are compared with respect to the NSGA-II, which is an approach representative of the state-of-the-art in the area.

REFERENCES

• 1: H. A. Abbass. The Self-Adaptive Pareto Differential Evolution Algorithm. In Congress on Evolutionary Computation (CEC'2002), volume 1, pages 831--836, Piscataway, New Jersey, May 2002. IEEE Service Center.
• 2: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 3: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 4: K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, April 2002.
• 5: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Test Problems for Evolutionary Multiobjective Optimization. In A. Abraham, L. Jain, and R. Goldberg, editors, Evolutionary Multiobjective Optimization. Theoretical Advances and Applications, pages 105--145. Springer, USA, 2005.
• 6: Matthias Ehrgott, Multicriteria Optimization, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 7: Alfredo G. Hernández-Díaz , Luis V. Santana-Quintero , Carlos A. Coello Coello , Julián Molina, Pareto-adaptive ε-dominance, Evolutionary Computation, v.15 n.4, p.493-517, Winter 2007 [doi>10.1162/evco.2007.15.4.493]
• 8: S. Kukkonen and J. Lampinen. An Extension of Generalized Differential Evolution for Multi-objective Optimization with Constraints. In Parallel Problem Solving from Nature - PPSN VIII, pages 752--761, Birmingham, UK, September 2004. Springer-Verlag. Lecture Notes in Computer Science Vol. 3242.
• 9: Z. Pawlak. Rough sets. International Journal of Computer and Information Sciences, 11(1):341--356, Summer 1982.
• 10: T. Robič and B. Filipič. DEMO: Differential Evolution for Multiobjective Optimization. In C. A. C. Coello, A. Hernández, and E. Zitzler, editors, Evolutionary Multi-Criterion Optimization. Third International Conference, EMO 2005, pages 520--533, Guanajuato, México, March 2005. Springer. Lecture Notes in Computer Science Vol. 3410.
• 11: L. V. Santana-Quintero and C. A. C. Coello. An Algorithm Based on Differential Evolution for Multi-objective Problems. International Journal of Computational Intelligence Research, 1(2):151--169, 2005.
• 12: R. Storn and K. Price. Differential evolution - a simple and efficient adaptative scheme for global optimization over continuous spaces. Technical Report TR-95- 12, International Computer Science, Berkeley, California, March 1995.
• 13: Rainer Storn , Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, v.11 n.4, p.341-359, December 1997 [doi>10.1023/A:1008202821328]
• 14: Eckart Zitzler , Kalyanmoy Deb , Lothar Thiele, Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation, v.8 n.2, p.173-195, June 2000 [doi>10.1162/106365600568202]
• 15: E. Zitzler and L. Thiele. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3(4):257--271, November 1999.
• 16: E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G.da Fonseca. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117--132, Summer 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
local search, multi-objective optimization, rough sets theory