Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax

这段摘要介绍了一类元启发式技术——分布估计算法（EDAs），它们被用于优化，作为传统策略（如进化算法）的更为复杂的替代品。EDAs通常通过从底层搜索空间中重复采样和选择来创建潜在候选解的显式概率模型，从而驱动最优解的搜索。大多数EDAs的理论研究都集中在伪布尔优化上。Jedidia等人提出了第一个用于优化涉及多值决策变量问题的EDAs。在他们构建的框架下，我们关注多值紧凑遗传算法（r-cGA）并提供了对广义OneMax函数的第一个运行时间分析。为了证明我们的结果，我们研究了遗传漂移和概率模型向最优解的进展对结果的影响。在找到正确的算法参数后，我们证明了r-cGA有效地解决了这个r值OneMax问题。我们展示了在高概率下，运行时间的上限是O（r2 n log2 r log3 n）。在实验结束时，我们提出了一个关于另一种多值OneMax函数的预期运行时间的猜想。

本文旨在通过建立概率模型来解决多值决策变量的优化问题，并对多值紧凑遗传算法（r-cGA）在一般化的OneMax函数上进行首次运行时间分析。

本文的关键思路是使用估计分布算法（EDAs）来创建候选解的概率模型，并通过遗传漂移和模型进展来推动搜索，同时发现正确的算法参数。

本文使用了r值LeadingOnes函数和r值OneMax函数来验证算法的有效性，并证明了r-cGA可以高效地解决r值OneMax问题。实验结果表明，算法的运行时间界为O(r2 n log2 r log3 n)。此外，本文提出了一个关于另一种多值OneMax函数期望运行时间的猜想。

最近的研究主要集中在伪布尔优化上，而本文是首次将EDAs应用于多值决策变量的优化问题。