MAP-Elites cell owners not protected during population eviction (regression from #150 fix)

[rethinkNow]

Description

The fix from #150 (commit 6ad0aa8) correctly added elite/non-elite separation in _enforce_population_limit(), prioritizing removal of non-cell-owning programs before cell owners. However, the subsequent rewrite in PR #154 (commit 6264c74) that added per-island feature maps did not carry over this protection.

Current behavior

_enforce_population_limit() (line 1678 in database.py) sorts all programs globally by fitness and removes the worst ones, regardless of whether they own a MAP-Elites cell:

sorted_programs = sorted(
    all_programs,
    key=lambda p: get_fitness_score(p.metrics, self.config.feature_dimensions),
)
for program in sorted_programs:
    if program.id not in protected_ids:
        programs_to_remove.append(program)

This means a cell owner with a low score (e.g., a diverse niche program) can be evicted before a homeless program with a higher score, defeating the diversity preservation purpose of MAP-Elites.

Expected behavior

Programs that own a MAP-Elites cell in any island should be prioritized for survival. Non-cell-owning (homeless) programs should be evicted first.

Suggested fix

Collect all cell-owning program IDs from island_feature_maps and prioritize removing non-owners first:

def _enforce_population_limit(self, exclude_program_id=None):
    if len(self.programs) <= self.config.population_size:
        return

    num_to_remove = len(self.programs) - self.config.population_size

    # Collect all cell-owning program IDs across all islands
    elite_ids = set()
    for island_map in self.island_feature_maps:
        elite_ids.update(island_map.values())

    protected_ids = {self.best_program_id, exclude_program_id} - {None}

    all_programs = list(self.programs.values())
    non_elite = sorted(
        [p for p in all_programs if p.id not in elite_ids and p.id not in protected_ids],
        key=lambda p: get_fitness_score(p.metrics, self.config.feature_dimensions),
    )
    elite = sorted(
        [p for p in all_programs if p.id in elite_ids and p.id not in protected_ids],
        key=lambda p: get_fitness_score(p.metrics, self.config.feature_dimensions),
    )

    # Remove non-elite first, then elite if still needed
    programs_to_remove = non_elite[:num_to_remove]
    if len(programs_to_remove) < num_to_remove:
        remaining = num_to_remove - len(programs_to_remove)
        programs_to_remove.extend(elite[:remaining])

    # ... rest of removal logic

Additional context

• The original fix in commit 6ad0aa8 (by @claude bot) correctly implemented this using feature_map_program_ids = set(self.feature_map.values())
• PR Fix map elites #154 rewrote database.py with per-island feature maps (self.island_feature_maps) but did not adapt the elite protection
• git merge-base --is-ancestor 6ad0aa8 HEAD confirms the fix commit is not in the current main

Additionally, when a cell owner is replaced within a cell (line 339), the old program is removed from self.islands but NOT from self.programs, creating zombie programs that consume population slots but can never be sampled for prompts.

Related: #150, #167