Exploiting gradient information in numerical multi--objective evolutionary optimization

ABSTRACT

Various multi--objective evolutionary algorithms (MOEAs) have obtained promising results on various numerical multi--objective optimization problems. The combination with gradient--based local search operators has however been limited to only a few studies. In the single--objective case it is known that the additional use of gradient information can be beneficial. In this paper we provide an analytical parametric description of the set of all non--dominated (i.e. most promising) directions in which a solution can be moved such that its objectives either improve or remain the same. Moreover, the parameters describing this set can be computed efficiently using only the gradients of the individual objectives. We use this result to hybridize an existing MOEA with a local search operator that moves a solution in a randomly chosen non--dominated improving direction. We test the resulting algorithm on a few well--known benchmark problems and compare the results with the same MOEA without local search and the same MOEA with gradient--based techniques that use only one objective at a time. The results indicate that exploiting gradient information based on the non--dominated improving directions is superior to using the gradients of the objectives separately and that it can furthermore improve the result of MOEAs in which no local search is used, given enough evaluations.

REFERENCES

• 1: P. A. N. Bosman and D. Thierens. Exploiting gradient information in continuous iterated density estimation evolutionary algorithms. In B. Kröse et al., editors, Proceedings of the 13th Belgium--Netherlands Artificial Intelligence Conference BNAIC'01, pages 69--76, 2001.
• 2: P. A. N. Bosman and D. Thierens. The balance between proximity and diversity in multi--objective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 7:174--188, 2003.
• 3: P. A. N. Bosman and D. Thierens. The naive MIDEA: a baseline multi--objective EA. In C. A. Coello Coello et al., editors, Evolutionary Multi--Criterion Optimization -- EMO'05, pages 428--442, Berlin, 2005. Springer--Verlag.
• 4: M. Brown and R. E. Smith. Effective use of directional information in multi--objective evolutionary computation. In E. Cantú-Paz et al., editors, Proceedings of the GECCO--2003 Genetic and Evolutionary Computation Conference, pages 778--789, Berlin, 2003. Springer--Verlag.
• 5: K. Deb. Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3):205--230, 1999.
• 6: M. Dellnitz, O. Schütze, and T. Hestermeyer. Covering pareto sets by multilevel subdivision techniques. Journal of Optimization Theory and Applications, 124(1):113--136, 2005.
• 7: J. Fliege and B. F. Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479--494, 2000.
• 8: M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards, 6:409--436, 1952.
• 9: H. Ishibuchi, T. Yoshida, and T. Murata. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 7:204--223, 2003.
• 10: J. D. Knowles and D. Corne. M--PAES: a memetic algorithm for multiobjective optimization. In Proceedings of the 2000 Congress on Evolutionary Computation - CEC--2000, pages 325--332, Piscataway, New Jersey, 2000. IEEE Press.
• 11: J. D. Knowles and D. Corne. On metrics for comparing non--dominated sets. In Proceedings of the 2002 Congress on Evol. Comp. CEC 2002, pages 666--674, Piscataway, New Jersey, 2002. IEEE Press.
• 12: J. D. Knowles and D. W. Corne. A comparison of diverse approaches to memetic multiobjective combinatorial optimization. In W. Hart et al., editors, Proceedings of the Workshop on Memetic Algorithms WOMA at the Genetic and Evolutionary Computation Conference - GECCO--2000, pages 103--108, 2000.
• 13: M. Lahanas, D. Baltas, and S. Giannouli. Global convergence analysis of fast multiobjective gradient based dose optimization algorithms for high-dose-rate brachytherapy. Phys. Med. Biol., 48:599--617, 2003.
• 14: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 15: P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical Report Caltech Concurrent Computation Program, Report. 826, California Institute of Technology, Pasadena, California, 1989.
• 16: H. Mühlenbein and T. Mahnig. FDA -- a scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation, 7:353--376, 1999.
• 17: 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
• 18: J. David Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.93-100, July 01, 1985
• 19: S. Schäffler , R. Schultz , K. Weinzierl, Stochastic method for the solution of unconstrained vector optimization problems, Journal of Optimization Theory and Applications, v.114 n.1, p.209-222, July 2002 [doi>10.1023/A:1015472306888]
• 20: El-Ghazali Talbi , Malek Rahoual , Mohamed Hakim Mabed , Clarisse Dhaenens, A Hybrid Evolutionary Approach for Multicriteria Optimization Problems: Application to the Flow Shop, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.416-428, March 07-09, 2001
• 21: 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]
• 22: Eckart Zitzler , Marco Laumanns , Lothar Thiele , Carlos M. Fonseca , Viviane Grunert da Fonseca, Why Quality Assessment Of Multiobjective Optimizers Is Difficult, Proceedings of the Genetic and Evolutionary Computation Conference, p.666-674, July 09-13, 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

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

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
evolutionary algorithms, gradients, memetic algorithms, multi--objective optimization, numerical optimization