Пользователь
0,0
рейтинг
27 ноября 2013 в 15:11

Генетические алгоритмы в Matlab играючи из песочницы

Игра включите свет
Предисловие

Здравствуй, Хабр! Хотелось бы предложить вам простой прикладной урок по генетическим алгоритмам. Если вы неплохо знакомы и работаете с ними, то чтение его напрасная трата времени. Этот урок именно для тех, кто хочет начать из использовать, но не знает как. Предполагается, что вы уже знакомы со смыслом генетических алгоритмов, немного представляете как они работают.

Суть генетических алгоритмов

Этот часть некоторые могут пропустить. Много где говорилось, я просто повторю для порядка. Как любой алгоритм многофакторной оптимизации, генетические алгоритмы призваны минимизировать целевую функцию и выдать соответствующий минимуму набор входных аргументов. Приятной особенностью именно генетических алгоритмов есть теоретическая возможность получения глобального минимума функции, читай «получения лучшего из возможных ответов». Каким образом это достигается, объясню немного позже. Генетические алгоритмы, по своей сути, не что иное, как приближенное моделирование процесса эволюции. Они оперируют понятиями «ген» и «популяция». «Ген» — это набор входных аргументов, а «популяция» — это набор генов. В классических генетических алгоритмах что бы получить ген из аргументов функции, их просто записывают подряд в двоичном коде. Получаем такую огромную двоичную змею. Как и в природном процессе эволюции, здесь есть естественный отбор. Те гены, для которых значение функции больше всех, отсеиваются, лучшие переходят в следующее поколение без изменений (элита). Другие скрещиваются с другими генами (кросс-овер). Способ скрещивания может быть разным. В самом простом случае, каждый ген из произвольной пары разрезают на две части и к началу первого гена прикрепляют конец второго, а к началу второго — конец первого. Пропорции сечения, естественно, должны быть равны для каждого из этой парочки. Есть ещё одна, обычно немногочисленная, группа генов-мутантов, у которых случайно изменяется один или несколько бит. Именно они и кросс-овер обеспечивают получения глобального минимума, даже если мы находимся в локальном.

Постановка задачи

В социальной сети ВК есть довольно инетерсная игра под названием «Включите свет» именно она пробудила желание написать статью, так как задачи, которые решает в ней пользователь просто отлично подходят для генетических алгоритмов. В трёх словах суть игры следующая: необходимо скоммутировать электростнцию и домики кабелями. На каждой клетке игрового поля находится один из чётырех типов кабелей: L-образный, Т-образный, I-образный, половинка I-образного для подключения домика (обозначим как H). Игрок свободен их вращать с шагом 90 градусов. В общем сначала лучше попробовать, что бы вникнуть.
Попробовали? Идём дальше. Необходимо построить целевую функцию от состояния игрового поля. Входными данными есть угол поворота каждого из фрагментов кабеля. Легко понять, что закодировать его можно 2 битами. Всего поле в начале игры 5x5 клекток. Следовательно длина гена в двоичном коде составит 5x5x2=50 бит. Целевая функция так и будет принимать на вход массив нулей и единиц (в Matlab есть такая возможность).
Как же оценивать качество состояния игрового поля? Я предлагаю использовать количество соединений между соседними клетками. Оценка игрового поля есть сумма оценок клеток. Каждое соединение клетки с соседом — балл. Соседей в клетки 4: верхний, нижний, левый, правый.

Особенности реализации

Не хотелось бы пастить исходники и построчно их разбирать, как некоторые это любят делать на Хабре. Для этого сойдёт и git репозиторий: github.com/player999/turnonthelight. Комментарии в README должны помочь. Сейчас советую открыть исходники и чиать их вместе со статьей. Я нарочно их сделал достаточно попроще. Просто затронем важные моменты реализации. На вход программы попадает начальное состояния игрового поля в текстовом файле примерно в таком виде:
H1 H0 I1 I1 I3
I1 H2 T1 T1 I3
L3 L2 H1 L0 H1
H0 L1 T3 I0 T3
L0 I0 L0 L0 L0

Тут буква — тип ячейки, а цифра — ориентация от 0 до 270 градусов с шагом 90 градусов по часовой стрелке. Это поле считывается с помощью функции scheme_config, которая вызывается из основного скрипта run. Дальше к нему можно применить генетический алгоритм посредством вызова функции solve_scheme. В скрипте run целевая функция обозначается как fun, которая есть оберткой для функции eval_bits. eval_bits принимает две двоичные строки, которые описывают игровое поле. Первая — типы ячеек, вторая — их ориентации. Естественно, на протяжении работы генетического алгоритма первый параметр должен быть постоянен. Игрок не может изменять типы ячеек. Эти строки строятся массива клеток игрового поля функцией scheme2string. eval_bits есть оберткой для eval_scheme. Это и есть ядро целевой функции, а eval_bits просто преобразовывает аргументы в матрицу, описывающую игровое поле.
Надеюсь понятно как работает целевая функция. Теперь к самой минимизации. Сначала необходимо получить структуру с опциями генетического алгоритма. Их там много и на любой вкус. Но указал только самые важные.
options = gaoptimset('PopulationType','bitstring','PopulationSize',1000,'Generations',100);

PopulationType — представление аргументов. В нашем случае — битовая строка. И хоть тут фигурирует слово «строка», в самом деле это массив double из нулей и единиц.
PopulationSize — сколько генов будет на каждой итерации. Чем больше генов, тем, качественней будет работать алгоритм, но вместе с тем и медленней. Для каждого гена ведб нужно вычислять целевую функцию.
Generations — количество итераций генетического алгоритма. Это одно из возможных условий выхода. Ещё одним, например, есть выход, когда изменение целевой функции прекращается.
Дальше следует вызов функции оптимизации:
opt = ga(fun,length(pos),[],[],[],[],[],[],[],options);

Тут пропущенны массивы с ограничениями, так как для этой задачи они не актуальны. length(pos) отражает количество аргументов. Детальней об этих функциях можно прочесть в справке Matlab, она шикарна. Также рекомендую поиграть с настройками Optimization Toolbox (команда optimtool), все те же настройки, облаченные в графический интерфейс для удобства.
Далее происходит преобразования наилучшего гена с помощью string2scheme обратно в игровое поле и отрисовка игровго поля функцией draw_scheme.

Выводы

Хоть алгоритм ещё и требует настройки, но он уверенно доказал то, что может искать решения головоломки. Надеюсь вам хоть немного помогла статья, ну или хотя бы развлекла. Вот результат работы, например.
Ркзультат работы
Тарас Захарченко @FT232BM
карма
8,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (6)

  • +2
    А есть какие-нибудь метрики срвнения генетических алгоритмов оптимизации с более традиционными?
    например, со стохастическим градиентным спуском?
    • +1
      К сожалению, сейчас работа с алгоритмами многофакторной оптимизации — больше искусство. Давать именно количественную оценку, а не качественную можно только для конкретно взятой задачи.
      Тем не менее можно давать общие рекомендации (читай «качественные оценки»):
      *Стохастический градиентный спуск занимает немного больше процессорного времени, чем генетические алгоритмы, так как ЦФ вычисляется два раза (нужно уточнить). Ещё больше занимает времени методы оптимизации второго порядка, там где происходит манипуляция с производными второй степени, например метод сопряженных градиентов.
      *Память что градиентные методы, что ГА кушают относительно немного, в отличии, опять таки от методов второго порядка. Упомянуты метод сопряженных градиентов ещё более-менее терпим к малы объемам памяти, но BFGS или метод Левенберга-М. например, требуют очень много оной.
      *Как уже писал в своей статье, ГА дают хотя бы теоретическую надежду на получение глобального минимума, а градиентные методы — напротив, это самая чувствительная к локальным минимумам группа.
    • 0
      Когда у нас конечное, дискретное, но при этом очень большое пространство входных параметров (как, например, здесь), то лучше метода Монте-Карло не существует. А еще и целевая функция не непрерывная. Тут, по-моему, вообще сложно говорить о градиентных методах.
      ГА нам предлагает, по сути, управляемый Монте-Карло. Чем и хорош.
      • 0
        Когда у нас конечное, дискретное, но при этом очень большое пространство входных параметров (как, например, здесь)

        В таких условиях на практике Particle Swarm Optimization нередко показывает себя лучше, чем ГА. К тому-же это подход очень хорошо поддается распараллеливанию, в том числе и на GPU.
        • 0
          Я так понимаю, вы имеете в виду данную вариацию метода PSO, поскольку в остальных входные параметры из R^n. Мне не нравится подход в стиле «погрузим дискретные значения в непрерывную область, все посчитаем, в конце затолкаем опять в конечную» — в случае с градиентным спуском у меня это плохо работало. Более того, если целевая функция определена исключительно на дискретном пространстве, нужно каждую итерацию (например) округлять значения, а это накладно и вообще мне не по душе :)
          Но вообще конкретно с PSO такой вариант не пробовал, может, и получится.
  • 0

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.