Discovering new robust local search algorithms with neuro-evolution

• URL: http://arxiv.org/abs/2501.04747v1
• Date: Wed, 08 Jan 2025 10:31:16 GMT
• Title: Discovering new robust local search algorithms with neuro-evolution
• Authors: Mohamed Salim Amri Sakhri, Adrien Goëffon, Olivier Goudet, Frédéric Saubion, Chaïmaâ Touhami,
• Abstract summary: This paper explores a novel approach aimed at overcoming existing challenges in the realm of local search algorithms. Our aim is to improve the decision process that takes place within a local search algorithm so as to make the best possible transitions in the neighborhood at each iteration. This approach offers a promising avenue for the emergence of new local search algorithms and the improvement of their problem-solving capabilities for black-box problems.
• Score: 0.9786690381850356
• License:
• Abstract: This paper explores a novel approach aimed at overcoming existing challenges in the realm of local search algorithms. Our aim is to improve the decision process that takes place within a local search algorithm so as to make the best possible transitions in the neighborhood at each iteration. To improve this process, we propose to use a neural network that has the same input information as conventional local search algorithms. In this paper, which is an extension of the work [Goudet et al. 2024] presented at EvoCOP2024, we investigate different ways of representing this information so as to make the algorithm as efficient as possible but also robust to monotonic transformations of the problem objective function. To assess the efficiency of this approach, we develop an experimental setup centered around NK landscape problems, offering the flexibility to adjust problem size and ruggedness. This approach offers a promising avenue for the emergence of new local search algorithms and the improvement of their problem-solving capabilities for black-box problems.

Related papers

• Resolving the Exploration-Exploitation Dilemma in Evolutionary Algorithms: A Novel Human-Centered Framework [0.0]
  A new human-centered framework is proposed to resolve the so-called exploration-exploitation dilemma. Unlike the traditional approach, the search process will not be compromised of a single-phase. We demonstrate its effectiveness on 14 well-known benchmark problems in unconstrained optimization.
  arXiv  Detail & Related papers  (2025-01-04T01:06:46Z)
• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  We introduce OptVQ, a novel vector quantization method that employs the Sinkhorn algorithm to optimize the optimal transport problem. Our experiments on image reconstruction tasks demonstrate that OptVQ achieves 100% codebook utilization and surpasses current state-of-the-art VQNs in reconstruction quality.
  arXiv  Detail & Related papers  (2024-12-19T18:58:14Z)
• Evolutionary Algorithm with Detection Region Method for Constrained Multi-Objective Problems with Binary Constraints [9.764702512419946]
  This paper proposes a novel algorithm called DRMCMO based on the detection region method. In DRMCMO, detection regions dynamic monitor feasible solutions to enhance convergence, helping the population escape local optima. We have modified three existing test suites to serve as benchmark test problems for CMOPs with binary constraints.
  arXiv  Detail & Related papers  (2024-11-13T08:39:04Z)
• Enhancing CNN Classification with Lamarckian Memetic Algorithms and Local Search [0.0]
  We propose a novel approach integrating a two-stage training technique with population-based optimization algorithms incorporating local search capabilities. Our experiments demonstrate that the proposed method outperforms state-of-the-art gradient-based techniques.
  arXiv  Detail & Related papers  (2024-10-26T17:31:15Z)
• Deep Reinforcement Learning for Online Optimal Execution Strategies [49.1574468325115]
  This paper tackles the challenge of learning non-Markovian optimal execution strategies in dynamic financial markets. We introduce a novel actor-critic algorithm based on Deep Deterministic Policy Gradient (DDPG) We show that our algorithm successfully approximates the optimal execution strategy.
  arXiv  Detail & Related papers  (2024-10-17T12:38:08Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions [9.89901717499058]
  Local search is a basic algorithm and is widely used for various optimization problems. We provide approximation guarantees of standard local search algorithms under various constraints in terms of localizability. The main application of our framework is sparse optimization, for which we show that restricted strong concavity and restricted smoothness of the objective function imply localizability.
  arXiv  Detail & Related papers  (2020-06-02T05:37:52Z)
• Parallelization Techniques for Verifying Neural Networks [52.917845265248744]
  We introduce an algorithm based on the verification problem in an iterative manner and explore two partitioning strategies. We also introduce a highly parallelizable pre-processing algorithm that uses the neuron activation phases to simplify the neural network verification problems.
  arXiv  Detail & Related papers  (2020-04-17T20:21:47Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.