Feasible Infeasible Search for Highly Constrained Spaces

16 concepts20 papers1 proposal

When optimizing solutions in complex design spaces, mathematical or functional constraints often act as formidable walls. Consider generating a playable video game level: the map must have a continuous path from the start to the exit. If a generated level lacks this path, it is completely unplayable—an invalid solution.

In traditional evolutionary optimization, individuals that violate such hard constraints are either discarded immediately or heavily penalized. However, this approach creates a severe problem. In highly constrained landscapes, valid solutions are rare needles in a haystack of invalid configurations. Discarding infeasible individuals destroys valuable genetic material and isolates disconnected pockets of valid space, leaving the optimizer trapped in local optima.

To overcome this, a powerful paradigm has emerged: Feasible-Infeasible Dual-Population Search. Instead of forcing a single population to balance both validity and quality, this approach splits the evolutionary workload into two distinct, interacting populations.

The Dual-Population Architecture

The core mechanism of this strategy—frequently implemented as the Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm—is deceptively simple. The algorithm maintains two separate pools of candidate solutions:

  1. The Feasible Population: Contains individuals that satisfy all hard constraints. This population is evolved to maximize the actual objective function (e.g., visual appeal, mechanical complexity, or performance).
  2. The Infeasible Population: Contains individuals that violate one or more constraints. Crucially, this population completely ignores the final objective function; instead, it is evolved purely to minimize constraint violations.
                  [ Initial Population ]
                            |
                            v
               +------------+------------+
               |                         |
     Meets Constraints?        Fails Constraints?
               |                         |
               v                         v
     [ Feasible Population ]   [ Infeasible Population ]
               |                         |
     Optimize Objective        Minimize Violations
               |                         |
               +------------+------------+
                            |
                            v
                Boundary Crossing & Selection

As noted in a comprehensive survey by Jing Liang et al. in A Survey on Evolutionary Constrained Multiobjective Optimization, this architecture decouples the search for validity from the search for optimality. By maintaining both groups, the system prevents the optimization criteria from drowning out the search for basic functionality, and vice versa.

Infeasible Solutions as Evolutionary Stepping Stones

Why does keeping broken solutions around make the search more efficient? The answer lies in how landscapes are structured. An infeasible individual is often only a single mutation away from becoming an exceptionally high-quality feasible individual.

Imagine a game level that is beautifully designed but missing a single door connecting the key to the exit. Under a traditional penalty system, this level would be given a terrible fitness score and discarded. In a dual-population framework, however, it is recognized as highly valuable by the infeasible population because its constraint violation is minimal.

As Antonios Liapis et al. demonstrated in Sentient Sketchbook: Computer-aided game level authoring, the infeasible population acts as an evolutionary bridge. By optimizing purely for constraint satisfaction, invalid individuals are gradually pushed toward the boundary of feasibility. The moment a mutation fixes the broken constraint (e.g., adding the missing door), the individual crosses the threshold and is transferred into the feasible population.

This mechanism allows the algorithm to discover valid designs that are completely unreachable through local mutations of existing feasible individuals. The infeasible population acts as a scout, traversing invalid territory to find entry points into isolated pockets of the feasible region that a single-population approach would miss.

Pushing and Pulling the Search Space

The interaction between these two populations creates a dynamic "push and pull" effect along the feasibility boundary. This behavior is explicitly leveraged by Zhun Fan et al. in Push and Pull Search Embedded in an M2M Framework for Solving Constrained Multi-objective Optimization Problems. Their framework demonstrates that first pushing a population freely toward an unconstrained Pareto front, and then pulling solutions back into the feasible region, allows the optimizer to navigate around large, mathematically isolated infeasible barriers.

By operating on the boundary of the valid search space, the dual-population strategy preserves genetic diversity. As explored by Antonios Liapis et al. in Transforming Exploratory Creativity with DeLeNoX,, this boundary-riding behavior is essential for exploratory creativity, enabling algorithms to break through representational biases and discover complex, novel structures.

Versatility Across Domains

While the dual-population framework is highly abstract, its ability to handle strict constraints has made it a cornerstone in Procedural Content Generation (PCG) and complex engineering design.

Procedural Content Generation in Games

Game design is defined by strict functional requirements. A level must be navigable; a spaceship must have symmetrical physics. Early work by Julian Togelius et al. in Optimizing Visual Properties of Game Content Through Neuroevolution used dual populations to generate 2D spaceships, ensuring they met functional physics constraints while optimizing for human aesthetic preferences.

Similarly, the framework has been applied to spatial layout problems. Julian Togelius et al. in Towards a Generic Method of Evaluating Game Levels separated candidate maps into feasible and infeasible groups based on path connectivity, allowing the feasible group to focus entirely on high-level design metrics like area control and exploration balance. In Mario Level Generation From Mechanics Using Scene Stitching, Michael Cerny Green et al. used FI-2Pop to stitch together mini-scenes, ensuring 100% playability while matching the mechanical sequence of a target playtrace.

Quality-Diversity Algorithms

The strategy integrates naturally with Quality-Diversity (QD) algorithms like MAP-Elites, which aim to find a diverse library of high-performing solutions. In Procedural Content Generation through Quality Diversity, Ahmed Khalifa 0001 et al. detailed how maintaining diversity within both the valid and invalid archives ensures that the final output collection is both varied and functional. This approach has been successfully deployed in mixed-initiative design tools, such as the dungeon generation frameworks presented by Alberto Alvarez et al. in Empowering Quality Diversity in Dungeon Design with Interactive Constrained MAP-Elites and Interactive Constrained MAP-Elites Analysis and Evaluation of the Expressiveness of the Feature Dimensions, as well as bullet-hell level generation in Talakat: Bullet Hell Generation through Constrained Map-Elites by Ahmed Khalifa 0001 et al.

Beyond Games: Decoupled Optimization

The underlying philosophy of separating constraint mapping from objective optimization extends well beyond evolutionary algorithms. For instance, in materials science, Danial Khatamsaz et al. in Bayesian optimization with active learning of design constraints using an entropy-based approach utilized a two-loop architecture to navigate the combinatorial explosion of alloy design. One loop maps the boundaries of feasible regions while the other optimizes performance within them, demonstrating that decoupling constraint learning from objective optimization prevents algorithms from wasting resources on unfeasible designs.

Conclusion

Dual-population constraint handling works because it treats invalid solutions not as failures to be purged, but as stepping stones to be cultivated. By maintaining a dedicated population that minimizes constraint violations, the search space remains connected, allowing the optimizer to gracefully skirt along the boundaries of feasibility and discover optimal solutions that single-population methods would discard out of hand.

Key Foundational Work

Effective heuristic methods for finding non-optimal solutions of interest in constrained optimization models (2010) — contributed 1 concept elements to this direction.
Optimizing Visual Properties of Game Content Through Neuroevolution (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dual_population_constraint_handling_2afb1fdc,
  title = {dual-population constraint handling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-population-constraint-handling/rdr_2afb1fdca4b14c998b2e53e451d55528},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_dual_population_constraint_handling_2afb1fdc_v1,
  title = {dual-population constraint handling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-population-constraint-handling/rdr_2afb1fdca4b14c998b2e53e451d55528/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake