The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm
Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ,λ)) genetic algorithm, where adaptation of the population size helps to achieve the linear running time on the OneMax problem. However, on problems which interfere wit...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2020-12-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1438 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850025678341144576 |
|---|---|
| author | Anton Olegovich Bassin Maxim Viktorovich Buzdalov Anatoly Abramovich Shalyto |
| author_facet | Anton Olegovich Bassin Maxim Viktorovich Buzdalov Anatoly Abramovich Shalyto |
| author_sort | Anton Olegovich Bassin |
| collection | DOAJ |
| description | Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ,λ)) genetic algorithm, where adaptation of the population size helps to achieve the linear running time on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to the performance degradation. In particular, this is the case with the “one-fifth rule” on problems with weak fitness-distance correlation.We propose a modification of the “one-fifth rule” in order to have less negative impact on the performance in the cases where the original rule is destructive. Our modification, while still yielding a provable linear runtime on OneMax, shows better results on linear function with random weights, as well as on random satisfiable MAX-3SAT problems. |
| format | Article |
| id | doaj-art-cac3398a2d4741e8a69dfb16134c0df9 |
| institution | DOAJ |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2020-12-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-cac3398a2d4741e8a69dfb16134c0df92025-08-20T03:00:45ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172020-12-0127448850810.18255/1818-1015-2020-4-488-5081094The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic AlgorithmAnton Olegovich Bassin0Maxim Viktorovich Buzdalov1Anatoly Abramovich Shalyto2ITMO UniversityITMO UniversityITMO UniversitySelf-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ,λ)) genetic algorithm, where adaptation of the population size helps to achieve the linear running time on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to the performance degradation. In particular, this is the case with the “one-fifth rule” on problems with weak fitness-distance correlation.We propose a modification of the “one-fifth rule” in order to have less negative impact on the performance in the cases where the original rule is destructive. Our modification, while still yielding a provable linear runtime on OneMax, shows better results on linear function with random weights, as well as on random satisfiable MAX-3SAT problems.https://www.mais-journal.ru/jour/article/view/1438parameter adaptation(1 + (λ,λ)) galinear functionsmax-3sat |
| spellingShingle | Anton Olegovich Bassin Maxim Viktorovich Buzdalov Anatoly Abramovich Shalyto The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm Моделирование и анализ информационных систем parameter adaptation (1 + (λ,λ)) ga linear functions max-3sat |
| title | The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm |
| title_full | The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm |
| title_fullStr | The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm |
| title_full_unstemmed | The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm |
| title_short | The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm |
| title_sort | one fifth rule with rollbacks for self adjustment of the population size in the 1 λ λ genetic algorithm |
| topic | parameter adaptation (1 + (λ,λ)) ga linear functions max-3sat |
| url | https://www.mais-journal.ru/jour/article/view/1438 |
| work_keys_str_mv | AT antonolegovichbassin theonefifthrulewithrollbacksforselfadjustmentofthepopulationsizeinthe1llgeneticalgorithm AT maximviktorovichbuzdalov theonefifthrulewithrollbacksforselfadjustmentofthepopulationsizeinthe1llgeneticalgorithm AT anatolyabramovichshalyto theonefifthrulewithrollbacksforselfadjustmentofthepopulationsizeinthe1llgeneticalgorithm AT antonolegovichbassin onefifthrulewithrollbacksforselfadjustmentofthepopulationsizeinthe1llgeneticalgorithm AT maximviktorovichbuzdalov onefifthrulewithrollbacksforselfadjustmentofthepopulationsizeinthe1llgeneticalgorithm AT anatolyabramovichshalyto onefifthrulewithrollbacksforselfadjustmentofthepopulationsizeinthe1llgeneticalgorithm |