统一建模随机局部搜索算法，证明其具备图灵完备性。
Generalization and Completeness of Stochastic Local Search Algorithms
- 构建通用形式化模型，用大结构与小参数结构统一SLS方法。
- 证明遗传算法可模拟任意图灵机，具图灵完备性。
- 揭示此类算法的性质判定不可解，适合理论研究者参考。
本文将随机局部搜索（SLS）启发式方法统一为一个通用的形式化模型，包含尽可能大的公共结构和尽可能小的参数结构。每个具体算法通过不同方式实例化参数部分获得。文中给出了遗传算法（GA）、蚁群优化（ACO）和粒子群优化（PSO）的具体实例。基于该框架，证明了SLS算法整体具有图灵完备性：构造出能模拟任意图灵机的遗传算法。这表明，对于遗传算法乃至整个SLS方法集，任何关于输入与输出关系的非平凡性质判断均不可判定。对PSO和ACO也给出了类似的非正式论证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。