Draft:Random-key optimizers
(Redirected from Draft:Random-Key Optimizers)
| Submission rejected on 1 April 2025 by Caleb Stanford (talk). This topic is not sufficiently notable for inclusion in Wikipedia. Rejected by Caleb Stanford 13 hours ago. Last edited by Caleb Stanford 13 hours ago. |  |
Comment: Fails WP:GNG. The article is based on an arXiv preprint from 2024. Please do not use Wikipedia to advertise your latest research paper. Caleb Stanford (talk) 14:30, 1 April 2025 (UTC)
- Comment: Possible WP:LLM generated Sophisticatedevening🍷(talk) 12:49, 31 March 2025 (UTC)
- Comment: In accordance with Wikipedia's Conflict of interest policy, I disclose that I have a conflict of interest regarding the subject of this article. Antoniochavesunifesp (talk) 12:43, 31 March 2025 (UTC)
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
The Random-key optimizer (RKO) is a metaheuristic optimization algorithm that employs a continuous random-key representation to encode solutions. It is designed to solve combinatorial and continuous optimization problems by leveraging evolutionary and trajectory algorithm principles.
Overview
[edit]RKO is based on the concept of random-key encoding, where solutions are represented as vectors of real numbers within a predefined range (typically [0,1]). These vectors are then decoded into feasible solutions using a problem-specific decoding function. The method is inspired by the Biased Random-Key Genetic Algorithm (BRKGA) but incorporates modifications to enhance efficiency and adaptability.
History
[edit]The RKO method was introduced as a general-purpose optimization framework for solving complex decision-making problems. It builds upon the foundation of random-key genetic algorithms (RKGA), first introduced in the late 1990s, and extends their applicability by incorporating adaptive strategies and heuristic refinements.
Literaturereview
[edit]- Bean (1994): Random-Key Genetic Algorithms (RKGA)
- Gonçalves and Almeida (2002), Gonçalves & Resende (2011): Biased Random-Key Genetic Algorithms (BRKGA)
- Lin et al. (2010); Bewoor et al. (2017, 2018): Particle Swarm Optimization (PSO)
- Garcia-Santiago et al. (2015): Harmony Search (HS)
- Pessoa and Andrade (2018): Iterated Local Search (ILS), Iterated Greedy Search (IGS)
- Andrade et al. (2019): ILS, Tabu Search (TS) and Simulated Annealing (SA)
- Andrade et al. (2021): Implicit Path-Relinking (IPR)
- Schuetz et al. (2022): Dual Annealing
- Mangussi et al. (2023): SA, ILS, and Variable Neighborhood Search (VNS)
- Chaves et al. (2024): Greedy Randomized Adaptive Search Procedure (GRASP)
- Chaves et al. (2025): RKO Solver
Algorithm
[edit]The general structure of the RKO involves the following steps:
- Initialization: Generate a population of random-key encoded solutions.
- Decoding: Convert random-key vectors into feasible solutions using a problem-specific decoding function.
- Evaluation: Assess the quality of each solution based on a predefined objective function.
- Search Process:
- Components:
- Initial Solutions: Generate a diverse set of random-key vectors to explore the solution space.
- Pool of Elite Solutions: Maintain a set of high-quality solutions for refinement and recombination.
- Shaking: Introduce perturbations to escape local optima and enhance exploration.
- Blending: Combine solutions to create new promising candidates.
- Local Search: Apply improvement procedures to refine candidate solutions.
- Metaheuristics: Incorporate additional optimization techniques (e.g., simulated annealing, VNS, ILS, etc.) to guide the search process.
- Components:
- Termination: Repeat the process until a stopping criterion is met (e.g., time limit, maximum iterations, or convergence threshold).
Applications
[edit]RKO has been applied to a variety of combinatorial optimization problems, including:
- α-Neighborhood p-Median Problem (α-NpMP)
- α-Neighborhood p-Center Problem (α-NpCP)
- Node Capacitated Graph Partitioning Problem (NCGPP)
- Tree Hub Location Problem (THLP)
- Balanced Edge Partition Problem (BEPP)
- Operating Room Scheduling Problem (ORSP)
- Job Sequencing and Tool Switching Problem (SSP)
- HEV Traveling Salesman Problem with Time Windows (HEVTSPTW)
- Steiner Triple Covering Problem (STCP)
- Traveling Thief Problem (TTP)
- One-Dimensional Multi-Period Cutting Stock Problem (MPCSP)
- Capacitated Vehicle Routing Problem (CVRP)
- Portfolio Optimization
Recent Developments
[edit]- Continuous RKO algorithm for discrete optimization.
- Multi-thread software framework with several RKOs that collaborate through solution sharing in a pool and local search.
- Problem-independent framework—only a problem-dependent decoder needs to be implemented.
- New adaptation of Nelder-Mead search for optimization in real n-dimensional unit hypercube.
- Randomized Variable Neighborhood Descent (RVND) procedure integrating simple local search techniques.
- Open-source software available on GitHub.
External links
[edit]References
[edit]- Andrade, C.E., Byers, S.D., Gopalakrishnan, V., Halepovic, E., Poole, D.J., Tran, L.K., & Volinsky, C.T. (2019). "Scheduling software updates for connected cars with limited availability." Applied Soft Computing, 82, 105575. doi:10.1016/j.asoc.2019.105575.
- Andrade, C.E., Toso, R.F., Gonçalves, J.F., & Resende, M.G. (2021). "The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications." European Journal of Operational Research, 289, 17–30. doi:10.1016/j.ejor.2019.11.037.
- Bean, J.C. (1994). "Genetic algorithms and random keys for sequencing and optimization." ORSA Journal on Computing, 6, 154–160. doi:10.1007/s10729-008-9080-9.
- Chaves, A.A., Resende, M.G.C., & Silva, R.M.A. (2024). "A random-key grasp for combinatorial optimization." Journal of Nonlinear & Variational Analysis, 8. doi:10.23952/jnva.8.2024.6.03.
- Garcia-Santiago, C., Del Ser, J., Upton, C., Quilligan, F., Gil-Lopez, S., & Salcedo-Sanz, S. (2015). "A random-key encoded harmony search approach for energy-efficient production scheduling with shared resources." Engineering Optimization, 47, 1481–1496. doi:10.1080/0305215X.2014.
- Gonçalves, J.F., & De Almeida, J.R. (2002). "A hybrid genetic algorithm for assembly line balancing." Journal of Heuristics, 8, 629–642. doi:10.1023/A:1020377910258.
- Gonçalves, J.F., & Resende, M.G.C. (2011). "Biased random-key genetic algorithms for combinatorial optimization." Journal of Heuristics, 17, 487–525. doi:10.1007/s10732-010-9143-1.
- Lin, T.L., Horng, S.J., Kao, T.W., Chen, Y.H., Run, R.S., Chen, R.J., Lai, J.L., & Kuo, I.H. (2010). "An efficient job-shop scheduling algorithm based on particle swarm optimization." Expert Systems with Applications, 37, 2629–2636. doi:10.1016/j.eswa.2009.08.015.
- Londe, M.A., Pessoa, L.S., Andrade, C.E., & Resende, M.G. (2025). "Biased random-key genetic algorithms: A review." European Journal of Operational Research, 321, 1–22. doi:10.1016/j.ejor.2024.03.030.
- Mangussi, A.D., Pola, H., Macedo, H.G., ao, L.A.J., Proença, M.P.T., Gianfelice, P.R.L., Salezze, B.V., & Chaves, A.A. (2023). "Meta-heurĂsticas via chaves aleatĂłrias aplicadas ao problema de localização de hubs em árvore." Anais do SimpĂłsio Brasileiro de Pesquisa Operacional, 25. doi:10.59254/sbpo-2023-174934.
- Noronha, T.F., & Ribeiro, C.C. (2024). "Biased random-key genetic algorithms: A tutorial with applications." ACM International Conference Proceeding Series, 110–115. doi:10.1145/3665065.
- Pessoa, L.S., & Andrade, C.E. (2018). "Heuristics for a flowshop scheduling problem with stepwise job objective function." European Journal of Operational Research, 266, 950–962. doi:10.1016/j.ejor.2017.10.045.
- Schuetz, M.J., Brubaker, J.K., Montagu, H., van Dijk, Y., Klepsch, J., Ross, P., Luckow, A., Resende, M.G., & Katzgraber, H.G. (2022). "Optimization of robot-trajectory planning with nature-inspired and hybrid quantum algorithms." Physical Review Applied, 18, 054045. doi:10.1103/PhysRevApplied.18.054045.