No Access

A CLUSTERING-BASED NICHING FRAMEWORK FOR THE APPROXIMATION OF EQUIVALENT PARETO-SUBSETS

OLIVER KRAMER

Department of Computer Science, Carl von Ossietzky University Oldenburg, Uhlhornsweg 84, 26111 Oldenburg, Germany

Search for more papers by this author

and

HOLGER DANIELSIEK

TU Dortmund, Department of Computer Science, Otto-Hahn-Str. 14, 44221 Dortmund, Germany

Search for more papers by this author

https://doi.org/10.1142/S1469026811003112Cited by:2 (Source: Crossref)

Abstract

In many optimization problems in practice, multiple objectives have to be optimized at the same time. Some multi-objective problems are characterized by multiple connected Pareto-sets at different parts in decision space — also called equivalent Pareto-subsets. We assume that the practitioner wants to approximate all Pareto-subsets to be able to choose among various solutions with different characteristics. In this work, we propose a clustering-based niching framework for multi-objective population-based approaches that allows to approximate equivalent Pareto-subsets. Iteratively, the clustering process assigns the population to niches, and the multi-objective optimization process concentrates on each niche independently. Two exemplary hybridizations, rake selection and DBSCAN, as well as SMS-EMOA and kernel density clustering demonstrate that the niching framework allows enough diversity to detect and approximate equivalent Pareto-subsets.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

A. Augeret al., Theory of the hypervolume indicator: Optimal μ-distributions and the choice of the reference point, FOGA '09 Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithm (2009) pp. 87–102. Google Scholar
N. Beume, B. Naujoks and M. Emmerich, European Journal of Operational Research 181(3), 1653 (2007), DOI: 10.1016/j.ejor.2006.08.008. Crossref, Google Scholar
H. G. Beyer and H. P. Schwefel, Natural Computing 1, 3 (2002), DOI: 10.1023/A:1015059928466. Crossref, Google Scholar
K. Bringmann and T. Friedrich, The maximum hypervolume set yields near-optimal approximation, Proceedings of GECCO, Genetic and Evolutionary Computation Conference (2010) pp. 511–518. Google Scholar
K. P. Chan and T. Ray , An evolutionary algorithm to maintain diversity in the parametric and the objective space , Proceedings of IEEE International Conference on Computational Robotics and Autonomous Systems (CIRAS 2005), page CD proceedings ( IEEE Computer Society Press , 2005 ) . Google Scholar
C. A. Coello Coello , G. B. Lamont and D. A. van Veldhuizen , Evolutionary Algorithms for Solving Multi-Objective Problems , 2nd edn. , Genetic and Evolutionary Computation Series ( Springer Science+Business Media , New York, NY, USA , 2007 ) . Google Scholar
K. A. De Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems, PhD thesis, University of Michigan, Ann Arbor, MI, USA, 1975 . Google Scholar
K. Deb , Multi-Objective Optimization using Evolutionary Algorithms ( John Wiley & Sons , Chichester, UK , 2001 ) . Google Scholar
K. Deb and D. E. Goldberg, An investigation of niche and species formation in genetic function optimization, Proceedings of the Third International Conference on Genetic Algorithms, ed. J. D. Schaffer (Morgan Kaufmann Publishers Inc, San Francisco, CA, USA, 1989) pp. 42–50. Google Scholar
K. Debet al., IEEE Transactions on Evolutionary Computation 6, 182 (2000), DOI: 10.1109/4235.996017. Crossref, Google Scholar
K. Deb and S. Tiwari, European Journal of Operational Research 185(3), 1062 (2008), DOI: 10.1016/j.ejor.2006.06.042. Crossref, Google Scholar
F. Edgeworth , Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences ( C. Kegan Paul and Co , London , 1881 ) . Google Scholar
M. Emmerich, N. Beume and B. Naujoks, An emo algorithm using the hypervolume measure as selection criterion, in EMO (2005), pp. 62–76 . Google Scholar
M. Esteret al., A density-based algorithm for discovering clusters in large spatial databases with noise, Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), eds. E. Simoudis, J. Han and U. Fayyad (AAAI Press, 1996) pp. 226–231. Google Scholar
C. M. Fonseca and P. J. Fleming, ICGA 416 (1993). Google Scholar
D. Goldberg , Genetic Algorithms in Search, Optimization and Machine Learning ( Addison Wesley , 1989 ) . Google Scholar
A. Hinneburg and D. A. Keim, Knowl. Inf. Syst. 5(4), 387 (2003), DOI: 10.1007/s10115-003-0086-9. Crossref, Google Scholar
J. H. Holland , Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence , 2nd edn. ( The MIT Press , Cambridge, MA, USA , 1992 ) . Crossref, Google Scholar
J. Horn, N. Nafpliotis and D. E. Goldberg, A niched pareto genetic algorithm for multiobjective optimization, Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence (1994) pp. 82–87. Google Scholar
O. Kramer and H. Danielsiek, Dbscan-based multi-objective niching to approximate equivalent pareto-subsets, Proceedings of GECCO, Genetic and Evolutionary Computation Conference (2010) pp. 503–510. Google Scholar
O. Kramer and P. Koch, Rake selection: A novel evolutionary multi-objective optimization algorithm, Proceedings of KI 2009: Advances in Artificial Intelligence, 32nd Annual German Conference on AI5803 (Springer, Berlin, 2009) pp. 177–184. Google Scholar
H. W. Kuhn and A. W. Tucker, Nonlinear Programming (1951) pp. 481–492. Google Scholar
S. W. Mahfoud, Crossover interactions among niches, Proceedings of the First IEEE Conference on Evolutionary Computation, ed. Z. Michalewicz (IEEE, 1994) pp. 188–193. Google Scholar
S. W. Mahfoud, Niching Methods for Genetic Algorithms, PhD thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 1995 . Google Scholar
V. Pareto , Cours d'Economie Politique ( Lausanne , 1896 ) . Google Scholar
E. Parzen, Annals of Mathematical Statistics 33, 1065 (1962), DOI: 10.1214/aoms/1177704472. Crossref, Google Scholar
M. Preuss, C. Kausch, C. Bouvy, and F. Henrich, Decision space diversity can be essential for solving multiobjective real-world problems, 634 (2008) 367–377 . Google Scholar
G. Rudolph, B. Naujoks and M. Preuss, Capabilities of emoa to detect and preserve equivalent pareto subsets, EMO 2007: Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization4403, Lecture Notes in Computer Science (Springer, 2007) pp. 36–50. Google Scholar
P. Schnell, Biometrika 6, 47 (1964). Google Scholar
O. M. Shir, Niching in Derandomized Evolution Strategies and its Applications in Quantum Control, PhD thesis, Leiden University, The Netherlands, 2008 . Google Scholar
O. M. Shiret al., Enhancing decision space diversity in evolutionary multiobjective algorithms, EMO '09: Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization (Springer-Verlag, Berlin, Heidelberg, 2009) pp. 95–109. Google Scholar
N. Srinivas and K. Deb, Evolutionary Computation 2, 221 (1994), DOI: 10.1162/evco.1994.2.3.221. Crossref, Google Scholar
A. Thom and O. Kramer, Acceleration of dbscan-based clustering with reduced neighborhood evaluations, in KI, (2010), pp. 195–202 . Google Scholar
T. Ulrich, J. Bader and E. Zitzler, Integrating decision space diversity into hypervolume-based multiobjective search, Proceedings of GECCO, Genetic and Evolutionary Computation Conference (2010) pp. 455–462. Google Scholar
D. A. van Veldhuizen and G. B. Lamont, Evolutionary Computation 8(2), 125 (2000). Crossref, Google Scholar
A. Zhou, Q. Zhang and Y. Jin, Transaction on Evolutionary Computation 13(5), 1167 (2009). Crossref, Google Scholar
E. Zitzler, M. Laumanns and L. Thiele, SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization, Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001) (International Center for Numerical Methods in Engineering (CIMNE), 2002) pp. 95–100. Google Scholar
E. Zitzler and L. Thiele, IEEE Transactions on Evolutionary Computation 3(4), 257 (1999), DOI: 10.1109/4235.797969. Crossref, Google Scholar
J. B. Zydallis, D. A. van Veldhuizen and G. B. Lamont, A statistical comparison of multiobjective evolutionary algorithms including the momga-ii, in EMO (2001), pp. 226–240 . Google Scholar