Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation
Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation
复制标题
DOI：
10.1145/3583133.3590701
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Mario Alejandro Hevia Fajardo;P. Lehre;Shishen Lin
中科院分区：
文献类型：
--
作者：
Mario Alejandro Hevia Fajardo;P. Lehre;Shishen Lin
协同进化算法已经在博弈论应用和对手优化问题中找到了几个应用，特别是在策略空间是离散和指数大的情况下，以及经典博弈论方法失败的情况下。然而，协同进化算法的应用是困难的，因为它们经常表现出病态的行为，如循环行为和进化遗忘。这些挑战阻碍了协同进化算法的广泛应用。我们推导出，通过严格的数学方法，一个简单的协同进化算法，直到它发现离散双线性问题的最大解的预期时间的界限。尽管问题的不传递性导致算法的循环行为，我们证明了该算法在预期的O（n1.5）时间内获得最大解。然而，该算法很快就会忘记最大最小解，并远离它。沿着的方式，我们提出了新的数学工具来计算的期望时间的协同进化算法，以获得一个最大最小解。我们相信，这些工具可以帮助进一步推进运行时分析在共同进化和进化算法。
Co-evolutionary algorithms have found several applications in game-theoretic applications and optimisation problems with an adversary, particularly where the strategy space is discrete and exponentially large, and where classical game-theoretic methods fail. However, the application of co-evolutionary algorithms is difficult because they often display pathological behaviour, such as cyclic behaviour and evolutionary forgetting. These challenges have prevented the broad application of co-evolutionary algorithms. We derive, via rigorous mathematical methods, bounds on the expected time of a simple co-evolutionary algorithm until it discovers a Maximin-solution on the discrete Bilinear problem. Despite the intransitive nature of the problem leading to a cyclic behaviour of the algorithm, we prove that the algorithm obtains the Maximin-solution in expected O(n1.5) time. However, the algorithm quickly forgets the Maximin-solution and moves away from it. Along the way, we present new mathematical tools to compute the expected time for co-evolutionary algorithms to obtain a Maximin-solution. We are confident that these tools can help further advance runtime analysis in both co-evolutionary and evolutionary algorithms.