Blog

This is an extension of a blog post I wrote a couple months ago. You can find it here.

One of the big takeaways in my introduction to Evolutionary Algorithms was the sheer number of numerical parameters.

• \(\mu\) And \(\lambda\)
• Mutation Rate
• \(k\) in k-Tournament Selection

Not only this, but the sheer number of parameters:

• The genotype
• The mutator operator
• The survivor selection algorithm

And one might be wondering, what is the best operator for \(x\) or \(y\)? Let’s look at an example.

Recall the problem from the previous discussion: We are going to consider a sample problem, a deciphering program. The premise of the problem is as follows:

There is a string of characters (without spaces) hidden away that, after set, is inaccessible.
There are two ways to retrieve data about the hidden message:

1: Get the length of the string.

2: Given a string, the problem will output how many characters match within the two strings.

Disregarding the other technical details, let us focus on the survivor selection. We used \(k\) -tournament selection (with \(k = 50\)). But, let’s run a little experiment:

Run the Evolutionary Algorithm, with \(k\) ranging from \(5\) (basically the bare minimum) to \(100\) (\(\lambda\), the population size), and see how fast the algorithm terminates. Do this 1,000 times to get accurate results.

The result?

This makes sense. Our problem has one local optimum: the actual solution. So we do not need a lot of genetic diversity, we need aggressive selective pressure^[1] to reach the top quickly.

As \(k\) gets closer to \(\mu\), the average termination time decreases. What does this tell us? We picked the wrong survivor selection algorithm.

With \(k = \mu\), we no longer have \(k\) -tournament selection; we have truncation selection (where only the most fit individuals survive). And that's the interesting part about Evolutionary Algorithms: there are no objective, best parameters.

How do we alleviate this? Trial and error. There is no telling when one parameter is going to perform better than another.

After a couple of trial runs, and objectives in mind (average terminating fitness, best terminating fitness, time to termination), the answer might surprise (and delight) you.

1. How elitist the survivor selection algorithm is, picking the strongest individuals more often. ↩︎

Let's propose an Evolutionary Algorithm experiment; say we already have a framework in place (like the Secret Message framework we previously implemented). How difficult would it be to completely switch problem instances?

First, we need another problem instance. Our previous problem instance was pretty straightforward: it had one local optimum. Let's take on a problem with many local optima, such as the 3-SAT problem.

The premise of 3-SAT is simple. From a global pool of variables (\(x_1\), \(x_2\), \(\ldots\), \(x_n\)), we have a basic clause of three variables or-ed together (signified by \(\vee\)):

$$x_p \vee x_q \vee x_r$$

Then, and (signified by a \(\wedge\)) several clauses together:

$$\left(x_p \vee x_q \vee x_r\right) \wedge \left(x_s \vee x_t \vee x_u\right) \wedge \ldots \wedge \left(x_v \vee x_w \vee x_y\right)$$

The only stipulation is that any variable can be negated (signified by a \(\neg\)). So, supposing we want to negate \(x_p\); \(x_s\) and \(x_u\); and \(x_v\), \(x_w\), and \(x_y\); we can do the following:

$$\left(\neg x_p \vee x_q \vee x_r\right) \wedge \left(\neg x_s \vee x_t \vee \neg x_u\right) \wedge \ldots \wedge \left(\neg x_v \vee \neg x_w \vee \neg x_y\right)$$

Now, we simply have to assign all the variables such that all the clauses will evaluate to true. It may sound simple, but it belongs to the hardest classes of problems in computer science. There is no guaranteed algorithm to produce the right answer at this time.

For a more visual approach, please reference the figure below. The goal is to make every inner node green, by having at least one connected outer node be green. Note the green nodes have to account for negation as well.

This sounds like a good problem candidate for an Evolutionary Algorithms.

The SAT Problem

We can skip over the problem specific parts to worry more about the Evolutionary Algorithm aspect. Suppose we already have a well-defined SAT class that takes care of SAT-specific properties and methods, like so:

class SAT:
    def __init__(self, filename):
        """Create a SAT object that is read in from a CNF file."""
        ...

    @property
    def variables(self):
        """Get *all* the variables."""
        ...

    @property
    def total_clauses(self):
        """Get the total number of clauses."""
        ...

    @property
    def clauses_satisfied(self):
        """Get the number of satisfied clauses."""
        ...

    def __getitem__(self, key):
        """Get a particular variable (key)"""
        ...

    def __setitem__(self, key, value):
        """Set a variable (key) to value (True/False)"""
        ...

From this, we can create a new genotype for our Individual.

The New Genotype

The genotype structure was very similar to what we had before:

• The genotype is the SAT problem we defined above.
• Fitness is defined by a percentage of the total satisfied clauses.
• Mutation is uniform, choose a percentage \(p\) of alleles and flip their value.
• Recombination is uniform, randomly assemble values from both parents.

Looking at the refactoring, not much has changed.

The New EA Framework

Now that we have updated our Individual, the next thing to update would be the Evolutionary Algorithm framework, including:

• The Population
• The EA Itself

Except, we don't have to.

That's the beauty of Evolutionary Algorithms, they are incredibly adaptable. By swapping out the Individual, the rest of the evolutionary algorithm should still work.

For our SAT problem, there were some parameters updated, to make the algorithm more efficient:

• The mutation rate has been reduced to 5%
• The tournament size has been reduced to 15 individuals (out of \(\lambda = 100\)).

The Result

So, let's try our Evolutionary Algorithm. Taking a SAT instance with 75 variables and 150 clauses, this makes the search space

$$2^{75} \approx 3.77 \times 10^{22}$$

Great, so roughly 1,000 times the grains of sand on Earth, easy. So, can our EA do it?

After roughly 100 iterations, yes. See the visualization below.

Marvelous, our EA managed to find a solution after only 100 iterations in a giant search space. And all we had to do was swap out one class.