Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function
Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function
复制标题
双线性函数最大最小优化的竞争协同进化算法的运行时分析
DOI：
10.1145/3512290.3528853
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
P. Lehre
中科院分区：
文献类型：
--
作者：
P. Lehre
协同进化算法具有广泛的应用，例如硬件设计、棋盘游戏策略的进化以及修补软件错误。然而，人们对这些算法知之甚少，其应用往往受到病理行为的限制，如梯度丧失、相对过度泛化和平庸的客观停滞。开发一种理论来预测协同进化算法何时能有效、可靠地找到解决方案，这是一个公开的挑战。本文为基于种群的竞争协同进化算法的运行时分析提供了第一步。我们提供了一个数学框架来描述和推理共同进化过程的性能。该框架的一个示例应用显示了一个简单的协同进化算法在多项式期望时间内获得解的场景。最后，我们描述了协同进化算法需要指数时间以压倒性的高概率获得解的设置。
Co-evolutionary algorithms have a wide range of applications, such as in hardware design, evolution of strategies for board games, and patching software bugs. However, these algorithms are poorly understood and applications are often limited by pathological behaviour, such as loss of gradient, relative over-generalisation, and mediocre objective stasis. It is an open challenge to develop a theory that can predict when co-evolutionary algorithms find solutions efficiently and reliably. This paper provides a first step in developing runtime analysis for population-based competitive co-evolutionary algorithms. We provide a mathematical framework for describing and reasoning about the performance of co-evolutionary processes. An example application of the framework shows a scenario where a simple coevolutionary algorithm obtains a solution in polynomial expected time. Finally, we describe settings where the co-evolutionary algorithm needs exponential time with overwhelmingly high probability to obtain a solution.
通过支付查询找到 Bimatrix 博弈的近似纳什均衡
影响因子：
1.2
作者：
Fearnley J
通讯作者：
Fearnley J
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Dang D.-C.
通讯作者：
Dang D.-C.