Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms
Authors: Tianhao Lu, Chao Bian, Chao Qian
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | This paper provides the first running time analysis (the essential theoretical aspect of EAs) for practical i MOEAs. Specifically, we prove that the expected running time of the welldeveloped interactive NSGA-II (called R-NSGA-II) for solving the One Min Max and One Jump Zero Jump problems are all asymptotically faster than the traditional NSGA-II. Meanwhile, we present a variant of One Min Max, and prove that RNSGA-II can be exponentially slower than NSGA-II. These results provide theoretical justification for the effectiveness of i MOEAs while identifying situations where they may fail. Experiments are also conducted to validate the theoretical results. |
| Researcher Affiliation | Academia | National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China School of Artificial Intelligence, Nanjing University, Nanjing 210023, China |
| Pseudocode | Yes | Algorithm 1: NSGA-II Algorithm (Deb et al. 2002) |
| Open Source Code | Yes | The data and code are provided in the supplementary material. |
| Open Datasets | No | The paper uses standard benchmark problems like 'One Min Max' and 'One Jump Zero Jump', and also 'bi-objective NK-landscape (Aguirre and Tanaka 2007)'. While these are established problems, the paper does not provide specific links, DOIs, repository names, or detailed access information for datasets for these problems. It refers to the problem definitions themselves rather than specific data files. |
| Dataset Splits | No | No specific training/test/validation dataset splits are provided. The paper discusses theoretical analysis and experimental validation on defined problems, not on datasets that are split for training, validation, and testing. |
| Hardware Specification | No | No specific hardware details (e.g., GPU models, CPU types, memory) used for running the experiments are provided. |
| Software Dependencies | No | No specific software dependencies with version numbers are mentioned (e.g., programming languages, libraries, or frameworks). |
| Experiment Setup | Yes | For the One Min Max problem, we set the population size N of NSGA-II and R-NSGA-II to 4(n + 1) and 1, respectively, as suggested by Theorems 1 and 2. For the One Jump Zero Jump problem, the parameter k is set to 2. The population size N of NSGA-II and R-NSGA-II is set to 4(n 2k +3) and 1, respectively, according to Theorems 3 and 4. We set the problem size n from 10 to 50, with a step of 10. We set a maximum number of fitness evaluation, i.e., 10^5. |