Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation

Damy M.F. Ha; Timo M. Deist; Peter A.N. Bosman

doi:10.1007/978-3-031-14721-0_13

Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation

Damy M.F. Ha^*, Timo M. Deist, Peter A.N. Bosman

^*Corresponding author for this work

Algorithmics

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

29 Downloads (Pure)

Abstract

Evolutionary algorithms (EAs) are well-known to be well suited for multi-objective (MO) optimization. However, especially in the case of real-valued variables, classic domination-based approaches are known to lose selection pressure when approaching the Pareto set. Indicator-based approaches, such as optimizing the uncrowded hypervolume (UHV), can overcome this issue and ensure that individual solutions converge to the Pareto set. Recently, a gradient-based UHV algorithm, known as UHV-ADAM, was shown to be more efficient than (UHV-based) EAs if few local optima are present. Combining the two techniques could exploit synergies, i.e., the EA could be leveraged to avoid local optima while the efficiency of gradient algorithms could speed up convergence to the Pareto set. It is a priori however not clear what would be the best way to make such a combination. In this work, therefore, we study the use of a dynamic resource allocation scheme to create hybrid UHV-based algorithms. On several bi-objective benchmarks, we find that the hybrid algorithms produce similar or better results than the EA or gradient-based algorithm alone, even when finite differences are used to approximate gradients. The implementation of the hybrid algorithm is available at https://github.com/damyha/uncrowded-hypervolume.

Original language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings
Editors	Günter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
Publisher	Springer
Pages	179-192
Number of pages	14
ISBN (Print)	9783031147203
DOIs	https://doi.org/10.1007/978-3-031-14721-0_13
Publication status	Published - 2022
Event	17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 - Dortmund, Germany Duration: 10 Sept 2022 → 14 Sept 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13399 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Country/Territory	Germany
City	Dortmund
Period	10/09/22 → 14/09/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Hybrid algorithm
Multi-objective
Real-valued optimization

Access to Document

10.1007/978-3-031-14721-0_13

978-3-031-14721-0_13Final published version, 344 KB

Cite this

Ha, D. M. F., Deist, T. M., & Bosman, P. A. N. (2022). Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation. In G. Rudolph, A. V. Kononova, H. Aguirre, P. Kerschke, G. Ochoa, & T. Tušar (Eds.), Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings (pp. 179-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13399 LNCS). Springer. https://doi.org/10.1007/978-3-031-14721-0_13

Ha, Damy M.F. ; Deist, Timo M. ; Bosman, Peter A.N. / Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation. Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. editor / Günter Rudolph ; Anna V. Kononova ; Hernán Aguirre ; Pascal Kerschke ; Gabriela Ochoa ; Tea Tušar. Springer, 2022. pp. 179-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f8cd73d609624d48a5fc7db09ae1eb57,

title = "Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation",

abstract = "Evolutionary algorithms (EAs) are well-known to be well suited for multi-objective (MO) optimization. However, especially in the case of real-valued variables, classic domination-based approaches are known to lose selection pressure when approaching the Pareto set. Indicator-based approaches, such as optimizing the uncrowded hypervolume (UHV), can overcome this issue and ensure that individual solutions converge to the Pareto set. Recently, a gradient-based UHV algorithm, known as UHV-ADAM, was shown to be more efficient than (UHV-based) EAs if few local optima are present. Combining the two techniques could exploit synergies, i.e., the EA could be leveraged to avoid local optima while the efficiency of gradient algorithms could speed up convergence to the Pareto set. It is a priori however not clear what would be the best way to make such a combination. In this work, therefore, we study the use of a dynamic resource allocation scheme to create hybrid UHV-based algorithms. On several bi-objective benchmarks, we find that the hybrid algorithms produce similar or better results than the EA or gradient-based algorithm alone, even when finite differences are used to approximate gradients. The implementation of the hybrid algorithm is available at https://github.com/damyha/uncrowded-hypervolume.",

keywords = "Hybrid algorithm, Multi-objective, Real-valued optimization",

author = "Ha, {Damy M.F.} and Deist, {Timo M.} and Bosman, {Peter A.N.}",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022 ; Conference date: 10-09-2022 Through 14-09-2022",

year = "2022",

doi = "10.1007/978-3-031-14721-0_13",

language = "English",

isbn = "9783031147203",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "179--192",

editor = "G{\"u}nter Rudolph and Kononova, {Anna V.} and Hern{\'a}n Aguirre and Pascal Kerschke and Gabriela Ochoa and Tea Tu{\v s}ar",

booktitle = "Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings",

}

Ha, DMF, Deist, TM & Bosman, PAN 2022, Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation. in G Rudolph, AV Kononova, H Aguirre, P Kerschke, G Ochoa & T Tušar (eds), Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13399 LNCS, Springer, pp. 179-192, 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022, Dortmund, Germany, 10/09/22. https://doi.org/10.1007/978-3-031-14721-0_13

Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation. / Ha, Damy M.F.; Deist, Timo M.; Bosman, Peter A.N.
Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. ed. / Günter Rudolph; Anna V. Kononova; Hernán Aguirre; Pascal Kerschke; Gabriela Ochoa; Tea Tušar. Springer, 2022. p. 179-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13399 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation

AU - Ha, Damy M.F.

AU - Deist, Timo M.

AU - Bosman, Peter A.N.

N1 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2022

Y1 - 2022

N2 - Evolutionary algorithms (EAs) are well-known to be well suited for multi-objective (MO) optimization. However, especially in the case of real-valued variables, classic domination-based approaches are known to lose selection pressure when approaching the Pareto set. Indicator-based approaches, such as optimizing the uncrowded hypervolume (UHV), can overcome this issue and ensure that individual solutions converge to the Pareto set. Recently, a gradient-based UHV algorithm, known as UHV-ADAM, was shown to be more efficient than (UHV-based) EAs if few local optima are present. Combining the two techniques could exploit synergies, i.e., the EA could be leveraged to avoid local optima while the efficiency of gradient algorithms could speed up convergence to the Pareto set. It is a priori however not clear what would be the best way to make such a combination. In this work, therefore, we study the use of a dynamic resource allocation scheme to create hybrid UHV-based algorithms. On several bi-objective benchmarks, we find that the hybrid algorithms produce similar or better results than the EA or gradient-based algorithm alone, even when finite differences are used to approximate gradients. The implementation of the hybrid algorithm is available at https://github.com/damyha/uncrowded-hypervolume.

AB - Evolutionary algorithms (EAs) are well-known to be well suited for multi-objective (MO) optimization. However, especially in the case of real-valued variables, classic domination-based approaches are known to lose selection pressure when approaching the Pareto set. Indicator-based approaches, such as optimizing the uncrowded hypervolume (UHV), can overcome this issue and ensure that individual solutions converge to the Pareto set. Recently, a gradient-based UHV algorithm, known as UHV-ADAM, was shown to be more efficient than (UHV-based) EAs if few local optima are present. Combining the two techniques could exploit synergies, i.e., the EA could be leveraged to avoid local optima while the efficiency of gradient algorithms could speed up convergence to the Pareto set. It is a priori however not clear what would be the best way to make such a combination. In this work, therefore, we study the use of a dynamic resource allocation scheme to create hybrid UHV-based algorithms. On several bi-objective benchmarks, we find that the hybrid algorithms produce similar or better results than the EA or gradient-based algorithm alone, even when finite differences are used to approximate gradients. The implementation of the hybrid algorithm is available at https://github.com/damyha/uncrowded-hypervolume.

KW - Hybrid algorithm

KW - Multi-objective

KW - Real-valued optimization

UR - http://www.scopus.com/inward/record.url?scp=85137269429&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-14721-0_13

DO - 10.1007/978-3-031-14721-0_13

M3 - Conference contribution

AN - SCOPUS:85137269429

SN - 9783031147203

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 179

EP - 192

BT - Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings

A2 - Rudolph, Günter

A2 - Kononova, Anna V.

A2 - Aguirre, Hernán

A2 - Kerschke, Pascal

A2 - Ochoa, Gabriela

A2 - Tušar, Tea

PB - Springer

T2 - 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022

Y2 - 10 September 2022 through 14 September 2022

ER -

Ha DMF, Deist TM, Bosman PAN. Hybridizing Hypervolume-Based Evolutionary Algorithms and Gradient Descent by Dynamic Resource Allocation. In Rudolph G, Kononova AV, Aguirre H, Kerschke P, Ochoa G, Tušar T, editors, Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings. Springer. 2022. p. 179-192. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-14721-0_13