GenAMusic: Музыкальный композитор, основанный на интерактивном генетическом алгоритме

GenAMusic: Музыкальный Композитор, основанный на Интерактивном Генетическом Алгоритме

Васильев Алексей

Департамент компьютерных наук

Институт Транспорта и Связи

Ломоносова 1-1, Рига, Латвия

Email: servent@apollo.lv

12 марта 2001 г.

Аннотация

Данная работа посвящена применению генетических алгоритмов в искусстве, в частности в музыке. Здесь описывается система, основанная на интерактивном генетическом алгоритме (ИГА) и использующая в качестве оценочной функции человека. Рассматриваемые результаты были получены при подаче на вход системы, как стохастических данных, так и нестохастических, а именно, фрагментов классического произведения: “Лунная соната” Бетховена. С помощью ИГА была создана новая композиция в стиле “Лунной сонаты”.

Ключевые слова: Генетические Алгоритмы; Генерация Музыки.

Содержание:

1.       Введение в генетические алгоритмы.. 1

2.       Существующие работы с использованием ГА в музыке. 2

3.       Описание генератора мелодий. 3

3.1.    Пример работы генератора мелодий со стохастическими данными. 3

3.1.1.     Пример 1. 3

3.1.2.     Пример 2. 5

3.2.    Пример работы генератора мелодий с заданными исходными данными. 5

3.3.    Программная реализация. 6

4.       Заключение. 7

5.       Используемая литература. 7

1.  Введение в генетические алгоритмы

Генетические алгоритмы (ГА) – это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом [1]. Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином [2].

ГА работают с совокупностью “особей” - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее “приспособленности” согласно тому, насколько “хорошо” соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность “воспроизводить” потомство с помощью “перекрестного скрещивания” с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтан­ные изменения в генах.

Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.

ГА состоит из следующих компонент:

·  Хромосома.  Решение рассматриваемой проблемы. Состоит из генов.

·  Начальная популяция хромосом.

·  Набор операторов для генерации новых решений из предыдущей популяции.

·  Целевая функция  для оценки пригодности (fitness) решений.

Стандартные операторы для всех типов генетических алгоритмов:

·  Селекция (reproduction). Отбор хромосом в соответствии со значениями их функции пригодности.

·  Скрещивание (crossover). Обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным.

·  Мутация (mutation). Стохастическое изменение части хромосом.

Алгоритм работы простого ГА [3] выглядит следующим образом:

НАЧАЛО /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

останов = FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания

Скрестить выбранные особи и получить двух потомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась, ТО останов = TRUE

КОНЕЦ

КОНЕЦ

2.  Существующие работы с использованием ГА в музыке

Написание мелодии это поиск во множестве всех мелодий композиций, которые хорошо “звучат”. Эта область решений не структурирована: хорошие мелодии могут отличаться от плохих всего парой нот. Неструктурированная область решений делает поиск непредсказуемым и поэтому трудным. В задачах подобного рода хорошо себя зарекомендовала теория генетических алгоритмов.

В большинстве случаев все работы по ГА в музыке можно разделить на два типа:

1.  Для создания соло или ритмов из последовательностей аккордов или нот.

2.  Для создания непосредственно главной мелодии.

Больших достижений с использованием ГА в музыке добился Билес [4] (GenJam). Он использовал интерактивный генетический алгоритм (ИГА) для оценки приспособленности мелодий. GenJam генерирует джаз соло на основе априорных знаний о последовательности аккордов и о том, какой темп и ритмический стиль будет использоваться для этого. Функционирует он на уровне начинающего джазиста, однако с его помощью уже записано несколько музыкальных компакт дисков.

В ритмовом контексте в самом простом случае [5] битовая хромосома определяет модель ритма. Ноль означает играть ноту, единица – не играть. Генерируется популяция таких ритмов, затем она накладывается на заданную последовательность нот, благодаря чему некоторые ноты в последовательности пропадают (ноль наложился), а вместо них продолжают звучать предыдущие.

При создании главной мелодии для получения хороших результатов (уменьшения пространства поиска) обычно вместо стохастической первой популяции задают набор готовых мелодий [6]. Затем после некоторого числа поколений эти мелодии объединяются друг с другом. Именно вариацию подобного типа мы и будем рассматривать в данной работе.

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

Как и в любых других областях, помимо основных (селекция, мутация, скрещивание) операторов ГА, широко используются еще и дополнительные операторы [7], специфичные в данной предметной области:

·  Мутация. Мутировать альт, тенор и бас вверх или вниз на один полутон или тон. Процесс случайный.

·  Одна-нота. Случайным образом заменить одну ноту на другую, случайную.

·  Обмен. Случайно выбрать фрагменты одинаковой длины и обменяться ими.

·  Транспонирование. Случайно выбрать фрагмент хромосомы и транспонировать его выше или ниже к лучшей квинте.

·  Перестановка. Случайно выбрать фрагмент и переставить в нем ноты.

·  Сортировка по возрастанию. Случайно выбрать фрагмент и отсортировать его ноты по возрастанию.

·  Сортировка по убыванию. Случайно выбрать фрагмент и отсортировать его ноты по убыванию.