The Hidden Impact: How Fitness Calculation Makes or Breaks AI Evolution

Hey there! Let’s chat about something pretty fascinating in the world of Artificial Intelligence, specifically about algorithms that mimic evolution to solve problems. We call these Evolutionary Algorithms, and when they get competitive, like a digital survival of the fittest, they’re known as Competitive Co-evolutionary Algorithms, or CoEAs for short.

What’s the Big Deal with CoEAs?

Unlike your standard optimization algorithm that just looks at a single solution and says, “Yep, that’s good” or “Nope, that’s bad” based on a fixed rule, CoEAs are a bit more social. They have populations of solutions, and these solutions figure out how good they are by interacting with *other* solutions, usually from a competing population. Think predator vs. prey, or two players in a game. The outcome of these interactions tells a solution how “fit” it is. This makes CoEAs super useful for problems that are naturally interactive, like training game-playing AI or designing complex systems where components compete.

But, and it’s a big but, these competitive dynamics can get messy. Researchers have noticed some weird, “pathological” behaviors. We’re talking about things like:

• Evolutionary forgetting: Good solutions getting lost because the current opponents aren’t tough enough to keep them selected.
• Cyclic dynamics: The algorithm just going in circles in the search space, making progress but then losing it.
• Disengagement: One side gets so dominant the other can’t put up a fight, and the whole process grinds to a halt.

These issues are well-known, but honestly, understanding *why* they happen is tricky because the population dynamics are complex. And without truly understanding the cause, fixing them is like playing whack-a-mole.

The Puzzle of Fitness Aggregation

One of the core challenges in CoEAs is figuring out how to take all those interaction outcomes (the “payoffs”) and boil them down into a single “fitness” score for each solution. You could average them, take the best one, take the worst one, use the median, or get fancy with more complex statistics. Lots of methods have been proposed over the years.

Here’s the kicker: nobody really knows which method is best, or when a particular method might actually *hurt* the optimization process. Most of the studies so far have just been empirical – trying something out and seeing if it works, without a deep theoretical understanding of *why*. Some folks even suspect that using *any* aggregation method might be part of the problem!

I’ve always felt that to really get a handle on CoEAs and their quirky dynamics, we need to dig in with rigorous analysis. That’s what this work is all about – taking a step towards that goal by looking closely at two common fitness aggregation methods using runtime analysis.

Introducing the Bilinear Problem

The study zeroes in on a specific type of problem called the Bilinear problem. Why Bilinear? Well, it’s a classic type of Maximin optimization problem (where one player tries to maximize their outcome assuming the other player is trying to minimize it). It’s thought to have a structure similar to problems in hot areas like training Generative Adversarial Networks (GANs). Plus, it’s a tough nut to crack because it has “intransitive” properties – like in rock-paper-scissors, there’s no single best strategy, just cycles. Continuous versions of this problem are known to cause cyclic behavior in other algorithms.

For the theoretical part, the researchers looked at a simplified version of Bilinear with an infinite discrete search space (think integer numbers, positive and negative). This allows for a cleaner analysis of the algorithm’s movement without hitting boundaries.

The Bilinear function basically has a saddle point, which is the optimal solution or “Nash equilibrium.” The search space can be divided into four quadrants relative to this optimal point. Where a solution lies in these quadrants turns out to be super important for how the fitness methods behave.

The (1, Lambda) CoEA and Geometric Mutation

The specific algorithm studied is a simple one called the (1, Lambda) CoEA. It’s like a minimalist evolutionary process:

• You start with one “parent” solution for each competing population (say, population X and population Y).
• In each generation, each parent creates Lambda (λ) “offspring” through mutation. So, you get λ offspring for X and λ for Y.
• Each offspring from population X interacts with *all* offspring from population Y, and vice versa.
• Based on the outcomes of these interactions, a fitness value is assigned to each offspring.
• The best offspring from population X becomes the new parent for X, and the best offspring from Y becomes the new parent for Y.

The mutation operator used in the theoretical analysis is called “geometric mutation.” Basically, it takes the parent’s value and adds or subtracts a random number drawn from a geometric distribution. This means larger jumps are less likely, but possible.

Now, let’s look at those two fitness aggregation methods they compared:

Method 1: Averaging Interactions (f_avg)

With f_avg, an offspring’s fitness is the average payoff it gets from interacting with *all* the offspring in the competing population. Seems fair, right? Average performance should give you a good idea of how good a solution is overall.

But here’s the surprising theoretical finding: When using f_avg on the Bilinear problem, the (1, Lambda) CoEA is incredibly inefficient. The analysis shows it has an *infinite expected runtime* to find the optimal solution!

Why does this happen? The algorithm *does* exhibit cyclic behavior, which is expected on this kind of problem. However, the analysis revealed that in generations where the current parent solutions are near the boundaries between the quadrants of the search space, the f_avg method tends to assign the highest fitness to offspring that are actually *farther away* from the optimum. Even though in many generations the distance might stay the same or even slightly decrease, these “bad” steps near the quadrant boundaries, though perhaps rare individually, happen often enough over time to cause the algorithm to drift away from the optimum in expectation. It gets stuck in cycles that don’t converge.

Method 2: Worst Interaction (f_wrs)

With f_wrs, an offspring’s fitness is determined by the *worst* payoff it gets from interacting with any single offspring in the competing population. This is a much more risk-averse approach. A solution is only considered good if it can perform reasonably well even against the toughest opponent it faced in that generation’s sample.

In sharp contrast to f_avg, the theoretical analysis showed that using f_wrs on the Bilinear problem makes the (1, Lambda) CoEA efficient! It finds a solution near the optimum in polynomial time (meaning the time it takes grows reasonably with the problem size, not exponentially).

The algorithm still shows cyclic behavior, but the key difference lies again in those critical generations near the quadrant boundaries. The f_wrs method, by focusing on the worst interaction, tends to favor offspring that are *closer* to the optimal boundaries during these transitions. This slight push towards the optimum during quadrant changes, even if the distance stays stable within a quadrant, causes the algorithm to make overall progress towards the optimal solution over time.

It’s a fascinating dichotomy: one method, seemingly reasonable, leads to infinite runtime, while the other, focusing on the worst case, leads to efficiency. It highlights how the specific way you calculate fitness can dramatically alter the algorithm’s fundamental dynamics and performance.

Experimental Validation Across Search Spaces

The theoretical analysis was done on an infinite integer search space for simplicity. But do these findings hold up in other settings? The researchers ran experiments on Bilinear problems defined over different search spaces:

• Integers (like the theory)
• Real numbers
• Binary strings (like in many real-world genetic algorithms)

The experimental results strongly supported the theoretical findings. With f_avg, the runtime “exploded” even for relatively small problems, with many runs failing to find the optimum within a huge time limit. This confirms the inefficiency seen in the theory.

With f_wrs, the algorithms were much more efficient across all tested search spaces. The runtime seemed to grow much slower, aligning with the polynomial time predicted by the theory. It seems the core insight about how these fitness measures handle the problem’s structure translates well beyond the specific theoretical setup.

Wrapping It Up

So, what’s the takeaway? Choosing how to aggregate interaction outcomes into a fitness score in Competitive Co-evolutionary Algorithms isn’t just a minor detail; it can be the difference between an algorithm that never finds the solution and one that does so efficiently.

This study provides rigorous evidence that for problems like the Bilinear problem, using the worst interaction as fitness is significantly better than using the average. The key insight seems to be how these methods influence the algorithm’s movement when it’s near critical points in the search space, like the boundaries between quadrants around the optimum.

This work is a great step towards a deeper, theoretical understanding of CoEAs and their dynamics. It suggests that when designing CoEAs for interactive problems, we need to be really careful about how we define fitness, perhaps focusing on methods that encourage movement towards optimal boundaries during cyclic phases.

Of course, this study focused on a specific problem class. An open question is whether these findings apply to other types of intransitive problems or how other fitness measures might behave. But for now, we have a solid piece of the puzzle showing just how much fitness calculation matters in the complex dance of co-evolution.

Source: Springer