ЕСТЕСТВЕННЫЕ АЛГОРИТМЫ: ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

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

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

В общем смысле работа генетического алгоритма начинается с применения эквивалента биологического образования новых генов на пространство случайно распределенных решений для нахождения в итоге оптимального набора.

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

Впервые генетический алгоритм был предложен Джоном Холландом в 1975 году в Мичиганском университете.

Целесообразность применения ГА для моделирования музыкального творчества обосновали профессор кафедры компьютерных наук Гонг–Конгского университета Эндрю Хорнер и профессор кафедры индустриальной инженерии Университета Иллинойса Дэвид Голдберг в 1991 году.

Первыми успешными исследованиями в области применения генетических алгоритмов в генеративной музыке можно считать изыскания Джона Бильса — профессора Рочестерского института технологий (Нью–Йорк, США). Он использовал ГА для имитации джазовой импровизации в собственном ПО GenJam (Genetic Jammer — Генетический Джэммер). Данная программа читает заранее подготовленные с помощью программы Band–In–A–Box MIDI файлы, включающие партию аккордов пианино, баса, ритм–секции, и генерирует соло. Оценка происходит посредством человеческого восприятия. Посредством команд ‘g’ или “b” (‘good’ or ‘bad’) слушатель оценивает сгенерированные куски как удачные или нет.

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

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

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

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

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

GJ оперирует шестью операторами мутации для фраз:

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

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

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

4) генетический ремонт;

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

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

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

И шестью операторами для тактов:

1) Отсутствие мутации;

2) реверс;

3) поворот вправо;

4) инверсия (замена фермат паузами, пауз ферматами, и отражение нот относительно ноты до четвертой октавы);

5) сортировка нот на повышение;

6) сортировка нот на понижение;

7) транспозиция нот (повышение каждой ноты на определенное число от 1 до 4, паузы и ферматы во внимание не принимаются).

Далее приведены таблицы примеров мутаций относительно такта и фразы, представленных на рисунке:

Таблица — пример применения операторов мутации для такта 

Оператор мутации	Мутированный такт
Отсутствие мутации	0 15 15 7 5 0 7 9
Реверс	9 7 0 5 7 15 15 0
Поворот вправо	15 15 0 9 7 0 5 7
Инверсия	6 8 15 10 8 0 0 15
Сортровка нот на повышение	5 7 0 7 9 15 15 0
Сортировка нот на понижение	9 7 0 7 5 15 15 0
Траспозиция нот	12 10 0 8 10 15 15 0

Таблица — пример применения операторов мутации для фразы 

Оператор мутации	Мутированный такт
Отсутствие мутации	57 57 11 38
Реверс	38 11 57 57
поворот вправо	57 11 38 57
Генетический ремонт	57 57 11 29
суперфраза	41 16 57 62
разжижитель	31 57 11 38
cирота	17 59 43 22

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