Краткий обзор генетических алгоритмов. Генетические алгоритмы - очень интересный класс алгоритмов оптимизации, которые заимствуют концепции из биологической эволюции. Генетический алгоритм состоит из процесса мутации, оценки и отбора. Алгоритмы мутации могут варьироваться от безобидных изменений до совершенно разных изменений за итерацию. Алгоритм оценки измеряет, насколько каждый код «подходит» для поставленной задачи. Иногда это может потребовать дополнительных вычислений путем форматирования кода в результирующий организм. Наконец, в процессе выбора определяется, сколько кодов передать следующему поколению и какая процедура выбора используется для выбора этих кодов.
В этой статье мы обсудим основной код, который подвергается мутации, и то, как мы можем улучшить представление этого кода для получения более значимых результатов.
Генетические алгоритмы можно использовать для решения игр, например, в приведенном ниже примере:
Генетический код этой игры со змеями относится к серии ходов. На каждом временном шаге пользователь может повернуть налево, повернуть направо или не предпринимать никаких действий. Состав этих трех решений, давайте сокращенно их: (L, R, NA), аналогичен генетическому коду (A, C, G, T). Алгоритм итеративно изучает некоторую последовательность:
L | L | R | R | NA | NA | L | NA | NA | …. | L | R | # The Cardinality of this Sequence could be something like 1 million decisions results in complete victory in Snake.
Эта последовательность была оптимизирована для некоторых оценочных показателей, например, чтобы выжить в игре со змейкой как можно дольше. Оценка этой метрики требует некоторых вычислений, поскольку алгоритм должен запустить игру, чтобы узнать, насколько код подходит для выживания. К счастью, эволюционные алгоритмы могут использовать преимущества распараллеливания и запускать несколько симуляций одновременно, чтобы как можно быстрее развивать будущие поколения.
Помимо мета-деталей, таких как то, как код должен развиваться и как ускорить его оценку… Самое важное, что следует учитывать при использовании генетических алгоритмов, - это структура базового кода!
В приведенном выше примере со змеей решения игры можно легко разделить на 3 действия: повернуть налево, повернуть направо или не предпринимать никаких действий. Результирующая последовательность ходов, которая приводит к победе в игре «змейка», составляет много ходов, но эволюция последовательности будет происходить слева направо, потому что это мутации, которые приведут к наивысшей метрике оценки.
Однако, если вы примените генетические алгоритмы, например, для создания изображения, у вас будет гораздо более сложный диапазон возможных мутаций, и нет такого интуитивного пути для мутации (например, слева направо для решений о движении).
Изображение 300 x 300 (довольно маленькое изображение с низким разрешением), представленное в 3 8-битных цветовых каналах, дает 300x300x24x255 = 550 800 000 различных конфигураций изображений.
В этом примере базовый пиксельный код составляет результирующий организм, изображение. В предыдущем примере код решения, лежащий в основе, составляет результирующий организм, испытание игры в змейку. Теперь посмотрим, как музыка состоит из нот.
Фортепианная музыка чаще всего может быть разбита на ноты.
Этот код используется для создания результирующего организма, музыки. Каждая музыкальная нота может принимать около 40 значений, может содержать любое заданное количество нот на временной шаг (хотя очень редко превышает 4 или 5), а также может варьироваться в зависимости от темпа, в котором ноты воспроизводятся, (для Например, примечание с открытым кружком указывает на нажатие клавиши в течение 2 временных шагов, тогда как закрытый кружок указывает на нажатие клавиши только для 1 временного шага).
Если бы мы использовали генетические алгоритмы для создания музыки, мы бы добились большего успеха, чем попытки создавать изображения. Это в первую очередь связано с тем, что у нас есть доступ к гораздо более семантически репрезентативному базовому коду, который можно изменять.
Аудио и звуковые данные могут быть разложены таким образом, чтобы имитировать представление изображений в пикселях. Аудиосэмпл с качеством cd состоит из 44000 выборок в секунду, состоящих из синусоидальных волн, описывающих аудиоданные. Эти волны греха обрабатываются с помощью файлов, таких как mp3, для создания результирующих цифровых звуков. Аудиоданные на самом деле намного сложнее, чем данные изображения в целом, однако это представление нот дает нам более значимый код, который можно использовать для случайной генерации аудиоданных.
В South Park Studios есть интерфейс, позволяющий создать собственного персонажа: http://southpark.cc.com/avatar.
С помощью этого инструмента вам разрешено только выполнять переходы, такие как переключение шляпы, цвета, куртки, волос и т. Д. Благодаря этому более семантическому представлению вы сможете выполнить такую задачу, как: «создать аватар южного парка, который выглядит очень похоже на меня », намного быстрее. Это связано с наличием более высокоуровневого и семантического кода, который нужно изменять.
Я надеюсь, что эта статья помогла вдохновить на размышления о генетических кодах и о том, как мы можем предварительно обработать наши данные с целью использования генетических алгоритмов. Поэкспериментируйте с высокоуровневыми представлениями ваших данных, прежде чем применять генетические алгоритмы, спасибо за чтение! Пожалуйста подпишитесь!
CShorten
Коннор Шортен - студент факультета информатики Атлантического университета Флориды. Научные интересы в области науки о данных, глубокого обучения и разработки программного обеспечения. В основном кодирование на Python, JavaScript и C ++. Следите за дополнительными статьями по этим темам.
