Эволюционные методы в алгоритмической композиции. Л-системы
Л-системы как один из эволюционных методов решения задач алгоритмической композиции (процесса генерации музыкальных отрывков, мелодий и произведений с помощью вычислительных методов). Базовое описание контекстно-независимой системы, основные команды.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 29.04.2018 |
| Размер файла | 137,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Эволюционные методы в алгоритмической композиции. Л-системы
Эволюционные вычисления в широком смысле можно определить как область информатики, в которой используются вычислительные модели, аналогичные идеям Дарвиновского эволюционного процесса. Существует огромное множество методов оптимизации на основе эволюционных методов (например, муравьиный алгоритм, алгоритм имитации отжига). Одним из эволюционных методов решения задач алгоритмической композиции (процесса генерации музыкальных отрывков, мелодий и произведений с помощью вычислительных методов) являются Л-системы, лежащие на стыке таких сфер математики, как эволюционные методы и формальная грамматика.
Л-системы были описаны в 1968 году венгерским ботаником Аристидом Линденмайером для изучения развития простых многоклеточных организмов, позже базис Л-систем был расширен для моделирования сложных ветвящихся структур - разнообразных деревьев и цветов. Впервые для решения задач автоматической генерации музыки их применил в своей диссертации 1996 года американский программист и композитор Люк Дюбуа.
Как описывает Диас-Герез Густаво в своей диссертации «Алгоритмическая композиция: использование математических моделей в музыке», в основе работы Л-систем лежит набор правил замещения, рекурсивно применяющийся на начальную строку символов и интерпретирующий конечную строку как структурные элементы организма. Правила замещения определяют как каждый конкретный символ в текущем поколении должен быть перемещен. Базовое описание контекстно-независимой системы заключается в формуле:
G = |A, P, б|,
где А - алфавит системы (набор всех символов включая пустой символ, е), Р - это конечной набор правил замещения (определенный в виде входящий символ - выходящий символ1, выходящий символn), и б - символ или строка из алфавита, используемая в качестве начального состояния. Также в работе алгоритма участвуют A* - набор всех возможных символов строк из А, А+ - набор всех возможных символьных строк без пустого символа. Л-системы не имеют конечных символов, хотя конечный символ может быть эмулирован путем замены текущего символа на самого себя.
Так как чаще всего Л-системы используются для моделирования роста растений, раковин моллюсков, пчелиных сот и т.д., поэтому основным представлением работы Л-системы является графическое. Чаще всего для этого используется так называемый «черепаший язык», описанный Антоном Швецом в книге «Примеры программ Perl». Черепаха находится на координатной плоскости и может передвигаться по ней только вперёд, но может также поворачиваться на месте. При движении черепаха способна чертить линию карандашом, или двигаться, не оставляя за собой след. Есть возможность заменять карандаши, и тем самым управлять толщиной линии и её цветом. «Черепаший язык» является основой языка программирования LOGO.
Основные команды передаваемые «черепахе» следующие:
F - один шаг вперед - рисование сегмента линии;
ш - задание угла для поворота черепахи;
+ - поворот влево на заданный угол;
- - поворот вправо на заданный угол;
[- сохранение заданной позиции и угла;
] - восстановление исходных позиций;
/ - глубина итерации.
В качестве примера можно привести простую систему, имитирующую рост водорослей Lйmna на стоячей воде, также впервые смоделированную Аристидом Линденмайером:
- символы - A B;
- начальное положение - A;
- правила замещения - (A > AB), (B > A);
В итоге получаем следующую последовательность поколений:
алгоритмический вычислительный команда
Последовательность поколений водорослей Lйmna на стоячей воде
|
Поколение |
Состояние |
|
|
0 |
A |
|
|
1 |
AB |
|
|
2 |
ABA |
|
|
3 |
ABAAB |
|
|
4 |
ABAABABA |
|
|
5 |
ABAABABAABAAB |
|
|
6 |
ABAABABAABAABABAABABAABAABABAABAAB |
Исходя из классификации Герхарда Ниерхауса, данной в книге «Парадигмы автоматической генерации музыки», Л-системы можно разделить на несколько групп.
Контекстно-независимые и чувствительные к контексту. Л-система называется контекстно-независимой (0Л-системой), если замещение происходит независимо от окружающих символов. Л-система называется чувствительной к контексту, если правила замещения определяются положением символа, который следует заменить (например, заменить A на ABA, если A стоит после B).
Л-система называется стохастической, если возможны несколько правил для каждого символа-предшественника. Одно из нескольких правил для данного символа строки состояния каждый раз выбирается случайно, с некоторой заданной вероятностью. Само собой, каждому из правил для данного предшественника приписывается вероятность выбора правила - число от нуля до единицы (сумма таких чисел должна равняться единице).
Пример работы стохастической Л-системы - моделирование роста ветви деревья
Параметрической называется Л-система, в которой начальный набор символов может меняться - например, добавляться новые символы в зависимости от определенных условий.
Использование Л-систем для генерации алгоритмических композиций подразумевает использование вместо символов определенных музыкальных параметров. Например профессор Португальского университета Педро Пестана назначает алфавит из семи символов - нот, входящих в гамму до мажор, а правила замещения определяет исходя из матрицы переходных вероятностей.
Другим воплощением Л-систем в алгоритмической композиции является программа LMUSE Дэвида Шарпа, в которой различные музыкальные параметры, такие, как высота, продолжительность, и громкость могут быть назначены различным компонентам положения, толщины линии и т.д.
Таким образом, Л-системы можно считать экспертной системой, основанной на правилах, и подходящей для решения определенных задач в сфере алгоритмической композиции.
Размещено на Allbest.ru
...Подобные документы
Сущность, принципы и описание методов и этапов имитационного моделирования. Процессы и применение дискретного и непрерывного алгоритма. Характеристика методов построения математических моделей для решения управленческих задач банковской системы.
курсовая работа [80,5 K], добавлен 29.05.2014Характеристика алгоритма, его свойств, способов записи. Особенности, типовые примеры линейной алгоритмической структуры. Анализ разветвляющей алгоритмической структуры. Изучение основных операторов циклов. Эволюция, классификация языков программирования.
контрольная работа [492,2 K], добавлен 15.02.2010Проектирование системы массового обслуживания, состоящей из двух генераторов псевдослучайных величин и электронной вычислительной машины, обрабатывающей поступающие заявки. Разработка структурной схемы и алгоритмической модели проектируемой системы.
курсовая работа [194,5 K], добавлен 30.10.2013Использование MS Excel для математических расчетов. Описание численных методов решения системы линейных алгебраических уравнений. Решение систем линейных алгебраических уравнений с методами Крамера и Зейделя и с помощью табличного процессора MS Excel.
курсовая работа [1,6 M], добавлен 14.02.2021Трудности использования эволюционных алгоритмов. Построение вычислительных систем, основанных на принципах естественного отбора. Недостатки генетических алгоритмов. Примеры эволюционных алгоритмов. Направления и разделы эволюционного моделирования.
реферат [187,4 K], добавлен 21.01.2014Особенности решения задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования. Общая характеристика классических и числовых методов решения.
дипломная работа [2,4 M], добавлен 20.01.2013Обзор области генерации сетевого трафика. Описание выбранных методов, моделей, алгоритмов решения задач. Создание модели поведения пользователя, распределение количества посещённых страниц сайта. Выбор средств реализации программного продукта (проекта).
курсовая работа [1,3 M], добавлен 30.06.2017Состав и назначение основных элементов персонального компьютера. Периферийные устройства. Понятие и основные виды архитектуры ЭВМ и их характеристика. Детальный анализ алгоритма и алгоритмической системы. Сущность и развитие языков программирования.
дипломная работа [40,3 K], добавлен 08.07.2014Обзор существующих подходов в генерации музыкальных произведений. Особенности создания стилизованных аудио произведений на основе современных нейросетевых алгоритмов. Выбор средств и библиотек разработки. Практические результаты работы алгоритма.
дипломная работа [4,0 M], добавлен 13.10.2017Решение неформализованных задач экспертными системами. Системы искусственного интеллекта, эвристический поиск решения. Особенности работы экспертных систем. Знания о процессе решения задач, используемые интерпретатором. Системы обнаружения неисправности.
презентация [100,1 K], добавлен 12.02.2014Описание вычислительной техники, характеристика операционных систем и языков программирования. Сравнительный анализ аналогов и прототипов. Разработка алгоритма решения задачи. Выбор средств и методов решения задач. Проектирование программного обеспечения.
отчет по практике [1,0 M], добавлен 23.03.2015Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.
лабораторная работа [310,6 K], добавлен 13.02.2009Описание математической модели определения тока в электрической цепи с помощью решения системы алгебраических уравнений методом Гаусса. Описание и разработка блок-схемы программы. Ввод данных задачи, составление программы и анализ результатов решения.
контрольная работа [231,8 K], добавлен 15.08.2012Обзор методов и подходов решения поставленной задачи аппроксимации логического вывода экспертной системы. Разработка и описание метода сетевого оператора для решения данной задачи. Разработка алгоритма решения. Проведение вычислительного эксперимента.
дипломная работа [1,5 M], добавлен 23.02.2015Назначение компьютерной сети - объединение нескольких ЭВМ для общего решения информационных, вычислительных, учебных и других задач. Операционные системы - машиннозависимый вид программного обеспечения, ориентированный на конкретные модели компьютеров.
контрольная работа [37,5 K], добавлен 17.12.2009Итерационные методы решения нелинейных уравнений, системы линейных алгебраических уравнений (СЛАУ). Решение нелинейных уравнений методом интерполирования. Программная реализация итерационных методов решения СЛАУ. Практическое применение метода Эйлера.
курсовая работа [1,6 M], добавлен 20.01.2010Математическое описание численных методов решения уравнения, построение графика функции. Cтруктурная схема алгоритма с использованием метода дихотомии. Использование численных методов решения дифференциальных уравнений, составление листинга программы.
курсовая работа [984,2 K], добавлен 19.12.2009Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Использование объектно-ориентированного подхода для минимизации затрат в процессе продажи и обслуживания контрольно-кассовых машин. Детализация алгоритмической и логической реализации операций системы. Построение базовой модели и диаграммы деятельности.
контрольная работа [381,8 K], добавлен 19.03.2015Разработка программы, имитирующей работу системы массового обслуживания. Методы и средства решения задачи. Создание концептуальной и структурной моделей системы. Анализ и оценка результатов моделирования, определение достоинств и недостатков системы.
курсовая работа [469,5 K], добавлен 03.03.2015
