This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
IEEE SYSTEMS JOURNAL

1

A Novel Automatic Composition System Using
Evolutionary Algorithm and Phrase Imitation
Chuan-Kang Ting, Senior Member, IEEE, Chia-Lin Wu, and Chien-Hung Liu, Student Member, IEEE

Abstract—Music is a significant achievement of human activities
and culture. Composing music is a complex and challenging task
in that many factors, such as scale, key, chord, rhythm, and pitch,and their interactions need to be considered. With the advanceof computer technology and artificial intelligence, automatic composition systems emerge and present some promising results. In
particular, composing music through evolutionary algorithms hasreceived increasing attention. Although evolutionary approaches
are capable of generating compositions that follow music theory,these compositions are easily recognized as machine-made products due to their unpredictability in melodic progression, which isan important factor affecting a human’s impression and feeling ona song. This paper aims for an automatic composition system thatemulates human intelligence in music composition. Specifically,
we propose the phrase imitation-based evolutionary composition(PIEC) to generate compositions by an evolutionary algorithm
based on music theory and imitation of the characteristics andmelodic progression of human-composed music. The PIEC conducts intraphrase and interphrase rearrangement to imitate theascending/descending motion of phrases. Furthermore, we design
four fitness functions for the PIEC to evolve compositions considering note distribution, interval variance, and music theory. The
experimental results show that the proposed PIEC can effectively
generate satisfactory compositions with the characteristics of thesample melody. The results also validate the effects of phrase imitation and the four fitness functions on evolutionary composition.
Index Terms—Computational creativity, evolutionary algorithm, humanlike intelligence, music composition system, phrase
imitation.

I. I NTRODUCTIONM

USIC is an important channel for humans to express
feelings and emotions. Music theory is developed asa standard for music composition. The theory records andregulates the criteria for composing music. A complete music
composition generally contains three components: music style,rhythm, and pitch sequence. Music style can be identified by
the chord progression. Rhythm is characterized by the repeatingbeats in different phrases. Pitch sequence plays a key role and isusually viewed as the core of the composition. A piece of music
can be separated into melody and accompaniment, where themelody conveys the major impression to the audience and theaccompaniment is used to intensify harmony and music flavor.
Composing satisfactory music is very challenging and complex because all the aforementioned components and their
Manuscript received March 2, 2015; revised August 13, 2015; accepted
September 17, 2015.
The authors are with the Department of Computer Science and Information
Engineering, National Chung Cheng University, Chiayi 621, Taiwan (e-mail:ckting@cs.ccu.edu.tw; wcl101m@cs.ccu.edu.tw; lch101p@cs.ccu.edu.tw).
Digital Object Identifier 10.1109/JSYST.2015.2482602

interactions need to be considered. Some studies propose music
systems using artificial intelligence technologies to analyze
and create music. This manner has achieved considerable successes in automatic accompaniment. As for melody, despitesome promising results, the enormous permutations of notes
and beats still pose a big challenge to melody composition.
Evolutionary algorithms have shown to be effective in various
optimization problems [7], [8], [28], complex systems [23],[38], [41], and real-world applications [9], [16], [36]. Genetic
algorithm (GA) is a well-known evolutionary algorithm and has
succeeded in dealing with complex and large-scale problems[12], [15], [18], [29], [33], [35]. In view of this fruitfulness,
GA is utilized in automatic composition and accompaniment
system. In particular, the stochastic nature and search ability of
GA are beneficial for automatic composition. The evolutionary
composition approaches ordinarily utilize knowledge such asmusic theory, characteristics, and the experiences of performance or composition to imitate the human’s composition.
Horner and Goldberg [17] proposed a GA to compose melody
between two predetermined music segments. Biles [2] developed the genetic jammer (GenJam), which uses GA to generate jazz solo segments. The fitness values of these segments
are evaluated according to human feedback. Diaz-Jerez [11]proposed composing with Melomics, an automatic composition
system using evolutionary approaches. The results have beensuccessfully played or incorporated by professional musicians.
Liu and Ting [21] presented a GA using fitness evaluation basedon music theory to address the fatigue issue at human-assisted
evaluation.
In evolutionary composition systems, the evolutionary algorithm can probably find a proper permutation of notes; however,the stochastic search may also lead to a weird melody if not
guided by some music characteristics. This unexpectedness
is like a double-edged sword: Beyond personal experienceand preference in composition, the evolutionary algorithm can
explore huge combinations and permutations of notes for a satisfactory melody. On the other hand, the melodies evolved without certain guidance and criteria usually lack regular repeatedsegments and composition character. Such kind of melodies has
few memory points and thus is hard to remember. In general, themajor challenge to evolutionary composition is how to compose
music considering a huge variety of pitches, intervals, melodic
directions, rhythms, and musical structures. The evolutionary
algorithm can consider as many of these music characteristics
to generate compositions as possible. Nonetheless, excessive
considerations will probably mislead the search of the evolutionary algorithm, or some of the characteristics may be depressed in the resultant compositions. Therefore, an appropriate

1932-8184 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
2

IEEE SYSTEMS JOURNAL

selection of characteristics and emulation of human composition is needed and beneficial for evolutionary composition.
This paper proposes the phrase imitation-based evolutionary
composition (PIEC), which uses GA to generate a new melody
with the characteristics of a sample melody composed by humans. More specifically, the PIEC creates melodies by imitating
the arrangement of notes and rhythm in each phrase of thesample melody. The PIEC possesses three features. First, thePIEC performs intraphrase and interphrase rearrangement tomake the phrase motion, i.e., ascending and descending, of new
melodies consistent with that of the sample melody. Second,
the PIEC reduces dissonant intervals by fixing inappropriate
notes according to scale and chords. Third, we design four
fitness functions for the PIEC based on the music characteristicsof the sample melody. The four fitness functions involve thedifference of note variance (NV), difference of interval variance(IV), rules of arrangement (RA), and hybrid evaluation. Thesefitness functions render guidance for the evolution of melodies
as well as intensification on the imitation of the sample melody.
The collaboration of these three features contributes to the balance of uniqueness of generated melodies and their similarity
with the sample melody. By imitating phrases, the PIEC canattain compositions similar with the sample melody in phrase
characteristics but dissimilar in notes within phrases.
The remainder of this paper is organized as follows. Section II
reviews the related work. Section III sheds light on the proposed
PIEC. The experimental results are presented and discussed in
Section IV. Finally, Section V draws the conclusions of thispaper.
II. R ELATED W ORK
Evolutionary composition depends upon the great search
power and stochastic nature of the evolutionary algorithm. It
has become one of the main methods for automatic music composition. Evolutionary composition can be classified into three
types: interactive, rule-based, and learning-based evolutionary
composition. The following sections recapitulate the studies onthese three types of evolutionary composition.
A. Interactive Evolutionary Composition
The evaluation of generated compositions has a vital effect on computer composition systems. Interactive evolutionary
composition makes use of the listener’s feedback for the fitness
evaluation of the phrases or compositions generated by theevolutionary algorithm. Biles [2] used real-time human evaluation on the jazz solos created by the GenJam, a GA-based
composition system using the chords, scales, and rhythms of
the accompaniment. The fitness values of generated music segments are evaluated by the audience. However, after long-time
listening, the audience lose their concentration and thus judge
inaccurately due to fatigue. To solve this issue, Biles et al. [5]combined GenJam with a neural network, where the latter isused to learn human feedback. Biles further presented the details about the learning mechanism and the utilization of chords,
measures, rhythms, and phrases for music composition in
GenJam architecture [3], [4]. Johanson and Poli [20] and Tokuiand Iba [37] both applied interactive genetic programming (GP)to compose music. The former used GP to evolve the pitches ofnotes, whereas the latter focused on the rhythm. Jacob [19] usedan evolutionary algorithm to evolve the weights, phrase lengths,
and transposition table for a new melody, given the motif andthe chord progression. The evaluation requires the audience toevaluate only certain parts of music to reduce their loading.
Collaborating with musicians for professional feedback isanother important direction in interactive evolutionary computation. Diaz-Jerez [11] adopted the compositions scored by professional composers in Melomics for automatic composition.
Manaris et al. [24] designed an interactive music generator
based on the Markov model, GA, and power laws. The system
can interact with the human player’s performance and respondwith meaningful music.
Human feedback renders a direct evaluation of generated
compositions. Nevertheless, the fatigue caused by repeatedly
listening will gradually run out the human evaluator’s patienceand music sensitivity. It also limits the population size and thenumber of generations used for the evolutionary algorithm incomposition.
B. Rule-Based Evolutionary Composition
The evolutionary algorithm in rule-based evolutionary composition uses explicit rules for the fitness function. The evaluation rules usually refer to music elements, such as rhythm,
phrase, scale, or chord, from personal experience or music theory. Horner and Goldberg [17] proposed composing music by
GA using static patterns. A complete composition is generated
by iteratively creating a music segment that can bridge two music parts. McIntyre [27] used the four-part Baroque harmony toestablish a stable progression. The notes are selected according
to the given chords and distributed to the four music tracks. This
design ensures the harmony and stability but limits the selectionof nonharmonic notes. Tzimeas and Mangina [39] modified
the input melodies to construct a new melody. Based on thepatterns of jazz scale and rhythm, the input Baroque music istransformed to jazz music by GP. They further proposed thecritically-damped-oscillator fitness function for flexibly adjusting the evolutionary direction according to the given genre andrhythm [40]. The various rhythms are formulated as multiple
objectives, for which the weights are calculated by the similarity between candidate rhythms and the given rhythm. Ozcan and
Ercal [31] provided a musical evolutionary assistant (AMUSE)
to generate improvisations by using predetermined chords andrhythms. The AMUSE evaluates compositions using the information of intervals, pitch contour, and notes. Oliwa [30] designed a polyphony composition according to the features of jazzmusic, such as the tendency of scale, duration of notes, and coordination of musical instruments. Freitas and Guimaraes [13]used the nondominated sorting genetic algorithm-II to analyze
melodies for the possible progression of harmony. Matić [26]utilized the input melodies as the basis for the evaluation ofgenerated melodies. The fitness function is based on the mean
and variance of intervals and the proportion of scale notes in ameasure. Liu and Ting [21] proposed using the evaluation rules
based on music theory in polyphony composition. The rules
consider chord notes, leap, harmony, and rhythm.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
TING et al.: AUTOMATIC COMPOSITION SYSTEM USING EVOLUTIONARY ALGORITHM AND PHRASE IMITATION

3

Fig. 1. Workflow of the proposed music composition system.

In general, rule-based evolutionary composition can efficiently generate compositions of a specific music genre. However, the resultant compositions are subject to the predetermined
fixed rules in essence.
C. Learning-Based Evolutionary Composition
Learning-based evolutionary composition leverages music
data to build the models for the evolutionary algorithm tocompose music. Different from the interactive evolutionary
composition, the learning-based evolutionary composition uses
existing compositions or records instead of real-time human
feedback. Gibson and Byrne [14] employed a neural network toestablish the rhythm model and applied GA to find out all possible combinations of rhythms. Spector and Alpern [34] used
Fahlman’s quickprop algorithm and a neural network to findthe characteristics of music. The results are then applied in thefitness evaluation of GP. Dannenberg et al. [10] proposed using
Bayesian and linear classifiers to classify music data. The neuralnetwork is adopted to learn the music characteristics and applied to GA for generating music. Burton and Vladimirova [6]presented the adaptive resonance theory using a clustering algorithm to recognize the characteristics and classifications of compositions for the arrangement of percussion. Manaris et al. [25]used Zipf’s law to examine the classifications of neural network
among classical, popular, and unpopular music. The GP thenuses the classification results to evolve new compositions.
Ramirez et al. [32] utilized the information of records to build
music models for pitches and rhythms. They used GA basedon the models to create compositions. Acampora et al. [1]proposed the four-part harmony creation, which exploits thefeatures of the four-part harmony as the basis of evaluating
chord structure and harmony. They applied data mining tofind several principles and used fuzzy control to determine theweights of these principles for evolutionary composition.
The learning-based evolutionary composition utilizes machine learning technologies to analyze, classify, or cluster music data. These results are commonly used for fitness evaluationin evolutionary composition. Although this method addresses
the fatigue issue at the interactive evolutionary composition, thelearning results may mislead the direction of the evolutionary
search and bring about weird compositions.
The aforementioned studies reveal that melodic progressionis less affected by some characteristics, e.g., arrangement ofscale, repeats of rhythms, and progression of harmony. The
information about melodic progression among phrases is useful for composition. The PIEC is designed to generate newcompositions by imitating the melodic progression associatedwith note distribution and ascending/descending motions of thesample melody. More details of the proposed PIEC are given in
the next section.
III. P ROPOSED C OMPOSITION S YSTEM
The proposed music composition system aims to emulate
human intelligence in music composition. As Fig. 1 shows, thesystem adopts human compositions as a basis to generate new
melody. Given a sample melody, the proposed system analyzes
and extracts its characteristics, including chord, scale, rhythm,
melodic progression, and pitch sequences. These characteristics are used in the PIEC to generate new compositions. The
proposed PIEC is a novel evolutionary composition approachthat considers music theory and imitation of phrases at composition. Furthermore, this paper presents note fixing to adjust
inappropriate notes during and after evolution. Music form isapplied to improve the structure and euphony of compositions.
The PIEC follows the rhythm, chords, and scales of the sample melody and imitates its melodic progression among phrases
for GA to compose new melodies. This paper develops the GA
operators, melody imitation, note rearrangement, and evaluation of generated melodies for the PIEC. Algorithm 1 showsthe evolutionary process of PIEC. The population initialization,
parent selection, crossover, mutation, and survivor selection
operators follow the paradigm of GA. After an offspring is
generated, the PIEC additionally performs intraphrase and interphrase rearrangement on it to adjust notes for the imitation

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
4

IEEE SYSTEMS JOURNAL

Algorithm 1 PIEC
Initialize (P )Evaluate (P )repeatC←∅
repeatP arents ← Select(P )c ← Crossover(P arents)c ← Mutate(c)c ← IntraPhraseRearrange(c)c ← InterPhraseRearrange(c)c ← DissonantToneFixing(c)Evaluate (c)C ← C ∪ {c}until C is filled
P ← Survival(P, C)
until the terminal condition is satisfied
P ← EndingNoteFixing(P )P ← MusicalForm(P )TABLE IR EPRESENTATION OF P ITCHES I NTO I NTEGERSof the sample melody. The note recognition and fixing mechanism fixes illegal notes. The resultant offspring is evaluatedby one of the four proposed fitness functions. The evolutionary
process continues until the termination criterion is satisfied. The
following sections elucidate the designs for the composition
system and PIEC.
A. Representation and Genetic Operators
The PIEC uses integer strings to represent chromosomes in
the GA. The genes of a chromosome are encoded by integers
ranging from 1 to 25 to represent the pitches. According to thetwelve-tone equal temperament, an octave contains 12 pitches.
Table I lists the integer for each pitch, where a pitch is expressed
as a lowercase letter using the Helmholtz pitch notation. For
instance, integer 1 represents pitch c, and 13 denotes pitch c2 .
Fig. 2 illustrates a chromosome and its corresponding notes in
two measures in Ionian mode on C.
The PIEC randomly generates the initial population of chromosomes. Afterward, it performs selection, crossover, mutation, and survival operations to enhance chromosomes in theFig. 2. Example of chromosome representation.

course of evolution. This paper adopts the two-tournament
selection operator, which repeats choosing the better of two
randomly picked chromosomes twice for a pair of parents.
The two-point crossover then cuts each parent into three segments and exchanges the second segment of two parents to
produce their offspring. Next, the random resetting mutation
changes some genes to random values probabilistically. The
select–crossover–mutate process continues until the offspring
population is filled. The PIEC adopts the (μ + λ) strategy forthe survivor selection; that is, the survivors are selected fromthe union of parent and offspring populations for the next
generation.
B. Melody Imitation
In this paper, we propose two approaches of rearranging
notes to imitate the sample melody: intraphrase and interphrase
rearrangement. In the rearrangement, the PIEC first analyzes
the distribution of pitches and the occurrence order of phrases
in the sample melody, given its scale and phrase information.
The PIEC then uses the results to adjust the pitches of notes forimitating musical progression.
1) Intraphrase Rearrangement: The intraphrase rearrangement is designed to modify the note sequence within a phraseof compositions generated by GA. Restated, the order of pitches
is rearranged to follow that of the sample melody. The intraphrase rearrangement consists of two steps: First, the notesin the phrase are sorted in ascending order of pitch values. For
example, the sorted sequences of sample and new phrases inFig. 3 are 1-2-3-4-5-5 and 1-5-5-8-10-15, respectively. Next,
the notes of the new phrase are rearranged according to theorder of pitches in the sample phrase; for example, pitch 8 of
the new phrase is moved to the first position corresponding to
the position of the fourth order in the sample phrase. Throughintraphrase rearrangement, the resemblance in the progressionof notes between sample and new phrases can be promoted.
2) Interphrase Rearrangement: The interphrase rearrangement focuses on the progression of phrases. Specifically, it
shifts the pitches of all notes in the phrases of the new melody
to mimic the progression of phrases in the sample melody. The
mean of pitches in a phrase serves as a representative pitch
for that phrase. Using integer representation, the mean can becalculated by
n
1
x=
xi
(1)
n i=1
where xi denotes the pitch value of the ith note and n denotes
the number of pitches in the phrase.
The sequence of mean pitches is used to represent the progression of phrases. In the interphrase arrangement, the phrases
are first sorted in ascending order of mean pitches. The pitch ofeach note in a phrase is then shifted according to the comparison

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
TING et al.: AUTOMATIC COMPOSITION SYSTEM USING EVOLUTIONARY ALGORITHM AND PHRASE IMITATION

5

Fig. 3. Intraphrase rearrangement.

Fig. 4. Interphrase rearrangement.

of new and sample melodies in the order of mean pitches ofphrases. As Fig. 4 shows, the sorted phrase sequence of thesample melody is Ph3-Ph4-Ph1-Ph2, while that of the newmusic is Ph2-Ph1-Ph3-Ph4 with mean pitches 4.14-6.57-8.1112.20. For imitation to the sample melody, the pitch of phrase
P1 should be shifted to be the second highest, that of phrase P2

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
6

IEEE SYSTEMS JOURNAL

Fig. 5. Examples of diatonic and harmonic tones. (a) Diatonic tone. (b) Harmonic tone.

Fig. 6. Recognition of ending note.

should be shifted to be the highest, and so on. Therefore, theinterphrase rearrangement increases the pitch of each note in
Ph1 and Ph2 of the new melody by Round(8.11 − 6.57) = 2
and Round(12.20 − 4.14) = 8 semitones, respectively. Similarly, the pitch of each note in Ph3 and Ph4 is decreased by
4 and 6 semitones, respectively. The new melody can then havethe same phrase sequence with the sample melody in terms ofmean pitches.

of GA. This paper devises four fitness functions based on different music characteristics. The first two fitness functions dependon the statistics of notes, the third is a rule-based evaluation,and the fourth hybridizes the first and third fitness functions forreceiving their advantages. Note that chromosomes with low
fitness values are preferred for these four fitness functions.
1) Difference of Note Variance (NV): This fitness functionuses the statistics of pitches to describe the distribution ofnotes in a phrase. It evaluates chromosomes according to thedifference between the generated melody and sample melody
in the variance of pitches. Specifically, the variance of pitches
in a phrase is computed by1
(xi − x)2 .
n i=1nVarnote (x) =(2)

The fitness value is defined by
C. Note Recognition and Fixing
The PIEC adopts two procedures to recognize and fix notes,
including dissonant tones and inappropriate ending note. The
dissonant tones are defined according to the chords and scales
in the sample melody. For example, the notes in Fig. 5(a) are
categorized into diatonic and chromatic tones according to thescale (C major): Diatonic tones are the members of the scale,whereas chromatic tones are not. In addition, the notes areclassified into harmonic and nonharmonic tones given a chord:
Harmonic tones are the chord notes, while nonharmonic tones
are not. For the example of the G chord in Fig. 5(b), the chord
notes d, g, and b are harmonic, and others are nonharmonic.
A chromatic nonharmonic tone is defined as an illegal note.
Illegal notes may be produced during initialization, crossover,and mutation operations. After mutation, the note recognition
and fixing process checks the offspring and replaces its illegal
notes with diatonic or harmonic tones at random to avoid thedestruction of harmony.
Furthermore, the ending note must be a chord note. Fig. 6
illustrates the replacement of the ending note: If the note is
not a chord note, it will be replaced by the nearest chord note.
In case of equal distance to two nearest notes, it chooses thenote according to the ascending/descending state of music progression. This process is performed on the chromosomes afterGA evolution.

fnote =

N 






sample 
−
Var
P
h
 (3)
Varnote P hnew
note
i
i
i=1

where N is the number of phrase and P hnew
and P hsampleareii
the ith phrase of the new melody and sample melody, respectively. The fitness value reflects the difference of note distribution between new and sample melodies. This fitness function
favors the melodies having similar variances with the sample
melody.
2) Difference of Interval Variance (IV): This fitness functionuses Matić’s approach [26] to calculate the difference in variances of intervals between the generated and sample melodies.
An interval yi represents the distance of two adjacent notes, i.e.,yi = xi+1 − xi . The mean and variance of intervals in a phrase
P h are given byȳ =Varintvl (P h) =

n−1
1 
yi
n − 1 i=1n−11 (yi − ȳ)2 .
n − 1 i=1

(4)
(5)

The fitness value based on the difference of interval variances
is defined by
N 







− Varintvl P hsample
fintvl =Varintvl P hnew
 . (6)iii=1

D. Fitness Function
The fitness function evaluates the performance of chromosomes and exerts a significant effect on the evolutionary search

Similar with the NV fitness, this fitness function prefers thegenerated melodies that have similar variances with the sample
melody.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
TING et al.: AUTOMATIC COMPOSITION SYSTEM USING EVOLUTIONARY ALGORITHM AND PHRASE IMITATION

7TABLE IIE VALUATION RULES OF A RRANGEMENT

Fig. 7. Example of adjustment using musical form.

3) Rules of Arrangement (RA): This fitness function evaluates chromosomes according to music theory. Let xi,j denotethe jth pitch in the ith phrase, yi,j = xi,j+1 − xi,j denote theinterval, and superscripts new and sample indicate the new
melody and sample melody, respectively. Table II lists thefive evaluation rules, where H denotes the set of harmonic
tones and Dk denotes the set of kth diatonic tones. The firstrule examines whether sample and new melodies bothuse repeated notes (i.e., yi,j = 0) at the same time. If either
samplenewor yi,jis zero, it implies that the progression directions
yi,jare different, and the evaluation value is thus added by one.
The second to fifth rules examine the identity of notes and the
distance of intervals. The second rule penalizes the excessively
new| > 9) from a harmonic note xnew
large interval (|yi,ji,j ∈ H,
where the tolerance value 9 is determined by the largest intervalof the six combinations of major triad and minor triad plus
their inverted chords. The third rule is defined as follows: If
note xnew
i,j belongs to the set of fourth diatonic tone D4 , its
new≤subsequent note should be in D3 or D5 within interval yi,j
2 (major second) to ensure that the disharmony can be solved.
Similarly, the fourth rule is associated with note xnew
i,j ∈ D7
newwith interval yi,j
≤ 1 (minor second). The last rule regularizes
that, if xnew
i,j belongs to D1 , D2 , D3 , D5 , or D6 , it can benew≤ 5.
followed by any note within the perfect fourth, i.e., yi,jThis fitness function examines all notes of the chromosome.
Whenever a rule is matched, the evaluation value is increased byone. The final score acts as the fitness value of the chromosome.
A higher fitness implies a more serious violation of music
theory. Thus, chromosomes with low fitness are preferred.
4) Hybrid Evaluation: The hybrid approach is designed forgaining the advantages of NV and RA evaluation. The NV evaluation considers the note distribution in phrases, while the RA
evaluation guides the search for good compositions through theevaluation rules based on music theory. The hybrid evaluationsums up the fitness values obtained from NV and RA fitness
functions. Considering the fact that the ranges of NV and RA
fitness values are different, we standardize the fitness values by

=
fnote

fnote − μfnote
σfnote

(7)


=
frule

frule − μfrule
σfrule(8)where μf and σf are the mean and standard deviation of fitness
values of the population, respectively.
The hybrid fitness value is defined by+ frule.
fhybrid = fnote(9)

TABLE III
PARAMETER S ETTING FOR THE PIECThis evaluation is expected to acquire the advantages of fitness
evaluation based on phrase characteristics and music theory.
E. Musical Form
The PIEC further utilizes the musical form of the sample
melody to enhance the structure and euphony of generated
compositions. In the light of musical form, some phrases will
occur repeatedly in different positions of a composition. For
following the musical form of the sample melody, the PIEC
first identifies the phrases of the generated composition that are
corresponding to the repeated phrases in the sample melody.
These identified phrases are then adjusted by the manner of Liu
and Ting [22] to establish the musical form: The best phrase
replaces the other phrases. For example, in Fig. 7, phrase 4
holds the best fitness and is thus used to replace phrases 1
and 2 in the generated melody. In this way, the generated
compositions can have the same musical form as the sample
melody.
IV. E XPERIMENT R ESULTS
This paper conducts a series of experiments to generate music and examine the performance of the proposed composition
system. Table III lists the parameter setting for the PIEC in theexperiments. The PIEC follows the rhythm, chords, and scalesof the sample melody and uses GA to compose new music. In
addition, the PIEC imitates the melodic progression of phrases
in the sample melody through intra-/interphrase rearrangement
and fitness function. In the experiments, we investigate theeffects of the four proposed fitness functions, which involve
the NV, IV, RA, and hybrid evaluation. The following presents
and discusses the results from the PIEC adopting ChristianPetzold’s “Menuet in G major, BWV Anh 114” as the sample

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
8

IEEE SYSTEMS JOURNAL

Fig. 8. Variation of NV, IV, RA, and hybrid evaluation values against generations for PIEC using different fitness functions. (a) NV value; (b) IV value; (c) RA
value; (d) hybrid value.

melody. More experimental data and results can be downloaded
via http://cilab.cs.ccu.edu.tw/PIEC_Compositions.zip.
Fig. 8 shows the progress of NV, IV, and RA evaluation
values against generations over 30 runs of PIEC using NV,
IV, and RA fitness functions. The experimental results showthat NV, IV, and RA evaluation values decrease with evolution,
particularly for the PIEC using the corresponding fitness function. This outcome reflects that the fitness functions can resolve
the difference from the sample melody. Figs. 9 and 10 show
the compositions obtained from PIEC-NV and PIEC-IV,
respectively. The results indicate two features of PIEC-NV
and PIEC-IV: First, NV involves the note distribution in aphrase, whereas IV depends on intervals used to describe therelationship between notes. Therefore, PIEC-NV focuses on reducing the difference in note distribution, while PIEC-IV aims
to decrease the difference in intervals from the sample melody.
In particular, PIEC-IV is suitable for evolving the phrases with
continuous ascending or descending in that IV evaluation helps
to maintain the intervals between notes. Second, the results in
Fig. 8(a) and (b) indicate that PIEC-NV and PIEC-IV converge
after 400 generations, where the decreases of NV and IV values
both retard due to the fixation of notes and intervals in phrases.
Regarding PIEC-RA, the results in Figs. 8 and 11 reflect that

PIEC-RA prefers harmonic tones for the notes, which causes
the widespread use of harmonic tones in phrases and thusincreases the occurrence of repeated notes. Owing to the RA
evaluation based on music theory, PIEC-RA seldom generates
disharmonic melodies. The melodies generated by PIEC-RA,
nonetheless, may sound strange and machine-made since theevaluation does not refer to the music characteristics of thesample melody, which is reflected in the large difference ofvariances in the NV and IV evaluation.
The aforementioned experimental results indicate the effectsof evaluation methods on evolutionary composition: PIEC-NV
and PIEC-IV consider imitating the distribution and relationship of notes in the phrases of the sample melody, respectively,
but may result in disharmonic compositions. On the other
hand, PIEC-RA takes music theory into account to generateharmonic melodies but omits the music characteristics of thesample melody. The PIEC-Hybrid is proposed to gain the advantages from NV and RA evaluation. According to the resultsin Fig. 8(d), PIEC-Hybrid can achieve compositions with low
values of both NV and RA evaluation. In addition, the composition obtained from PIEC-Hybrid (cf. Fig. 12) excludes
disharmonic notes and has a similar note distribution with thesample melody.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
TING et al.: AUTOMATIC COMPOSITION SYSTEM USING EVOLUTIONARY ALGORITHM AND PHRASE IMITATION

Fig. 9. Resultant composition of PIEC-NV.

9

Fig. 11. Resultant composition of PIEC-RA.

Fig. 12. Resultant composition of PIEC-hybrid.
Fig. 10. Resultant composition of PIEC-IV.

This paper further investigates the influences of the four
fitness functions on evolutionary composition. According to thedesign of NV and IV fitness functions, the sample melody has
the best fitness; however, this best fitness can also be achievedby other compositions because the two fitness functions aredevised to tolerate certain variation in note or interval. As for
the RA and hybrid fitness functions, they both consider thefitness according to music theory. The sample melody may
not gain the best fitness value due to some potential violation
with music theory. By and large, the four fitness functions

TABLE IVC OMPARISON OF THE C OMPOSITIONS G ENERATED BYPIEC U SING D IFFERENT F ITNESS F UNCTIONS

facilitate imitating the sample melody by generating compositions similar yet different in various facets. Table IV compares
the motion (ascending/descending) similarity of adjacent notes,
variance of notes, and variance of intervals between the sample

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
10

IEEE SYSTEMS JOURNAL

TABLE VC OUNTS OF T ICKING “S IMILAR ” A GAINST D ISSIMILAR FOR E ACH C OMPARISON PAIR OF M ELODIESTABLE VI
p-VALUES OF O NE -TAILED S IGN T EST ON S IMILARITY B ETWEEN T WO M ELODIESTABLE VIIP REFERENCE C OUNTS IN THE PAIRWISE C OMPARISONS A MONG THE S AMPLE M ELODY AND F OUR PIEC C OMPOSITIONS

melody and the compositions generated by PIEC using thefour fitness functions. According to the results, PIEC-NV andPIEC-IV have the most similar distributions of notes and intervals with the sample melody, respectively. The PIEC-RA gains
higher motion similarity than PIEC-NV and PIEC-IV in that the
intra-/interphrase rearrangement tangles with the NV and IV
evaluation. However, PIEC-RA performs poorly in the imitation of note and interval distributions. By contrast, PIECHybrid achieves as high motion similarity as PIEC-NV does
and attains comparably low variances of notes and intervals
as PIEC-NV and PIEC-IV. This outcome validates that PIECHybrid gains the advantages of PIEC-NV and PIEC-RA.
To evaluate the composition results, we conducted a survey
on the similarity and preference among the sample melody andthe generated melodies. The survey includes nine sets, eachconsisting of one sample melody (Smp) and four melodies
generated by PIEC using NV, IV, RA, and hybrid fitness
functions. For each set, the participants listen to two melodies
randomly selected from the five melodies and answer twoquestions: 1) whether they are similar and 2) which one ispreferred. Each pair of comparison includes 35 questionnaire
results. First, Table V shows that most listeners believe thetwo melodies are similar (≥ 25 out of 35 counts). We further
carried out a one-tailed sign test on the counts. With confidence level α = 0.05, the p-values on Table VI validate that
the PIEC can generate compositions similar with the sample
melodies. Second, we investigate the preference among the five
melodies. Tables VII and VIII present the counts of preferencein the pairwise comparisons and their corresponding z-scores,
respectively. To explore the rank of the five approaches (i.e.,sample, NV, IV, RA, and hybrid), we consider the sums ofz-scores for one approach against the other approaches. According to Fig. 13, the melodies generated by PIEC-Hybrid
are more preferred than the sample melodies for eight out ofnine music, whereas the melodies generated by PIEC-IV andPIEC-RA are mostly inferior to the sample melodies. In general, the survey results show that the PIEC can imitate thesample melody and generate similar compositions; in addition,
PIEC using the hybrid fitness function can achieve melodies
preferable to the sample melody.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
TING et al.: AUTOMATIC COMPOSITION SYSTEM USING EVOLUTIONARY ALGORITHM AND PHRASE IMITATION

11TABLE VIIIz-S CORES ON THE R ESULTS OF PAIRWISE C OMPARISONS A MONG THE S AMPLE M ELODY AND F OUR PIEC C OMPOSITIONS

Fig. 13. Comparison of sums of z-scores with respect to the sample melody(Smp) and PIEC using NV, IV, RA, and hybrid fitness functions.

V. C ONCLUSION
This paper has proposed a novel automatic composition
system to compose music using evolutionary algorithm andphrase imitation considering human intelligence in music composition. The proposed PIEC follows the rhythm, chords, andscales of a sample melody and generates melodies by GA andimitation of the melodic progression of phrases in the sample melody. Specifically, the imitation focuses on three music
characteristics: motion of phrases, note distribution, and interval distribution. The intraphrase and interphrase rearrangement
methods are devised to mimic the ascending/descending motion
within and between phrases, respectively. Furthermore, we design four fitness functions for the PIEC to evolve compositions
considering different music characteristics. The NV fitness
function evaluates compositions according to the similarity
with the sample melody in note distribution. Likewise, the IV
fitness function considers the variance of intervals in phrases.
The RA fitness function evaluates compositions according tofive evaluation rules based on music theory. Finally, the hybrid
method combines NV and RA fitness functions to gain theiradvantages.
Several experiments are carried out to examine the performance of PIEC and its generated compositions. The experimental results show that the PIEC can compose satisfactorycompositions through evolution and imitation of the melodic
progression of phrases. This paper further investigates theeffects of the four fitness functions. PIEC-NV and PIEC-IV
can generate compositions with similar distributions of notes
and intervals to the sample melody, respectively. PIEC-RA
can effectively exclude disharmonic notes and achieve propercompositions in terms of music theory. PIEC-Hybrid possesses
the advantage of PIEC-NV in imitating note distribution inphrases and that of PIEC-RA in generating harmonic melody.
The survey results show that PIEC can imitate and compose melodies similar with the sample melody; in addition,
PIEC-Hybrid ordinarily achieves melodies preferable to thesample melody. These outcomes validate the effectiveness ofthe proposed PIEC in music composition.
Future work includes some directions. First, PIEC follows
the rhythm of the sample composition. In addition to melody,the evolution of rhythms is a challenging yet promising direction for evolutionary composition. Second, the technology
of extracting chords and scales from the sample melody canincrease the automatic level of PIEC’s imitation. Third, PIEC
aims to imitate the sample melody for generating compositions
that are close to human-made character. The imitation, nevertheless, may result in compositions too similar to the sample
music. The way to maintain the music characteristics without
strong resemblance is an important topic for future work.
Moreover, music style can be considered in the melody imitation operators and evaluation methods such as RA to enhancecomposition.
ACKNOWLEDGMENT
The authors would like to thank the editor and reviewers fortheir valuable comments and suggestions and Dr. C.-W. Ting
for the help with the statistical analysis.
R EFERENCES[1] G. Acampora et al., “A hybrid computational intelligence approach forautomatic music composition,” in Proc. IEEE Int. Conf. Fuzzy Syst., 2011,
pp. 202–209.
[2] J. A. Biles, “GenJam: A genetic algorithm for generating jazz solos,” inProc. Int. Comput. Music Conf., 1994, pp. 131–131.
[3] J. A. Biles, “Life with GenJam: Interacting with a musical IGA,” in Proc.
IEEE Int. Conf. Syst., Man, Cybern., vol. 3, 1999, pp. 652–656.
[4] J. A. Biles, “GenJam: Evolutionary computation gets a gig,” in Proc.
Conf. Inf. Technol. Curriculum, 2002, pp. 1–11.
[5] J. A. Biles, P. G. Anderson, and L. W. Loggi, “Neural network fitness
functions for a musical IGA,” in Proc. Int. Comput. Sci. Conf., 1996,
pp. 39–44.
[6] A. R. Burton and T. Vladimirova, “Genetic algorithm utilising neuralnetwork fitness evaluation for musical composition,” in Proc. Artif. Neural
Nets Genetic Algorithms, 1998, pp. 219–223.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
12[7] T. Chai, Y. Jin, and B. Sendhoff, “Evolutionary complex engineering
optimization: Opportunities and challenges,” IEEE Comput. Intell. Mag.,
vol. 8, no. 3, pp. 12–15, Aug. 2013.
[8] W. Chu, X. Gao, and S. Sorooshian, “A solution to the crucial problem of
population degeneration in high-dimensional evolutionary optimization,”
IEEE Syst. J., vol. 5, no. 3, pp. 362–373, Sep. 2011.
[9] S. Damas, O. Cordón, and J. Santamaria, “Medical image registration
using evolutionary computation: An experimental survey,” IEEE Comput.
Intell. Mag., vol. 6, no. 4, pp. 26–42, Nov. 2011.
[10] R. B. Dannenberg, B. Thom, and D. Watson, “A machine learning approach to musical style recognition,” in Proc. Int. Comput. Music Conf.,
1997, pp. 344–347.
[11] G. Diaz-Jerez, “Composing with Melomics: Delving into the computational world for musical inspiration,” Leonardo Music J., vol. 21,
pp. 13–14, 2011.
[12] M. Ellabaan, Y. S. Ong, S. D. Handoko, C. K. Kwoh, and H. Y. Man, “Discovering unique, low-energy transition states using evolutionary molecular memetic computing,” IEEE Comput. Intell. Mag., vol. 8, no. 3,
pp. 54–63, Aug. 2013.
[13] A. R. R. Freitas and F. G. Guimaraes, “Melody harmonization in evolutionary music using multiobjective genetic algorithms,” in Proc. Sound
Music Comput. Conf., 2011.
[14] P. M. Gibson and J. A. Byrne, “Neurogen, musical composition using
genetic algorithms and cooperating neural networks,” in Proc. 2nd Int.
Conf. Artif. Neural Netw., 1991, pp. 309–313.
[15] J. S. González, M. B. Payan, and J. M. Riquelme-Santos, “Optimizationof wind farm turbine layout including decision making under risk,” IEEE
Syst. J., vol. 6, no. 1, pp. 94–102, Mar. 2012.
[16] N. C. Hien, N. Mithulananthan, and R. C. Bansal, “Location and sizingof distributed generation units for loadabilty enhancement in primary
feeder,” IEEE Syst. J., vol. 7, no. 4, pp. 797–806, Dec. 2013.
[17] A. Horner and D. E. Goldberg, “Genetic algorithms and computer-assisted
music composition,” in Proc. 4th Int. Conf. Genetic Algorithms, 1991,
pp. 479–482.
[18] W. H. Ip, D. Wang, and V. Cho, “Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence
encoding scheme,” IEEE Syst. J., vol. 7, no. 4, pp. 649–657, Dec. 2013.
[19] B. Jacob, “Composing with genetic algorithms,” in Proc. Int. Comput.
Music Conf., 1995, pp. 452–455.
[20] B. Johanson and R. Poli, “GP-music: An interactive genetic programming
system for music generation with automated fitness raters,” in Proc. 3rd
Int. Conf. Genetic Program., 1998, pp. 181–186.
[21] C.-H. Liu and C.-K. Ting, “Polyphonic accompaniment using genetic
algorithm with music theory,” in Proc. IEEE Congr. Evol. Comput., 2012,
pp. 1–7.
[22] C.-H. Liu and C.-K. Ting, “Evolutionary composition using music theory
and charts,” in Proc. IEEE Symp. Comput. Intell. Creativity Affective
Comput., 2013, pp. 63–70.
[23] J. D. Lohn and G. S. Hornby, “Evolvable hardware: Using evolutionary
computation to design and optimize hardware systems,” IEEE Comput.
Intell. Mag., vol. 1, no. 1, pp. 19–27, Feb. 2006.
[24] B. Manaris, D. Hughes, and Y. Vassilandonakis, “Monterey mirror: Combining Markov models, genetic algorithms, and power laws,” in Proc.
IEEE Congr. Evol. Comput., 2011, pp. 33–40.
[25] B. Manaris et al., “A corpus-based hybrid approach to music analysis and composition,” in Proc. Nat. Conf. Artif. Intell., vol. 22, 2007,
pp. 839–845.
[26] D. Matić, “A genetic algorithm for composing music,” Yugoslav J. Oper.
Res., vol. 20, no. 1, pp. 157–177, 2013.
[27] R. A. McIntyre, “Bach in a box: The evolution of four part Baroqueharmony using the genetic algorithm,” in Proc. 1st IEEE Conf. Evol.
Comput., 1994, pp. 852–857.
[28] A. Mukhopadhyay, U. Maulik, S. Bandyopadhyay, and C. A. CoelloCoello, “A survey of multiobjective evolutionary algorithms for data
mining: Part I,” IEEE Trans. Evol. Comput., vol. 18, no. 1, pp. 4–19,
Feb. 2014.
[29] D. C. Nguyen and F. Azadivar, “Application of computer simulation andgenetic algorithms to gene interactive rules for early detection and prevention of cancer,” IEEE Syst. J., vol. 8, no. 3, pp. 1005–1013, Sep. 2014.
[30] T. M. Oliwa, “Genetic algorithms and the abc music notation language
for rock music composition,” in Proc. 10th Annu. Conf. Genetic Evol.
Comput., 2008, pp. 1603–1610.
[31] E. Özcan and T. Erçal, “A genetic algorithm for generating improvised
music,” in Artif. Evol., 2008, pp. 266–277.
[32] R. Ramirez, A. Hazan, E. Maestre, and X. Serra, “A genetic rule-basedmodel of expressive performance for jazz saxophone,” Comput. Music J.,
vol. 32, no. 1, pp. 38–50, Spring 2008.

IEEE SYSTEMS JOURNAL[33] G. A. Samra and F. Khalefah, “Localization of license plate number using dynamic image processing techniques and genetic algorithms,” IEEE
Trans. Evol. Comput., vol. 18, no. 2, pp. 244–257, Apr. 2014.
[34] L. Spector and A. Alpern, “Induction and recapitulation of deep musical structure,” in Proc. Int. Joint Conf. Artif. Intell., vol. 95, 1995,
pp. 41–48.
[35] Y. Sun and D. J. Verschuur, “A self-adjustable input genetic algorithm
for the near-surface problem in geophysics,” IEEE Trans. Evol. Comput.,vol. 18, no. 3, pp. 309–325, Jun. 2014.
[36] M.-H. Tayarani, X. Yao, and H. Xu, “Meta-heuristic algorithms in car
engine design: A literature survey,” IEEE Trans. Evol. Comput., vol. 19,
no. 5, pp. 609–629, 2015.
[37] N. Tokui and H. Iba, “Music composition with interactive evolutionary
computation,” in Proc. 3rd Int. Conf. Generative Art, vol. 17, 2000,
pp. 215–226.
[38] P. W. Tsai, M. K. Khan, J. Sy, and B. Y. Liao, “Interactive artificial
bee colony supported passive continuous authentication system,” IEEE
Syst. J., vol. 8, no. 2, pp. 395–405, Jun. 2014.
[39] D. Tzimeas and E. Mangina, “Jazz Sebastian Bach: A GA system formusic style modification,” in Proc. Int. Conf. Syst. Netw. Commun., 2006,
pp. 36–36.
[40] D. Tzimeas and E. Mangina, “Dynamic techniques for genetic algorithmbased music systems,” Comput. Music J., vol. 33, no. 3, pp. 45–60,
Fall 2009.
[41] J. Zhang et al., “Evolutionary computation meets machine learning: A
survey,” IEEE Comput. Intell. Mag., vol. 6, no. 4, pp. 68–75, Nov. 2011.

Chuan-Kang Ting (S’01–M’06–SM’13) received
the B.S. degree from National Chiao Tung University, Hsinchu, Taiwan, in 1994, the M.S. degree from
National Tsing Hua University, Hsinchu, Taiwan, in
1996, and the Dr. rer. nat. degree from the Universityof Paderborn, Paderborn, Germany, in 2005.
He is currently an Associate Professor at the Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi,
Taiwan. His research interests include evolutionary
computation, computational intelligence, machinelearning, and their applications in music, art, networks, and bioinformatics.
Dr. Ting is an Associate Editor of the IEEE C OMPUTATIONAL I NTELLI GENCE M AGAZINE and an editorial board member of the Soft Computing andMemetic Computing journals.

Chia-Lin Wu received the B.S. degree in computer science and information engineering fromFu Jen Catholic University, New Taipei City, Taiwan,
in 2012 and the M.S. degree in computer scienceand information engineering from National Chung
Cheng University, Chiayi, Taiwan, in 2014.
Her research interests include evolutionary algorithm for music composition and machine learning.

Chien-Hung Liu (S’12) received the B.S. degree incomputer science and information engineering from
National Chung Cheng University, Chiayi, Taiwan,
in 2011, where he is currently working toward the
Ph.D. degree at the Department of Computer Scienceand Information Engineering.
His research interests include evolutionary computation, memetic algorithm, computer composition,and creative intelligence.