Archive (in MOEAs)

The archive's core function is to preserve non-dominated solutions found throughout the evolutionary run. It acts as a historical memory, preventing the loss of high-quality solutions that may be displaced in the main population due to genetic drift or selection pressure. This ensures the final reported result is the best set of trade-offs discovered, not just the final generation's population.

• Mechanism: Solutions are added if they are non-dominated with respect to the current archive contents.
• Example: In a financial portfolio optimization (maximize return, minimize risk), the archive stores all efficient frontier portfolios found from generation 1 to N.

Beyond storing elite solutions, a sophisticated archive actively manages solution diversity across the objective space. This prevents clustering and ensures a well-distributed approximation of the entire Pareto front.

• Techniques: Use metrics like crowding distance or nearest-neighbor distance to prune overly similar solutions.
• Benefit: Provides decision-makers with a broad spectrum of viable trade-offs. For instance, in engineering design, it yields options ranging from ultra-efficient to ultra-robust configurations.

The archive serves as a convergence metric for the MOEA. By tracking how the archive's quality improves (or stabilizes) over generations, algorithms can implement intelligent stopping criteria.

• Metrics Used: The hypervolume indicator of the archive is a common measure; when its improvement per generation falls below a threshold, the search can terminate.
• Practical Impact: This prevents unnecessary computational expense by halting the search once the Pareto front approximation has sufficiently converged.

The final archive is the direct output presented to the human decision-maker or downstream system. It provides a curated set of Pareto-optimal candidates for final selection based on higher-level business rules or preferences not encoded in the algorithm.

• Use Case: A logistics planner uses an archive of routing solutions (minimize cost, minimize time, minimize CO2) and selects the final plan based on current weather and driver availability.
• Integration: Archives can interface with Multi-Criteria Decision Making (MCDM) tools for post-hoc analysis.

In research and development, the final state of an archive is used for the quantitative evaluation and comparison of different MOEAs. Performance indicators are calculated on the archive's contents.

• Key Indicators: Hypervolume, Inverted Generational Distance (IGD), and Spread are all computed using the archive as the algorithm's output set.
• Standardization: This allows for fair comparison between algorithms like NSGA-II, SPEA2, and MOEA/D on benchmark problems.

Archives are implemented with different strategies, each with trade-offs in complexity and performance.

• Unbounded Archive: Stores every non-dominated solution found. Can grow large and slow down dominance checks.
• Bounded (Fixed-Size) Archive: Uses a density measure (e.g., crowding distance) to maintain a fixed number of the most diverse, high-quality solutions. Common in modern MOEAs.
• Adaptive Archives: Dynamically adjust size or pruning criteria based on the shape of the discovered front.
• Elitist Integration: In algorithms like NSGA-II, the archive concept is often implicit, with elitism achieved by combining parent and offspring populations before non-dominated sorting.

The Pareto front is the set of all Pareto optimal solutions plotted in the objective space. It represents the optimal trade-off surface where improving one objective necessitates worsening another. An MOEA's archive aims to approximate this front.

• Visual Representation: A curve or surface in 2D or 3D objective space.
• Goal of MOEAs: To find a diverse and convergent approximation of the true Pareto front.

Non-dominated sorting is a ranking procedure that classifies a population of solutions into successive Pareto fronts (Front 1, Front 2, etc.). It is a core component of algorithms like NSGA-II for managing archives and selection pressure.

• Front 1: Contains all solutions not dominated by any other in the population.
• Subsequent Fronts: Contain solutions only dominated by those in previous fronts.
• Archive Role: Often stores only the highest-ranked (non-dominated) fronts.

Crowding distance is a density estimation metric used to promote diversity within an archive or population. It measures the average distance between a solution and its nearest neighbors along each objective axis.

• Calculation: Sum of side lengths of the cuboid formed by a solution's neighbors.
• Archive Maintenance: When pruning an archive to a fixed size, solutions with a larger crowding distance (in less crowded regions) are preferentially retained.
• Prevents Clustering: Ensures the archive spans the entire Pareto front approximation.

The hypervolume indicator (or S-metric) is a Pareto-compliant performance metric that measures the volume of objective space dominated by an archive's solutions, bounded by a predefined reference point. It simultaneously assesses convergence and diversity.

• Single Metric: A larger hypervolume indicates a better archive.
• Reference Point: A crucial, often user-defined, point worse than all solutions.
• Archive Quality: Can be used to directly guide the search or to compare the performance of different MOEAs.

Elitism in MOEAs refers to the strategy of preserving the best-performing solutions (elites) from one generation to the next. The archive is the primary mechanism for implementing elitism in multi-objective optimization.

• Prevents Regression: Ensures Pareto optimal solutions are not lost due to genetic operators like crossover or mutation.
• Accelerates Convergence: By continually refining a set of high-quality candidates.
• Common Practice: The archive is often merged with the current population to create the parent pool for the next generation.

An external archive is a separate, often unbounded, storage structure maintained alongside the main evolving population. It is a specific implementation of the archive concept, distinct from a steady-state archive that replaces the population.

• Separation of Concerns: The population explores the search space, while the archive records historical bests.
• Update Rules: Governed by Pareto dominance checks; new solutions enter only if they are non-dominated with respect to the archive's contents.
• Final Output: At algorithm termination, the external archive is presented as the solution set.