arXiv:2411.04293cs.AIcond-mat.dis-nn2024-11被引 8

一种可组合多种优化算法的随机键求解器,能高效解决各类组合优化难题。

A Random-Key Optimizer for Combinatorial Optimization

  • 用随机键编码解空间,通过专用解码器生成可行解
  • 融合模拟退火、迭代局部搜索等算法,共享精英解提升性能
  • 在3类难解问题上表现优异,适合需要快速求解的工程场景

本文提出随机键优化器(RKO),一种适用于组合优化问题的通用且高效的随机局部搜索方法。RKO采用随机键概念,将解表示为随机键向量,并通过问题特异性解码器转化为可行解。该框架可集成多种经典元启发式算法,如模拟退火、迭代局部搜索和贪婪随机自适应搜索过程等,各算法可独立或并行运行,通过精英解池实现解共享。RKO使用C++实现并公开于GitHub(github.com/RKO-solver)。在三个NP难组合优化问题上的实验表明:α-邻域p-中位问题、枢纽树选址问题与节点容量图划分问题,RKO均能产生高质量解,验证了其在多样化问题域中的有效性与鲁棒性。

原文摘要 · Abstract (English)

This paper introduces the Random-Key Optimizer (RKO), a versatile and efficient stochastic local search method tailored for combinatorial optimization problems. Using the random-key concept, RKO encodes solutions as vectors of random keys that are subsequently decoded into feasible solutions via problem-specific decoders. The RKO framework is able to combine a plethora of classic metaheuristics, each capable of operating independently or in parallel, with solution sharing facilitated through an elite solution pool. This modular approach allows for the adaptation of various metaheuristics, including simulated annealing, iterated local search, and greedy randomized adaptive search procedures, among others. The efficacy of the RKO framework, implemented in C++ and publicly available (Github public repository: github.com/RKO-solver), is demonstrated through its application to three NP-hard combinatorial optimization problems: the alpha-neighborhood p-median problem, the tree of hubs location problem, and the node-capacitated graph partitioning problem. The results highlight the framework's ability to produce high-quality solutions across diverse problem domains, underscoring its potential as a robust tool for combinatorial optimization.

组合优化元启发式随机键求解器

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。