Fast Pareto Optimization Using Sliding Window Selection

Frank Neumann; Carsten Witt

doi:10.3233/FAIA230463

Fast Pareto Optimization Using Sliding Window Selection

Frank Neumann^*
, Carsten Witt

^*Corresponding author for this work

University of Adelaide

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

79 Downloads (Orbit)

Abstract

Pareto optimization using evolutionary multi-objective algorithms such as the classical GSEMO algorithm has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime of the classical GSEMO algorithm and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.

Original language	English
Title of host publication	Proceedings of the 26^th European Conference on Artificial Intelligence, including 12^th Conference on Prestigious Applications of Intelligent Systems
Editors	Kobi Gal, Kobi Gal, Ann Nowe, Grzegorz J. Nalepa, Roy Fairstein, Roxana Radulescu
Publisher	IOS Press BV
Publication date	28 Sept 2023
Pages	1771-1778
ISBN (Electronic)	9781643684369
DOIs	https://doi.org/10.3233/FAIA230463
Publication status	Published - 28 Sept 2023
Event	26^th European Conference on Artificial Intelligence - Krakow, Poland Duration: 30 Sept 2023 → 4 Oct 2023

Conference

Conference	26^th European Conference on Artificial Intelligence
Country/Territory	Poland
City	Krakow
Period	30/09/2023 → 04/10/2023

Series	Frontiers in Artificial Intelligence and Applications
Volume	372
ISSN	0922-6389

Bibliographical note

Funding Information:
This work has been supported by the Australian Research Council (ARC) through grant FT200100536 and by the Independent Research Fund Denmark through grant 10.46540/2032–00101B.

Publisher Copyright:
© 2023 The Authors.

Access to Document

10.3233/FAIA230463

FulltextFinal published version, 337 KB

OpenUrl availability

Full text

Cite this

Neumann, F., & Witt, C. (2023). Fast Pareto Optimization Using Sliding Window Selection. In K. Gal, K. Gal, A. Nowe, G. J. Nalepa, R. Fairstein, & R. Radulescu (Eds.), Proceedings of the 26^th European Conference on Artificial Intelligence, including 12^th Conference on Prestigious Applications of Intelligent Systems (pp. 1771-1778). IOS Press BV. https://doi.org/10.3233/FAIA230463

Neumann, Frank ; Witt, Carsten. / Fast Pareto Optimization Using Sliding Window Selection. Proceedings of the 26^th European Conference on Artificial Intelligence, including 12^th Conference on Prestigious Applications of Intelligent Systems. editor / Kobi Gal ; Kobi Gal ; Ann Nowe ; Grzegorz J. Nalepa ; Roy Fairstein ; Roxana Radulescu. IOS Press BV, 2023. pp. 1771-1778 (Frontiers in Artificial Intelligence and Applications, Vol. 372).

@inproceedings{a1c3e9b9bc604dad85533eca09b1cd95,

title = "Fast Pareto Optimization Using Sliding Window Selection",

abstract = "Pareto optimization using evolutionary multi-objective algorithms such as the classical GSEMO algorithm has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime of the classical GSEMO algorithm and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.",

author = "Frank Neumann and Carsten Witt",

note = "Funding Information: This work has been supported by the Australian Research Council (ARC) through grant FT200100536 and by the Independent Research Fund Denmark through grant 10.46540/2032–00101B. Publisher Copyright: {\textcopyright} 2023 The Authors.; 26<sup>th</sup> European Conference on Artificial Intelligence, ECAI 2023 ; Conference date: 30-09-2023 Through 04-10-2023",

year = "2023",

month = sep,

day = "28",

doi = "10.3233/FAIA230463",

language = "English",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press BV",

pages = "1771--1778",

editor = "Kobi Gal and Kobi Gal and Ann Nowe and Nalepa, \{Grzegorz J.\} and Roy Fairstein and Roxana Radulescu",

booktitle = "Proceedings of the 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems",

}

Neumann, F & Witt, C 2023, Fast Pareto Optimization Using Sliding Window Selection. in K Gal, K Gal, A Nowe, GJ Nalepa, R Fairstein & R Radulescu (eds), Proceedings of the 26^th European Conference on Artificial Intelligence, including 12^th Conference on Prestigious Applications of Intelligent Systems. IOS Press BV, Frontiers in Artificial Intelligence and Applications, vol. 372, pp. 1771-1778, 26^th European Conference on Artificial Intelligence, Krakow, Poland, 30/09/2023. https://doi.org/10.3233/FAIA230463

Fast Pareto Optimization Using Sliding Window Selection. / Neumann, Frank; Witt, Carsten.
Proceedings of the 26^th European Conference on Artificial Intelligence, including 12^th Conference on Prestigious Applications of Intelligent Systems. ed. / Kobi Gal; Kobi Gal; Ann Nowe; Grzegorz J. Nalepa; Roy Fairstein; Roxana Radulescu. IOS Press BV, 2023. p. 1771-1778 (Frontiers in Artificial Intelligence and Applications, Vol. 372).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Fast Pareto Optimization Using Sliding Window Selection

AU - Neumann, Frank

AU - Witt, Carsten

N1 - Funding Information: This work has been supported by the Australian Research Council (ARC) through grant FT200100536 and by the Independent Research Fund Denmark through grant 10.46540/2032–00101B. Publisher Copyright: © 2023 The Authors.

PY - 2023/9/28

Y1 - 2023/9/28

N2 - Pareto optimization using evolutionary multi-objective algorithms such as the classical GSEMO algorithm has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime of the classical GSEMO algorithm and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.

AB - Pareto optimization using evolutionary multi-objective algorithms such as the classical GSEMO algorithm has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime of the classical GSEMO algorithm and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.

U2 - 10.3233/FAIA230463

DO - 10.3233/FAIA230463

M3 - Article in proceedings

AN - SCOPUS:85175857137

T3 - Frontiers in Artificial Intelligence and Applications

SP - 1771

EP - 1778

BT - Proceedings of the 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems

A2 - Gal, Kobi

A2 - Nowe, Ann

A2 - Nalepa, Grzegorz J.

A2 - Fairstein, Roy

A2 - Radulescu, Roxana

PB - IOS Press BV

T2 - 26<sup>th</sup> European Conference on Artificial Intelligence

Y2 - 30 September 2023 through 4 October 2023

ER -

Neumann F, Witt C. Fast Pareto Optimization Using Sliding Window Selection. In Gal K, Gal K, Nowe A, Nalepa GJ, Fairstein R, Radulescu R, editors, Proceedings of the 26^th European Conference on Artificial Intelligence, including 12^th Conference on Prestigious Applications of Intelligent Systems. IOS Press BV. 2023. p. 1771-1778. (Frontiers in Artificial Intelligence and Applications, Vol. 372). doi: 10.3233/FAIA230463

Fast Pareto Optimization Using Sliding Window Selection

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this