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