Генетические алгоритмы

О чём урок

Генетические алгоритмы (ГА) основаны на эволюционном подходе к ИИ, при котором для получения оптимального решения заданной задачи используются методы эволюции популяции. Они были предложены в 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 ферзях.

План урока

1. Тест перед лекцией
2. Типичные задачи
3. ✍️ Упражнения: Генетические алгоритмы
4. Заключение
5. 🚀 Задание
6. Тест после лекции
7. Обзор и самостоятельное изучение
8. Задание: Диофантово уравнение