Overview
Course project for Evolutionary Computing at Vrije Universiteit Amsterdam (M.Sc. AI). Beating multiple enemies in a 2D platformer can be framed as a Constrained Multi-Objective Optimization Problem (CMOOP). This study compares two fitness evaluation strategies inside the Island Model for neuroevolution of game-playing controllers in the EvoMan framework.
The optimization problem
EvoMan exposes 20 game-state sensors as input to a controller, and the controller outputs 5 actions (jump, shoot, move left/right, release). We use a single hidden layer of 10 neurons, giving 265 weighted connections per individual, and those weights are the genotype.
Per-game fitness:
f = γ * (100 - e_e) + (1 - γ) * (e_p) - log(t)
with γ = 0.9 (prioritise damaging the enemy), e_e = enemy energy, e_p = player energy, t = game duration. Total gain across enemies is the generalisation metric.
Two algorithms compared
Traditional Island Model. 5 islands, 50 individuals each (population 250), circular migration topology, tournament selection, line recombination crossover with α ∈ [-0.25, 1.25] (the wider range prevents weights from collapsing toward zero). Per-weight Gaussian mutation, 30 generations.
Fitness-Sharing CMOOP. Same Island Model topology, different fitness adjustment. Each individual is assigned a beaten vector v_b, a binary vector indicating which enemies it defeated. Fitness is then adjusted by similarity in beaten-vector space, so individuals beating the same set of enemies reduce each other's fitness. The hypothesis: niches form around enemy subsets and produce more efficient offspring against those enemies, instead of generic mediocre controllers.
Findings
The new fitness-sharing method did not generalise better than the baseline Island Model across the full enemy set. Both methods produced controllers that beat the training subset; neither generalised significantly to the held-out enemies.
What did surface from the experiments: a candidate fitness function that used kill count rather than fitness magnitude looked promising in preliminary runs. It wasn't tested as the primary method but is the obvious next iteration. The Island Model's headline strength remains diversity maintenance through parallel isolated evolution, and that part works. The fitness function is where this kind of work lives or dies, and we identified one worth following up.
This is reported as a negative result with a useful finding inside it, which is what the field generally prefers over an oversold positive.
Stack
Python, NumPy, EvoMan framework, Island Model evolutionary algorithm, custom fitness-sharing implementation.
