Методы адаптации параметров в стохастических алгоритмах для оптимизации информационно-вычислительных процессов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Антонов Кирилл Александрович

• Антонов Кирилл Александрович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Антонов Кирилл Александрович

Оглавление

Реферат

Synopsis

Введение

Глава 1. Обзор методов адаптации параметров в

стохастических алгоритмах оптимизации

1.1. Обзор эволюционных алгоритмов для решения задач комбинаторной оптимизации

1.2. Методы оптимизации в многомерных пространствах при ограниченных вычислительных ресурсах

1.3. Обзор существующих методов решения задачи маршрутизации с ограничениями на грузоподъемность

1.4. Постановка задач диссертационного исследования

Выводы по главе

Глава 2. Метод адаптации покомпонентной вероятности

мутации в (1 + А)-эволюционных алгоритмах

2.1. Формализация рассматриваемой задачи дискретной оптимизации

2.2. Описание предложенного метода

2.2.1. Предварительные сведения

2.2.2. Общее описание

2.3. Выбор параметра, задающего достаточное число голосов для уменьшения нижней границы вероятности мутации (quorum)

2.4. Экспериментальный анализ

2.4.1. Экспериментальный анализ на функции, вычисляющей число единиц в бинарной строке (OneMax)

2.4.2. Экспериментальный анализ на функции, вычисляющей число единиц от начала бинарной строки до первого нуля (LeadingOnes)

2.4.3. Экспериментальный анализ на задачах, отражающих свойства реальных задач (W-Müdel)

Выводы по главе

Глава 3. Метод оценки быстродействия (1 + А)-эволюционных алгоритмов, использующих адаптацию

покомпонентной вероятности мутации

3.1. Постановка задачи

3.2. Метод численного приближения нижней оценки времени работы

для (1 + А)-эволюционных алгоритмов

3.2.1. Разбиение пространства поиска на классы решений

задачи оптимизации, имеющих одинаковую структуру

3.2.2. Описание метода

3.3. Доказательство корректности предложенного метода

3.3.1. Марковская цепь на пространстве ^-классов

3.3.2. Доказательство единственности и конечности

ожидаемого времени достижения оптимума

3.4. Численный анализ предложенного метода на задачах с нетривиальным ландшафтом функции приспособленности

3.4.1. Применение к функции RUGGEDNESS

3.4.2. Численные приближения нижних оценок времени работы методов адаптации вероятности мутации на функции RUGGEDNESS

3.4.3. Тепловые карты эффективности параметров для

функции RUGGEDNESS

3.4.4. Графики потерь (Regret Plots)

3.4.5. Применение к функции PLATEAU

3.4.6. Численные приближения нижних оценок времени работы методов адаптации вероятности мутации на функции PLATEAU

3.4.7. Тепловые карты эффективности параметров для

функции PLATEAU

3.5. Детали реализации

3.5.1. Реализация метода решения системы линейных уравнений

3.5.2. Оценка вероятностей переходов методом Монте-Карло

3.5.3. Улучшенные вычисления методом Монте-Карло

3.5.4. Выбор множеств значений вероятностей мутаций

3.5.5. Конфигурации

Выводы по главе

Глава 4. Метод многомерной Байесовской оптимизации с понижением размерности вещественнозначных функций

4.1. Введение в многомерную Баейсовскую оптимизацию

4.1.1. Байесовская оптимизация

4.1.2. Регрессия на основе Гауссовского Процесса

4.1.3. Байесовская оптимизация в пространствах высокой размерности

4.2. Предложенный метод байесовской оптимизации Keгnel-PCA-BO

4.2.1. Общий обзор метода

4.2.2. Масштабирование точек данных

4.2.3. Уменьшение размерности в гильбертовом пространстве

4.2.4. Обучение прямого отображения

4.2.5. Обучение обратного отображения

4.2.6. Байесовская оптимизация в пространстве пониженной размерности

4.3. Экспериментальное сравнение с классическими методами

Выводы по главе

Глава 5. Применение разработанных методов к задаче

адаптации параметров в стохастических алгоритмах для маршрутизации доставки с ограничениями

5.1. Решаемая задача

5.1.1. Классическая задача оптимизации доставки грузов

5.1.2. Малоитерационная параллельная оптимизация доставки грузов (МИПО): дополнительные ограничения

5.1.3. Метод решения поставленной задачи

5.1.4. Формализация адаптации параметра мутации в

(1 + А)-ЭА для решения МИПО

5.2. Предлагаемый метод адаптации параметров

5.2.1. Выбор обучающих экземпляров МИПО

5.2.2. Обучение нейронных сетей независимо друг от друга на выбранных экземплярах МИПО

5.2.3. Итоговая адаптация параметра мутации на произвольной задаче МИПО из заданного класса

5.2.4. Применение адаптации параметра в (1 + А)-ЭА для

новых задач МИПО

5.3. Аналоги для решения задачи МИПО и адаптации параметров

5.3.1. Аналоги (1 + А)-ЭА с адаптацией в по номеру итерации

5.3.2. Аналоги (1 + А)-ЭА с адаптацией в по состоянию метода

5.4. Численное сравнение предложенного метода с аналогами

5.4.1. Сравнение

5.4.2. Анализ шума

5.4.3. Улучшение финального решения

5.5. Использование методов, выносимых на защиту

5.5.1. Первый метод, выносимый на защиту

5.5.2. Второй метод, выносимый на защиту

5.5.3. Третий метод, выносимый на защиту

5.5.4. Анализ вклада метода Кегпе1-РСЛ-БО в эффективность метода обучения нейронной сети по сравнению с методом Байесовской оптимизации

Выводы по главе

Заключение

Список рисунков

Список таблиц

Список литературы

Приложение А. Константы, использованные в реализации

Приложение Б. Таблица, в которой собраны характеристики

финальных решений задачи МИПО

Приложение В. Акт внедрения

Приложение Г. Тексты публикаций автора

Введение диссертации (часть автореферата) на тему «Методы адаптации параметров в стохастических алгоритмах для оптимизации информационно-вычислительных процессов»

Реферат

Актуальность. Современные информационно-вычислительные системы решают задачи большой размерности при ограниченных вычислительных ресурсах [1—3]. Это характерно, в частности, для задач глобальной оптимизации, возникающих в интеллектуальных логистических системах, цифровом управлении промышленными объектами, проектировании схем и в других прикладных сферах [4; 5].

При этом особенно актуальны универсальные и адаптивные методы оптимизации, способные эффективно справляться с неопределённостью и автоматически подстраиваться под изменяющиеся свойства задач [6]. Одним из наиболее перспективных классов таких методов являются эволюционные алгоритмы, однако их практическая применимость ограничивается необходимостью настройки параметров, отсутствием теоретических оценок времени сходимости для прикладных задач и, кроме того, эволюционные алгоритмы требуют значительных вычислительных ресурсов при решении задач высокой размерности [7].

Актуальность настоящей работы обусловлена необходимостью преодоления этих ограничений. Повышение адаптивности и производительности таких алгоритмов имеет важное значение для применения в отечественных цифровых платформах, в том числе в логистике, что делает исследование актуальным не только научно, но и в контексте технологического развития России [8].

Степень разработанности темы исследования. Адаптация параметров в стохастических алгоритмах для комбинаторной оптимизации - активно развивающееся направление, находящееся на стыке теории эволюционных вычислений и прикладной оптимизации [9]. Значительное число исследований в этой области посвящено адаптации таких параметров, как вероятность мутации, размер популяции, коэффициенты скрещивания и параметры локального поиска.

Существуют как теоретические работы Doerr и др. [10], направленные на анализ сходимости и времени работы адаптивных алгоритмов, так и практико-ориентированные исследования Bäck и др. [11], с целью эвристического решения задач при ограниченных вычислительных ресурсах. Однако в известных методах в большинстве случаев полученные оценки носят асимптотический характер и не гарантируют высокую производительность программ, их реализующих на задачах конечной размерности. Более того, для функций с нетривиальной

структурой пространства решений (например, с плато или многими локальными экстремумами) теоретические оценки времени сходимости часто отсутствуют вовсе [12].

Таким образом, несмотря на активный интерес к рассматриваемой тематике, остаются открытыми вопросы точного численного анализа, масштабируемой адаптации параметров в условиях ограниченного бюджета и применения адаптивных методов к задачам, возникающим в информационно-вычислительных системах. Решение этих вопросов лежит в основе настоящей диссертационной работы.

Цель исследования. Целью исследования является повышение эффективности эволюционных алгоритмов при решении крупномасштабных задач комбинаторной и псевдобулевой оптимизации в условиях ограниченных вычислительных ресурсов за счёт использования адаптации параметров в эволюционных алгоритмах.

Результаты направлены на практическое применение в интеллектуальных логистических системах, включая задачи оптимизации маршрутов доставки, и имеют значение для развития отрасли информационно-вычислительных систем, а также для повышения технологической независимости России за счёт интеграции в отечественные цифровые платформы.

Для достижения поставленной цели решались следующие задачи:

1. Разработка метода адаптации покомпонентной вероятности мутации в (1 + А)-эволюционных алгоритмах, применимых к псевдобулевым функциям, не требующего предварительной настройки параметров.

2. Разработка метода оценки быстродействия (1 + А)-эволюционных алгоритмов, применимых к псевдобулевым функциям и использующих адаптацию покомпонентной вероятности мутации.

3. Разработка метода многомерной Байесовской оптимизации с понижением размерности вещественнозначных функций, характеризующихся наличием множества локальных оптимумов.

4. Применение предложенных методов к задаче оптимизации доставки грузов, включающей множество ограничений и необходимость быстрой реакции на изменения параметров задачи в реальном времени.

Теоретическая значимость. Теоретическая значимость работы заключается в углублении представлений об адаптивных стохастических алгоритмах и расширяет инструментарий их анализа на функциях, возникающих в прикладных задачах численной оптимизации. В частности, разработан и реализован численный метод оценки времени работы адаптивных алгоритмов на конкретных задачах, основанный на динамическом программировании и Монте-Карло-моделировании. Это позволило перейти от асимптотических оценок к приближенным нижним оценкам времени работы алгоритма при конечном размере задач.

Практическая значимость. Практическая значимость результатов подтверждена их предполагаемым внедрением в российской технологической компании Уеего^е, специализирующейся на интеллектуальном управлении логистикой и цепочками поставок, которая позиционирует себя как платформа комбинаторной оптимизации1. Об этом имеется соответствующий акт. Разработанные методы компания предполагает использовать при оптимизации маршрутов доставки и повышения адаптивности планирования в условиях оперативно меняющихся данных.

Таким образом, результаты работы способствуют развитию отечественных технологий в сфере интеллектуального управления информационно-вычислительными системами и сложной цифровой логистики, в частности. Предложенные научно обоснованные алгоритмические решения могут использоваться в рамках программ цифровой трансформации отраслей экономики России. Это придаёт исследованию не только научную, но и практическую значимость с точки зрения укрепления технологического суверенитета и повышения конкурентоспособности страны.

Положения, выносимые на защиту, обладающие научной новизной.

1. Метод адаптации покомпонентной вероятности мутации в (1 + А)-эволюционных алгоритмах, применимых к псевдобулевым функциям, не требующий предварительной настройки параметров, отличающийся тем, что с целью повышения быстродействия указанных алгоритмов и

^«рБ^/уеегоиЬе.ги/

обеспечения автоматической корректировки нижней границы вероятности мутации компонент потомков, используется механизм коллективного отбора на основе характеристик полученных потомков.

2. Метод оценки быстродействия (1 + А)-эволюционных алгоритмов, применимых к псевдобулевым функциям и использующих адаптацию покомпонентной вероятности мутации, отличающийся тем, что с целью получения численных приближений нижних оценок времени работы указанных алгоритмов до достижения оптимума на практически значимых функциях, для которых отсутствуют аналитические нижние оценки, используется сочетание динамического программирования и Монте-Карло-моделирования.

3. Метод многомерной Байесовской оптимизации с понижением размерности вещественнозначных функций, характеризующихся наличием множества локальных оптимумов, отличающийся тем, что с целью получения решений со значением целевой функции, близким к оптимальному при ограниченных вычислительных ресурсах, осуществляется построение и управление нелинейным векторным представлением точек многомерного пространства на основе ядерного преобразования с учетом весов, определяемых по наблюдаемым значениям целевой функции.

Метод оценки быстродействия (1 + А)-эволюционных алгоритмов, применимых к псевдобулевым функциям и использующих адаптацию покомпонентной вероятности мутации, отличающийся тем, что с целью получения численных нижних оценок времени работы указанных алгоритмов до достижения оптимума на практически значимых функциях, для которых отсутствуют аналитические нижние оценки, используется сочетание динамического программирования и Монте-Карло-моделирования.

Методы исследования. В диссертационной работе использовались методы теории вероятностей, теории алгоритмов, численного моделирования, а также экспериментального анализа. Для построения адаптивных алгоритмов применялись методы из области эволюционных вычислений и Байесовской оптимизации. Теоретический анализ методов включал использование линейной алгебры, стохастических моделей и построение рекуррентных соотношений.

Достоверность. Достоверность полученных результатов подтверждается строгим математическим обоснованием, численными экспериментами, воспроизводимостью вычислений, а также их независимой экспертной оценкой на авторитетных международных конференциях, индексируемых Scopus и Web of Science.

Для первого метода, выносимого на защиту, проведены вычислительные эксперименты, демонстрирующие улучшенную сходимость эволюционного алгоритма с предложенной адаптацией покомпонентной вероятности мутации. Для второго метода математически доказана его корректность и применимость в реальных условиях; полученные оценки времени работы не противоречат теоретическим. Для третьего метода проведено экспериментальное сравнение с существующими аналогами на широком классе стандартных тестовых функций, показавшее его эффективность и масштабируемость при изменении параметров задачи. Статистическая значимость численных результатов, полученных при применении разработанных методов к задаче адаптации параметров для оптимизации маршрутизации доставки грузов, подтверждена корректными статистическими тестами.

Публикации по теме диссертации. Все работы были опубликованы в научных изданиях, входящих в международные реферативные базы данных и системы цитирования Scopus и Web of Science:

1. Rodionova A., Antonov K., Buzdalova A., Doerr C. Offspring population size matters when comparing evolutionary algorithms with self-adjusting mutation rates // Proceedings of the Genetic and Evolutionary Computation Conference. — 2019. — С. 855—863.

2. Antonov K., Buzdalova A., Doerr C. Mutation Rate Control in the Evolutionary Algorithm with a Self-adjusting Lower Bound // International Conference on Mathematical Optimization Theory and Operations Research. — Springer. 2020. — С. 305—319.

3. Antonov K., Buzdalov M., Buzdalova A., Doerr C. Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms // IEEE Congress on Evolutionary Computation (CEC). — 2021. — С. 878—885.

4. Antonov K., Raponi E, Wang H., Doerr C. High dimensional Bayesian optimization with kernel principal component analysis // International Conference on Parallel Problem Solving from Nature. — Springer. 2022. — С. 11S—131.

Методы, выносимые на защиту, покрыты опубликованными статьями.

1. Первый метод, выносимый на защиту, опубликован в статье [2].

2. Второй метод, выносимый на защиту, опубликован в статье [3].

3. Третий метод, выносимый на защиту, опубликован в статье [4].

Соответствие паспорту специальности. Диссертация соответствует первому пункту паспорта специальности 2.3.S: "Разработка компьютерных методов и моделей описания, оценки и оптимизации информационных процессов и ресурсов, а также средств анализа и выявления закономерностей на основе обмена информацией пользователями и возможностей используемого программно-аппаратного обеспечения".

Разработанные в диссертации методы направлены на оптимизацию информационно-вычислительных процессов по критерию, задаваемому целевой функцией, определённой на множестве возможных параметров этих процессов. Предложенные методы обеспечивают достижение как можно более лучших решений по заданному критерию в условиях ограниченных вычислительных ресурсов благодаря использованию стохастических алгоритмов с адаптацией параметров. Эффективность предложенных методов продемонстрирована на примере оптимизации маршрутизации доставки грузов.

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях:

1. The Genetic and Evolutionary Computation Conference (GECCO), Прага, Чехия. 2019.

2. Mathematical Optimization Theory and Operation Research (MOTOR), Новосибирск, Россия. 2020.

3. IEEE Congress on Evolutionary Computation (IEEE CEC), Краков, Польша. 2021

4. Parallel Problem Solving from Nature (PPSN XVII), Дортмунд, Германия. 2022.

5. Научная и учебно-методическая конференция университета ИТМО, СПб., 2022.

6. XI Конгресс молодых ученых, СПб., ИТМО, 2022.

7. XII Конгресс молодых ученых, СПб., ИТМО, 2023.

8. The 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA), Потсдам, Германия. 2023.

9. The Genetic and Evolutionary Computation Conference (GECCO), Мельбурн, Австралия. 2024.

Награды.

1. Лучшая статья на главном треке международной конференции IEEE CEC-2021: https://cec2021.mini.pw.edu.pl/upload/CEC-2021/_Best_ Paper_Awards.pdf

2. Победитель в номинации номинации "За лучший доклад молодого ученого" на конференции "XI Конгресс молодых ученых": https://kmu.itmo. ru/file/download/576

Личный вклад автора. Все основные результаты, представленные в диссертации, получены лично автором. Автором самостоятельно разработаны методы, выносимые на защиту. Также автором выполнены программная реализация методов, постановка экспериментов, анализ полученных данных и внедрение разработанных методов для решения задачи оптимизации маршрутов доставки грузов. В статьях, выполненных в соавторстве, личный вклад такой:

1. В публикации [1] автор разработал и экспериментально исследовал метод 3-rate и влияние нижней границы вероятности мутации (40-50% вклада). Остальные авторы занимались анализом других методов и общей интерпретацией результатов (50-60% вклада).

2. В публикации [2] автор разработал предложенный метод с адаптацией нижней границы вероятности мутации, реализовал программные эксперименты, провёл тестирование и выполнил анализ полученных результатов (около 90-95% вклада). Остальные авторы участвовали в обсуждении концепции и редактировании текста статьи (около 5-10% вклада).

3. В публикации [3] автор провёл исследование, разработал методику смешивания динамического программирования с моделированием Монте-Карло, реализовал программные эксперименты, провёл вычислительные

исследования и анализ результатов (около 80-85% вклада). Идея применения динамического программирования и формула перехода были предложены соавторами (около 15-20% вклада). 4. В публикации [4] автор предложил и разработал метод Кегпе1-РСА-ВО, реализовал его, организовал и провёл экспериментальное исследование, а также выполнил анализ и интерпретацию результатов (около 85-90% вклада). Соавторы принимали участие в обсуждении концепции и редактировании текста статьи (около 10-15% вклада).

Внедрение результатов работы. Реализация предложенных в диссертационной работе методов размещена в открытом доступе: метод 12, метод 23, о4 5

метод 3 , внедрение .

Предложенные в диссертационной работе методы предполагается внедрить в российской технологической компании Уеего^е6, специализирующейся на интеллектуальном планировании доставок, которая позиционирует себя как платформа комбинаторной оптимизации. Об этом имеется соответствующий акт.

Результаты диссертационной работы были использованы в следующих научных исследованиях, направленных на укрепление технологического суверенитета и повышения конкурентоспособности России:

1. Буздалов М., Шныткин М., Миронович В., Иванова А., Винокуров Д., Петрова И., Буздалова А., Антонов К., Буланова Н. Теоретические основы динамической настройки параметров в эволюционных алгоритмах // Грант РНФ 20-51-15009. — 2020 - 2022.

2. Антонов К., Пикалов М., Писмеров А. Методы динамической настройки параметров эволюционных алгоритмов с помощью машинного обучения и анализа ландшафта функции приспособленности // Научно-исследовательская работа магистрантов и аспирантов (НИРМА). ШИ 622277. — 2023.

2Репозиторий на github https://github.com/AntKirill/self-adaptive-mutation-ea

3Репозиторий на github https://github.com/AntKirill/ea/tree/cluster_experiments/

4Репозиторий на github https://github.com/wangronin/Bayesian-Optimization/tree/KPCA-BO

5Репозиторий на github https://github.com/kiralexant/pcsi-fewshot-cvrp/

6https://veeroute.ru/

Заключение диссертации по теме «Другие cпециальности», Антонов Кирилл Александрович

Заключение

В диссертации были получены следующие основные результаты:

1. Разработан метод адаптации покомпонентной вероятности мутации в (1 + А)-эволюционных алгоритмах, применимых к псевдобулевым функциям, не требующий предварительной настройки параметров, отличающийся тем, что с целью повышения быстродействия указанных алгоритмов и обеспечения автоматической корректировки нижней границы вероятности изменения компонент потомков, используется механизм коллективного отбора на основе характеристик полученных потомков.

2. Разработан метод оценки быстродействия (1 + А)-эволюционных алгоритмов, применимых к псевдобулевым функциям и использующих адаптацию покомпонентной вероятности мутации, отличающийся тем, что с целью получения математического ожидания числа итераций указанных алгоритмов до достижения оптимума при наилучшей возможной адаптации вероятности мутации на практически значимых функциях, для которых отсутствуют аналитические нижние оценки, используется сочетание динамического программирования и Монте-Карло-моделирования.

3. Разработан метод многомерной Байесовской оптимизации с понижением размерности вещественнозначных функций (Кегпе1-РСЛ-БО), характеризующихся наличием множества локальных оптимумов, отличающийся тем, что с целью получения решений со значением целевой функции, близким к оптимальному при ограниченных вычислительных ресурсах, осуществляется построение и управление нелинейным векторным представлением точек многомерного пространства на основе ядерного преобразования с учетом весов, определяемых по наблюдаемым значениям целевой функции.

4. Разработанные методы использованы для обучения и анализа нейронной сети, используемой для адаптации параметров в стохастических алгоритмах, применяемых для приближенного решения задачи доставки грузов в высоко-параллельной среде. В среднем по всем рассмотренным задачам, улучшение финального решения составляет 1.6% относительно лучшего из аналогов. Показано, что при одинаковом бюджете запусков ЭА обучение модели с Кегпе1-РСЛ-БО сокращает время в среднем на « 33% относительно классического БО, при одинаковом финальном качестве на всех

обучающих, маленьких и средних тестовых экземплярах. На крупнейшем тестовом экземпляре зафиксировано небольшое преимущество по среднему финальному качеству при использовании модели, обученной Кегпе1-РСА-ВО.

Результаты работы способствуют развитию отечественных технологий в сфере интеллектуального управления информационно-вычислительными системами и сложной цифровой логистики, в частности. Предложенные научно обоснованные алгоритмические решения могут использоваться в рамках программ цифровой трансформации отраслей экономики России. В частности, предложенные в диссертационной работе методы предполагается внедрить в российскую технологическую компанию Уеего^е1, специализирующейся на интеллектуальном планировании доставок, которая позиционирует себя как платформа комбинаторной оптимизации. Это придаёт исследованию не только научную, но и практическую значимость с точки зрения укрепления технологического суверенитета и повышения конкурентоспособности страны.

Тема исследования имеет перспективы дальнейшего развития - предложенный метод адаптации параметров для задачи МИПО может быть распространён на другие задачи комбинаторной оптимизации, решаемые в высокопараллельной среде, и применён в алгоритмах со структурой, отличающейся от (1 + А)-ЭА, например в (ц + А)-ЭА. Более того, нейронная сеть может использоваться для синтеза общей структуры алгоритма, в частности - для управления переключением на локальный поиск в пределах одной популяции. Таким образом, перспективным направлением является расширение модели нейросе-тевой адаптации для работы в пространстве различных эвристик и их комбинирования. Это позволит получать алгоритмы, нацеленные на улучшение качества финального решения для заданного класса задач без участия человека, что автоматизирует и существенно упрощает оптимизацию информационно-вычислительных процессов, сводящуюся к задачам комбинаторной оптимизации.

Список литературы диссертационного исследования кандидат наук Антонов Кирилл Александрович, 2025 год

Список литературы

1. Bottou L, Bousquet O. The Tradeoffs of Large Scale Learning // Advances in Neural Information Processing Systems. — 2007. — С. 161—168.

2. Hansen N., Auger A., Finck S., Ros R. Real-parameter black-box optimization benchmarking 2010: Experimental setup // Proceedings of the 12th annual conference companion on Genetic and evolutionary computation. — 2010. — С. 1447—1452.

3. Binois M, Gramacy R. B., Ludkovski M. A survey on high-dimensional Bayesian optimization // ACM Computing Surveys (CSUR). — 2021. — Т. 54, № 1. — С. 1—33.

4. Handbook of metaheuristics. Т. 146. — Springer, 2010. — (International Series in Operations Research & Management Science).

5. Pisinger D., Ropke S. A general heuristic for vehicle routing problems // Computers & Operations Research. — 2007. — Т. 34, № 8. — С. 2403—2435.

6. Eiben A., Smith J. Introduction to evolutionary computing. — Springer, 2003.

7. Doerr C., Doerr B. Theory of parameter control in evolutionary algorithms // ACM Transactions on Evolutionary Learning and Optimization. — 2018. — Т. 3, № 1. — С. 1—37.

8. Hin I., Maydanova S., Lepekhin A., Jahn C., Weigell J., Korablev V. Digital platforms for the logistics sector of the Russian Federation // Technological Transformation: A New Role For Human, Machines And Management: TT-2020. — Springer. 2021. — С. 179—188.

9. Karafotias G., Hoogendoorn M., Eiben A. Parameter Control in Evolutionary Algorithms: Trends and Challenges // IEEE Transactions on Evolutionary Computation. — 2015. — Т. 19. — С. 167—187.

10. Doerr B., Doerr C. Theory of parameter control for discrete blackbox optimization: Provable performance gains through dynamic parameter choices // Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. — 2020. — С. 271—321.

11. Back T. H., Kononova A. V., Stein B. van, Wang H., Antonov K. A., Kalkreuth R. T., Nobel J. de, Vermetten D., Winter R. de, Ye F. Evolutionary algorithms for parameter optimization—thirty years later // Evolutionary Computation. — 2023. — T. 31, № 2. — C. 81—122.

12. Antonov K., Buzdalova A., Buzdalov M., Doerr C. Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms // 2021 IEEE Congress on Evolutionary Computation (CEC). — 2021. — C. 878—885.

13. Jones D. R., Schonlau M, Welch W. J. Efficient Global Optimization of Expensive Black-Box Functions // Journal of Global Optimization. — 1998. — T. 13, № 4. — C. 455—492.

14. Ralphs T. K., Kopman L., Pulleyblank W. R., Trotter L. E. On the capacitated vehicle routing problem // Mathematical programming. — 2003. — T. 94. — C. 343—359.

15. Uchoa E., Pecin D., Pessoa A., Poggi M., Vidal T., Subramanian A. New benchmark instances for the capacitated vehicle routing problem // European Journal of Operational Research. — 2017. — T. 257, № 3. — C. 845—858.

16. Braekers K., Ramaekers K., Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review // Computers & industrial engineering. — 2016. — T. 99. — C. 300—313.

17. Toth P., Vigo D. Exact solution of the vehicle routing problem // Fleet management and logistics. — Springer, 1998. — C. 1—31.

18. Vidal T., Crainic T. G., Gendreau M., Prins C. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows // Computers & operations research. — 2013. — T. 40, № 1. — C. 475—489.

19. Helsgaun K. General k-opt submoves for the Lin-Kernighan TSP heuristic // Mathematical Programming Computation. — 2009. — T. 1. — C. 119—163.

20. Kool W, Van Hoof H, Welling M. Attention, learn to solve routing problems! // arXiv preprint arXiv:1803.08475. — 2018.

21. Ardon L. Reinforcement Learning to Solve NP-hard Problems: an Application to the CVRP. — 2022.

22. Bossek J., Doerr C., Kershke P., Neumann A., Neumann F. Evolving Sampling Strategies for One-Shot Optimization Tasks // Parallel Problem Solving from Nature - PPSN XVI. — Springer, 2020. — (Lecture Notes in Computer Science ; 12269).

23. Rodionova A., Antonov K., Buzdalova A., Doerr C. Offspring population size matters when comparing evolutionary algorithms with self-adjusting mutation rates // Proceedings of the Genetic and Evolutionary Computation Conference. — 2019. — C. 855—863.

24. Buzdalov M, Doerr C. Optimal Mutation Rates for the (1 + À) EA on OneMax // Parallel Problem Solving from Nature - PPSN XVI. — Springer, 2020. — C. 574—587.

25. Böttcher S., Doerr B., Neumann F. Optimal fixed and adaptive mutation rates for the LeadingOnes problem // International Conference on Parallel Problem Solving from Nature. — Springer. 2010. — C. 1—10.

26. Weise T., Wu Z. Difficult Features of Combinatorial Optimization Problems and the Tunable W-Model Benchmark Problem for Simulating them // Proceedings of Genetic and Evolutionary Computation Conference Companion. — 2018. — C. 1769—1776.

27. Doerr B., Giessen C, Witt C, Yang J. The (1+À) Evolutionary Algorithm with Self-adjusting Mutation Rate // Proceedings of the Genetic and Evolutionary Computation Conference. — Berlin, Germany : ACM, 2017. — C. 1351—1358.

28. Doerr B., Doerr C. Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings // Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. — 2015. — C. 1335—1342.

29. Doerr C., Ye F., Horesh N., Wang H., Shir O. M., Back T. Benchmarking discrete optimization heuristics with IOHprofiler // Proceedings of the Genetic and Evolutionary Computation Conference Companion. — 2019. — C. 1798—1806.

30. De Jong K. A. An analysis of the behavior of a class of genetic adaptive systems. — University of Michigan, 1975.

31. Scholkopf B., Smola A., Muller K.-R. Nonlinear component analysis as a kernel eigenvalue problem // Neural Computation. — 1998. — Т. 10, № 5. — С. 1299—1319.

32. Bull A. D. Convergence Rates of Efficient Global Optimization Algorithms // J. Mach. Learn. Res. — 2011. — Т. 12. — С. 2879—2904.

33. Rasmussen C. E., Williams C. K. I. Gaussian processes for machine learning. — MIT Press, 2006.

34. Raponi E, Wang H., Bujny M., Boria S., Doerr C. High Dimensional Bayesian Optimization Assisted by Principal Component Analysis // Proceedings of the Parallel Problem Solving from Nature. Т. 12269. — Springer, 2020. — С. 169—183.

35. Byrd R. H, Lu P., Nocedal J., Zhu C. A limited memory algorithm for bound constrained optimization // SIAM Journal on scientific computing. — 1995. — Т. 16, № 5. — С. 1190—1208.

36. Hansen N., Ostermeier A. Completely Derandomized Self-Adaptation in Evolution Strategies // Evolutionary Computation. — 2001. — Т. 9, № 2. — С. 159—195.

37. Hansen N., Auger A., Ros R., Mersmann O, Tusar T., Brockhoff D. COCO: A platform for comparing continuous optimizers in a black-box setting // Optimization Methods and Software. — 2020. — С. 1—31.

38. Theory of Evolutionary Computation-Recent Developments in Discrete Optimization / под ред. B. Doerr, F. Neumann. — Springer, 2020.

39. Back T., Emmerich M., Shir O. M. Evolutionary algorithms for real world applications [Application Notes] // IEEE Computational Intelligence Magazine. — 2008. — Т. 3, № 1. — С. 64—67.

40. Evolutionary Computation in Bioinformatics / под ред. G. Fogel, D. Corne. — USA : Morgan Kaufmann, 2003.

41. Harman M, Mansouri A., Zhang Y. Search-Based Software Engineering: Trends, Techniques and Applications // ACM Computing Surveys. — 2012. — Т. 45. — С. 1—78.

42. Automated Machine Learning - Methods, Systems, Challenges / под ред. F. Hutter, L. Kotthoff, J. Vanschoren. — Berlin, Heidelberg : Springer, 2019. — (The Springer Series on Challenges in Machine Learning).

43. Doerr C. Non-Static Parameter Choices in Evolutionary Computation // Proceedings of Genetic and Evolutionary Computation Conference Companion. — New York, NY, USA : ACM, 2017. — С. 736—761.

44. Eiben A. E, Hinterding R., Michalewicz Z. Parameter control in evolutionary algorithms // IEEE Transactions on Evolutionary Computation. — 1999. — Т. 3. — С. 124—141.

45. Doerr C. Complexity Theory for Black-Box Optimization Heuristics // Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. — Springer, 2020. — С. 133—212.

46. Droste S., Jansen T, Wegener I. Upper and Lower Bounds for Randomized Search Heuristics in Black-box Optimization // Theory of Computing Systems. — 2006. — Т. 39. — С. 525—544.

47. Doerr B., Winzen C. Playing Mastermind with Constant-Size Memory // Theory of Computing Systems. — 2014. — Т. 55. — С. 658—684.

48. Badkobeh G., Lehre P. K., Sudholt D. Unbiased Black-Box Complexity of Parallel Search // Proceedings of the Parallel Problem Solving from Nature. Т. 8672. — Springer, 2014. — С. 892—901.

49. Lehre P. K., Sudholt D. Parallel Black-Box Complexity with Tail Bounds // IEEE Transactions on Evolutionary Computation. — 2020. — Т. 24, № 6. — С. 1010—1024.

50. Doerr C, Lengler J. Introducing elitist black-box models: When does elitist behavior weaken the performance of evolutionary algorithms? // Evolutionary Computation. — 2017. — Т. 25, № 4. — С. 587—606.

51. Lehre P. K., Witt C. Black-Box Search by Unbiased Variation // Algorithmica. — 2012. — Т. 64, № 4. — С. 623—642.

52. Rowe J., Vose M. Unbiased Black Box Search Algorithms // Proceedings of the Genetic and Evolutionary Computation Conference. — ACM, 2011. — С. 2035—2042.

53. Witt C. Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions // Combinatorics, Probability & Computing. — 2013. — Т. 22. — С. 294—318.

54. Sudholt D. A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms // IEEE Transactions on Evolutionary Computation. — 2013. — Т. 17. — С. 418—435.

55. Gießen C, Witt C. The Interplay of Population Size and Mutation Probability in the (1 + A) EA on OneMax // Algorithmica. — 2017. — Т. 78, № 2. — С. 587—609.

56. Oliveto P. S., Sudholt D., Witt C. A tight lower bound on the expected runtime of standard steady state genetic algorithms // Proceedings of the Genetic and Evolutionary Computation Conference. — ACM, 2020. — С. 1323—1331.

57. Chicano F., Sutton A. M, Whitley L. D, Alba E. Fitness probability distribution of bit-flip mutation // Evolutionary computation. — 2015. — Т. 23, № 2. — С. 217—248.

58. Gießen C., Witt C. Optimal Mutation Rates for the (1 + A) EA on OneMax Through Asymptotically Tight Drift Analysis // Algorithmica. — 2018. — Т. 80, № 5. — С. 1710—1731.

59. Aleti A., Moser I. A Systematic Literature Review of Adaptive Parameter Control Methods for Evolutionary Algorithms // ACM Computing Surveys. — 2016. — Т. 49. — С. 1—35.

60. Bäck T. Self-adaptation in genetic algorithms // Proceedings of the first european conference on artificial life. — MIT press Cambridge. 1992. — С. 263—271.

61. Fialho A., Da Costa L, Schoenauer M., Sebag M. Extreme Value Based Adaptive Operator Selection // Parallel Problem Solving from Nature - PPSN X / под ред. G. Rudolph, T. Jansen, N. Beume, S. Lucas, C. Poloni. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2008. — С. 175—184.

62. Doerr B., Doerr C, Yang J. Optimal parameter choices via precise black-box analysis // Theoretical Computer Science. — 2020. — Т. 801. — С. 1—34.

63. Buskulic N., Doerr C. Maximizing drift is not optimal for solving OneMax // Proceedings of the Genetic and Evolutionary Computation Conference Companion. — 2019. — C. 425—426.

64. Shahriari B., Swersky K., Wang Z, Adams R. P., Freitas N. de. Taking the Human Out of the Loop: A Review of Bayesian Optimization // Proceedings of the IEEE. — 2016. — T. 104, № 1. — C. 148—175.

65. Santner T. J., Williams B. J., Notz W. I. The Design and Analysis of Computer Experiments. — Springer, 2003.

66. Niederreiter H. Low-discrepancy and low-dispersion sequences // Journal of number theory. — 1988. — T. 30, № 1. — C. 51—70.

67. Li C., Gupta S., Rana S., Nguyen V., Venkatesh S., Shilton A. High Dimensional Bayesian Optimization Using Dropout // Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI). — AAAI Press, 2017. — C. 2096—2102.

68. Ulmasov D., Baroukh C., Chachuat B., Deisenroth M. P., Misener R. Bayesian optimization with dimension scheduling: Application to biological systems // Computer Aided Chemical Engineering. T. 38. — Elsevier, 2016. — C. 1051—1056.

69. Ben Salem M., Bachoc F., Roustant O, Gamboa F., Tomaso L. Sequential dimension reduction for learning features of expensive black-box functions. — 2019 ; — preprint.

70. Duvenaud D. K., Nickisch H., Rasmussen C. Additive Gaussian Processes // Advances in Neural Information Processing Systems. T. 24. — Curran Associates, Inc., 2011.

71. Delbridge I., Bindel D., Wilson A. G. Randomly Projected Additive Gaussian Processes for Regression // Proceedings of the 37th International Conference on Machine Learning (ICML). — PMLR, 11.2020. — C. 2453—2463.

72. Rolland P., Scarlett J., Bogunovic I., Cevher V. High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups // Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. — PMLR, 03.2018. — C. 298—307.

73. Muehlenstaedt T., Roustant O, Carraro L., Kuhnt S. Data-Driven Kriging Models Based on FANOVA-decomposition // Statistics and Computing. — 2012. — Май. — Т. 22, № 3. — С. 723—738.

74. Ginsbourger D., Roustant O, Schuhmacher D., Durrande N., Lenz N. On ANOVA decompositions of kernels and Gaussian random field paths // Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014. — Springer, 2016. — С. 315—330.

75. Wang Z, Hutter F., Zoghi M., Matheson D., Freitas N. de. Bayesian optimization in high dimensions via random embeddings // Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). — 2016. — С. 1778—1784.

76. Guhaniyogi R., Dunson D. B. Compressed Gaussian Process for Manifold Regression // Journal of Machine Learning Research. — 2016. — Т. 17, № 69. — С. 1—26.

77. Gaudrie D., Riche R. L., Picheny V., Enaux B., Herbert V. Modeling and Optimization with Gaussian Processes in Reduced Eigenbases - Extended Version // Structural and Multidisciplinary Optimization. — 2020. — Июнь. — Т. 61, № 6. — С. 2343—2361.

78. Pinto E. C, Doerr C. Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms. — 2018.

79. Afshani P., Agrawal M., Doerr B., Doerr C., Larsen K. G., Mehlhorn K. The query complexity of a permutation-based variant of Mastermind // Discrete Applied Mathematics. — 2019. — Т. 260. — С. 28—50.

80. Antonov K., Buzdalova A., Doerr C. Mutation Rate Control in the (1 + A) Evolutionary Algorithm with a Self-adjusting Lower Bound // International Conference on Mathematical Optimization Theory and Operations Research. — Springer, 2020. — С. 305—319.

81. Pinto E. C, Doerr C. A simple proof for the usefulness of crossover in blackbox optimization // Parallel Problem Solving from Nature - PPSN XV. — 2018. — С. 29—41.

82. Najaran M, Prägel-Bennett A. An analysis of the fitness landscape of travelling salesman problem // Evolutionary computation. — 2016. — Т. 24, № 2. — С. 347—384.

83. Buzdalova A., Doerr C., Rodionova A. Hybridizing the 1/5-th success rule with Q-learning for controlling the mutation rate of an evolutionary algorithm // Parallel Problem Solving from Nature - PPSN XVI. — 2020. — C. 485—499.

84. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, Third Edition. — 3rd. — The MIT Press, 2009.

85. Golub G. H, Van Loan C. F. Matrix computations. — JHU press, 2013.

86. Apache Software Foundation. Apache Commons Math. — 2024. — Project website. https://commons.apache.org/proper/commons-math/.

87. García-González A., Huerta A., Zlotnik S., Diez P. A kernel Principal Component Analysis (kPCA) digest with a new backward mapping (pre-image reconstruction) strategy // arXiv:2001.01958. — 2020.

88. Antonov K., Raponi E., Wang H, Doerr C. High dimensional Bayesian optimization with kernel principal component analysis // International Conference on Parallel Problem Solving from Nature. — Springer. 2022. — C. 118—131.

89. Helsgaun K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems // Roskilde: Roskilde University. — 2017. — T. 12. — C. 966—980.

90. Vidal T. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood // Computers & Operations Research. — 2022. — T. 140. — C. 105643.

91. Dragomir A. G., Müller D. I. Problem size reduction methods for large CVRPs // Computers & Operations Research. — 2024. — T. 172. — C. 106820.

92. Beasley J. E. Route First—Cluster Second Methods for Vehicle Routing // Omega. — 1983. — T. 11, № 4. — C. 403—408.

93. Ye F., Doerr C., Back T. Leveraging Benchmarking Data for Informed One-Shot Dynamic Algorithm Selection // Proceedings of Genetic and Evolutionary Computation Conference Companion. — 2021. — C. 245—246.

94. Thomaser A., Kononova A., Vogt M.-E, Back T. One-shot Optimization for Vehicle Dynamics Control Systems: Towards Benchmarking and Exploratory Landscape Analysis // Proceedings of Genetic and Evolutionary Computation Conference Companion. — 2022. — C. 2036—2045.

95. Doerr B., Doerr C, Ebel F. Tight bounds for mutation-based evolutionary algorithms // Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. — ACM. 2015. — C. 1439—1446.

96. Jansen T., Zarges C. Theory of evolutionary algorithms for combinatorial optimization: a decade of progress // Theoretical Computer Science. — 2021. — T. 832. — C. 2—51.

97. Dang D., Doerr C, Lehre P. K. Escaping Local Optima with Diversity-based Parent Selection // International Conference on Parallel Problem Solving from Nature. — Springer, 2020. — C. 237—251.

98. Doerr B., Doerr C, Yang J. Self-adjusting mutation rates in evolutionary algorithms // Proceedings of the Genetic and Evolutionary Computation Conference. — ACM. 2018. — C. 1475—1482.

99. Reijnen R., Wu Y, Bukhsh Z, Zhang Y. Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization // arXiv preprint arXiv:2505.16471. — 2025.

100. Elfwing S., Uchibe E., Doya K. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning // Neural networks. — 2018. — T. 107. — C. 3—11.

101. Cybenko G. Approximation by superpositions of a sigmoidal function // Mathematics of control, signals and systems. — 1989. — T. 2, № 4. — C. 303— 314.

102. Hornik K., Stinchcombe M, White H. Multilayer feedforward networks are universal approximators // Neural networks. — 1989. — T. 2, № 5. — C. 359— 366.

103. He K., Zhang X., Ren S., Sun J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification // Proceedings of the IEEE international conference on computer vision. — 2015. — C. 1026—1034.

104. Rice J. R. The algorithm selection problem // Advances in computers. T. 15. — Elsevier, 1976. — C. 65—118.

105. Tan S.-Y., Yeh W.-C. The vehicle routing problem: State-of-the-art classification and review // Applied Sciences. — 2021. — Т. 11, № 21. — С. 10295.

106. Doerr B., Kiinnemann M. Optimizing linear functions with the (1+ A) evolutionary algorithm—different asymptotic runtimes for different instances // Theoretical Computer Science. — 2015. — Т. 561. — С. 3— 23.

107. Harremoes P. Binomial and Poisson distributions as maximum entropy distributions // IEEE Transactions on Information Theory. — 2001. — Т. 47, № 5. — С. 2039—2041.

108. Rudolph G. Evolutionary Strategies // Handbook of Natural Computing / под ред. G. Rozenberg, T. Back, J. N. Kok. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. — С. 673—698.

109. Jansen T. Evolutionary Algorithms and Other Randomized Search Heuristics // Analyzing Evolutionary Algorithms: The Computer Science Perspective. — 2013. — С. 7—29.

110. Feller W. An Introduction to Probability Theory and Its Applications. Volume 1. — 3rd. — New York : John Wiley & Sons, 1968.

111. Lin S., Kernighan B. W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem // Operations Research. — 1973. — Т. 21, № 2. — С. 498— 516.

112. Razali N. M, Wah Y. B. [и др.]. Power comparisons of shapiro-wilk, kolmogorov-smirnov, lilliefors and anderson-darling tests // Journal of statistical modeling and analytics. — 2011. — Т. 2, № 1. — С. 21—33.

113. National Institute of Standards and Technology (NIST). 1.3.5.14. AndersonDarling Test. — 2022. — URL: https : / / www . itl . nist . gov / div898/handbook/eda/section3/eda35e . htm (дата обр. 26.09.2025) ; NIST/SEMATECH e-Handbook of Statistical Methods, ITL.

114. Sheather S. J. Density estimation // Statistical science. — 2004. — С. 588— 597.

115. Welch B. L. The generalization of 'STUDENT'S'problem when several different population varlances are involved // Biometrika. — 1947. — Т. 34, № 1/2. — С. 28—35.

116. Student. The probable error of a mean // Biometrika. — 1908. — C. 1—25.

117. Lehmann E. L, Romano J. P. Testing statistical hypotheses. — Springer, 2005.

118. Snoek J., Larochelle H., Adams R. P. Practical Bayesian Optimization of Machine Learning Algorithms // Advances in neural information processing systems. — 2012. — C. 2960—2968.