Not Just for Archiving: Provable Benefits of Reusing the Archive in Evolutionary Multi-objective Optimization

• URL: http://arxiv.org/abs/2508.16993v1
• Date: Sat, 23 Aug 2025 11:25:19 GMT
• Title: Not Just for Archiving: Provable Benefits of Reusing the Archive in Evolutionary Multi-objective Optimization
• Authors: Shengjie Ren, Zimin Liang, Miqing Li, Chao Qian,
• Abstract summary: We analytically show that the archive can even further help MOEAs through reusing its solutions during the process of new solution generation.<n>Our analysis focuses on the well-established SMS-EMOA applied to the commonly studied OneJumpZeroJump problem.<n>We also show that reusing archive solutions can be better than using a large population size directly.
• Score: 19.269008655837535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary Algorithms (EAs) have become the most popular tool for solving widely-existed multi-objective optimization problems. In Multi-Objective EAs (MOEAs), there is increasing interest in using an archive to store non-dominated solutions generated during the search. This approach can 1) mitigate the effects of population oscillation, a common issue in many MOEAs, and 2) allow for the use of smaller, more practical population sizes. In this paper, we analytically show that the archive can even further help MOEAs through reusing its solutions during the process of new solution generation. We first prove that using a small population size alongside an archive (without incorporating archived solutions in the generation process) may fail on certain problems, as the population may remove previously discovered but promising solutions. We then prove that reusing archive solutions can overcome this limitation, resulting in at least a polynomial speedup on the expected running time. Our analysis focuses on the well-established SMS-EMOA algorithm applied to the commonly studied OneJumpZeroJump problem as well as one of its variants. We also show that reusing archive solutions can be better than using a large population size directly. Finally, we show that our theoretical findings can generally hold in practice by experiments on four well-known practical optimization problems -- multi-objective 0-1 Knapsack, TSP, QAP and NK-landscape problems -- with realistic settings.

Related papers

• Barbarians at the Gate: How AI is Upending Systems Research [58.95406995634148]
  We argue that systems research, long focused on designing and evaluating new performance-oriented algorithms, is particularly well-suited for AI-driven solution discovery.<n>We term this approach as AI-Driven Research for Systems ( ADRS), which iteratively generates, evaluates, and refines solutions.<n>Our results highlight both the disruptive potential and the urgent need to adapt systems research practices in the age of AI.
  arXiv  Detail & Related papers  (2025-10-07T17:49:24Z)
• \(X\)-evolve: Solution space evolution powered by large language models [16.586197761629744]
  We introduce (X)-evolve, a paradigm-shifting method that instead evolves solution spaces (X) (sets of individual solutions)<n>A score-based search algorithm then efficiently explores this parametrically defined space, guided by feedback from objective function scores.
  arXiv  Detail & Related papers  (2025-08-11T12:47:59Z)
• When to Truncate the Archive? On the Effect of the Truncation Frequency in Multi-Objective Optimisation [6.391724105255245]
  We show that, interestingly, truncating the archive once a new solution generated tends to be the best, whereas considering an unbounded archive is often the worst.<n>Our results highlight the importance of developing effective subset selection techniques.
  arXiv  Detail & Related papers  (2025-04-02T03:33:49Z)
• Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization [20.883780207120783]
  We show that using an archive can allow a small population and accelerate the search of SPU-based MOEAs substantially.<n>Specifically, we analyze the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II for solving a commonly studied bi-objective problem OneJumpZero.
  arXiv  Detail & Related papers  (2025-01-28T06:21:38Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Maintaining Diversity Provably Helps in Evolutionary Multimodal Optimization [20.621635722585502]
  We show that a simple method that considers diversity of solutions in the solution space can benefit the search in evolutionary algorithms (EAs) We prove that the proposed method, working with crossover, can help enhance the exploration, leading to multimodal or even exponential acceleration on the expected running time.
  arXiv  Detail & Related papers  (2024-06-04T17:52:14Z)
• An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms [22.123838452178585]
  We show for the first time, that using an archive can guarantee speed-ups for MOEAs. We prove that for two well-established MOEAs, using an archive brings a acceleration on the expected running time.
  arXiv  Detail & Related papers  (2024-06-04T08:59:16Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours.<n>We focus on the case of linear utility functions parametrised by weight vectors w.<n>We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.