2_5413713075817717523

1. Метод генетического алгоритма оптимизации

Выполнил студент БПИ-211
Дьячков М.О.

2. Цель

программная реализация
генетического алгоритма с
визуализацией процесса
эволюционного поиска экстремума
2

3. Задачи

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

4. Актуальность

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

5. История создания метода

Генетический
алгоритм
классических
методов
оптимизации,
основанный
—
один
из
эволюционной
на
принципах
естественного отбора и наследственности. Он
был разработан во второй половине XX века и
стал
важным
методах
инструментом
оптимизации
в
численных
благодаря
своей
способности находить глобальный экстремум в
сложных
многоэкстремальных
задачах.
Основоположником
генетических
алгоритмов
считается
Холланд
профессор
Джон
Мичиганского университета.
-
5

6. Как работает метод

Генетические алгоритмы –
адаптивные методы поиска,
которые используются для
решения задач функциональной
оптимизации. Они основаны на
механизмах и моделях эволюции,
и генетических процессов
биологических алгоритмов.
Алгоритм создает «популяцию»
случайных решений, оценивает их
«приспособленность», затем
скрещивает лучшие решения и
применяет случайные мутации для
создания нового, более
эффективного поколения. Процесс
повторяется, пока не будет
найдено лучшее решение
6

7. Алгоритм решения

Шаг 1. Инициализация популяции
Создаётся N случайных точек в пространстве поиска.
Каждая особь — вектор координат:
Особь i=(xi,yi),i=1…N
xi и yiyi выбираются случайно в заданных диапазонах:
xi∈[xmin,xmax],yi∈[ymin,ymax]
*Особь – одно решение задачи.
*Популяция — набор решений задачи. В начале
алгоритма случайным образом генерируется набор
решений (начальная популяция).
7

8. Алгоритм решения

Шаг 2. Оценка приспособленности (Fitness)
Для каждой особи вычисляется значение целевой функции.
При поиске минимума:
fitnessi​=f(xi​,yi​)
Чем меньше значение, тем лучше особь.
При поиске максимума задача сводится к минимизации:
fitnessi=−f(xi,yi)
8

9. Алгоритм решения

Шаг 3. Проверка условия останова
Алгоритм завершается, если выполнено одно из условий:
1.Достигнуто максимальное количество поколений.
2.Пользователь остановил выполнение.
3.Результат не улучшается в течение нескольких поколений
(опционально).
Если условие выполнено → возвращается лучшая найденная
особь.
Если нет → переход к шагу 4.
9

10. Алгоритм решения

Шаг 4. Селекция (отбор родителей)
Используется турнирный отбор:
1.Случайно выбирается k особей (обычно k=3).
2.Из них выбирается одна с наилучшим fitness.
3.Выбранная особь становится родителем.
4.Процесс повторяется, пока не набрано N родителей.
Вероятность выбора лучшей особи выше, чем у худшей.
10

11. Алгоритм решения

Шаг 5. Кроссинговер (скрещивание)
Из двух родителей P1​ и P2​ создаются два потомка C1​ и C2​.
Используется арифметический кроссинговер:
C1​=α⋅P1​+(1−α)⋅P2​
C2​=(1−α)⋅P1​+α⋅P2​
где α∈[0,1] — случайное число.
Кроссинговер выполняется с
вероятностью pcrossover (обычно 0.6–0.9).
Если скрещивание не произошло, потомки — копии
родителей.
11

12. Алгоритм решения

Шаг 6. Мутация
Каждая особь может быть случайно изменена с вероятностью pmut (обычно
0.01–0.1).
Используется гауссовская мутация:
x′=x+N(0,σ)
y′=y+N(0,σ)
где N(0,σ) — случайное значение из нормального распределения.
После мутации координаты ограничиваются заданными диапазонами:
x′=max(xmin​,min(xmax​,x′))
Мутация поддерживает разнообразие и помогает избежать застревания в
локальных минимумах.
12

13. Алгоритм решения

Шаг 7. Элитизм
Лучшие E особей текущего поколения переходят в следующее
поколение без изменений.
Остальные N−E мест заполняются потомками, полученными
после кроссинговера и мутации.
Элитизм гарантирует, что лучшее найденное решение не будет
потеряно.
Шаг 8. Формирование нового поколения
Новое поколение = элита + потомки.
Старая популяция заменяется новой.
Затем происходит возврат к шагу 2 (оценка популяции).
13

14. Если кратко

1.Инициализация популяции
2.Оценка fitness
3.Проверка останова → если ДА, выход
4.Селекция родителей
5.Кроссинговер
6.Мутация
7.Элитизм
8.Новое поколение → переход к шагу 2
14

15. Минусы и плюсы

+:
-:
• Не требуют вычисления
•Медленная сходимость
производных
(требуют много вычислений)
• Находят глобальный оптимум (не •Нет гарантии нахождения
застревают в локальных
глобального оптимума
минимумах)
•Чувствительны к выбору
• Работают с любыми функциями параметров
•Эффективность падает с
(разрывными, зашумлёнными,
негладкими)
ростом размерности задачи
• Легко распараллеливаются
• Просты в реализации
15

16. Практика

1. Инженерное проектирование —
оптимизация формы крыльев, конструкций,
антенн
2. Машинное обучение — настройка
гиперпараметров нейросетей, отбор
признаков
3. Робототехника — обучение движению,
оптимизация траекторий
4. Экономика и финансы — оптимизация
инвестиционных портфелей
5. Биоинформатика — анализ ДНК,
предсказание структуры белков
6. Логистика — задача коммивояжёра,
маршрутизация транспорта
7. Энергетика — оптимизация работы
электростанций, размещение ветряков
8. Игры — создание адаптивных ботов,
генерация уровней
16

17. Python в реализации генетического алгоритма

имеет мощные библиотеки для
оптимизации;
обеспечивает простоту и скорость
разработки за счёт
минималистичного синтаксиса;
позволяет легко визуализировать
процесс оптимизации;
работает на всех основных
операционных системах без
изменений кода;
17

18. Графическое приложение

18

19. Вывод

• Эффективный способ оптимизации без производных.
• Сочетает исследующий и направленный поиск.
• Применяется в инженерных, научных и прикладных
задачах.
• Богатые библиотеки (scipy, numpy, matplotlib).
• Простота разработки и высокая скорость реализации.
• Кроссплатформенность и активная поддержка
сообщества.
19