One of the big takeaways in my introduction to Evolutionary Algorithm 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 such.
- 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:
- Get the length of the string.
- 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.
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 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.
A 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.
How elitist the survivor selection algorithm is, picking the strongest individuals more often. ↩︎