Type of Document Dissertation Author Gwee, Nigel Author's Email Address firstname.lastname@example.org 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 Keywords
- artificial neural network
- finite state machine
- species counterpoint
- genetic algorithm
Date of Defense 2002-10-24 Availability unrestricted AbstractSuccessful 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
If you have questions or technical problems, please Contact LSU-ETD Support.