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

Клеточные автоматы были впервые описаны математиком Джоном фон Нейманом в качестве модели биологического самовоспроизводства. Это дискретные динамические системы, поведение которых полностью определяется в терминах локальных зависимостей. Клеточный автомат может мыслиться как стилизованный мир. Пространство представлено равномерной сеткой, каждая ячейка или клетка которой содержит несколько битов данных; время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем, небольшой справочной таблицей, по которой любая клетка на каждом шаге вычисляет своё новое состояние, основываясь на состоянияях её близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми. «Локальными» в смысле того, что чтобы узнать, что произойдет мгновение спустя, достаточно посмотреть на состояние ближайшего окружения: никакое дальнодействие не допускается. «Одинаковость» означает, что законы везде одни и те же.

Клеточные автоматы характеризуются двумя главными особенностями:

n–мерная решетка, в которой каждая ячейка характеризуется дискретным состоянием в данный момент;

динамическое поведение, контролируемое набором правил. Эти правила определяют положение ячеек в последующих поколениях, исходя из положения соседних ячеек.

Ячейки в клеточном автомате запоминают положения автомата. Самый простой случай — это когда возможны только два состояния в ячейке: 0 — мертвая, или 1 — живая.

Существует три типа соседства ячеек в клеточных автоматах (рассмотрим двумерные автоматы)

Фон–Ньюманновское соседство, где каждая клетка имеет четырех соседей–ячеек — южную, северную, восточную и западную, а радиус соседства — 1:

соседство Мура, где у каждой клетки восемь соседей по направлениям, радиусом 1:

расширенное соседство Мура с радиусом 2 и больше

В случаях одномерного автомата такие соседства будут отображаться только центральными строками.

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

Наверное, наиболее известным считать клеточный автомат под названием игра «Жизнь», описанная в 1970 году Джоном Хортоном Конуэем. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колонии живых организмов. Рассматривается бесконечная плоская решётка квадратных ячеек–клеток. Время в этой игре дискретно (t=0, 1, 2, ...). Клетка может быть живой или мёртвой. Изменение её состояния в следующий момент времени t+1 определяется состоянием её соседей в момент времени t(соседей у клетки восемь, четверо имеют с ней общие рёбра, а четверо только вершины). Основная идея состоит в том, чтобы начав с некоего расположения клеток, проследить за эволюцией исходной позиции под действием «генетических законов» Конуэя, которые управляют рождением, гибелью и выживанием клеток. Конуэй тщательно подбирал свои правила и долго проверял их на «практике», добиваясь, чтобы они по возможности удовлетворяли трём условиям:

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

В то же время должны существовать такие начальные конфигурации, которые заведомо обладают способностью беспредельно развиваться.

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

Следствием этих требований явились следующие правила игры «Жизнь»:

Выживание. Каждая клетка, имеющая две или три соседние живые клетки, выживает и переходит в следующее поколение.

Гибель. Каждая клетка, у которой больше трёх соседей, погибает из–за перенаселённости. Каждая клетка, вокруг которой свободны все соседние клетки или же занята всего одна клетка, погибает от одиночества.

Рождение. Если число занятых клеток, с которыми граничит какая–нибудь пустая клетка в точности равно трём, то на этой клетке происходит рождение нового организма.

Один из вариантов картирования поколений жизни клеточного автомата в пространство музыкальных событий был предложен Густавом Диас-Жересом. Поскольку каждое поколение подразумевает набор ячеек, прямое картирование возможно только между каждой возможной конфигурацией ячеек и музыкальным событием. Пусть s будет числом возможных положений ячеек, номером ячеек в решетке (от 0 до t–1), и ее положением ячейки в позиции p (p от 0 до n–1). Далее каждая возможная конфигурация ячеек в поколении однозначно кодируется числовым образом следующей формулой:

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

Номер события = u mod(число элементов в пространстве событий)

Циклические клеточные автоматы были разработаны профессором математики Университета штата Висконсин Дэвидом Гриффитом. Клетка может находиться в n состояниях, которые будем нумеровать числами 0, 1, ..., n — 1. Будем говорить, что состояние m является следующим за состоянием k, если m +1= k (mod n). Клетка из состояния m переходит в следующее состояние k, только если одна из соседних клеток имеет состояние k.

При этом, если начать со случайно заполненного поля, могут наблюдаться три различных стадии. Первая стадия — случайное поле. Затем начинают появляться цветные области, которые будут поглощать области, заполненные случайно. Эти блоки будут «волнообразно» менять свой цвет. Далее возникают спирали, которые также называют демонами. И наконец, на третьей стадии, поле будет поглощено демонами.

Самым известным воплощением клеточных автоматов для генерации алгоритмических композиций является интерактивная система бразильского композитора, получившего степень доктора математических наук в Великобритании, Эдуардо Река Миранды - CAMUS. CAMUS генерирует мелодию на основе двух клеточных автоматов: игра в «жизнь» Джона Неймана и Demon Cyclic Space Больцмана.

CAMUS оперирует трехмерными версиями обоих автоматов параллельно. При каждом шаге живые ячейки Игры в жизнь используются для определения четырехнотных аккордов, в то время когда координаты живых клеток определяют интервалы сыгранных нот. Базовый тон выбирается стохастическими методами (Марковскими цепями), и координата x живой клетки определяет интервал до следующей самой высокой ноты, координата y — дает полутоновый интервал, и, наконец, координата z дает последний интервал от второй самой высокой ноты до самой высокой.

Циклический клеточный автомат же отвечает за оркестровку, то есть инструмент, который будет играть полученные мелодии. Это происходит за счет простого выбора MIDI–канала, в котором расположен инструмент.