ЭВОЛЮЦИОННЫЕ  МЕТОДЫ  В  АЛГОРИТМИЧЕСКОЙ  КОМПОЗИЦИИ.  ГЕНЕТИЧЕСКИЕ  АЛГОРИТМЫ  И  МУРАВЬИНЫЙ  АЛГОРИТМ

Славщик  Арсений  Алексеевич

аспирант  Сибирского  Федерального  Университета,  Институт  Космических  и  Информационных  Технологий,  НУЛ  САПР

E-mail:  arssanderson@yandex.ru

Эволюционные  вычисления  в  широком  смысле  можно  определить  как  область  информатики,  в  которой  используются  вычислительные  модели,  аналогичные  идеям  Дарвиновского  эволюционного  процесса.  Существует  огромное  множество  методов  оптимизации  на  основе  эволюционных  методов  (например,  муравьиный  алгоритм,  алгоритм  имитации  отжига).  Для  решения  задач  алгоритмической  композиции  (процесса  генерации  музыкальных  отрывков,  мелодий  и  произведений  с  помощью  вычислительных  методов)  на  данный  момент  используются  четыре:  генетические  алгоритмы,  один  из  методов  роевого  интеллекта  —  муравьиный  алгоритм,  Л-системы,  и  клеточные  автоматы  [4,  c.  7—9].  В  данной  статье  будет  дан  обзор  первых  двух. 

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

В  общем  смысле  работа  генетического  алгоритма  начинается  с  применения  эквивалента  биологического  образования  новых  генов  на  пространство  случайно  распределенных  решений  для  нахождения  в  итоге  оптимального  набора  [5,  c.  3—6]. 

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

Первыми  целесообразность  применения  ГА  для  моделирования  музыкального  творчества  обосновали  профессор  кафедры  компьютерных  наук  Гонг-Конгского  университета  Эндрю  Хорнер  и  профессор  кафедры  индустриальной  инженерии  Университета  Иллинойса  Дэвид  Голдберг  в  1991  году  [3,  с.  479—482].

Первыми  успешными  исследованиями  в  области  применения  генетических  алгоритмов  в  генеративной  музыке  можно  считать  Джона  Бильса  —  профессора  Рочестерского  института  технологий  (Нью-Йорк,  США).  Он  использовал  его  для  имитации  джазовой  импровизации  в  собственном  ПО  GenJam  (GJ)  [1,  с.  1—8].  Данная  программа  читает  заранее  подготовленные  MIDI  файлы,  включающие  партию  аккордов  пианино,  баса,  и  ритм-секции,  и  генерирует  соло.  Оценка  происходит  посредством  человеческого  восприятия.  Посредством  команд  ‘g’  или  “b”  слушатель  оценивает  сгенерированные  куски  как  удачные  или  нет,  соответственно.

Главная  новаторская  сущность  GJ  заключается  в  двух  главных  отличиях  —  во-первых  GJ  использует  оперирует  двумя  популяциями  —  тактов  и  фраз,  а  также  то,  что  GJ  использует  целую  популяцию  тактов  и  фраз  для  построения  соло,  а  не  один  «лучший»  отрывок. 

Рисунок  1.  Пример  фразы  и  ее  тактов

В  обоих  популяциях,  число  слева  от  жирной  линии  представляет  собой  значение  фитнес-функции,  а  остальные  числа  —  хромосомы. 

Индивиды  в  тактовой  популяции  состоят  из  значения  фитнес-функции  и  хромосомы,  которые  интерпретируются  как  серия  8  событий,  по  одному  на  каждую  из  восьмеричных  нот.  Существует  три  типа  событий:  новая  нота  (нота  плюс  окончание  ноты),  пауза  (окончание  предыдущей  ноты),  и  фермата  (продолжение  предыдущей  ноты). 

Такт  и  фраза  инициализируются  посредством  генерации  произвольной  битовой  строки  соответствующей  длины.  Значение  фитнесс-функции  равно  0.  Для  фраз  строки  случайно  распределены.  Для  тактов  строки  выглядят  как  восемь  четырехбитовых  событий  (0—15,  где  0  —  пауза,  15  —  фермата,  а  1—14  новые  ноты).  Вероятность  наступления  паузы  5—24,  а  новой  ноты  —  1—24. 

В  GJ  генетические  операторы  (отбор,  замещение,  мутация,  турнир)  используются  следующим  образом.  Четыре  индивида  отбираются  случайно  для  формирования  семьи.  Из  четырех  индивидов  два  с  самой  высокой  фитнес-функцией  отбираются  как  родители,  а  два  худших  замещаются  двумя  из  следующего  поколения. 

GJ  оперирует  шестью  операторами  мутации: 

1.  Отсутствие  мутации  (фраза  подходит  по  критериям);

2.  реверс  (выстраивает  фразу  в  обратном  порядке);

3.  поворот  вправо  (сдвигает  последовательность  в  сторону  первой  ноты);

4.  суперфраза  (генерирует  новую  фразу  из  четырех  лучших  индивидов  трех  прошедших  турниров);

5.  разжижитель  (решает  проблему  сходимости  генетического  алгоритма  на  одном  «супериндивиде»  —  добавляет  случайный  такт  в  фразу);

6.  cирота  (генерирует  новую  фразу  выбирая  победителей  четырех  независимых  турниров,  причем  победители  самые  редко  встречающиеся  такты  в  популяции).

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

Муравьиный  алгоритм.  МА  —  это  один  из  методов  так  называемого  роевого  интеллекта  [2,  с.  41—49].  Рой  обычно  превращается  в  пространственно-временные  структуры  за  счет  процесса  самоорганизации.  Данный  процесс  происходит  за  счет  текущей  динамики  роевых  структур,  а  не  за  счет  какого-то  центрального  управления.  Роевые  особи  взаимодействуют  друг  с  другом  на  протяжении  долго  периода  времени,  модифицируя  окружающую  среду  за  счет  сигмергии  —  механизма  непрямого  взаимодействия  агента  и  действия.  Принцип  сигмергии  в  том,  что  след,  оставленный  в  окружающей  среде  посредством  действия  стимулирует  возникновение  следующего  действия  того  же  или  другого  агента.  И  тогда  последующие  действия  начинают  усиливать  друг  друга  и  строиться  за  счет  друг  друга,  приводя  к  спонтанному  появлению  очевидной  систематической  активности.  В  цифровой  интерпретации  виртуальный  рой  визуализируется  на  более  абстрактном  уровне  —  он  представляет  собой  набор  локальных  правил  и  взаимодействий  между  цифровыми  единицами. 

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

Уровни  описания  муравьиного  алгоритма  строятся  на  иерархической  структуре  Западной  музыки:  микро  (от  долей  секунды  до  секунды),  мини  (нота,  от  секунды  до  нескольких),  мезо  (мелодия,  ритмическая  структура,  от  нескольких  секунд  до  десятков),  макро  (архитектура  композиции,  несколько  минут).

Одно  из  самых  известных  воплощений  роевого  алгоритма  —  Интерактивная  импровизационная  система  SWARMUSIC  Тима  Блэквелла,  Университет  Суссекса.  Суть  работы  программы  заключается  в  следующем:  музыкальное  пространство  наполнено  музыкальными  событиями,  каждое  из  которых  отвечает  за  ноту,  сыгранную  в  определенное  время  с  точной  громкостью.  Таким  образом,  три  оси  музыкального  пространства  это  —  громкость,  импульс  и  высота  ноты.  А  любое  музыкальное  событие  имеет  три  коррдинаты{Xj}  =  (Xloudness,  Xpulse,  Xpitch)  и  принадлежит  интервалу  [Xj  min,  Xj  max].  Система  имеет  несколько  независимых  субсистем,  каждая  из  которых  отвечает  за  рой  в  составе  мультироя,  и  имеет  три  функции:  захват,  анимация,  и  интерпретация.  Каждая  из  частиц  роя  привязана  к  одному  или  более  из  четырех  ускорителей:  ускорение  к  центру  массы  роя,  к  целевой  группе  центра  массы,  к  частичной  цели  отталкивающее  ускорение  от  окрестности  частицы.  Ускорители  обеспечивают  равновесность  индивидуального  и  группового  поведения.  Например,  межчастичное  отталкивание  производит  контроль  за  ускорением  в  сторону  центра  масс  и,  таким  образом,  предупреждает  коллапс,  связанный  с  группированием  нот  в  блоки  и  проигрыванием  одинаковых  нот. 

Список  литературы:

1.Biles  J.A.  GenJam:  A  Genetic  Algorithm  for  Generating  Jazz  Solos.  Proceedings  of  the  1994  International  Computer  Music  Conference.  San  Francisco:  International  Computer  Music  Association,  1994,  1—8  c. 

2.Blackwell  T.M.  Swarm  music:  Improvised  music  with  multi-swarms.  In  Proc.  The  2003  AISB  Symposium  on  Artificial  Intelligence  and  Creativity  in  Arts  and  Science.  2003,  41—49  c. 

3.Horner  A.,  Goldberg  D.E.  Genetic  Algorithms  and  Computer-Assisted  Music  Composition.  Proceedings  of  the  1991  International  Computer  Music  Conference.  San  Francisco:  International  Computer  Music  Association.  1991,  479—482  c. 

4.Miranda  E.  Evolutionary  Computer  Music.  Springer-Verlag  London  Series,  2007,  7—10  c. 

5.Papadopoulos  G.  AI  Methods  for  Algorithmic  Composition  :  A  survey,  a  Critical  View  and  Future  Prospects.  AISB  Symposium  on  Musical  Creativity,  1999,  3—6  c.