О чём урок
Генетические алгоритмы (ГА) основаны на эволюционном подходе к ИИ, при котором для получения оптимального решения заданной задачи используются методы эволюции популяции. Они были предложены в 1975 году Джоном Генри Холландом.
Генетические алгоритмы базируются на следующих идеях:
- Допустимые решения задачи можно представить как гены.
- Скрещивание позволяет объединить два решения для получения нового допустимого решения.
- Отбор используется для выбора более оптимальных решений с помощью некоторой функции приспособленности.
- Мутации вводятся для дестабилизации оптимизации и выхода из локального минимума.
Если вы хотите реализовать генетический алгоритм, вам потребуется следующее:
- Найти метод кодирования решений нашей задачи с помощью генов g∈Γ.
- На множестве генов Γ необходимо определить функцию приспособленности fit: Γ→R. Меньшие значения функции соответствуют лучшим решениям.
- Определить механизм скрещивания для объединения двух генов с целью получения нового допустимого решения crossover: Γ2→Γ.
- Определить механизм мутации mutate: Γ→Γ.
Во многих случаях скрещивание и мутация представляют собой достаточно простые алгоритмы для манипулирования генами как числовыми последовательностями или битовыми векторами.
Конкретная реализация генетического алгоритма может варьироваться от случая к случаю, но общая структура выглядит следующим образом:
- Выберите начальную популяцию G⊂Γ.
- Случайным образом выберите одну из операций, которая будет выполнена на этом шаге: скрещивание или мутация.
- Скрещивание:
- Случайным образом выберите два гена g1, g2 ∈ G.
- Вычислите скрещивание g=crossover(g1,g2).
- Если fit(g)<fit(g1) или fit(g)<fit(g2), замените соответствующий ген в популяции на g.
- Мутация: выберите случайный ген g∈G и замените его на mutate(g).
- Повторяйте с шага 2, пока не будет достигнуто достаточно малое значение fit или пока не будет достигнут лимит на количество шагов.
Задачи, которые обычно решаются с помощью генетических алгоритмов:
- Оптимизация расписания.
- Оптимальная упаковка.
- Оптимальная нарезка.
- Ускорение полного перебора.
Продолжите обучение в следующих ноутбуках:
Перейдите в этот ноутбук, чтобы увидеть два примера использования генетических алгоритмов:
- Справедливое разделение сокровищ.
- Задача о 8 ферзях.
Генетические алгоритмы используются для решения…
План урока
- Тест перед лекцией
- Типичные задачи
- ✍️ Упражнения: Генетические алгоритмы
- Заключение
- 🚀 Задание
- Тест после лекции
- Обзор и самостоятельное изучение
- Задание: Диофантово уравнение
Урок входит в полный доступ. Полный текст и видео открываются после оплаты. Первые уроки каждого курса бесплатны.