[Paper] Benchmarking metaheuristic algorithms for the bi-objective redundancy allocation problem in repairable systems with multiple strategies

Source: arXiv - 2512.18343v1

Overview

The paper tackles a classic engineering challenge—how to allocate redundant components in a repairable system so that you spend the least money while keeping the system as available as possible. By framing the problem as a bi‑objective optimization and rigorously benchmarking 65 modern metaheuristic algorithms, the authors provide a practical yardstick for anyone who needs to design fault‑tolerant hardware, cloud services, or IoT deployments.

Key Contributions

• Comprehensive benchmark of 65 multi‑objective metaheuristics on six increasingly complex redundancy‑allocation instances.
• Introduction of Scaled Binomial Initialization (SBI), a simple yet powerful way to seed the search that consistently improves hypervolume scores.
• Systematic analysis of four redundancy strategies (cold, warm, hot, mixed) and their impact on cost vs. availability trade‑offs under different weight (budget) limits.
• Open‑source release of all code, data, and reference Pareto fronts (Zenodo DOI: 10.5281/zenodo.17981720) for reproducibility.
• Empirical evidence that budget size (number of objective‑function evaluations) dramatically reshapes algorithm rankings, warning against “one‑size‑fits‑all” performance claims.

Methodology

1. Problem formulation – The redundancy allocation problem (RAP) is modeled as a binary decision vector: each subsystem decides how many spare components to install and which standby strategy to use (cold, warm, hot, or mixed).
2. Availability evaluation – System availability is computed analytically using continuous‑time Markov chains, which capture failure/repair dynamics for each redundancy mode.
3. Benchmark design – Six case studies (small to large systems) are generated with controlled structural complexity. For each case, four weight limits (tight to loose) are imposed, yielding 24 test configurations.
4. Algorithm pool – 65 state‑of‑the‑art multi‑objective metaheuristics (NSGA‑II variants, MOEA/D, CMOPSO, NNIA, etc.) are run under two initialization regimes: random and SBI.
5. Evaluation budget – Every algorithm gets a fixed budget of 2 × 10⁶ objective‑function evaluations, split into multiple independent runs to enable statistical testing.
6. Performance metrics – The primary quality indicator is hypervolume (the volume of objective space dominated by the obtained Pareto front). A budget‑based performance profile tracks how quickly each algorithm approaches its best hypervolume.

Results & Findings

• Dominant strategies: Hot standby and mixed redundancy dominate the Pareto‑optimal fronts. Cold and warm standby appear rarely, especially under tight weight limits.
• Weight‑limit effect: When the allowable total weight is low, hot standby is preferred (it needs fewer spares). With looser limits, mixed redundancy—combining hot and cold spares—yields better cost‑availability balances.
• Impact of SBI: Adding SBI to the initial population boosts hypervolume by up to 30 % on average and, in several instances, the SBI seed is already near the final reference front. This can flip the ranking of algorithms (e.g., NNIA‑SBI outruns NSGA‑II without SBI).
• Budget sensitivity: Algorithms behave differently under varying budgets.
  • Tight budgets (few evaluations): NNIA‑SBI and CMOPSO‑SBI achieve the highest early hypervolume.
  • Medium/large budgets: NSGAIIARSBX‑SBI climbs to the top, delivering the best final fronts.
• Scalability: Larger RAP instances (more subsystems, more binary variables) need substantially more evaluations to reach comparable hypervolume levels, confirming that search effort must be planned ahead.

Practical Implications

• Design automation tools can embed SBI as a cheap pre‑processing step to give engineers a strong starting point, reducing the number of expensive simulation calls (Markov‑chain evaluations).
• Cloud‑native services that rely on redundant micro‑services can use the hot‑standby vs. mixed‑standby insights to decide whether to keep warm containers (higher cost) or spin up cold instances only when needed.
• Hardware manufacturers can apply the benchmark results to choose an optimizer that fits their computational budget—e.g., NNIA‑SBI for rapid prototyping, NSGAIIARSBX‑SBI for final design validation.
• The open dataset enables developers to test custom heuristics or machine‑learning‑based surrogate models without re‑implementing the Markov‑chain availability calculations.
• Budget‑aware optimization: The study highlights that reporting a single “best algorithm” is misleading; practitioners should match the optimizer to the available evaluation budget and problem size.

Limitations & Future Work

• The benchmark focuses on binary decision variables; extending to continuous sizing (e.g., component capacities) would broaden applicability.
• Availability is modeled with exponential failure/repair times; real‑world data often exhibit non‑exponential behavior, which could affect the Pareto fronts.
• Only hypervolume is used as the quality metric; incorporating diversity‑oriented measures could give a fuller picture of solution spread.
• Future research could explore adaptive budget allocation, where the algorithm dynamically decides how many evaluations to spend on exploration vs. exploitation based on intermediate hypervolume gains.
• Integrating surrogate modeling (e.g., Gaussian processes) to approximate the Markov‑chain evaluation could dramatically cut computational cost for very large systems.

Authors

• Mateusz Oszczypała
• David Ibehej
• Jakub Kudela

Paper Information

• arXiv ID: 2512.18343v1
• Categories: cs.NE
• Published: December 20, 2025
• PDF: Download PDF