Урок из полного доступа, первые уроки курса бесплатно Официальный курс Microsoft AI for Beginners на русском
Урок 22 · Текст · ~5 мин

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

Урок 22 из 25 курса «Основы ИИ для начинающих»: официальный курс Microsoft AI for Beginners (Майкрософт) на русском языке. Урок входит в платный доступ; первые уроки курса бесплатно.

О чём урок

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

Генетические алгоритмы базируются на следующих идеях:

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

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

  • Найти метод кодирования решений нашей задачи с помощью генов g∈Γ.
  • На множестве генов Γ необходимо определить функцию приспособленности fit: Γ→R. Меньшие значения функции соответствуют лучшим решениям.
  • Определить механизм скрещивания для объединения двух генов с целью получения нового допустимого решения crossover: Γ2→Γ.
  • Определить механизм мутации mutate: Γ→Γ.

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

Конкретная реализация генетического алгоритма может варьироваться от случая к случаю, но общая структура выглядит следующим образом:

  1. Выберите начальную популяцию G⊂Γ.
  2. Случайным образом выберите одну из операций, которая будет выполнена на этом шаге: скрещивание или мутация.
  3. Скрещивание:
  • Случайным образом выберите два гена g1, g2 ∈ G.
  • Вычислите скрещивание g=crossover(g1,g2).
  • Если fit(g)<fit(g1) или fit(g)<fit(g2), замените соответствующий ген в популяции на g.
  1. Мутация: выберите случайный ген g∈G и замените его на mutate(g).
  2. Повторяйте с шага 2, пока не будет достигнуто достаточно малое значение fit или пока не будет достигнут лимит на количество шагов.

Задачи, которые обычно решаются с помощью генетических алгоритмов:

  1. Оптимизация расписания.
  2. Оптимальная упаковка.
  3. Оптимальная нарезка.
  4. Ускорение полного перебора.

Продолжите обучение в следующих ноутбуках:

Перейдите в этот ноутбук, чтобы увидеть два примера использования генетических алгоритмов:

  1. Справедливое разделение сокровищ.
  2. Задача о 8 ферзях.

Генетические алгоритмы используются для решения…

План урока

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

Урок входит в полный доступ. Полный текст и видео открываются после оплаты. Первые уроки каждого курса бесплатны.

Откройте полный доступ

Вы прошли бесплатные уроки. Выберите тариф, чтобы продолжить обучение.

Курсы Microsoft 1 490 ₽ Разовый платёж, навсегда
  • Все курсы от Microsoft (3 шт.)
  • Именной сертификат по каждому пройденному курсу
Оплатить
Полный доступ 4 900 ₽ Разовый платёж, навсегда
  • Все 77 курсов от 11 AI-провайдеров
  • Библиотека промптов и новые курсы
Оплатить

Безопасная оплата через Robokassa: СБП, карты, электронные кошельки. Доступ откроется в этом браузере и придёт письмом. Уже оплатили? Восстановить доступ

Полезные гиды