Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values

• URL: http://arxiv.org/abs/2606.17731v1
• Date: Tue, 16 Jun 2026 09:47:39 GMT
• Title: Evolutionary Algorithms and Multi-Objective Minimum Spanning Trees with Limited Distinct Weight Values
• Abstract summary: Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective problems are rather limited.<n>We derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.
• Score: 6.387555054340123
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.

Related papers

• Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation [49.86232017439639]
  We introduce Multi-Output Augmented Behavioral Cloning (MA-BC)<n>MA-BC partitions divergent expert data while pooling state-action pairs where no behavior conflict is observed.<n>We establish a novel lower bound for multi-objective imitation learning, demonstrating that MA-BC is minimax optimal.
  arXiv  Detail & Related papers  (2026-05-12T11:49:08Z)
• 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)
• Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems [16.803653908913514]
  We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. We show that the MOEA/D algorithm, given an appropriate setting, finds all extreme points within expected fixed-objective time in the oracle model.
  arXiv  Detail & Related papers  (2023-06-06T05:13:29Z)
• On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem [0.0]
  We contribute to the efficient approximation of the $mathcalNP$-hard multi-objective minimum spanning tree problem (moMST) adopting evolutionary computation. We design several highly biased sub-graph-based mutation operators founded on the gained insights. Our results confirm that the sub-graph based operators beat baseline algorithms from the literature.
  arXiv  Detail & Related papers  (2023-05-31T22:35:17Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• A Pareto-optimal compositional energy-based model for sampling and optimization of protein sequences [55.25331349436895]
  Deep generative models have emerged as a popular machine learning-based approach for inverse problems in the life sciences. These problems often require sampling new designs that satisfy multiple properties of interest in addition to learning the data distribution.
  arXiv  Detail & Related papers  (2022-10-19T19:04:45Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  We study the scenario of components that are independent and normally distributed. We introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
  arXiv  Detail & Related papers  (2021-09-13T09:24:23Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
  OJZJ problem is a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark.<n>We prove that SEMO with probability one does not compute the full Pareto front, regardless of the runtime.<n>We also show the tighter bound $frac 32 e nk+1 pm o(nk+1)$, which might be the first runtime bound for an MOEA that is tight apart from lower-order terms.
  arXiv  Detail & Related papers  (2020-12-14T03:07:39Z)
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem [13.264683014487376]
  We study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization. We show that a simple $(mu+1)$-EA can effectively compute a diversified population of spanning trees of high quality.
  arXiv  Detail & Related papers  (2020-10-21T11:50:49Z)
• Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem [14.352521012951865]
  We introduce a new effective multi-objective model for the chance-constrained knapsack problem. Our experimental results show that this leads to significant performance improvements when using the approach in evolutionary multi-objective algorithms.
  arXiv  Detail & Related papers  (2020-04-07T08:46:51Z)

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.