Escaping Local Optima with Non-Elitist Evolutionary Algorithms
Authors: Duc-Cuong Dang, Anton Eremeev, Per Kristian Lehre12275-12283
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The theoretical analysis is complemented with an empirical investigation on instances of the set cover problem, showing that non-elitist EAs can perform better than the elitist ones. We also provide examples where usage of mutation rates close to the error thresholds is beneficial when employing non-elitist population-based EAs. |
| Researcher Affiliation | Academia | 1Southampton Business School, University of Southampton, University Road, Southampton, SO17 1BJ, United Kingdom 2Sobolev Institute of Mathematics SB RAS, 13, Pevtsov str., Omsk, 644099, Russia 3School of Computer Science, University of Birmingham, Edgbaston, B15 2TT Birmingham, United Kingdom |
| Pseudocode | Yes | Algorithm 1 (Dang and Lehre 2016a) Require: Initial population P0 X λ, parameter χ [0, n]. 1: for t N until a termination cond. is met do 2: for i = 1 to λ do 3: Sample It(i) psel(Pt), and set x := Pt(It(i)). 4: Sample x pmut(x, χ), and set Pt+1(i) := x . 5: end for 6: end for |
| Open Source Code | Yes | The plots with confidence intervals, and the source code with the instruction on how to reproduce the experiments are provided in the supplementary material. |
| Open Datasets | Yes | We carried out some preliminary experiments with the non-elitist EAs on several instances of the Set Cover Problem (SCP) from the OR-library (Beasley 1990), representing the CYC and CLR families (Grossman and Wool 1997) and the Stein (Fulkerson, Nemhauser, and Trotter 1974) family of hard unicost benchmarks. |
| Dataset Splits | No | The paper mentions using instances of the Set Cover Problem but does not provide specific details on training, validation, or test dataset splits, such as percentages or sample counts. |
| Hardware Specification | Yes | They were compiled, then called from a Python program running on a server machine with AMD EPYC 7502 processors, Ubuntu 20.04 OS, GCC 9.3.0 and Python 3.8.3. |
| Software Dependencies | Yes | They were compiled, then called from a Python program running on a server machine with AMD EPYC 7502 processors, Ubuntu 20.04 OS, GCC 9.3.0 and Python 3.8.3. |
| Experiment Setup | Yes | Each algorithm was allowed the same budget of 2 108 function calls to evaluate its solutions, and each setting on each instance were tested with 40 replications of the run using different random seeds. The algorithms were implemented in C++ using its standard library for the random number generation. The graphs of non-elitist EAs with tournament selection are passing close to the best-known solution size 144 when χ = 0.67 if the tournament size is k = 2, and when χ = 1.08 if k = 3. |