Academic Journal
From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms *
| العنوان: | From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms * |
|---|---|
| المؤلفون: | Doerr, Benjamin, Zheng, Weijie |
| المساهمون: | École polytechnique (X), Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Institut Polytechnique de Paris (IP Paris), ANR-11-LABX-0056,LMH,LabEx Mathématique Hadamard(2011) |
| المصدر: | ISSN: 1532-4435. |
| بيانات النشر: | HAL CCSD Microtome Publishing |
| سنة النشر: | 2023 |
| مصطلحات موضوعية: | Estimation-of-distribution algorithms genetic drift restart strategy randomized search heuristics theory of computing, Estimation-of-distribution algorithms, genetic drift, restart strategy, randomized search heuristics, theory of computing, [INFO]Computer Science [cs] |
| الوصف: | International audience ; Estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). Too small values lead to the undesired effect of genetic drift, while larger values slow down the process. Building on a quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter regimes. Via a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. For many situations where the optimal parameter values are known, this shows that the restart scheme automatically finds these optimal values, leading to the asymptotically optimal performance. We also conduct an extensive experimental analysis. On four classic benchmarks, the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. We also conduct experiments with PBIL (cross-entropy algorithm) on the max-cut problem and the bipartition problem. Again, the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| Relation: | hal-04483214; https://hal.science/hal-04483214; https://hal.science/hal-04483214/document; https://hal.science/hal-04483214/file/Zheng_Doerr__From_Understanding_Genetic_Drift_to_Smart_Restarts__JMLR__2023.pdf |
| الاتاحة: | https://hal.science/hal-04483214 https://hal.science/hal-04483214/document https://hal.science/hal-04483214/file/Zheng_Doerr__From_Understanding_Genetic_Drift_to_Smart_Restarts__JMLR__2023.pdf |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.31DA2D70 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |