Evolving Strings

In this tutorial for the Evolvable Ruby gem, we'll walk through a slightly simplified implementation of the evolve string command-line program by following the steps defined in Evolvable's Getting Started guide.

Using Evolvable, we'll build upon evolutionary processes such as selection, crossover, and mutation to evolve a population of randomly initialized strings to match a target string, similarly to the way the above command-line program works.

Step 1

"Include the Evolvable module in the class for the instances you want to evolve."

Since we want to build instances that can evolve to match a given string, EvolvableString seems like a fine name.

class EvolvableString
  include Evolvable
end

The name of your "evolvable" class can be anything; the important thing is that it includes the Evolvable module which enables evolutionary behaviors.

Step 2

"Implement .gene_space, define any gene classes referenced by it, and include the Evolvable::Gene module for each."

In the context of Evolvable, a "Gene" can be thought of as an object that in some way affects the behavior of your evolvable instances. Gene objects are used to encapsulate a "sample space" and return a sample outcome.

We'll complete this step in two parts. We'll first define the .gene_space method.

class EvolvableString
  # ...

  TARGET_STRING = 'supercalifragilisticexpialidocious'

  def self.gene_space
    { char_genes: { type: 'CharGene', count: TARGET_STRING.length } }
  end
end

This configures the types of genes that we want for each evolvable instance. In theory, we're configuring a hyperdimensional mapping of all the possible gene values for an instance. A hyperdimensional "gene space" so to speak.

For this example, TARGET_STRING is hardcoded as the string that our population of string instances will evolve towards. Often there is no known target when working with evolutionary algorithms, but we've hardcoded one for the sake of simplicity. This is one of the simplifications of the Evolvable Strings web demo (coming soon) which uses a separate length gene to determine the number of char genes for each instance.

Above we referenced the CharGene class which will be used to represent a single letter in the strings we want to evolve. Let's define it.

class CharGene
  include Evolvable::Gene

  CHARS = ('a'..'z').to_a

  def to_s
    @to_s ||= CHARS.sample
  end
end

Gene objects must include the Evolvable::Gene module which enables them to undergo evolutionary operations such as crossover and mutation.

In the code above, the CHARS array contains lowercase letters of the alphabet from which the #to_s method randomly picks a letter when invoked for the first time. It is important that the data for a particular gene never change. Ruby's or-equals operator ||= is super useful for memoizing gene attributes. In this code, it is used to randomly pick a letter only once and return the same letter for the lifetime of this object.

You can write whatever methods needed to express genes. The #to_s method was chosen since this gene represents a one-letter string that will be joined with other one-letter strings to compose the final output.

Now that we've defined our gene space and gene class, we'll implement how we compare rival strings to each other.

Step 3

"Implement #value."

A value instance method is required. In terms of traditional genetic algorithms, it forms a part of the "fitness function". It is used when evaluating instances before undergoing evolutionary selection.

class EvolvableString
  # ...

  def value
    value = 0
     find_genes(:char_genes).each_with_index do |gene, index|
       value += 1 if gene.to_s == TARGET_STRING[index]
     end
     value
  end
end

This implementation uses the Evolvable#find_genes helper method to find all the gene objects configured under the char_genes key in the .gene_space method. It then iterates over each CharGene instance and compares its one-letter string with the target string. The "value" returned by this method equals the overall number of letters that an instance has in common with the target string.

In the next step, when we start evolving, this value is used to select instances whose genes will be used to initialize future generations of instances. The Evolvable gem seeks to give you complete control in how you evaluate instances and populations. See Evaluation for more.

Final Step

"Initialize a population and start evolving."

Check out the section on Populations for details on working with population objects, but here's the simplest way:

population = EvolvableString.new_population
# Might take a few seconds, but we can speed it up
# 34 is the length of the target string
population.evolve(goal_value: 34)

You can try this for yourself by loading everything previously defined in IRB. Or perhaps more quickly by, by cloning the evolvable repo and running bin/console at the command line in the evolvable directory.

The below code should return "supercalifragilisticexpialidocious"

population.best_instance.find_genes(:char_genes).join

What's Happening?

It'd be nice if we could receive insight into what's happening when we run population.evolve by defining the before_evolution hook which runs after each generation's evaluation and before each evolution. For each generation, we'll output the best instance's string representation, string matches count, and evolutions/generations count.

class EvolvableString
  # ...
  def self.before_evolution(population)
    best_instance = population.best_instance
    puts "#{best_instance} | #{best_instance.value} matches | Generation #{population.evolutions_count}"
  end

  # ...

  # We've also extracted the `find_genes(:char_genes).join` code from above
  # so our instance knows how to implicitly cast itself to a string.
  def to_s
    find_genes(:char_genes).join
  end
end

Now when you initialize a new population and run #evolve, you should see some output. Having this information helps in experimenting with gene configurations, evaluation definitions, and other evolvable configurations.

For this particular program, I've found that drastically increasing the probability that a char gene for a particular instance undergoes a single letter mutation can speed up the number of generations it takes to hit the target. You can experiment with this like so: population.mutation.probability = 0.8

This basically says that 80% of the instances from each generation should undergo one mutation on one gene. While this high probability seems to work really well for this simple program, typically 0.8 would be far too big. A more sane probability of 0.03 has been chosen as the default.

Thanks for following along!

To hear about future blog articles, presentations, and evolvable happenings, sign up for The Evolvable Newsletter.