How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems
How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems
复制标题
DOI：
10.1145/3583131.3590506
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Mario Alejandro Hevia Fajardo;P. Lehre
中科院分区：
文献类型：
--
作者：
Mario Alejandro Hevia Fajardo;P. Lehre
竞争性协同进化算法 (CoEA) 不仅仅依赖于外部函数来为采样解决方案分配适应度值。相反，他们使用竞争解决方案之间交互的结果聚合，从而对解决方案进行排名并做出选择决策。这使得 CoEA 成为解决具有本质交互域的优化问题的有用工具。在过去的几十年里，人们考虑了许多汇总交互结果的方法。目前，尚不清楚哪一个是最佳选择。先前的研究是零散的，并且大多数提出的适应度聚合方法（适应度测量）仅进行了实证研究。我们认为，只有通过严格分析 CoEA 的行为，才能正确理解 CoEA 的动态及其健康指标。在这项工作中，我们通过使用运行时分析来研究两种常用的健身指标，朝着这个目标迈出了一步。在优化双线性问题时，我们展示了 (1, Λ) CoEA 行为的二分法。如果使用最差交互作为适应度度量，则该算法可以有效地找到纳什均衡，但它需要指数时间 w.o.p。如果使用所有交互的平均值来代替。
Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to rank solutions and make selection decisions. This makes CoEAs a useful tool for optimisation problems that have intrinsically interactive domains. Over the past decades, many ways to aggregate the outcomes of interactions have been considered. At the moment, it is unclear which of these is the best choice. Previous research is fragmented and most of the fitness aggregation methods (fitness measures) proposed have only been studied empirically. We argue that a proper understanding of the dynamics of CoEAs and their fitness measures can only be achieved through rigorous analysis of their behaviour. In this work we make a step towards this goal by using runtime analysis to study two commonly used fitness measures. We show a dichotomy in the behaviour of a (1, Λ) CoEA when optimising a Bilinear problem. The algorithm finds a Nash equilibrium efficiently if the worst interaction is used as a fitness measure but it takes exponential time w.o.p. if the average of all interactions is used instead.