Article

Combining gradient techniques for numerical multi-objective evolutionary optimization

Authors:

Peter A. N. Bosman,

Edwin D. de JongAuthors Info & Claims

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Pages 627 - 634

https://doi.org/10.1145/1143997.1144111

Published: 08 July 2006 Publication History

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]

P. A. N. Bosman and E. D. de Jong. Exploiting gradient information in numerical multi-objective evolutionary optimization. In H.-G. Beyer et al., editors, Proceedings of the GECCO-2005 Genetic and Evolutionary Computation Conference, pages 755--762. ACM Press, New York, New York, 2005.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[6]

L. Davis. Adapting operator probabilities in genetic algorithms. In Proceedings of the 3rd International Conference on Genetic Algorithms, pages 61--69, San Francisco, California, 1989. Morgan Kaufmann.

Digital Library

[7]

K. Deb. Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3):205--230, 1999.

Digital Library

[8]

J. Fliege and B. F. Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479--494, 2000.

[9]

T.-P. Hong, H.-S. Wang, and W.-C. Chen. Simultaneously applying multiple mutation operators in genetic algorithms. Journal of Heuristics, 6:439--455, 2000.

Digital Library

[10]

B. A. Julstrom. What have you done for me lately? Adapting operator probabilities in a steady-state genetic algorithm. In L. Eshelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 81--87, San Francisco, CA, 1995. Morgan Kaufmann.

Digital Library

[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.

Digital Library

[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.

Digital Library

[17]

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes In C: The Art Of Scientific Computing. Cambridge University Press, Cambridge, 1992.

Digital Library

[18]

S. Schäffler, R. Schultz, and K. Weinzierl. Stochastic method for the solution of unconstrained vector optimization problems. Journal of Optimization Theory and Applications, 114(1):209--222, 2002.

Digital Library

[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.

Digital Library

[20]

R. S. Sutton and A. G. Bargo. Reinforcement Learning: an introduction. MIT Press, Cambridge, Massachusetts, 1998.

Digital Library

[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]

D. Thierens. An adaptive pursuit strategy for allocating operator probabilities. In H.-G. Beyer et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference - GECCO - 2005, pages 1539--1546, New York, New York, 2005. ACM Press.

Digital Library

[23]

T. White and F. Oppacher. Adaptive crossover using automata. In Y. Davidor et al., editors, Parallel Problem Solving from Nature - PPSN III. pages 229--238, Berlin, 1994. Springer-Verlag.

Digital Library

[24]

E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results. Evol. Computation, 8(2):173--195, 2000.

Digital Library

[25]

E. Zitzler, M. Laumanns, L. Thiele, C. M. Fonseca, and V. Grunert da Fonseca. Why quality assessment of multiobjective optimizers is difficult. In W. B. Langdon et al., editors, Proceedings of the GECCO-2002 Genetic and Evolutionary Computation Conference, pages 666--674, San Francisco, California, 2002. Morgan Kaufmann.

Digital Library

Cited By

Zhu CZhao XHe XTang Z(2024)Hybrid Optimization Method Based on Coupling Local Gradient Information and Global Evolution MechanismMathematics10.3390/math1208123412:8(1234)Online publication date: 19-Apr-2024
https://doi.org/10.3390/math12081234
Flor-Sánchez CReséndiz-Flores EGarcía-Calvillo I(2023)Kernel-based hybrid multi-objective optimization algorithm (KHMO)Information Sciences: an International Journal10.1016/j.ins.2022.12.095624:C(416-434)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.ins.2022.12.095
Ha DDeist TBosman P(2022)Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource AllocationParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_13(179-192)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_13
Show More Cited By

Index Terms

Combining gradient techniques for numerical multi-objective evolutionary optimization

Recommendations

Exploiting gradient information in numerical multi--objective evolutionary optimization
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

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 ...
Diversifying Multi-Objective Gradient Techniques and their Role in Hybrid Multi-Objective Evolutionary Algorithms for Deformable Medical Image Registration
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Gradient methods and their value in single-objective, real-valued optimization are well-established. As such, they play a key role in tackling real-world, hard optimization problems such as deformable image registration (DIR). A key question is to which ...
Evolutionary Algorithms for Multi-Objective Optimization: Performance Assessments and Comparisons

Evolutionary techniques for multi-objective (MO) optimization are currently gaining significant attention from researchers in various fields due to their effectiveness and robustness in searching for a set of trade-off solutions. Unlike conventional methods ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

July 2006

2004 pages

ISBN:1595931864

DOI:10.1145/1143997

General Chair:
Mike Cattolico
Tiger Mountain Scientific, Inc., USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO06

Sponsor:

GECCO06: Genetic and Evolutionary Computation Conference

July 8 - 12, 2006

Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
51
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu CZhao XHe XTang Z(2024)Hybrid Optimization Method Based on Coupling Local Gradient Information and Global Evolution MechanismMathematics10.3390/math1208123412:8(1234)Online publication date: 19-Apr-2024
https://doi.org/10.3390/math12081234
Flor-Sánchez CReséndiz-Flores EGarcía-Calvillo I(2023)Kernel-based hybrid multi-objective optimization algorithm (KHMO)Information Sciences: an International Journal10.1016/j.ins.2022.12.095624:C(416-434)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.ins.2022.12.095
Ha DDeist TBosman P(2022)Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource AllocationParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_13(179-192)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_13
He XZhou YChen Z(2019)An Evolution Path-Based Reproduction Operator for Many-Objective OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.278522423:1(29-43)Online publication date: Feb-2019
https://doi.org/10.1109/TEVC.2017.2785224
Nguyen MHui SFong A(2017)Submodular Memetic Approximation for Multiobjective Parallel Test Paper GenerationIEEE Transactions on Cybernetics10.1109/TCYB.2016.255207947:6(1562-1575)Online publication date: Jun-2017
https://doi.org/10.1109/TCYB.2016.2552079
Liu TGao XYuan Q(2017)An improved gradient-based NSGA-II algorithm by a new chaotic map modelSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2268-x21:23(7235-7249)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s00500-016-2268-x
Dominguez IAguirre A(2013)Building multivariate density functions based on promising direction vectors2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557766(1702-1709)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557766
Bosman P(2012)On Gradients and Hybrid Evolutionary Algorithms for Real-Valued Multiobjective OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2010.205144516:1(51-69)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1109/TEVC.2010.2051445
Martinez SCoello Coello C(2012)A direct local search mechanism for decomposition-based multi-objective evolutionary algorithms2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6252990(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6252990
Luong HBosman P(2012)Elitist archiving for multi-objective evolutionary algorithmsProceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part II10.1007/978-3-642-32964-7_8(72-81)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32964-7_8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents