A Random-Key Optimizer for Combinatorial Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909987906781184 |
|---|---|
| author | Chaves, Antonio A. Resende, Mauricio G. C. Schuetz, Martin J. A. Brubaker, J. Kyle Katzgraber, Helmut G. de Arruda, Edilson F. Silva, Ricardo M. A. |
| author_facet | Chaves, Antonio A. Resende, Mauricio G. C. Schuetz, Martin J. A. Brubaker, J. Kyle Katzgraber, Helmut G. de Arruda, Edilson F. Silva, Ricardo M. A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04293 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Random-Key Optimizer for Combinatorial Optimization Chaves, Antonio A. Resende, Mauricio G. C. Schuetz, Martin J. A. Brubaker, J. Kyle Katzgraber, Helmut G. de Arruda, Edilson F. Silva, Ricardo M. A. Artificial Intelligence Disordered Systems and Neural Networks Neural and Evolutionary Computing Optimization and Control 90-02, 90B40, 90C27 G.1.6; G.2.1; I.2.8 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. |
| title | A Random-Key Optimizer for Combinatorial Optimization |
| topic | Artificial Intelligence Disordered Systems and Neural Networks Neural and Evolutionary Computing Optimization and Control 90-02, 90B40, 90C27 G.1.6; G.2.1; I.2.8 |
| url | https://arxiv.org/abs/2411.04293 |