A pareto following variation operator for fast-converging multiobjective evolutionary algorithms

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 used to approximate the future front from the current available fronts with acceptable accuracy levels. However, the associated computational costs limit their effectiveness. In this work, we introduce a simple approach that has comparatively smaller computational cost and we have developed this model as a variation operator that can be used in any kind of multiobjective optimizer. When designing this model, we have considered the whole search procedure as a dynamic system that takes available objective values in current front as input and generates approximated design variables for the next front as output. Initial simulation experiments have produced encouraging results in comparison to NSGA-II. Our motivation was to increase the speed of the hosting optimizer. We have compared the performance of the algorithm with respect to the total number of function evaluation and Hypervolume metric. This variation operator has worst case complexity of O(nkN³), where N is the population size, n and k is the number of design variables and objectives respectively.

REFERENCES

• 1: S. Adra, A. Hamody, I. Griffin, and P. J. Fleming. A Hybrid Multi-objective Evolutionary Algorithm Using an Inverse Neural Network for Aircraft Control System Design. In IEEE Congress on Evolutionary Computation (CEC-2005), volume 1, pages 1--8, Edinburgh, UK, September 2005. IEEE Pres.
• 2: 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]
• 3: Peter A. N. Bosman , Edwin D. de Jong, Exploiting gradient information in numerical multi--objective evolutionary optimization, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068138]
• 4: Peter A. N. Bosman , Edwin D. de Jong, Combining gradient techniques for numerical multi-objective evolutionary optimization, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144111]
• 5: J. Branke, T. Kaußler, and H. Schmeck. Guiding Multi-Objective Evolutionary Algorithms Towards Interesting Regions. In I. C. Parmee, editor, Fourth International Conference on Adaptive Computing in Design and Manufacture (ACDM 2000), Poster Proceedings, pages 1--4, Plymouth, UK, 2000. Plymouth Engineering Design Centre, University of Plymouth.
• 6: M. Brown and R. E. Smith. Effective Use of Directional Information in Multi-objective Evolutionary Computation. In The 5th Annual Conference on Genetic and Evolutionary Computation (GECCO-2003), volume 2723/2003 of LNCS, pages 778--789, Chicago, Illinois, USA, 2003. Springer.
• 7: M. Brown and R. E. Smith. Directed Multiobjective Optimization. International Journal of Computers, Systems and Signals, 6(1):3--17, 2005.
• 8: D. Buche, N. Schraudolph, and P. Koumoutsakos. Accelerating Evolutionary Algorithms with Gaussian Process Fitness Function Models. IEEE Transactions on Systems, Man, and Cybernetics, 35(2):183--194, May 2005.
• 9: D. Chafekar, L. Shi, K. Rasheed, and J. Xuan. Multiobjective GA Optimization Using Reduced Models. IEEE Transactions on Systems, Man, and Cybernetics, 35(2):261--265, May 2005.
• 10: 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
• 11: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 12: 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.
• 13: 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.
• 14: 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.
• 15: Ken Harada , Jun Sakuma , Shigenobu Kobayashi, Local search for multiobjective function optimization: pareto descent method, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144115]
• 16: S. Huband, P. Hingston, L. Barone, and L. While. A Review of Multiobjective Test Problems and a Scalable Test Problem Toolkit. IEEE Transaction on Evolutionary Computation, 10(5):477--506, October 2006.
• 17: Y. Jin, A comprehensive survey of fitness approximation in evolutionary computation, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.1, p.3-12, January 2005 [doi>10.1007/s00500-003-0328-5]
• 18: Y. Jin, M. Olhofer, and B. Sendhoff. A Framework for Evolutionary Optimization with Approximate Fitness Functions. IEEE Transactions on Evolutionary Computation, 6(5):481--494, October 2002.
• 19: 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]
• 20: J. Knowles. ParEGO: A Hybrid Algorithm with On-line Landscape Approximation for Expensive Multiobjective Optimization Problems. IEEE Transactions on Evolutionary Computation, 10(1):50--66, February 2006.
• 21: Dudy Lim , Yew-Soon Ong , Yaochu Jin , Bernhard Sendhoff, A study on metamodeling techniques, ensembles, and multi-surrogates in evolutionary computation, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277203]
• 22: 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.
• 23: Lennart Ljung, System identification (2nd ed.): theory for the user, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 24: Lennart Ljung , Torkel Glad, Modeling of dynamic systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 25: P. K. Nain and K. Deb. Computationally Effective Search and Optimization Procedure Using Coarse to Fine Approximations. In IEEE Congress on Evolutionary Computation (CEC-2003), volume 3, pages 2081--2088, Canberra, NSW, Australia, December 2003. IEEE Press.
• 26: 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]
• 27: Y. S. Ong , K. Y. Lum , P. B. Nair, Hybrid evolutionary algorithm with Hermite radial basis function interpolants for computationally expensive adjoint solvers, Computational Optimization and Applications, v.39 n.1, p.97-119, January 2008 [doi>10.1007/s10589-007-9065-5]
• 28: Y. S. Ong, P. B. Nair, and A. J. Keane. Evolutionary Optimization of Computationally Expensive Problems via Surrogate Modeling. American Institute of Aeronautics and Astronautics Journal, 41(4):689--696, 2003.
• 29: Y.-S. Ong, P. B. Nair, and K. Lum. Max-Min Surrogate-Assisted Evolutionary Algorithm for Robust Design. IEEE Transactions on Evolutionary Computation, 10(4):392--404, August 2006.
• 30: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 31: T. Ray and W. Smith. A Surrogate Assisted Parallel Multiobjective Evolutionary Algorithm for Robust Engineering Design. Engineering Optimization, 38(8):997--1011, 2006.
• 32: H. Soh, Y. S. Ong, M. Salahuddin, T. Hung, and B. S. Lee. Playing in the Objective Space: Coupled Approximators for Multi-Objective Optimization. In IEEE Symposium on Computational Intelligence in Multicriteria Decision Making (ICDM-2007), pages 325--332. IEEE Press, April 2007.
• 33: D. E. Stewart and Z. Leyk. Meschach: Matrix Computations in C. In Centre for Mathematics and Its Applications, volume 32, Australian National University, Canberra, Australia, 1994. Available at: http://www.netlib.org/c/meschach/ and http://www.math.uiowa.edu/~dstewart/meschach/.
• 34: Z. Zhou, Y. S. Ong, P. B. Nair, A. J. Keane, and K. Y. Lum. Combining Global and Local Surrogate Models to Accelerate Evolutionary Optimization. IEEE Transactions on Systems, Man, and Cybernetics, 37(1):66--76, January 2007.
• 35: 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]

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