In many optimization problems, the "perfect" solution is often separated from the starting point by a vast desert of invalidity. Whether designing a Super Mario level that must be playable or engineering a UAV flight plan that avoids threats, algorithms frequently get stuck. Traditional methods often fail because they treat constraints as walls, preventing the search from "jumping over" infeasible regions to find better solutions on the other side.
The research direction emerging from these papers—often referred to as the Feasible-Infeasible Two-Population (FI-2Pop) approach—solves this by maintaining two separate, co-evolving populations: one that follows the rules and one that is allowed to break them.
The Problem of the Infeasible Barrier
In constrained optimization, we care about two things: feasibility (does it work?) and optimality (how good is it?). Standard evolutionary algorithms typically penalize "illegal" solutions. However, as Jing Liang and Ke Li point out, the global optimum often lies right on the edge of a constraint boundary or is hidden behind a "bridge" of infeasible space.
If an algorithm only keeps feasible individuals, it becomes blind to shortcuts. It might get trapped in a mediocre "feasible island," unable to cross a "sea" of invalidity to reach a much better continent.
Decoupling Search via Two Populations
The core mechanism, pioneered in the context of game design by researchers like Antonios Liapis, Georgios N. Yannakakis, and Julian Togelius, involves splitting the search into two archives:
- The Feasible Population: This group contains individuals that meet all hard constraints (e.g., a map where the exit is reachable). They are evolved to maximize the actual objective, such as visual appeal or fun.
- The Infeasible Population: This group contains individuals that fail at least one constraint. Crucially, they are not evolved to be "good"; they are evolved to be less wrong. Their "fitness" is simply how close they are to becoming feasible.
As Iman Rahimi and Efrén Mezura‐Montes argue, these infeasible individuals act as "scouts." They explore the forbidden zones of the search space. When an infeasible scout accidentally stumbles into feasibility, it is moved into the feasible population, often bringing high-quality genetic material from a region the feasible population could never have reached on its own.
Why It Works: Diversity and Guidance
This dual-track approach provides two main benefits:
- Diversity Maintenance: By keeping a population that ignores the main objective and only cares about meeting constraints, the algorithm preserves a wide variety of structural "blueprints." This prevents the "premature convergence" described by Wang Yafei, where an algorithm settles for a boring but safe solution too early.
- Navigating Narrow Passages: In complex problems, the "feasible region" might be a tiny, winding path. Shuang Li and Ming Yang demonstrate that an unconstrained population provides a "directional pull," guiding the search toward the Pareto front even when the algorithm doesn't know exactly how much a constraint is being violated.
Applications in Co-Creation and Design
This mechanism is particularly powerful in Mixed-Initiative Design. In tools like Interactive Constrained MAP-Elites, the AI uses this two-population approach to handle the "messiness" of human input. When a designer makes a manual change that breaks a level's logic, the infeasible population works in the background to "repair" the design, finding the shortest path back to a functional state while preserving the designer's creative intent.
By treating "illegal" solutions as valuable stepping stones rather than failures, dual-population strategies allow AI to navigate the complex trade-offs between what is possible and what is optimal.