论文标题
通过将链接内核引入GOMEA来解决多结构问题
Solving Multi-Structured Problems by Introducing Linkage Kernels into GOMEA
论文作者
论文摘要
基于模型的进化算法（MBEA）可以通过链接（或可变相互作用）学习高度扩展。但是，这要求链接模型可以捕获问题的可利用结构。通常，尝试使用诸如链接树之类的模型捕获单一类型的链接结构。但是，实际上，问题可能表现出多种连锁结构。例如，当目标具有不同的链接结构时，这就是多目标优化的情况。当使用旨在捕获单一类型的链接结构的链接模型时，这不能很好地建模，从而降低了MBEAS带来的优势。因此，在这里，我们介绍了链接内核，从而在其本地社区中为每个解决方案学习了连锁结构。我们将链接内核实施到MBEA中，称为GOMEA，以前在解决各种问题时被认为是高度可扩展的。我们进一步介绍了一种称为最佳陷阱（BOT）的新型基准功能，该功能具有可调式的不同链接结构。在机器人和最坏情况下，基于众所周知的Maxcut问题的变体，我们在实验上发现了与Gomea相对于GOMEA的链接 - 内基GOMEA的性能改善，而单个链接树以及MBEA以及称为DSMGA-II的MBEA。
Model-Based Evolutionary Algorithms (MBEAs) can be highly scalable by virtue of linkage (or variable interaction) learning. This requires, however, that the linkage model can capture the exploitable structure of a problem. Usually, a single type of linkage structure is attempted to be captured using models such as a linkage tree. However, in practice, problems may exhibit multiple linkage structures. This is for instance the case in multi-objective optimization when the objectives have different linkage structures. This cannot be modelled sufficiently well when using linkage models that aim at capturing a single type of linkage structure, deteriorating the advantages brought by MBEAs. Therefore, here, we introduce linkage kernels, whereby a linkage structure is learned for each solution over its local neighborhood. We implement linkage kernels into the MBEA known as GOMEA that was previously found to be highly scalable when solving various problems. We further introduce a novel benchmark function called Best-of-Traps (BoT) that has an adjustable degree of different linkage structures. On both BoT and a worst-case scenario-based variant of the well-known MaxCut problem, we experimentally find a vast performance improvement of linkage-kernel GOMEA over GOMEA with a single linkage tree as well as the MBEA known as DSMGA-II.
