Variable Search Stepsize for Randomized Local Search in Multi-Objective Combinatorial Optimization

• URL: http://arxiv.org/abs/2602.05675v1
• Date: Thu, 05 Feb 2026 13:59:05 GMT
• Title: Variable Search Stepsize for Randomized Local Search in Multi-Objective Combinatorial Optimization
• Authors: Xuepeng Ren, Maocai Wang, Guangming Dai, Zimin Liang, Qianrong Liu, Shengxiang Yang, Miqing Li,
• Abstract summary: We present a simple yet effective local search method, called variable stepsize randomized local search (VS-RLS)<n> VS-RLS transitions gradually from a broad, exploratory search in the early phases to a more focused, fine-grained search as the search progresses.<n>We demonstrate the effectiveness and generalizability of VS-RLS through extensive evaluations against local search and multi-objective evolutionary algorithms.
• Score: 12.70422671595511
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Over the past two decades, research in evolutionary multi-objective optimization has predominantly focused on continuous domains, with comparatively limited attention given to multi-objective combinatorial optimization problems (MOCOPs). Combinatorial problems differ significantly from continuous ones in terms of problem structure and landscape. Recent studies have shown that on MOCOPs multi-objective evolutionary algorithms (MOEAs) can even be outperformed by simple randomised local search. Starting with a randomly sampled solution in search space, randomised local search iteratively draws a random solution (from an archive) to perform local variation within its neighbourhood. However, in most existing methods, the local variation relies on a fixed neighbourhood, which limits exploration and makes the search easy to get trapped in local optima. In this paper, we present a simple yet effective local search method, called variable stepsize randomized local search (VS-RLS), which adjusts the stepsize during the search. VS-RLS transitions gradually from a broad, exploratory search in the early phases to a more focused, fine-grained search as the search progresses. We demonstrate the effectiveness and generalizability of VS-RLS through extensive evaluations against local search and MOEAs methods on diverse MOCOPs.

Related papers

• Random is Faster than Systematic in Multi-Objective Local Search [8.143459364469708]
  In multi-objective local search algorithms, a common practice is to maintain an archive of all non-dominated solutions found so far.<n>A central issue in this process is how to explore the neighbourhood of a selected solution.<n>We show that the random sampling method is consistently faster than the systematic exploration method across a range of multi-objective problems.
  arXiv  Detail & Related papers  (2026-01-09T21:27:30Z)
• Q-RAG: Long Context Multi-step Retrieval via Value-based Embedder Training [50.37345200692884]
  We propose Q-RAG, a novel approach that fine-tunes Embedder model for multi-step retrieval using reinforcement learning (RL)<n>Q-RAG offers a competitive, resource-efficient alternative to existing multi-step retrieval methods for open-domain question answering.
  arXiv  Detail & Related papers  (2025-11-10T17:31:02Z)
• Dynamic Search for Inference-Time Alignment in Diffusion Models [87.35944312589424]
  We frame inference-time alignment in diffusion as a search problem and propose Dynamic Search for Diffusion (DSearch)<n>DSearch subsamples from denoising processes and approximates intermediate node rewards.<n>It also dynamically adjusts beam width and tree expansion to efficiently explore high-reward generations.
  arXiv  Detail & Related papers  (2025-03-03T20:32:05Z)
• SMT(LIA) Sampling with High Diversity [12.198700284977962]
  We have developed the first sampling framework that integrates local search with CDCL(T) techniques.<n>HighDiv is capable of generating a highly diverse set of solutions for constraints under linear integer theory.
  arXiv  Detail & Related papers  (2025-02-25T07:53:46Z)
• 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)
• Learning to Control Local Search for Combinatorial Optimization [4.243592852049962]
  A zoo of generic as well as problem-specific variants of local search is commonly used to compute approximate solutions. In this paper we identify three independent algorithmic aspects of such local search algorithms and formalize their sequential selection over an optimization process. We show that NeuroLS is able to outperform both, well-known general purpose local search controllers from Operations Research as well as latest machine learning-based approaches.
  arXiv  Detail & Related papers  (2022-06-27T10:48:56Z)
• RF-Next: Efficient Receptive Field Search for Convolutional Neural Networks [86.6139619721343]
  We propose to find better receptive field combinations through a global-to-local search scheme. Our search scheme exploits both global search to find the coarse combinations and local search to get the refined receptive field combinations. Our RF-Next models, plugging receptive field search to various models, boost the performance on many tasks.
  arXiv  Detail & Related papers  (2022-06-14T06:56:26Z)
• Flipping the switch on local exploration: Genetic Algorithms with Reversals [0.0]
  Authors show that gradient-free search techniques are suitable for providing an optimal solution in the discrete domain. They also show that the use of multiple local searches can improve performance on local searches. It is observed that the proposed GA variants have the least average cost across all benchmarks including the problem proposed and IC performs better than its constituents.
  arXiv  Detail & Related papers  (2022-02-02T08:27:11Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)

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.