Abstract
Evolutionary algorithms (EAs) have been widely and successfully applied to solve multi-objective optimization problems, due to their nature of population-based search. Population update is a key component in multi-objective EAs (MOEAs), and it is performed in a greedy, deterministic manner. That is, the next-generation population is formed by selecting the first population-size ranked solutions (based on some selection criteria, e.g., non-dominated sorting, crowdedness and indicators) from the collections of the current population and newly-generated solutions. In this paper, we question this practice. We analytically present that introducing randomness into the population update procedure in MOEAs can be beneficial for the search. More specifically, we prove that the expected running time of a well-established MOEA (SMS-EMOA) for solving a commonly studied bi-objective problem, OneJumpZeroJump, can be exponentially decreased if replacing its deterministic population update mechanism by a stochastic one. Empirical studies also verify the effectiveness of the proposed stochastic population update method. This work is an attempt to challenge a common practice for the population update in MOEAs. Its positive results, which might hold more generally, should encourage the exploration of developing new MOEAs in the area.
Original language | English |
---|---|
Title of host publication | Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence |
Editors | Edith Elkind |
Publisher | International Joint Conferences on Artificial Intelligence |
Pages | 5513-5521 |
Number of pages | 9 |
ISBN (Electronic) | 9781956792034 |
DOIs | |
Publication status | Published - 25 Aug 2023 |
Event | 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 - Macao, China Duration: 19 Aug 2023 → 25 Aug 2023 |
Publication series
Name | IJCAI International Joint Conference on Artificial Intelligence |
---|---|
ISSN (Print) | 1045-0823 |
Conference
Conference | 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023 |
---|---|
Country/Territory | China |
City | Macao |
Period | 19/08/23 → 25/08/23 |
Bibliographical note
Funding Information:∗This work was supported by the National Science Foundation of China (62022039, 62276124). Chao Qian is the corresponding author.
Publisher Copyright:
© 2023 International Joint Conferences on Artificial Intelligence. All rights reserved.
ASJC Scopus subject areas
- Artificial Intelligence