This interactive art exhibit applet requires Java 5 or higher, which you can install from Sun's Java site if necessary.
To build your own models like this, you might want to check out NetLogo
To download this model file (for viewing/editing with NetLogo): Happy Birthday Darwin.nlogo
This model demonstrates a genetic algorithm evolving a correct version of the "Happy Birthday", as seems an appropriate way to honor Darwin on the event of his birthday. Genetic algorithms (GAs) are a biologically-inspired computer science technique that combines notions from Mendelian genetics and Darwinian evolution to search for good solutions to a given problem. The GA works by generating a random population of solutions to a problem, evaluating those solutions and then using cloning, recombination (crossover) and mutation to create new solutions to the problem.
To start with, songs are randomly generated. Each song contains all of the pieces of "Happy Birthday", but they are randomly temporally located, rather than in their correct locations to make the familiar tune.
These randomly generated songs are interbred to create a new generation of songs, wherein songs are more likely to be chosen for breeding if they are more "fit" (closer to correct) than the other songs in the population. Fitness is measured by both the number and severity of the "mistakes" that a song has, when compared to the correct version. For more information about how genetic algorithms work in general, see the "Simple Genetic Algorithm" model in the NetLogo Models Library.
Press the SETUP button to create an initial random population of solutions.
Press the STEP button to have one new generation created from the old generation.
Press the GO button to have the genetic algorithm run until a solution has been found.
Genetic Algorithm Parameters:
The POPULATION-SIZE slider controls the number of songs that are present in each generation.
The CROSSOVER-RATE slider controls what percent of each new generation is created through sexual reproduction (recombination or crossover between two parents' genetic material), and what percent (100 - CROSSOVER-RATE) is created through asexual reproduction (cloning of one parent's genetic material).
The MUTATION-RATE slider controls the percent chance of mutation. This chance controls the likelihood that each note of the song will be randomly moved to a nearby (temporal) location.
Music Parameters:
If you don't want to hear any music, but just watch the visual representations of the song, turn the PLAY-MUSIC? switch off.
Using the PLAY-EVERY slider, you can control how often (in generations) you get to listen to the fittest song in the population.
You can choose a specific instrument to have the song played with using the INSTRUMENT chooser. If you set the PLAY-RANDOM-INSTRUMENT? switch to ON, then the instrument will be chosen randomly each time the song is played.
The MUSIC-TEMPO slider determines the tempo at which the music will be played.
The FITNESS PLOT is used to show the best, average, and worst fitness values of the solutions at each generation. The current population of songs is displayed in the right part of the view, where songs with more mistakes are placed closer to the top of the view, and songs with fewer mistakes are placed closer to the bottom. Songs are placed horizontally such that songs that have similar genetic material are often placed closer together.
Also, the number of mistakes in the song that has the fewest mistakes, from the current generation, is shown in the FEWEST MISTAKES monitor. Note that the song with the fewest mistakes may NOT be the same as the "fittest" song, since fitness takes into account both the number of mistakes and the severity of the mistakes (i.e. how far away from the correct location a note is being played).
Simple Genetic Algorithm
Sound Machine
There is some question as to the precise origin of the "Happy Birthday" lyrics which apparently appeared in the late 19th century or early 20th century and were copyrighted in 1935 by Jessica Hill, though the copyright is currently held by Time Warner, and probably won't expire until 2030. To avoid any concerns of copyright infringement, I wrote some new alternate lyrics to substitute in place of the traditional Happy Birthday lyrics. The melody for Happy Birthday is currently in the public domain.
extensions [ sound ]
breed [ songs song ]
breed [ syllables syllable ]
breed [ balloons balloon ]
breed [ frontrows frontrow ]
songs-own [
positions ;; list of positions
fitness
mistakes
stored-color
]
syllables-own [ start-time ]
globals [
correct-song-syllables
correct-song-notes
correct-song-durations
correct-song-positions
headerturtle
winner ;; song that currently has the best solution
fewest-mistakes
]
to setup
clear-all
set correct-song-syllables ["On" "The" "Ori-" "" " " "gin" "of" "Species," "" " " "what" "a" "good" "" " " "book" "you" "wrote," "" " " "We" "re-" "mem-" "" " " "ber" "you" "Dar" "" " " "win," "and" "your" "birth-" "" " " "day" "we" "" " " "note!" "" " " ]
set correct-song-notes [0 0 2 -3 -7 0 5 4 -2 -12 0 0 2 -2 -12 0 7 5 -3 -7 0 0 12 -3 -7 9 5 4 -2 -7 2 10 10 9 -3 -7 5 7 -2 -12 5 -3 -7 ]
set correct-song-positions [0 3 4 4 4 8 12 16 16 16 24 27 28 28 28 32 36 40 40 40 48 51 52 52 52 56 60 64 64 64 68 76 79 80 80 80 84 88 88 88 92 92 92]
set correct-song-durations [3 1 4 12 12 4 4 8 12 12 3 1 4 12 12 4 4 8 12 12 3 1 4 12 12 4 4 4 16 16 8 3 1 4 8 8 4 4 4 4 8 12 12]
ask patches with [ pxcor > 27 ] [ set pcolor white ]
create-turtles 1 [
set headerturtle self
setxy 16 max-pycor - 0.3
set label "\"Fittest\" song in the initial population of random songs:"
set size 0
set label-color sky + 1.5 st ]
create-turtles 1 [
setxy max-pxcor min-pycor
set label "----------------------- no mistakes ----------------------- "
set size 0 set label-color sky st ]
create-turtles 1 [
setxy max-pxcor max-pycor - 0.3
set label "----------------------- all mistakes ---------------------- "
set size 0 set label-color sky st ]
set-default-shape songs "music song"
create-songs population-size [
set positions n-values (length correct-song-positions) [random 93]
calculate-fitness
position-song
]
update-display play-music? false
do-plotting
end
to go
if (count turtles = 1) [ stop ]
if [fitness] of winner = 0
[
if (play-music?) [ celebrate-victory ]
stop
]
create-next-generation
tick
ask headerturtle [
set label (word "\"Fittest\" song in the population at generation # " ticks ":")
]
update-display (play-music? and ticks mod play-music-every = 0) false
do-plotting
end
to celebrate-victory
update-display true false
ask headerturtle [
set label "ONCE MORE, WITH CONFIDENCE!"
set heading 90 bk 3
repeat round (world-width / 24 * 100) [ fd 0.04 display ]
]
let prev-instrument instrument
if (use-random-instruments?)
[
set instrument "BRIGHT ACOUSTIC PIANO"
]
update-display true true
set instrument prev-instrument
wait 5
reset
end
to reset
ask turtles with [ self != headerturtle ] [ die ]
ask headerturtle [ set label "Press \"Start/Restart\" to run again." ]
end
to update-display [ with-music? with-balloons?]
set winner min-one-of songs [fitness]
set fewest-mistakes min [mistakes] of songs
ask syllables [ die ]
ask winner
[
(foreach positions correct-song-positions correct-song-syllables correct-song-durations
[
hatch-syllables 1 [
set start-time ?1
set xcor 1 + (?1 mod 24)
if (?1 > 74) [ set xcor xcor - 4 ]
if (xcor = 4) [ set xcor xcor - 0.5 ]
set ycor world-height - 2.5 - 2.5 * floor (?1 / 24)
set label word ?3 " "
ifelse (?4 < 4)
[ set shape "music notes 3" ]
[ set shape "music notes 2" ]
if (?3 = "") ; chord part 1
[ set ycor ycor - 0.75 set shape "music bass note 1" ]
if (?3 = " ") ; chord part 2
[ set ycor ycor - 0.75 set shape "music bass note 2" ]
set size 0.8
ifelse (?1 = ?2)
[ set color magenta ]
[ set color gray ]
set label-color gray
set xcor xcor + 1
st
]
])
display
]
if (with-music?)
[
ask winner [
hatch-frontrows 1 [ set shape [shape] of myself set size 2.5 ]
]
ask songs [
set stored-color color
;set color lput 40 (extract-rgb color) ; make transparent
set color scale-color color 8 0 10
]
if (use-random-instruments? and not with-balloons?)
[ set instrument one-of get-reasonable-instrument-list ]
ifelse (with-balloons?)
[ play-music 0.9 127 true ]
[ play-music music-tempo 60 false ]
ask frontrows [ die ]
ask songs [ set color stored-color ]
]
end
to play-music [ the-tempo volume with-balloons? ]
play-song the-tempo volume 57 [positions] of winner
reset-timer
let delay ((max [positions] of winner) / the-tempo * 1 / 8 ) + 1.5
; print word "waiting " delay
if (with-balloons?)
[ repeat 10 [ make-balloon ]]
while [ timer < delay ]
[
ask syllables [ if (start-time / the-tempo * 1 / 8) < timer [ set label-color white ] ]
if (with-balloons?)
[
if (random 5 = 0) [ make-balloon ]
ask balloons [ fd 0.1 rt random 8 lt random 8
if (heading < 180 and heading > 45) [ set heading 45 ]
if (heading < 315 and heading > 180) [ set heading 315 ]
]
]
display
wait 0.1
]
; wait delay
end
to make-balloon
create-balloons 1 [
setxy random-xcor min-pycor - 0.4
set heading random 30 - random 30
set shape "balloon"
set size 2.8
carefully [ ; for earlier NetLogo versions, which don't support transparency.
set color lput 128 extract-rgb color
] [ ]
]
end
to position-song
set xcor (28 + ((sum positions) / 16) mod 12)
set ycor 0.5 + (world-height - 1.8) * (mistakes / (length correct-song-notes))
if (count songs with [ color = [color] of myself ] > (count songs / 2))
[ set color one-of base-colors ]
if (size != 1) [ set size 1]
end
;; ===== Generating Solutions
;; Each solution has its "fitness score" calculated.
;; Lower scores are "more fit", since we're measuring error
;; The lower a fitness score, the more likely that this solution
;; will be chosen to reproduce and create offspring solutions
;; in the next generation.
;;
to calculate-fitness ;; song procedure
set mistakes sum (map [ ifelse-value (?1 = ?2) [ 0 ] [ 1 ] ] positions correct-song-positions)
set fitness sum (map [ ln (1 + (?1 - ?2) * (?1 - ?2)) ] positions correct-song-positions)
end
;; This procedure does the main work of the genetic algorithm.
;; We start with the old generation of solutions.
;; We choose solutions with good fitness to produce offspring
;; through crossover (sexual recombination), and to be cloned
;; (asexual reproduction) into the next generation.
;; There is also a chance of mutation occurring in each individual.
;; After a full new generation of solutions has been created,
;; the old generation dies.
to create-next-generation
; The following line of code looks a bit odd, so we'll explain it.
; if we simply wrote "LET OLD-GENERATION SONGS",
; then OLD-GENERATION would mean the set of all songs, and when
; new solutions were created, they would be added to the breed, and
; OLD-GENERATION would also grow. Since we don't want it to grow,
; we instead write "SONGS WITH [TRUE]", which makes OLD-GENERATION
; an agentset, which doesn't get updated when new solutions are created.
let old-generation songs with [true]
; Some number of the population is created by crossover each generation
; we divide by 2 because each time through the loop we create two children.
let crossover-count (floor (population-size * crossover-rate / 100 / 2))
repeat crossover-count
[
; We use "tournament selection", with tournament size = 3.
; This means, we randomly pick 3 solutions from the previous generation
; and select the best one of those 3 to reproduce.
let parent1 min-one-of (n-of 3 old-generation) [fitness]
let parent2 min-one-of (n-of 3 old-generation) [fitness]
let child-positions-pair crossover ([positions] of parent1) ([positions] of parent2)
; create the two children, with their new genetic material
ask parent1 [ hatch 1 [ set positions item 0 child-positions-pair ] ]
ask parent2 [ hatch 1 [ set positions item 1 child-positions-pair ] ]
]
; the remainder of the population is created by cloning
; selected members of the previous generation
repeat (population-size - crossover-count * 2)
[
ask max-one-of (n-of 3 old-generation) [fitness]
[ hatch 1 ]
]
ask old-generation [ die ]
; now we're just talking to the new generation of solutions here
ask songs
[
; there's a chance of mutations occurring
mutate
; finally we update the fitness value for this solution
calculate-fitness
position-song
]
end
;; ===== Mutations
;; This reporter performs one-point crossover on two lists of bits.
;; That is, it chooses a random location for a splitting point.
;; Then it reports two new lists, using that splitting point,
;; by combining the first part of bits1 with the second part of bits2
;; and the first part of bits2 with the second part of bits1;
;; it puts together the first part of one list with the second part of
;; the other.
to-report crossover [bits1 bits2]
let split-point 1 + random (length bits1 - 1)
report list (sentence (sublist bits1 0 split-point)
(sublist bits2 split-point length bits2))
(sentence (sublist bits2 0 split-point)
(sublist bits1 split-point length bits1))
end
to mutate ;; song procedure
set positions map [ifelse-value (random-float 100.0 < mutation-rate) [(? + random 10 - random 10) mod 93] [?]]
positions
end
;; ====== Plotting
to do-plotting
let fitness-list [fitness] of songs
let best-fitness min fitness-list
let avg-fitness mean fitness-list
let worst-fitness max fitness-list
set-current-plot "Population Fitness Plot"
set-current-plot-pen "avg"
plot avg-fitness
set-current-plot-pen "best"
plot best-fitness
set-current-plot-pen "worst"
plot worst-fitness
end
to play-song [ the-tempo volume transpose assigned-positions ]
(foreach correct-song-notes assigned-positions correct-song-durations
[
note the-tempo volume (?1 + transpose) ?2 ?3
])
end
to note [ the-tempo volume pitch pos duration ]
sound:play-note-later (pos / the-tempo * 1 / 8) instrument pitch volume (duration * 1 / 8) / the-tempo
end
to birthday-song
let velocity 100
let transpose 57
set correct-song-notes [0 0 2 -3 -7 0 5 4 -2 -12 0 0 2 -2 -12 0 7 5 -3 -7 0 0 12 -3 -7 9 5 4 -2 -7 2 10 10 9 -3 -7 5 7 -2 -12 5 -3 -7 ]
set correct-song-positions [0 3 4 4 4 8 12 16 16 16 24 27 28 28 28 32 36 40 40 40 48 51 52 52 52 56 60 64 64 64 68 76 79 80 80 80 84 88 88 88 92 92 92]
set correct-song-durations [3 1 4 12 12 4 4 8 12 12 3 1 4 12 12 4 4 8 12 12 3 1 4 12 12 4 4 4 16 16 8 3 1 4 8 8 4 4 4 4 8 12 12]
(foreach correct-song-notes correct-song-positions correct-song-durations
[
note music-tempo 127 ?1 + transpose ?2 ?3
])
end
; only give back instruments that are semi-reasonable
to-report get-reasonable-instrument-list
report ["ACOUSTIC GRAND PIANO" "BRIGHT ACOUSTIC PIANO" "ELECTRIC GRAND PIANO" "HONKY-TONK PIANO" "ELECTRIC PIANO 1" "ELECTRIC PIANO 2"
"HARPSICHORD" "CLAVI" "CELESTA" "GLOCKENSPIEL" "MUSIC BOX" "VIBRAPHONE" "MARIMBA" "XYLOPHONE" "TUBULAR BELLS" "DULCIMER" "DRAWBAR ORGAN"
"PERCUSSIVE ORGAN" "ROCK ORGAN" "CHURCH ORGAN" "REED ORGAN" "ACCORDION" "HARMONICA" "TANGO ACCORDION" "NYLON STRING GUITAR" "STEEL ACOUSTIC GUITAR"
"JAZZ ELECTRIC GUITAR" "CLEAN ELECTRIC GUITAR" "MUTED ELECTRIC GUITAR" "OVERDRIVEN GUITAR" "DISTORTION GUITAR" "GUITAR HARMONICS" "ACOUSTIC BASS"
"FINGERED ELECTRIC BASS" "PICKED ELECTRIC BASS" "FRETLESS BASS" "SLAP BASS 1" "SLAP BASS 2" "SYNTH BASS 1" "SYNTH BASS 2" "VIOLIN" "VIOLA" "CELLO"
"CONTRABASS" "TREMOLO STRINGS" "PIZZICATO STRINGS" "ORCHESTRAL HARP" "TIMPANI" "STRING ENSEMBLE 1" "STRING ENSEMBLE 2" "SYNTH STRINGS 1"
"SYNTH STRINGS 2" "CHOIR AAHS" "VOICE OOHS" "SYNTH VOICE" "ORCHESTRA HIT" "TRUMPET" "TROMBONE" "TUBA" "MUTED TRUMPET" "FRENCH HORN" "BRASS SECTION"
"SYNTH BRASS 1" "SYNTH BRASS 2" "SOPRANO SAX" "ALTO SAX" "TENOR SAX" "BARITONE SAX" "OBOE" "ENGLISH HORN" "BASSOON" "CLARINET" "PICCOLO" "FLUTE"
"RECORDER" "PAN FLUTE" "BLOWN BOTTLE" "SHAKUHACHI" "WHISTLE" "OCARINA" "SQUARE WAVE" "SAWTOOTH WAVE" "CALLIOPE" "CHIFF" "CHARANG" "VOICE" "FIFTHS"
"BASS AND LEAD" "NEW AGE" "WARM" "POLYSYNTH" "CHOIR" "BOWED" "METAL" "HALO" "SWEEP" "RAIN" ;"SOUNDTRACK" "CRYSTAL"
"ATMOSPHERE" "BRIGHTNESS" ;"GOBLINS" "ECHOES"
"SCI-FI" "SITAR" "BANJO" "SHAMISEN" "KOTO" "KALIMBA" "BAG PIPE" "FIDDLE" "SHANAI" "TINKLE BELL" "AGOGO" "STEEL DRUMS" "WOODBLOCK"
"TAIKO DRUM" "MELODIC TOM" ;"SYNTH DRUM" "REVERSE CYMBAL"
;"GUITAR FRET NOISE" "BREATH NOISE" "SEASHORE"
;"BIRD TWEET" "TELEPHONE RING" "HELICOPTER" "APPLAUSE" "GUNSHOT"
]
end