Constrained Novelty Search

Constrained Novelty Search #

Name #

Constrained Novelty Search (CNS)

Taxonomy #

Constrained Novelty Search is a technique that belongs to the field of Evolutionary Computation, specifically in the area of Diversity Maintenance Methods. It is closely related to Novelty Search and Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm.

  • Computational Intelligence
    • Biologically Inspired Computation
      • Evolutionary Computation
        • Evolutionary Algorithms
          • Genetic Algorithms
            • Diversity Maintenance Methods
              • Constrained Novelty Search

Strategy #

Constrained Novelty Search builds upon the principles of Novelty Search, which promotes exploration of the search space by rewarding solutions that exhibit novel behaviors rather than optimizing for a specific objective. CNS extends this concept by introducing constraints that must be satisfied while still encouraging novelty.

Balancing Novelty and Feasibility #

CNS maintains two separate populations: a feasible population and an infeasible population. The feasible population consists of solutions that satisfy all constraints, while the infeasible population contains solutions that violate at least one constraint. The algorithm promotes the evolution of both populations simultaneously, balancing the exploration of novel solutions with the need to satisfy constraints.

Measuring Novelty #

Novelty is measured by comparing the behavior of a solution to the behaviors of its nearest neighbors in the behavior space. The behavior space is typically defined by a set of behavior characterization functions that capture relevant aspects of a solution’s performance. Solutions that exhibit behaviors that are significantly different from their neighbors are considered novel and are assigned higher novelty scores.

Constraint Handling #

CNS handles constraints by using a constraint violation function that quantifies the degree to which a solution violates the constraints. Solutions with lower constraint violation values are preferred over those with higher violation values. The infeasible population allows the exploration of promising regions of the search space that may contain solutions that are close to satisfying the constraints.

Procedure #

Data Structures #

  • FeasiblePopulation: A population of solutions that satisfy all constraints.
  • InfeasiblePopulation: A population of solutions that violate at least one constraint.
  • BehaviorSpace: A space defined by behavior characterization functions that capture relevant aspects of a solution’s performance.
  • NoveltyArchive: An archive that stores previously encountered novel solutions.

Parameters #

  • PopulationSize: The size of the feasible and infeasible populations.
  • NoveltyThreshold: The threshold for determining if a solution is considered novel.
  • ConstraintTolerance: The tolerance level for constraint violations.
  • MaxGenerations: The maximum number of generations allowed before termination.

Steps #

  1. Initialize the FeasiblePopulation and InfeasiblePopulation with random solutions.
  2. Evaluate the constraint violations and behaviors of each solution in both populations.
  3. While the termination criteria are not met, repeat steps 4-10.
  4. Calculate the novelty score for each solution in both populations based on its behavior and the behaviors of its nearest neighbors in the BehaviorSpace.
  5. Select parents from the FeasiblePopulation based on their novelty scores.
  6. Apply genetic operators (e.g., crossover and mutation) to the selected parents to create offspring.
  7. Evaluate the constraint violations and behaviors of the offspring.
  8. Add the offspring that satisfy all constraints to the FeasiblePopulation and the offspring that violate any constraints to the InfeasiblePopulation.
  9. Update the NoveltyArchive with novel solutions from both populations.
  10. If the FeasiblePopulation reaches the desired size, remove the least novel solutions. If the InfeasiblePopulation reaches the desired size, remove the solutions with the highest constraint violations.
  11. Return the best solution found in the FeasiblePopulation.

Considerations #

Advantages #

  • Promotes exploration of the search space by encouraging novelty.
  • Allows the discovery of solutions in constrained optimization problems that might be difficult to find using objective-based approaches.
  • Maintains diversity in the population, reducing the risk of premature convergence.

Disadvantages #

  • The effectiveness of CNS heavily depends on the choice of behavior characterization functions and the definition of the behavior space.
  • The novelty measure may not always correlate with the quality of solutions, leading to the exploration of unproductive regions of the search space.
  • The computational overhead of calculating novelty scores and maintaining the novelty archive can be significant.

Heuristics #

Defining the Behavior Space #

  • Choose behavior characterization functions that capture relevant aspects of the problem domain and the desired solution characteristics.
  • Ensure that the behavior space is expressive enough to differentiate between solutions but not so complex that it hinders the identification of novel behaviors.

Setting the Novelty Threshold #

  • Start with a relatively high novelty threshold to encourage exploration in the early stages of the search.
  • Gradually decrease the novelty threshold as the search progresses to focus on refining promising solutions.

Managing the Novelty Archive #

  • Limit the size of the novelty archive to prevent it from growing too large and slowing down the search process.
  • Regularly update the novelty archive to include newly discovered novel solutions and remove outdated or less relevant solutions.

Balancing Feasible and Infeasible Populations #

  • Maintain a balance between the sizes of the feasible and infeasible populations to ensure that both novelty and constraint satisfaction are given adequate attention.
  • Adjust the population sizes dynamically based on the progress of the search and the difficulty of satisfying the constraints.

Handling Constraint Violations #

  • Use a suitable constraint handling technique, such as penalty functions or repair mechanisms, to guide the search towards feasible regions of the search space.
  • Adapt the constraint tolerance level based on the problem characteristics and the desired trade-off between exploration and exploitation.