Exploration-Exploitation-Evaluation (EEE): A Framework for Metaheuristic Algorithms in Combinatorial Optimization

• URL: http://arxiv.org/abs/2510.05027v1
• Date: Mon, 06 Oct 2025 17:04:46 GMT
• Title: Exploration-Exploitation-Evaluation (EEE): A Framework for Metaheuristic Algorithms in Combinatorial Optimization
• Authors: Ethan Davis,
• Abstract summary: We introduce a framework for applying metaheuristic algorithms, such as ant colony optimization (ACO), to optimization problems like the traveling salesman problem (TSP)<n>We calculate that the probability of ACO finding the global optimum is approximately 1/40 in a single run and improves to 1/5 when aggregated over ten runs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a framework for applying metaheuristic algorithms, such as ant colony optimization (ACO), to combinatorial optimization problems (COPs) like the traveling salesman problem (TSP). The framework consists of three sequential stages: broad exploration of the parameter space, exploitation of top-performing parameters, and uncertainty quantification (UQ) to assess the reliability of results. As a case study, we apply ACO to the TSPLIB berlin52 dataset, which has a known optimal tour length of 7542. Using our framework, we calculate that the probability of ACO finding the global optimum is approximately 1/40 in a single run and improves to 1/5 when aggregated over ten runs.

Related papers

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Local Entropy Search over Descent Sequences for Bayesian Optimization [48.7994415668802]
  A practical alternative is to iteratively refine the neighborhood of an initial design using local optimization methods such as gradient descent.<n>We propose local entropy search (LES), a Bayesian optimization paradigm that explicitly targets the solutions reachable by the descent sequences.
  arXiv  Detail & Related papers  (2025-11-24T15:52:17Z)
• An Efficient and Almost Optimal Solver for the Joint Routing-Assignment Problem via Partial JRA and Large-α Optimization [0.0]
  The Joint Routing-Assignment (JRA) optimization problem determines the assignment of items to placeholders and a Hamiltonian cycle that visits each node pair exactly once.<n>Previous studies introduced an exact mixed-integer programming (MIP) solver, along with datasets and a Gurobi implementation.<n>This work presents a novel and more efficient approach that attains high-accuracy, near-optimal solutions for large-scale JRA problems.
  arXiv  Detail & Related papers  (2025-11-07T09:54:46Z)
• Hierarchical Quantum Optimization for Large-Scale Vehicle Routing: A Multi-Angle QAOA Approach with Clustered Decomposition [0.5505634045241289]
  We present a quantum optimization methodology for solving large-scale Vehicle Routing Problem (VRP)<n>The approach decomposes 13-locations based VRP problems through clustering into three balanced clusters each, then applies standard QAOA for intra-cluster Open Loop Traveling Salesman Problem (OTSP) and MA-QAOA for inter-cluster VRP routing.
  arXiv  Detail & Related papers  (2025-11-01T11:19:56Z)
• Evaluating the effectiveness, reliability and efficiency of a multi-objective sequential optimization approach for building performance design [0.8168080812068832]
  This paper proposes and evaluates a sequential approach for multi-objective design optimization of building geometry, fabric, HVAC system and controls for building performance.<n>The performance of the sequential approach is benchmarked against a full factorial search and compared to the NSGA-II algorithm.<n>This research indicates that a sequential optimization approach is a highly efficient and robust alternative to the standard NSGA-II algorithm.
  arXiv  Detail & Related papers  (2024-12-13T08:00:00Z)
• SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity [5.046146134689904]
  We show that there is no gap in complexity analysis between bilevel and single-level optimization when implementing SPABA. We propose several other bi-loop or nested bi-level algorithms to improve the state of complexity analysis.
  arXiv  Detail & Related papers  (2024-05-29T05:36:03Z)
• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  Generative Flow Ant Colony Sampler (GFACS) is a novel meta-heuristic method that hierarchically combines amortized inference and parallel search.<n>Our method first leverages Generative Flow Networks (GFlowNets) to amortize a emphmulti-modal prior distribution over solution space.<n>This prior is updated via parallel search in the spirit of Ant Colony Optimization (ACO) leading to the posterior distribution that generates near-optimal solutions.
  arXiv  Detail & Related papers  (2024-03-11T16:26:06Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm called ALEXR.<n>We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions.<n> Experimental results on GDRO and partial Area Under the ROC Curve for cFCCO demonstrate the promising performance of our algorithm.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• An Efficient Batch Constrained Bayesian Optimization Approach for Analog Circuit Synthesis via Multi-objective Acquisition Ensemble [11.64233949999656]
  We propose an efficient parallelizable Bayesian optimization algorithm via Multi-objective ACquisition function Ensemble (MACE) Our proposed algorithm can reduce the overall simulation time by up to 74 times compared to differential evolution (DE) for the unconstrained optimization problem when the batch size is 15. For the constrained optimization problem, our proposed algorithm can speed up the optimization process by up to 15 times compared to the weighted expected improvement based Bayesian optimization (WEIBO) approach, when the batch size is 15.
  arXiv  Detail & Related papers  (2021-06-28T13:21:28Z)
• Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
  We present a new algorithmic framework for grouped variable selection that is based on discrete mathematical optimization. Our methodology covers both high-dimensional linear regression and non- additive modeling with sparse programming. Our exact algorithm is based on a standalone branch-and-bound (BnB) framework, which can solve the associated mixed integer (MIP) problem to certified optimality.
  arXiv  Detail & Related papers  (2021-04-14T19:21:59Z)
• Enhanced Framework of Quantum Approximate Optimization Algorithm and Its Parameter Setting Strategy [4.082216579462797]
  An enhanced framework of quantum approximate optimization algorithm (QAOA) is introduced and the parameter setting strategies are analyzed. The enhanced QAOA is as effective as the QAOA but exhibits greater computing power and flexibility. The optimal solution can be found with a high probability in much less than $O(sqrtN)$
  arXiv  Detail & Related papers  (2020-12-16T14:40:56Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)

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.