Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this work we present a novel and efficient algorithm independent stopping criterion, called the MGBM criterion, suitable for Multiobjective Optimization Evolutionary Algorithms (MOEAs). The criterion, after each iteration of the optimization algorithm, gathers evidence of the improvement of the solutions obtained so far. A global (execution wise) evidence accumulation process inspired by recursive Bayesian estimation decides when the optimization should be stopped. Evidenceis collected using a novel relative improvement measure constructed on top of the Pareto dominance relations. The evidence gathered after each iteration is accumulated and updated following a rule based on a simplified version of a discrete Kalman filter. Our criterion is particularly useful in complex and/or high-dimensional problems where the traditional procedure of stopping after a predefined amount of iterations cannot be used and the waste of computational resources can induceto a detriment of the quality of the results. Although the criterion discussed here is meant for MOEAs,it can be easily adapted to other soft computing or numerical methods by substituting the local improvement metric with a suitable one.

REFERENCES

• 1: Carlos A. Coello, An updated survey of GA-based multiobjective optimization techniques, ACM Computing Surveys (CSUR), v.32 n.2, p.109-143, June 2000 [doi>10.1145/358923.358929]
• 2: C. A. Coello Coello. Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, chapter Recent Trends in Evolutionary Multiobjective Optimization, pages 7--32. Advanced Information and Knowledge Processing. Springer Verlag, 2004.
• 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 Multi-Objective Optimization. Technical Report 112, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, 2001.
• 6: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, chapter Scalable Test Problems for Evolutionary Multiobjective Optimization, pages 105--145. Advanced Information and Knowledge Processing. Springer Verlag, 2004.
• 7: R. E. Kalman. A new approach to linear filtering and prediction problems. Transaction of the ASME - Journal of Basic Engineering, pages 35--45, 1960.
• 8: V. Khare. Performance Scaling of Multi-Objective Evolutionary Algorithms. Master's thesis, School of Computer Science, The University of Birmingham, Edgbaston, Birmingan, UK, September 2002.
• 9: V. Khare, X. Yao, and K. Deb. Performance Scaling of Multi-objective Evolutionary Algorithms. In C. M. Fonseca, P. J. Fleming, E. Zitzler, K. Deb, and L. Thiele, editors, Evolutionary Multi-Criterion Optimization. Second International Conference, EMO 2003, pages 376--390, Faro, Portugal, April 2003. Springer. Lecture Notes in Computer Science. Volume 2632.
• 10: P. S. Maybeck. Stochastic models, estimation, and control, volume 141 of Mathematics in Science and Engineering. Academic Press, 1979.
• 11: O. Rudenko and M. Schoenauer. A steady performance stopping criterion for pareto-based evolutionary algorithms. In The 6th International Multi-Objective Programming and Goal Programming Conference, Hammamet (Tunisia), 2004.
• 12: N. Srinivas and K. Deb. Multiobjective optimization using nondominated sorting in genetic algorithms. Technical report, Department of Mechanical Engineering, Indian Institute of Technology, Kanpur, India, 1993.
• 13: N. Srinivas and K. Deb. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation, 2(3):221--248, Fall 1994.
• 14: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland, May 2001.
• 15: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In K. Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou, and T. Fogarty, editors,EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pages 95--100, Athens, Greece, 2002.
• 16: E. Zitzler and L. Thiele. An Evolutionary Algorithm for Multiobjective Optimization: The Strength Pareto Approach. Technical Report 43, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, May 1998.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms, Experimentation, Performance

Keywords:
MOEAs, multiobjective optimization evolutionary algorithms, stopping criterion