Назад в библиотеку

Гибридный генетический алгоритм с адаптивным управлением параметрами

Авторы: Chen, X., Wang, Y., & Li, Z. Год: 2021 Журнал: Journal of Computational Optimization
генетический алгоритм гибридный алгоритм адаптивное управление оптимизация

Аннотация

В данной статье представлен гибридный генетический алгоритм с адаптивным управлением параметрами (HGA-APC) для решения сложных задач оптимизации. Предложенный подход сочетает в себе преимущества генетического алгоритма (ГА) и локального поиска, что позволяет эффективно исследовать пространство решений. Ключевой особенностью HGA-APC является механизм адаптивного изменения вероятности кроссовера и мутации в зависимости от характеристик популяции. Экспериментальные результаты на стандартных тестовых функциях демонстрируют превосходство HGA-APC по сравнению с традиционными генетическими алгоритмами и другими гибридными методами.

Введение

Генетические алгоритмы (ГА) представляют собой мощный метод оптимизации, основанный на принципах естественного отбора и генетики. Однако традиционные ГА часто страдают от преждевременной сходимости и низкой скорости поиска вблизи оптимума. Для преодоления этих ограничений исследователи разработали различные модификации, включая гибридные подходы, которые сочетают ГА с другими методами оптимизации.

В данной работе мы предлагаем гибридный генетический алгоритм с адаптивным управлением параметрами (HGA-APC), который интегрирует локальный поиск в процесс эволюции и динамически регулирует параметры алгоритма на основе разнообразия популяции.

Ключевые особенности HGA-APC

Методология

Предложенный алгоритм HGA-APC состоит из следующих основных этапов:

  1. Инициализация популяции случайными решениями
  2. Оценка приспособленности каждой особи
  3. Адаптивный выбор параметров кроссовера и мутации на основе разнообразия популяции
  4. Применение генетических операторов (отбор, кроссовер, мутация)
  5. Локальный поиск для улучшения перспективных решений
  6. Формирование новой популяции с сохранением элитных особей
  7. Проверка критерия останова

Адаптивное управление параметрами

В HGA-APC вероятность кроссовера (pc) и вероятность мутации (pm) динамически изменяются в зависимости от разнообразия популяции, которое измеряется с помощью метрики дисперсии приспособленности:

pc = pc_min + (pc_max - pc_min) × (1 - D)
pm = pm_min + (pm_max - pm_min) × D

где D - мера разнообразия популяции (0 ≤ D ≤ 1), pc_min, pc_max, pm_min, pm_max - граничные значения вероятностей.

Алгоритм HGA-APC

Алгоритм HGA-APC
Вход: Параметры алгоритма, критерий останова
Выход: Лучшее найденное решение
1: Инициализировать популяцию P случайными особями
2: while не выполнен критерий останова do
3: Оценить приспособленность каждой особи в P
4: Вычислить меру разнообразия D популяции P
5: Адаптировать pc и pm на основе D
6: Применить отбор для формирования родительской пары
7: Применить кроссовер с вероятностью pc
8: Применить мутацию с вероятностью pm
9: Применить локальный поиск к лучшим особям
10: Сохранить элитные особи
11: Сформировать новую популяцию P'
12: P ← P'
13: end while
14: return лучшую особь из P

Экспериментальные результаты

Для оценки эффективности HGA-APC были проведены эксперименты на наборе из 10 стандартных тестовых функций, включая функции с одним и многими оптимумами. Алгоритм сравнивался с традиционным ГА, ГА с фиксированными параметрами и другими гибридными алгоритмами.

Тестовая функция Традиционный ГА ГА с фиксир. параметрами HGA-APC
Sphere 1.24e-03 8.76e-04 2.15e-06
Rosenbrock 45.32 32.18 12.45
Rastrigin 15.67 12.34 5.23
Ackley 1.45 1.12 0.38
Griewank 0.087 0.065 0.012

Таблица 1: Средние значения ошибки для различных алгоритмов после 1000 итераций

Преимущества HGA-APC

  • Более быстрая сходимость по сравнению с традиционными ГА
  • Улучшенная способность избегать локальных оптимумов
  • Автоматическая настройка параметров в процессе работы
  • Высокая точность решений для различных типов задач

Недостатки HGA-APC

  • Увеличенное время вычислений из-за локального поиска
  • Дополнительные параметры для настройки алгоритма
  • Более сложная реализация по сравнению с базовым ГА

Заключение

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

Ссылки

  1. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning.
  2. Eiben, A. E., & Smith, J. E. (2015). Introduction to Evolutionary Computing.
  3. Holland, J. H. (1992). Adaptation in Natural and Artificial Systems.
  4. Davis, L. (1991). Handbook of Genetic Algorithms.