Source-linked AI summary
AI Methods in Algorithmic Composition: A Comprehensive Survey
Jose David Fernandez, Francisco Vico
TL;DR
Algorithmic composition research faces difficult evaluation and comparison challenges across diverse computational methods. This survey reviews several hundred papers as a reference guide and finds no single approach consistently produces music on par with professional human composers.
Problem
Defining objective and convenient fitness functions for evaluating musical compositions remains difficult, limiting evolutionary methods to well-defined, restricted compositional problems.
Method
The survey briefly reviews several hundred papers to provide a reference guide to methods commonly used in algorithmic composition.
Results
Except for narrow imitation and improvisation cases, most algorithmic composition approaches do not produce content on par with professional human composers.
Takeaways & Limitations
Hybridizing multiple methods is identified as an obvious direction, and many researchers already follow this route.
Takeaways & Limitations
The survey excludes algorithmic sound synthesis, despite its blurred boundary with algorithmic composition in many systems.
Abstract
from arXiv · showhide
Algorithmic composition is the partial or total automation of the process of music composition by using computers. Since the 1950s, different computational techniques related to Artificial Intelligence have been used for algorithmic composition, including grammatical representations, probabilistic methods, neural networks, symbolic rule-based systems, constraint programming and evolutionary algorithms. This survey aims to be a comprehensive account of research on algorithmic composition, presenting a thorough view of the field for researchers in Artificial Intelligence.
1. Introduction
This survey reviews algorithmic composition as a focused area of Computational Creativity, bringing together existing research primarily for Artificial Intelligence researchers. It addresses the lack of a comprehensive, AI-centered survey of algorithmic composition and organizes the field around implementation methods.
- Scope: The survey reviews and brings together research on algorithmic composition, broadly understood as using algorithms to compose music.
- Contribution: Existing surveys do not comprehensively cover all algorithmic-composition methods from a perspective primarily focused on AI research.
- Organization: The article is designed as a reasonably short reference guide for AI researchers, structured primarily around methods used to implement algorithmic-composition systems.
- Motivation: Relevant literature is scattered across journals and scholarly books spanning computer science and music theory, creating accessibility barriers for researchers.
2. Introducing Algorithmic Composition
Algorithmic composition spans computer automation of compositional activities, with this survey emphasizing higher degrees of automation that encode creativity or perform creative tasks with minimal or no human intervention rather than typical computer-aided algorithmic composition. The section also distinguishes the survey’s scope from automated expressiveness, algorithmic sound synthesis, and nonlinear music, while reviewing early computational composition research from the mid-1950s onward.
- Scope and distinctions: The survey focuses on computational systems that encode human musical creativity or perform creative compositional tasks with minimal or no human intervention.This contrasts with computer-aided algorithmic composition, which primarily supports specific or monotonous tasks, supplies raw material, or aids composers’ creative processes.
- Scope and distinctions: The boundary between computer-aided and highly automated composition is unclear because automated generation can also serve as a compositional aid, and highly automated systems can be built on computer-aided frameworks.The survey notes that PWConstraints is built on PatchWork as an example of this relationship.
- Scope and distinctions: The survey largely excludes automated expressiveness, algorithmic sound synthesis, and nonlinear music because each involves related but distinct problems.These scenarios are mentioned sparingly, mainly when innovative or otherwise notable techniques are involved.
- Early research: Computers were first used to compose music in the mid-1950s, although computational music and Artificial Intelligence did not converge until later.Early computers were expensive, slow, difficult to use, and operated in batch mode.
- Early research: Early systems applied diverse computational methods, including rule systems, Markov chains, stochastic algorithms, serial composition, and hierarchical search with backtracking.Examples include Hiller and Isaacson’s Illiac Suite, Xenakis’s computer-assisted stochastic methods, Koenig’s PROJECT1, and Gill’s Schoenberg-inspired system.
3. The Methods
Algorithmic composition draws on a notably wide range of methods, including diverse Artificial Intelligence approaches as well as mathematical models from Complex Systems and Artificial Life.
- 3. The Methods: The survey organizes algorithmic composition research by methodology, with a subsection devoted to each approach.Its scope includes diverse Artificial Intelligence methods and mathematical models from Complex Systems and Artificial Life.
3.1 Grammars … 3.6 Self-Similarity and Cellular Automata
The survey organizes algorithmic-composition methods into symbolic techniques, machine learning, evolutionary optimization, and self-similarity or cellular-automata approaches. This taxonomy is approximate because methods are often hybridized, category boundaries are blurred, and some approaches remain difficult to classify.
- 3.1 Grammars: Grammars are treated as symbolic, knowledge-based methods but separated because of their historical importance in algorithmic composition.The survey characterizes grammars as part of classical “good old-fashioned AI.”
- 3.2 Symbolic, Knowledge-Based Systems: Symbolic and knowledge-based systems are grouped among the survey’s classical “good old-fashioned AI” techniques.The taxonomy places grammars and related symbolic work in Sections 3.1 and 3.2.
- 3.5 Evolutionary and Other Population-Based Methods: Evolutionary methods are grouped with other population-based optimization approaches and have been combined with almost every other method.This extensive hybridization makes evolutionary methods especially difficult to place in a hierarchical taxonomy.
- 3.6 Self-Similarity and Cellular Automata: Self-similarity and cellular-automata methodologies are included despite not really being forms of Artificial Intelligence.The survey retains them within its account of algorithmic-composition methods.
- 3.6 Self-Similarity and Cellular Automata: Existing algorithmic-composition literature is difficult to categorize neatly because methods are frequently hybridized, papers can fit multiple methodologies, and some approaches are unique.The taxonomy is described as roughly similar to Nierhaus’s, with differences such as classifying L-systems as grammars rather than self-similar systems.
- 3.3 Markov Chains: Markov chains are among the methodologies whose boundaries with rule systems and grammars are frequently blurred.Assigning a work to one of these categories can depend largely on terminology, intent, or theoretical framing.
- 3.6 Self-Similarity and Cellular Automata: The taxonomy is not fully comprehensive, with Amiot et al. (2006) identified as an arguably remote example using the Discrete Fourier Transform to vary rhythms.They represented rhythms in the frequency domain and generated variations by slightly perturbing transform coefficients.
3.1 Grammars and Related Methods
Grammar-based algorithmic composition uses hierarchical rewriting rules to generate musical structures, often with stochastic activation probabilities. Research has focused mainly on regular and context-free grammars, while automated rule generation addresses the difficulty of manually designing effective grammars.
- Grammars: Formal grammars generate musical sequences by repeatedly applying rewriting rules, making them suitable for representing hierarchical compositional structures.Rules can operate across multiple layers, from general themes to individual notes.
- Grammars: Stochastic grammars commonly assign activation probabilities to grammatical rules during generation.Early systems often defined rules manually from music-theoretic principles, while later approaches explored automated rule inference.
- Grammars: Most grammatical composition research uses regular and context-free grammars because context-sensitive and more general grammars are difficult to implement effectively.The survey notes that exceptions are generally limited to simple toy systems.
- L-systems: L-systems apply all possible rewriting rules in parallel and have been mapped to music through graphical renderings, symbolic sequences, and more complex dynamical trajectories.They have also supported partial compositional tools, including arpeggio generation and chord-progression construction.
- Evolutionary methods: Evolutionary approaches can evolve grammatical rules directly, as in GeNotator, or incorporate grammars into the fitness function rather than composition generation.In GeNotator, users interactively assign fitness to grammars specified through a graphical interface.
3.2 Symbolic, Knowledge-Based Systems and Related Methods
Knowledge-based systems represent compositional knowledge as structured symbols and rules, making them a natural foundation for algorithmic composition. Research developed from heuristic rule systems toward learning, evolutionary hybrids, and logic- or constraint-based formulations.
- Rule-based foundations: Knowledge-based systems use structured symbols and rules to represent musical-composition knowledge, providing a natural framework for algorithmic composition.The section treats knowledge-based system as an umbrella term for several rule-based paradigms.
- Rule-based foundations: Early systems applied hierarchical search, backtracking, and encoded music-theoretic rules to twelve-tone composition and eighteenth-century figured-bass harmonization.Gill’s system followed Schoenberg’s twelve-tone rules, while Rothgeb encoded treatise-derived rules for selecting chords from bass notes.
- Rule-based foundations: Rule-based composition systems addressed chorale harmonization, melody generation, emotional criteria, jazz improvisation, and species counterpoint using schemata, frames, constraints, and backtracking.These systems adapted their representations and search procedures to different musical styles and tasks.
- Learning and hybrid methods: Some systems allowed rule priorities or learned knowledge to change dynamically, combining static rules with constraints, directives, and deductions from successful compositions.MUSE exemplified rule-based learning by dynamically changing rule priorities and deducing new composite rules.
- Learning and hybrid methods: Rule sets were also converted into graduated fitness functions for evolutionary composition, while logic programming and constraint satisfaction encoded rules for melodic composition, harmonization, and counterpoint.Evolutionary methods used weighted or fuzzy rule-based fitness functions, and later systems formulated composition as constraint satisfaction problems.
3.3 Markov Chains and Related Methods
Markov chains model musical sequences through probabilistic state transitions, with higher-order and variable-order extensions supporting richer generation and analysis. Although basic corpus-trained chains capture mainly local similarities and often produce unmusical or aimless results, constrained and specialized applications remain useful.
- Core model: Corpus-trained probability matrices are the most common research approach, while composers’ software more often uses probabilities specified manually from music theory or experimentation.Designers must also decide how Markov states map to musical objects.
- Core model: Markov chains generate or analyze musical sequences by transitioning among states according to probabilities, with each next state depending on the current state or the last n states.In n-th order chains, the probability matrix has n + 1 dimensions; sequence analysis is also called n-gram modeling.
- Limitations: Basic corpus-trained Markov chains capture local statistical similarities, with low-order models producing strange, aimless music and high-order models reproducing the corpus too closely.These limitations led researchers to treat Markov chains primarily as sources of raw material rather than complete automated composition methods.
- Applications: Markov chains remained useful for restricted tasks such as rhythm selection and real-time jazz improvisation, where constraints, templates, or pre-defined licks refine generated material.Their limitations are less apparent in restricted problems than in whole-composition generation.
- Related methods: Variable-order Markov chains, HMMs, MDPs, and POMDPs extend basic models, enabling mixed-order generation, hidden-state inference, and action selection under probabilistic state transitions.HMMs use the Viterbi algorithm to find a globally optimized state sequence from observed outputs, unlike simpler local Markov optimization.
3.4 Artificial Neural Networks and Related Methods
Artificial neural networks have been applied to melody generation, harmonization, and hybrid composition systems, including combinations with probabilistic and evolutionary methods. Related connectionist approaches extend this repertoire to expert systems, Boolean networks, and compositional pattern producing networks.
- ANN-based composition: ANNs were adapted from musical analysis to composition, initially generating monophonic melodies through recurrent networks that mapped outputs to absolute pitches.Todd’s first composition system used a three-layer recurrent ANN and training examples to produce temporal sequences encoding melodies.
- ANN-based composition: ANNs supported diverse composition strategies, including models learning local and global patterns and systems assigning absolute pitches after Markov-chain motif generation.Mozer’s inversion-based approach reshaped random patterns by gradient descent, but its computational cost restricted testing to simple, short compositions.
- Hybrid systems: Hybrid systems combined ANNs with rule-based agents, probabilistic methods, or evolutionary algorithms for tasks such as four-part Bach-style harmonization and polyphonic elaboration.Evolutionary systems commonly trained an ANN as a fitness function; NEUROGEN used separate ANNs for pitch intervals and overall structure.
- Evolutionary hybrids: Replacing interactive or original fitness functions with ANN evaluators could underperform and risk exploiting unexpected evaluator quirks, while learned decision trees sometimes performed better and were easier to interpret.The GP-Music System’s trained ANNs were below the performance of interactive fitness, and Klinger and Rudolph found learned decision trees superior to feedforward ANNs.
- Related connectionist methods: Related connectionist methods included ad hoc expert systems, Boolean networks, and CPPNs, with CPPNs generating or modulating complex accompaniment patterns from pre-existing compositions.Neurswing only vaguely resembled a neural or connectionist system, whereas CPPNs used heterogeneous arbitrary node functions and interactive evolutionary design.
3.5 Evolutionary and Other Population-Based Methods
Evolutionary composition methods iteratively evolve populations through evaluation, selection, and variation, but their application is constrained by the difficulty of designing objective fitness functions for musical quality. Hybrid evo-devo strategies address complexity and computational cost, while interactive approaches face user fatigue during candidate evaluation.
- Evolutionary algorithm foundations: Evolutionary algorithms repeatedly evaluate, select, and reproduce varied candidate populations, causing best and mean fitness to tend to increase over time.Genotypes encode candidate solutions, which are translated into phenotypes; mutation and recombination help restore population diversity.
- Fitness-function design: Designing objective, convenient fitness functions for musical compositions is a central difficulty that limits evolutionary methods to well-defined, restricted composition problems.Subjective aesthetic evaluation can become impractical, making fitness design particularly challenging.
- Fitness-function design: Fitness has commonly been implemented as a weighted sum of musical features, although tuning feature weights can be difficult beyond toy problems.Alternative approaches include multi-objective evaluation and distances to target compositions or corpora, but multi-objective methods have been used only rarely.
- Evo-devo strategies: Iamus combines formal constraints and aesthetic principles with genomic development, producing high structural complexity at relatively low computational cost.Its evo-devo strategy evolves compositions in an environment governed by constraints while developing them from genomic encodings resembling embryological development.
- Interactive evolutionary methods: User fatigue is a problem common to interactive genetic algorithms because evaluating candidate solutions is comparatively slow and monotonous, even with small populations and few generations.Researchers have addressed this significant problem in different ways.
3.6 Self-Similarity and Cellular Automata
This section links the musical relevance of 1/f noise to self-similarity and surveys cellular automata as systems for generating and designing musical material. CA-based composition ranges from direct mappings of generated patterns to MIDI or notes to neural and evolutionary design of CA parameters.
- Self-Similarity: Music across many styles approximately exhibits a spectral density inversely proportional to frequency, known as a 1/f or pink-noise distribution.Voss and Clarke reported this result in the late 1970s, although their hours-long samples combined multiple compositions and non-musical sounds.
- Self-Similarity: Self-similarity is the research and artistic consensus explaining why 1/f noise can produce more musical results than other random processes.Its structure is statistically similar across several orders of magnitude.
- Cellular Automata: Cellular automata are discrete dynamic systems whose cells deterministically update from their own and neighboring states under transition rules.Cells are arranged on a regular grid or tiling and each has one of finitely many states.
- Cellular Automata: CA composition systems map generated patterns to musical output, including MIDI, note sequences, instrumentation, pitches, durations, and complex polyrhythmic structures.CAMUS combined Conway’s Game of Life for musical sequences with Crystalline Growths for instrumentation; later versions added Markov-controlled durations and three-dimensional CA.
- Cellular Automata: CA parameters can be designed with artificial neural networks or evolutionary algorithms rather than tuned manually by the composer.A neural network learned transition rules from a melody’s piano-roll temporal pattern and generated new compositions from other initial conditions.
4. Conclusions
The survey reviews AI methods for algorithmic composition as a reference guide, finding reasonable success in style imitation but persistent limitations in rigorous evaluation and professional-level automated composition. It concludes that hybrid methods are a promising direction, while creativity remains largely with human composers.
- Survey scope: The survey reviews several hundred papers as a short reference guide to methods for algorithmic composition, while noting weaknesses in research aims, methodology, and evaluation.The survey does not describe the reviewed papers in detail.
- Imitation: Style-imitation problems, including real-time systems elaborating musicians’ input, are considered largely solved through many methods with reasonable success.Examples include Cope’s EMI and Pachet’s Continuator.
- Creativity evaluation: Evaluating automated systems remains difficult because artistic creativity lacks a formal, unambiguous, effective definition, despite proposed computational-creativity frameworks.The passage states that no framework can be easily applied rigorously.
- Method categories: Symbolic AI, machine learning, evolutionary algorithms, and self-similarity techniques support different balances of imitation and automation, but each has important practical or output limitations.Symbolic methods are effective but labor-intensive; self-similarity and cellular automata generate rough material commonly used as raw material.
- Future directions: Except for strict style imitation and some real-time improvisation systems, approaches generally do not produce content on a par with professional human composers, motivating hybridization.The survey observes that many researchers already combine methods and identifies less-explored hybridizations as a way forward.
- Human–computer roles: CAAC software is prevalent and generative-music scenes embrace computer-generated music, but creativity remains largely in the hands of composers.The passage describes creativity as inherently subjective and disputes whether a computational system can become truly creative.