НАСТРОЙКА ПАРАМЕТРОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПРИ ПОМОЩИ АНАЛИЗА ЛАНДШАФТА ФУНКЦИИ ПРИСПОСОБЛЕННОСТИ И МАШИННОГО ОБУЧЕНИЯ
Аннотация
Выбор значений параметров в эволюционных алгоритмах сильно влияет на их производи-
тельность. Многие популярные методы настройки параметров ограничены максимальным числом
вычислений целевой функции для поиска хорошего набора значений параметров. Недавно был пред-
ложен подход к выбору алгоритмов для решения оптимизационных задач, использующий анализ
ландшафта функции приспособленности и машинное обучение для выбора оптимального алго-
ритма решения задачи на основе особенностей ее ландшафта. Подобное применение анализа
ландшафта функции приспособленности мотивирует на дальнейшие исследования, в частности,
применительно к настройке параметров эволюционных алгоритмов. Использование признаков
ландшафта функции приспособленности позволяет выявлять похожие задачи и использовать
данные о настройке параметров, полученные при тестировании на эталоных задачах, что значи-
тельно снижает число необходимых вычислений целевой функции при настройке. В этой работе
на примере генетического алгоритма рассматривается подход к автоматическому
выбору параметров с использованием анализа ландшафта целевой функции и машинного обучения.
В предлагаемом решении оцениваются особенности ландшафта целевой функции поставленной
задачи оптимизации и предлагаются оптимальные значения параметров алгоритма с помощью
нейронной сети. Данная сеть была обучена на наборе данных об особенностях ландшафта, вы-
раженных в виде числовых признаков и соответствующих им оптимальных наборов параметров
алгоритма. В отличие от подходов к автоматическому выбору алгоритмов оптимизации для кон-
кретной задачи, в данной работе рассматривается задача регрессии параметров алгоритма вме-
сто проблемы классификации наиболее подходящего алгоритма из заданного набора. Результаты
экспериментов на различных конфигурациях задачи W-model, а также на задачае MAX-3SAT пока-
зывают, что предлагаемый подход к автоматическому выбору параметров с учетом ландшафта
целевой функции может помочь определить подходящие значения статических параметров гене-
тического алгоритма , так как алгоритм с предложенными значениями параметров
превосходит другие рассмотренные варианты , в среднем требуя меньше вычисле-
ний целевой функции для нахождения оптимума, чем остальные рассмотренные алгоритмы.
Литература
Science & Business Media, 2007, Vol. 54.
2. Mersmann O., Preuss M., Trautmann H. Benchmarking evolutionary algorithms: Towards exploratory
landscape analysis, 2010.
3. Mersmann O. et al. Exploratory landscape analysis, Proceedings of the 13th annual conference on
Genetic and evolutionary computation, 2011, pp. 829-836.
4. Lopez-Ibanez,M., Dubois-Lacoste J., Caceres L.P., Stutzle T., Birattari M. The irace package: Iterated
racing for automatic algorithm configuration, Operations Research Perspectives, 2016, 3, pp. 43-58.
5. Hutter F., Hoos H.H., Leyton-Brown K. Sequential model-based optimization for general algorithm
configuration, Proceedings of Learning and Intelligent Optimization. Springer, 2011, pp. 507-523.
6. Ochoa G., Malan K. Recent advances in fitness landscape analysis, Proceedings of the Genetic and
Evolutionary Computation Conference Companion, 2019, pp. 1077-1094.
7. Kerschke P., Trautmann H. Automated algorithm selection on continuous black-box problems by combining
exploratory landscape analysis and machine learning, Evolutionary computation, 2019, pp. 99-127.
8. Janković A., Doerr C. Adaptive landscape analysis, Proceedings of the Genetic and Evolutionary
Computation Conference Companion, 2019, pp. 2032-2035.
9. Bassin A., Buzdalov M. The (1 + (λ, λ)) Genetic Algorithm for Permutations, Proceedings of Genetic
and Evolutionary Computation Conference Companion. ACM, 2020, pp. 1669-1677.
10. Weise T., Wu Z. Difficult features of combinatorial optimization problems and the tunable w-model
benchmark problem for simulating them, Proceedings of the Genetic and Evolutionary Computation
Conference Companion, 2018, pp. 1769-1776.
11. Kerschke P., Trautmann H. The R-Package FLACCO for exploratory landscape analysis with applications
to multi-objective optimization problems, 2016 IEEE Congress on Evolutionary Computation
(CEC). IEEE, 2016, pp. 5262-5269.
12. Doerr B., Doerr C., Ebel F. From black-box complexity to designing new genetic algorithms, Theoretical
Computer Science, 2015, Vol. 567, pp. 87-104.
13. Dang N., Doerr C. Hyper-parameter tuning for the (1+(λ, λ)) GA, Proceedings of the Genetic and
Evolutionary Computation Conference, 2019, pp. 889-897.
14. Kimura M. [et al.]. Evolutionary rate at the molecular level, Nature, 1968, Vol. 217, No. 5129,
pp. 624-626.
15. Cordell H.J. Epistasis: what it means, what it doesn’t mean, and statistical methods to detect it in humans,
Human molecular genetics, 2002, Vol. 11, No. 20, pp. 2463-2468.
16. Weise T. [et al.]. A tunable model for multiobjective, epistatic, rugged, and neutral fitness landscapes,
Proceedings of the 10th annual conference on Genetic and evolutionary computation, 2008, pp. 795-802.
17. Garay M.R. Computers and intractability. A guide to the theory of NP-completeness, 1979.
18. Beyer H.G. Evolution strategies, Scholarpedia, 2007, Vol. 2, No. 8, pp. 1965.
19. Eshelman L. On crossover as an evolutionarily viable strategy, Proceedings of the Fourth International
Conference on Genetic Algorithms, 1991, pp. 61-68.
20. Schumer M., Steiglitz K. Adaptive step size random search, IEEE Transactions on Automatic Control,
1968, Vol. 13, No. 3, pp. 270-276.
