|
Theory of computing
Правило «одной пятой» с возвратами для настройки размера популяции в генетическом алгоритме $(1 + (\lambda,\lambda))$
А. О. Басин, М. В. Буздалов, А. А. Шалыто Университет ИТМО, Кронверкский пр., д. 49, Санкт-Петербург, 197101 Россия
Аннотация:
Известно, что настройка параметров может существенно улучшить время работы эволюционных алгоритмов.Ярким примером этого является генетический алгоритм $(1 + (\lambda,\lambda))$, где адаптация размера популяции в процессе работы помогает достичь линейного времени работы на задаче OneMax. Однако если свойства решаемой задачи вступают в конфликт с принципами работы используемого метода настройки параметров, производительность эволюционного алгоритма может существенно ухудшаться. Так, например, происходит при использовании правила «одной пятой» в упомянутом алгоритме при решении задач со слабой корреляцией между приспособленностью и расстоянием до оптимума.
В данной работе предлагается модификация правила «одной пятой», существенно снижающая отрицательные эффекты от его использования при их наличии. Показывается, что данная модификация также достигает линейного времени работы на задаче OneMax, при этом ее использование приводит к улучшению производительности на линейных псевдобулевых функциях со случайными весами, а также на некотором классе задач MAX-3SAT.
Ключевые слова:
настройка параметров, $(1 + (\lambda,\lambda))$-ГА, линейные функции, MAX-3SAT.
Поступила в редакцию: 22.10.2020 Исправленный вариант: 18.11.2020 Принята в печать: 16.12.2020
Образец цитирования:
А. О. Басин, М. В. Буздалов, А. А. Шалыто, “Правило «одной пятой» с возвратами для настройки размера популяции в генетическом алгоритме $(1 + (\lambda,\lambda))$”, Модел. и анализ информ. систем, 27:4 (2020), 488–508
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais730 https://www.mathnet.ru/rus/mais/v27/i4/p488
|
Статистика просмотров: |
Страница аннотации: | 105 | PDF полного текста: | 28 | Список литературы: | 17 |
|