Running Time Analysis of MOEA/D with Crossover on Discrete Optimization Problem
Authors: Zhengxin Huang, Yuren Zhou, Zefeng Chen, Xiaoyu He2296-2303
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we present a running time analysis of a simple MOEA with crossover based on the MOEA/D framework (MOEA/D-C) on four discrete optimization problems. Our rigorous theoretical analysis shows that the MOEA/D-C can obtain a set of Pareto optimal solutions to cover the Pareto front of these problems in expected running time apparently lower than the one without crossover. Moreover, the MOEA/D-C only needs to decompose an MOP into a few scalar optimization subproblems according to several simple weight vectors. This result suggests that the use of crossover in decomposition-based MOEA can simplify the setting of weight vector for different problems and make the algorithm more efficient. This study theoretically explains why some decomposition-based MOEAs work well in computational experiments and provides insights in design of MOEAs for MOPs in future research. ... Experimental Verification: As shown in Figure 3, the curves of average fitness evaluations of numerical experiments (dash lines) on four problems are approximately in the order of the corresponding theoretical bounds (solid lines), respectively. This result confirms the correctness of theoretical bounds obtained in our analysis. |
| Researcher Affiliation | Academia | 1School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China 2Engineering Research Institute, Guangzhou College of South China, University of Technology, Guangzhou 510800, China |
| Pseudocode | Yes | Algorithm 1 MOEA/D-C |
| Open Source Code | No | The paper does not provide any links to open-source code for the MOEA/D-C methodology described. |
| Open Datasets | No | The paper defines several pseudo-Boolean functions (COCZ, WLPTNO, Dec-obj-MOP, Plateau-MOP) for theoretical analysis and experimental verification, but it does not refer to them as downloadable datasets or provide any concrete access information (links, DOIs, repositories) for a publicly available dataset. |
| Dataset Splits | No | The paper analyzes problem definitions and conducts experimental verification but does not specify any training/test/validation dataset splits, as it does not operate on typical external datasets with such partitioning. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., CPU, GPU models, memory, cloud instances) used to run the experiments. |
| Software Dependencies | No | The paper mentions using 'standard bit mutation' and 'one-point crossover' as operators within the MOEA/D framework, but it does not list any specific software components or libraries with version numbers (e.g., Python 3.8, PyTorch 1.9). |
| Experiment Setup | Yes | For parameters in Algorithm 1, in this analysis we set H = 2, T = m and pc = 0.5. So the set of decomposed weight vectors is {λ1 = (0, 1), λ2 = (0.5, 0.5), λ3 = (1, 0)} and the number of scalar optimization subproblems N (also the population size) is 3. For the variation operators in Step 5 and 7, we use the standard bit mutation and one-point crossover, respectively. Thus Algorithm 1 requires six fitness evaluations in an iteration. |