An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms
Authors: Chao Bian, Shengjie Ren, Miqing Li, Chao Qian
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In the previous sections, we have proved that when an archive is used in NSGA-II and SMS-EMOA, the expected number of fitness evaluations for solving One Min Max and Leading Ones Trailing Zeroes can be reduced by a factor of Θ(n). However, as only upper bounds on the running time of the original NSGA-II and SMS-EMOA have been derived, we conduct experiments to examine their actual performance to complement the theoretical results. Specifically, we set the problem size n from 10 to 50, with a step of 10. For NSGA-II and SMS-EMOA using an archive, the population size µ is set to 4 and 2, respectively, as suggested in Theorems 1–4. For the original NSGA-II and SMS-EMOA without an archive, we test three values of µ, i.e., n + 1, 2(n + 1), and 4(n + 1), as suggested by [Bian and Qian, 2022; Zheng and Doerr, 2023a; Zheng and Doerr, 2024]. Note that n + 1 is the size of the Pareto front of One Min Max and Leading Ones Trailing Zeroes. If using a population size µ < n + 1, the original algorithms without archive obviously cannot find the Pareto front. For each n, we run an algorithm 1000 times independently, and record the average number of fitness evaluations until the Pareto front is found. In case where the Pareto front cannot be found in acceptable running time, we set the maximum number of fitness evaluations to 5 × 10^4 for One Min Max and 2 × 10^5 for Leading Ones Trailing Zeroes. We can observe from Figure 1 that using an archive brings a clear acceleration. |
| Researcher Affiliation | Academia | Chao Bian1 , Shengjie Ren1 , Miqing Li2 and Chao Qian1 1National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China School of Artificial Intelligence, Nanjing University, Nanjing 210023, China 2School of Computer Science, University of Birmingham, Birmingham B15 2TT, U.K. {bianc, qianc}@lamda.nju.edu.cn, shengjieren36@gmail.com, m.li.8@bham.ac.uk |
| Pseudocode | Yes | Algorithm 1 NSGA-II [Deb et al., 2002] and Algorithm 2 SMS-EMOA [Beume et al., 2007] are provided. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It mentions 'The supplementary is available at arXiv' but does not explicitly state that code for this work is released or provide a specific code repository link. |
| Open Datasets | No | The paper evaluates on synthetic problems ('One Min Max' and 'Leading Ones Trailing Zeroes') which are mathematical functions, not traditional datasets that are publicly available or require train/validation/test splits. |
| Dataset Splits | No | The paper evaluates on synthetic problems, not datasets with conventional training/validation/test splits for reproducibility of data partitioning. |
| Hardware Specification | No | The paper does not provide any specific hardware details (e.g., CPU/GPU models, memory, or cloud instances) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers (e.g., Python, PyTorch, or specific solvers). |
| Experiment Setup | Yes | Specifically, we set the problem size n from 10 to 50, with a step of 10. For NSGA-II and SMS-EMOA using an archive, the population size µ is set to 4 and 2, respectively, as suggested in Theorems 1–4. For the original NSGA-II and SMS-EMOA without an archive, we test three values of µ, i.e., n + 1, 2(n + 1), and 4(n + 1), as suggested by [Bian and Qian, 2022; Zheng and Doerr, 2023a; Zheng and Doerr, 2024]. For each n, we run an algorithm 1000 times independently, and record the average number of fitness evaluations until the Pareto front is found. In case where the Pareto front cannot be found in acceptable running time, we set the maximum number of fitness evaluations to 5 × 10^4 for One Min Max and 2 × 10^5 for Leading Ones Trailing Zeroes. |