Title page for ETD etd-1028102-215542

Type of Document Dissertation
Author Gwee, Nigel
Author's Email Address ngwee1@lsu.edu
URN etd-1028102-215542
Title Complexity and Heuristics in Rule-Based Algorithmic Music Composition
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
Sukhamay Kundu Committee Chair
Donald Kraft Committee Member
Doris Carver Committee Member
Jan Herlinger Committee Member
Jianhua Chen Committee Member
Michael Khonsari Dean's Representative
  • artificial neural network
  • complexity
  • finite state machine
  • species counterpoint
  • genetic algorithm
Date of Defense 2002-10-24
Availability unrestricted
Successful algorithmic music composition requires the efficient creation of works that reflect human preferences. In examining this key issue, we make two main contributions in this dissertation: analysis of the computational complexity of algorithmic music composition, and methods to produce music that approximates a commendable human effort. We use species counterpoint as our compositional model, wherein a set of stylistic and grammatical rules governs the search for suitable countermelodies to match a given melody.

Our analysis of the complexity of rule-based music composition considers four different types of computational problems: decision, enumeration, number, and optimization. For restricted versions of the decision problem, we devise a polynomial algorithm by constructing a non-deterministic finite state transducer. This transducer can also solve corresponding restricted versions of the enumeration and number problems. The general forms of the four types of problems, however, are respectively NP-complete, #P-complete, NP-complete in the strong sense, and NP-equivalent. We prove this by first reducing from the well known Three-Dimensional Matching problem to the music composition decision problem, and then by reducing among the music problems themselves.

In order to compose music both correct and human-like, we formulate new ďartistryĒ rules to supplement traditional rules of musical style and grammar. We also propose the fuzzy application of these artistry rules, to complement the crisp application of the traditional rules. We then suggest two methods to model human preferences: (1) distinguish an expertís compositions from alternative compositions by determining rule weights; (2) train an artificial neural network to reflect an expertís musical preferences through the latterís evaluations of a set of compositions. We were able to approximate that elusive factor of human preference with better than 75% accuracy.

To solve the optimization problem, we adapt two different search algorithms: best-first search with branch-and-bound pruning (for m ≥ 1 optimal solutions), and a genetic algorithm (for m ≥ 1 near-optimal solutions). Through these algorithms, we test the techniques of rule weightings and of trained neural networks as evaluation functions. Our adaptation of the genetic algorithm produced optimal countermelodies in execution time favorably comparable to that taken by the best-first algorithm.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Gwee_dis.pdf 1.16 Mb 00:05:21 00:02:45 00:02:24 00:01:12 00:00:06

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.