Combining gradient techniques for numerical multi-objective evolutionary optimization

ABSTRACT

Recently, gradient techniques for solving numerical multi-objective optimization problems have appeared in the literature. Although promising results have already been obtained when combined with multi-objective evolutionary algorithms (MOEAs), an important question remains: what is the best way to integrate the use of gradient techniques in the evolutionary cycle of a MOEA. In this paper, we present an adaptive resource-allocation scheme that uses three gradient techniques in addition to the variation operator in a MOEA. During optimization, the effectivity of the gradient techniques is monitored and the available computational resources are redistributed to allow the (currently) most effective operator to spend the most resources. In addition, we indicate how the multi-objective search can be stimulated to also search $mboxemphalong $ the Pareto front, ultimately resulting in a better and wider spread of solutions. We perform tests on a few well-known benchmark problems as well as two novel benchmark problems with specific gradient properties. We compare the results of our adaptive resource-allocation scheme with the same MOEA without the use of gradient techniques and a scheme in which resource allocation is constant. The results show that our proposed adaptive resource-allocation scheme makes proper use of the gradient techniques only when required and thereby leads to results that are close to the best results that can be obtained by fine-tuning the resource allocation for a specific problem.

REFERENCES

• 1: T. Bäck. Self-adaptation in genetic algorithms. In F. J. Varela and P. Bourgine, editors, Proceedings of the 1st European Conference on Artificial Life, pages 227--235, Cambridge, MA, 1992. MIT Press.
• 2: 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]
• 3: 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.
• 4: 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.
• 5: 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.
• 6: Lawrence Davis, Adapting Operator Probabilities in Genetic Algorithms, Proceedings of the 3rd International Conference on Genetic Algorithms, p.61-69, June 01, 1989
• 7: K. Deb. Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3):205--230, 1999.
• 8: J. Fliege and B. F. Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479--494, 2000.
• 9: Tzung-Pei Hong , Hong-Shung Wang , Wei-Chou Chen, Simultaneously Applying Multiple Mutation Operators in Genetic Algorithms, Journal of Heuristics, v.6 n.4, p.439-455, September 2000 [doi>10.1023/A:1009642825198]
• 10: Bryant A. Julstrom, What Have You Done for Me Lately? Adapting Operator Probabilities in a Steady-State Genetic Algorithm, Proceedings of the 6th International Conference on Genetic Algorithms, p.81-87, July 15-19, 1995
• 11: B. A. Julstrom. Adaptive operator probabilities. In J. Alander, editor, Proceedings of the Second Nordic Workshop on Genetic Algorithms and their Applications (2NWGA), 1996.
• 12: 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.
• 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: J. Layton and P. Foster. Error-prone DNA polymerase IV is controlled by the stress-response sigma factor, RpoS, in Escherichia coli. Molec. Microbiology, 50(2):549--561, 2003.
• 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: 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]
• 19: O. Schütze, S. Mostaghim, M. Dellnitz, and J. Teich. Covering Pareto sets by multilevel evolutionary subdivision techniques. In Carlos M. Fonseca et al., editors, Evolutionary Multi-Criterion Optimization - EMO '03, pages 118--132, Berlin, 2003. Springer-Verlag.
• 20: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 21: M. A. L. Thathachar and P. S. Sastry. A class of rapidly converging algorithms for learning automata. IEEE Transactions on Systems, Man and Cybernetics, SMC-15:168--175, 1985.
• 22: Dirk Thierens, An adaptive pursuit strategy for allocating operator probabilities, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068251]
• 23: Tony White , Franz Oppacher, Adaptive Crossover Using Automata, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.229-238, October 09-14, 1994
• 24: 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]
• 25: 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
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation, Performance, Theory

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