Metaheuristics.jl

Metaheuristics.jl provides a suite of performance indicators to evaluate the quality of evolutionary optimization algorithms.

Important: Minimization Assumption All indicators in Metaheuristics.jl assume a minimization problem. If your problem is a maximization problem, you must transform it before using these indicators.

Available indicator categories include:

• Pareto Front Utilities: General utilities for Pareto fronts.
• Accuracy Indicators: gd (Generational Distance), gd_plus, igd (Inverted Generational Distance), and igd_plus to assess how close approximations are to the true Pareto front.
• Diversity/Distribution Indicators: spacing, covering ($C$-metric), and hypervolume.
• Distance/Hausdorff Indicators: deltap ($\Delta_p$) and epsilon_indicator ($\varepsilon$-indicator).

When solving the N-Queens problem, using a PermutationSpace(N) is more efficient than a binary matrix (BitArraySpace(N*N)). A permutation-based representation ensures that no two queens share the same row or column, significantly reducing the search space cardinality by eliminating horizontal and vertical attacks by design.

using Metaheuristics
N = 8
# Compare search space sizes
cardinality(BitArraySpace(N*N))
cardinality(PermutationSpace(N))

Algorithms marked with ✅ in the Batch Evaluation column support simultaneous evaluation of multiple solutions. This is useful for parallel computing (threads/distributed systems), GPU acceleration, or handling expensive function evaluations.

To enable this feature, set parallel_evaluation=true in the Options object.

# Example configuration (conceptual)
options = Options(parallel_evaluation=true)

GRASP is a metaheuristic that combines a construction phase with a local search phase. It involves using a greedy randomized constructor to build solutions and then refining them.

Key components include:

• Metaheuristics.GreedyRandomizedConstructor: The logic for constructing solutions.
• Metaheuristics.construct: The method used to build a solution.
• Metaheuristics.compute_cost: The method used to evaluate the cost of a solution.

BRKGA is a metaheuristic used for solving combinatorial optimization problems. It uses a biased random key representation to explore the search space.

Refer to the BRKGA documentation for specific implementation details and parameter tuning.

When the optimize function is called, the library follows a specific lifecycle consisting of three main stages:

1. Initialization: The initialize! function is called to create a State object. This typically involves generating an initial population based on the provided parameters and problem bounds.
2. Main optimization loop: The library enters a loop that continues as long as status.stop == false. In each iteration, it calls:
   • update_state!: To evolve the population or update parameters.
   • stop_criteria!: To check if the algorithm should terminate (e.g., based on iteration count or function evaluations).
3. Final Stage: Once the loop terminates, final_stage! is called to perform final cleanup, such as extracting the best solution from a population or handling infeasible solutions.