Лекция №6. Генетические алгоритмы

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

Основная идея генетических алгоритмов состоит в том, что решение ищется не одной последовательностью приближенных решений, а сразу целой популяцией приближенных решений. При этом на каждом шаге происходит генетический отбор лучших приближений, из которых создаются новая популяция. Для добавления "новой крови" периодически используется мутация решений.

Посмотрите нашу видео-лекцию, посвященную генетическим алгоритмам:

Опишем пример генетического алгоритма для решения оптимизационной задачи. Пусть наша задача состоит в нахождении минимума следующей функции

f(x, y, z) = x2(1 + sin(100x)) + y2(1 + sin(100y)) + z2(1 + sin(100z))

Мы видим, что эта функция имеет быстрые осциляции и локальные минимумы, поэтому использование градиентных методов будет затруднительно. Хотя это и сложная функция, но легко видеть, что минимум этой функции равен нулю, который достигается при x=y=z=0.

В генетическом алгоритме мы используем популяцию генов. При этом каждый ген состоит из равного количества хромосом. В нашем случае ген - это тройка вещественных чисел

G = [x, y, z].

Наш ген состоит из трех хромосом: x, y и z. Мы будем писать G(x), G(y), G(z) для указания соответствующих хромосом.

Мы будем рассматривать популяцию из пяти генов: G1, G2, G3, G4, G5. Для каждого гена можно вычислить его значения в нашей функции.

Рассмотрим работу генетического алгоритма

  1. Создаем популяцию из пяти генов случайным образом.
  2. Упорядочиваем гены в порядке возрастания их значений в целевой функции. Получаем последовательность

    G1, G2, G3, G4, G5.


  3. Гены G4 и G5 отбрасываем, как самые плохие.
  4. Конструируем новое поколение генов по следующему правилу

    [G1(x), G1(y), G2(z)]

    [G2(x), G1(y), G1(z)]

    [G1(x), G2(y), G1(z)]

    [G1(x), G3(y), G2(z)]

    [G2(x), G1(y), G3(z)]


  5. Для трех последних генов проводим мутацию, которая состоит в том, что мы добавляем случайные значения к хромосомам, при этом третий ген мутируется меньше чем четвертый, а четвертый меньше чем пятый.
  6. Переход к шагу 2.

Завершать алгоритм можно по разным критериям, например, выполнять заданное количество итераций.

Рассмотрим пример работы программы, которая реализует генетический алгоритм. Исходный текст программы на языке Python можно скачать AI-GenSimple3.

Приведем график эволюции решения, за которое мы принимаем значение лучшего гена:


Чтобы более точно оценить сходимость нашего алгоритма приведем этот график в логарифмическом формате:


Мы видим, что наш алгоритм достаточно быстро находит оптимальное решение.

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

Home | Лекции | Python | Видео | Скачать | Ссылки
Copyright (c) 2017, Roman Shamin
60
6684
31