1
$\begingroup$

I'm currently working on a problem formulation that requires non-binary individual representations in a genetic algorithm (GA). I've been exploring Holland's Schema Theorem as a theoretical basis for understanding the effectiveness of GAs. However, the theorem is typically discussed in the context of a "canonical GA" with binary representation, fixed-length individuals, fitness-proportional selection, single-point crossover, and gene-wise mutation.

In my case, each individual in the population can be represented by a string of integers within a certain range, making it a non-binary representation. I'm wondering whether the Schema Theorem still holds true for such a scenario. Can I apply the principles of the Schema Theorem to this type of GA with non-binary individual representations? If not, are there any alternative theorems or theoretical frameworks that can help demonstrate the effectiveness of GAs using non-binary representations? Specifically, I'm interested in understanding whether schemas with fitness greater than the population average are still likely to appear more frequently in the next generation, and how this might impact the convergence and optimization properties of the algorithm.

Any insights, references, or resources that could shed light on this topic?

$\endgroup$

1 Answer 1

2
$\begingroup$

It's been a while since I've been active in the research community, and it's possible that this is a controversial opinion, but I suspect it's still true that the Schema Theorem is not really used that much to inform our modern understanding of GAs. That doesn't mean that it's not true or useful as a tool to think about the dynamics, but I think we struggle to use it to answer interesting questions, so it's just not all that relevant today. The fact that it is independent of problem instance is a pretty large limitation, because GAs are great on some problems and terrible on some problems, so if your explanatory tool doesn't have "problem" as a variable in the model, you're obviously missing something really important. Specifically, what it really describes is the dynamics of the population over time, whether or not those dynamics are performing anything we'd describe as a useful search. It's similar to the idea of a hill-climber that thinks it's doing great because it's climbing the tiny hill that's nearby and completely missing the much higher peak over there. All you have is a model of how the climbing looks, and not a model of what climbing that particular peak means in the broader sense of how well you're doing on that optimization problem.

That said, you can kind of look at Holland's schema theorem as two things. It's (1) a qualitative statement that GAs work by recombining short pieces of solutions into longer components in a way that progressively improves overall fitness, and (2) a quantitative and precise inequality that puts bounds on the probabilities for the mechanisms that are responsible for that progressive improvement. The first part of that is pretty much a given to be true for any GA that'd we'd recognize as a GA. It's just the kind of statement that you squint a little and go, "Yeah, that seems obviously true I guess". The second part only works on the "canonical GA", because the computation of the probabilities assumes a specific structure and set of operators.

If you want a similar schema theorem for some custom representation and set of operators, there's no real alternative to just trying to do the same math Holland did. What does a "building block" look like in my non-binary GA? What is the probability that my crossover operator disrupts such a building block? What is the probability that it creates such a block? Same for the mutation operator. Coming up with those probabilities tends to be pretty hard to do for any complex representation, and if you do it successfully, you don't get a lot out of the effort (because that inequality is difficult to put to a pragmatic use).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .