Spelling Words with Genetic Algorithms

Genetic Algorithms in Elixir — by Sean Moriarity (32 / 101)

👈 Solving One-Max for the Last Time | TOC | What You Learned 👉

To illustrate the power of your new framework, you’ll use it to solve a new basic problem: spelling. You’ll teach your algorithm to spell an impossibly long word: supercalifragilisticexpialidocious.

Start by creating a new file called speller.exs in scripts and define a new problem:

​ ​defmodule​ Speller ​do​
​   @behaviour Problem
​   alias Types.Chromosome

​   ​def​ genotype, ​do​: ​# ...​
​ 
​   ​def​ fitness_function(chromosome), ​do​: ​# ...​
​ 
​   ​def​ terminate?(population), ​do​: ​# ...​
​ 
​ ​end​

Now you need to define a Problem implementation for your tasks. In this chapter, you learned there are three parts to every problem: a genotype, a fitness function, and termination criteria.

The first thing you’ll want to decide is the genotype. Your goal is to spell supercalifragilisticexpialidocious which is a 34-letter word. That means your search space is all 34-letter words. You can define your genotype like this:

​ ​def​ genotype ​do​
​   genes =
​     Stream.repeatedly(​fn​ -> Enum.random(​?a​..​?z​) ​end​)
​     |> Enum.take(34)
​   %Chromosome{​genes:​ genes, ​size:​ 34}
​ ​end​

Stream.repeatedly/1 returns a Stream that will continuously apply a function. In this case, the function you want it to apply is Enum.random/1 over every single alphabetical character. You then take 34 different characters from the stream to produce solutions.

The next thing you need is a fitness function. You want your fitness function to be a measure of how close the guessed word is to the target word. Luckily, Elixir has some functions that implement the desired behavior. Implement your fitness function like this:

​ ​def​ fitness_function(chromosome) ​do​
​   target = ​"​​supercalifragilisticexpialidocious"​
​   guess = List.to_string(chromosome.genes)
​   String.jaro_distance(target, guess)
​ ​end​

String.jaro_distance/2 returns the similarity between the two words, with 1 meaning the words are the same. You need to convert your genes to a string because String.jaro_distance/2 expects two Strings.

Because String.jaro_distance/2 only returns 1 when the words are the same, you can implement your termination criteria like this:

​ ​def​ terminate?([best | _]), ​do​: best.fitness == 1

That’s all you need. Your whole problem should look like:

​ ​defmodule​ Speller ​do​
​   @behaviour Problem
​   alias Types.Chromosome
​ 
​   ​def​ genotype ​do​
​     genes =
​       Stream.repeatedly(​fn​ -> Enum.random(​?a​..​?z​) ​end​)
​       |> Enum.take(34)
​     %Chromosome{​genes:​ genes, ​size:​ 34}
​   ​end​
​ 
​   ​def​ fitness_function(chromosome) ​do​
​     target = ​'supercalifragilisticexpialidocious'​
​     guess = chromosome.genes
​     String.jaro_distance(target, guess)
​   ​end​
​ 
​   ​def​ terminate?([best | _]), ​do​: best.fitness == 1
​ ​end​

Now, add the following below your module:

​ soln = Genetic.run(Speller)
​ 
​ IO.write(​"​​\n"​)
​ IO.inspect(soln)

Now run your algorithm:

​ ​$ ​​mix​​ ​​run​​ ​​scripts/speller.exs​
​ Current Best: 1.0
​ supercalifragilisticexpialidocious

That’s all it takes. Spelling a word you can just look up might not be the most impressive task; however, this problem shows the power of your framework. All you need to run a genetic algorithm against a problem is to define a genotype, fitness function, and termination criteria.

“It’s Taking Too Long…”

INFORMATION

You might find that your algorithm in the last problem takes awhile to converge. That’s OK. You haven’t been equipped with the necessary tools to write algorithms that converge quickly on more difficult problems like this one. In the next few chapters, you’ll add some tools that will make algorithms like this one a breeze.

As you continue through this book, you’ll use this same Problem abstraction to solve progressively more difficult problems.

👈 Solving One-Max for the Last Time | TOC | What You Learned 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.