RT Journal Article
T1 Generalization and completeness of stochastic local search algorithms
A1 Loscos Barroso, Daniel
A1 Martí Oliet, Narciso
A1 Rodríguez Laguna, Ismael
AB We generalize Stochastic Local Search (SLS) heuristics into a unique formal model. This model has two key components: a common structure designed to be as large as possible and a parametric structure intended to be as small as possible. Each heuristic is obtained by instantiating the parametric part in a different way. Particular instances for Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO) are presented. Then, we use our model to prove the Turing-completeness of SLS algorithms in general. The proof uses our framework to construct a GA able to simulate any Turing machine. This Turing-completeness implies that determining any non-trivial property concerning the relationship between the inputs and the computed outputs is undecidable for GA and, by extension, for the general set of SLS methods (although not necessarily for each particular method). Similar proofs are more informally presented for PSO and ACO.
PB Elsevier
SN 2210-6502
YR 2021
FD 2021-09-15
LK https://hdl.handle.net/20.500.14352/4698
UL https://hdl.handle.net/20.500.14352/4698
LA eng
NO CRUE-CSIC (Acuerdos Transformativos 2021)
NO Ministerio de Ciencia e Innovación (MICINN)
NO Comunidad de Madrid/FEDER
DS Docta Complutense
RD 10 may 2025