Towards high speed multiobjective evolutionary optimizers

ABSTRACT

One of the major difficulties when applying Multiobjective Evolutionary Algorithms (MOEA) to real world problems is the large number of objective function evaluations. Approximate (or surrogate) methods offer the possibility of reducing the number of evaluations, without reducing solution quality. Artificial Neural Network (ANN) based models are one approach that have been utilized to approximate the future front from the current available fronts with acceptable accuracy levels. However, the associated computational costs limit their effectiveness. In this research project, we have developed a simple approximation technique with comparatively smaller computational cost. Our model, has been developed as a variation operator that can be utilized in any kind of multiobjective optimizer. Initial simulation experiments have produced encouraging results in comparison to other existing sequential algorithms (i.e. NSGA-II, SPEA-II). In the next phase of the project, this model will be integrated into other existing parallel MOEA's to solve more complex and time intensive bench mark problems.

REFERENCES

• 1: Salem Fawaz Adra , Ian Griffin , Peter J. Fleming, An informed convergence accelerator for evolutionary multiobjective optimiser, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277110]
• 2: M. Emmerich, K. Giannakoglou, and B. Naujoks. Single- and Multiobjective Evolutionary Optimization Assisted by Gaussian Random Field Metamodels. IEEE Transactions on Evolutionary Computation, 10(4):421--439, August 2006.
• 3: M. Farina. A Neural Network Based Generalized Response Surface Multiobjective Evolutionary Algorithm. In IEEE Congress on Evolutionary Computation (CEC-2002), volume 1, pages 956--961, Honolulu, HI, May 2002. IEEE Press.
• 4: M. Farina, K. Deb, and P. Amato. Dynamic multiobjective optimization problems: Test cases, approximations, and applications. IEEE Transactions on Evolutionary Computation, 8(5):425--442, October 2004.
• 5: A. Gaspar-Cunha and A. Vieira. A Multiobjective Evolutionary Algorithm Using Neural Networks to Approximate Fitness Evaluations. International Journal of Computers, Systems and Signals, 6(1):18--36, 2005.
• 6: Michael Kirley , Robert Stewart, An analysis of the effects of population structure on scalable multiobjective optimization problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277124]
• 7: W. Liu, Q. Zhang, E. P. K. Tsang, C. Liu, and B. Virginas. On the Performance of Metamodel Assisted MOEA/D. In L. Kang, Y. Liu, and S. Y. Zeng, editors, ISICA-2007, volume 4683 of LNCS, pages 547--557, Wuhan, China, August 2007. Springer.
• 8: Lennart Ljung, System identification (2nd ed.): theory for the user, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 9: Lennart Ljung , Torkel Glad, Modeling of dynamic systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 10: Antonio J. Nebro , Enrique Alba , Francisco Luna, Multi-Objective Optimization using Grid Computing, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.11 n.6, p.531-540, January 2007 [doi>10.1007/s00500-006-0096-0]
• 11: F. Streichert, H. Ulmer, and A. Zell. Parallelization of multi-objective evolutionary algorithms using clustering algorithms. In C. A. C. Coello, A. H. Aguirre, and E. Zitzler, editors, EMO, volume 3410 of Lecture Notes in Computer Science, pages 92--107. Springer, 2005.
• 12: A. K. A. Talukder and M. Kirley. A Pareto Following Variation Operator for Evolutionary Dynamic Multi-objective Optimization. In Proceedings of the IEEE Congress on Evolutionary Computation 2008 (CEC 2008), Hong Kong, China, June 1-6 2008. IEEE Press, Piscataway, NJ. Accepted, To be published.
• 13: A.K.M. Khaled Ahsan Talukder , Michael Kirley , Rajkumar Buyya, A pareto following variation operator for fast-converging multiobjective evolutionary algorithms, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389234]
• 14: D. Van Veldhuizen, J. Zydallis, and G. Lamont. Considerations in engineering parallel multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 7(2):144--173, April 2003.

INDEX TERMS

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

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:
dynamic system identification, evolutionary multiobjective optimization, function evaluation, variation operator