Abstract
A class of metaheuristic techniques called estimation-of-distribution algorithms (EDAs) is employed in optimization as a more sophisticated substitute for traditional strategies like evolutionary algorithms. EDAs generally drive the search for the optimum by creating probabilistic models of potential candidate solutions through repeated sampling and selection from the underlying search space.
Most theoretical research on EDAs has focused on pseudo-Boolean optimization. Jedidia et al. (GECCO 2023) introduced a framework for EDAs for optimizing problems involving multi-valued decision variables. In addition, they conduct a mathematical runtime analysis of a multi-valued UMDA on the r-valued LeadingOnes function. Using their framework, here we focus on the multi-valued compact genetic algorithm (r-cGA) and provide a first runtime analysis of a generalized OneMax function.
To prove our results, we investigate the effect of genetic drift and progress of the probabilistic model towards the optimum. After finding the right algorithm parameters, we prove that the r-cGA solves this r-valued OneMax problem efficiently. We establish that the runtime bound is O(r2n log2 r log3 n) with high probability.
Most theoretical research on EDAs has focused on pseudo-Boolean optimization. Jedidia et al. (GECCO 2023) introduced a framework for EDAs for optimizing problems involving multi-valued decision variables. In addition, they conduct a mathematical runtime analysis of a multi-valued UMDA on the r-valued LeadingOnes function. Using their framework, here we focus on the multi-valued compact genetic algorithm (r-cGA) and provide a first runtime analysis of a generalized OneMax function.
To prove our results, we investigate the effect of genetic drift and progress of the probabilistic model towards the optimum. After finding the right algorithm parameters, we prove that the r-cGA solves this r-valued OneMax problem efficiently. We establish that the runtime bound is O(r2n log2 r log3 n) with high probability.
Original language | English |
---|---|
Title of host publication | 18th International Conference on Parallel Problem Solving From Nature PPSN 2024 |
Publisher | Springer |
Publication date | 2024 |
Pages | 53-69 |
ISBN (Print) | 978-3-031-70070-5 |
ISBN (Electronic) | 978-3-031-70071-2 |
DOIs | |
Publication status | Published - 2024 |
Event | 18th International Conference on Parallel Problem Solving From Nature - Hagenberg, Austria Duration: 14 Sept 2024 → 18 Sept 2024 |
Conference
Conference | 18th International Conference on Parallel Problem Solving From Nature |
---|---|
Country/Territory | Austria |
City | Hagenberg |
Period | 14/09/2024 → 18/09/2024 |
Keywords
- Estimation-of-distribution algorithms
- Multi-valued compact genetic algorithm
- Genetic drift
- OneMax