Data from: Improving HybrID: how to best combine indirect and direct encoding in evolutionary algorithms

Many challenging engineering problems are regular, meaning solutions to one part of a problem can be reused to solve other parts. Evolutionary algorithms with indirect encoding perform better on regular problems because they reuse genomic information to create regular phenotypes. However, on problems that are mostly regular, but contain some irregularities, which describes most real-world problems, indirect encodings struggle to handle the irregularities, hurting performance. Direct encodings are better at producing irregular phenotypes, but cannot exploit regularity. An algorithm called HybrID combines the best of both: it first evolves with indirect encoding to exploit problem regularity, then switches to direct encoding to handle problem irregularity. While HybrID has been shown to outperform both indirect and direct encoding, its initial implementation required the manual specification of when to switch from indirect to direct encoding. In this paper, we test two new methods to improve HybrID by eliminating the need to manually specify this parameter. Auto-Switch-HybrID automatically switches from indirect to direct encoding when fitness stagnates. Offset-HybrID simultaneously evolves an indirect encoding with directly encoded offsets, eliminating the need to switch. We compare the original HybrID to these alternatives on three different problems with adjustable regularity.
The results show that both Auto-Switch-HybrID and Offset-HybrID outperform the original HybrID on different types of problems, and thus offer more tools for researchers to solve challenging problems. The Offset-HybrID algorithm is particularly interesting because it suggests a path forward for automatically and simultaneously combining the best traits of indirect and direct encoding.

诸多具有挑战性的工程问题均具备规律性，即针对问题某一部分的求解方案可被复用，用以解决该问题的其他子部分。采用间接编码（indirect encoding）的进化算法在规律性问题上表现更优，原因在于其可复用基因组信息来生成规整的表型（phenotype）。然而，针对那些整体具备规律性但存在部分不规则之处的问题（这类问题也是多数现实世界问题的写照），间接编码却难以应对其中的不规则部分，进而降低了算法性能。直接编码（direct encoding）则更擅长生成不规则表型，却无法利用问题的规律性。一款名为HybrID的算法兼顾了两者的优势：它首先借助间接编码进行进化以利用问题的规律性，随后切换至直接编码来处理问题中的不规则部分。尽管已有研究表明HybrID的表现优于间接编码与直接编码，但该算法的初始实现版本需要手动指定从间接编码切换至直接编码的时机。本文中，我们提出了两种无需手动指定该参数的改进HybrID的新方法。其一为Auto-Switch-HybrID，它会在适应度（fitness）停滞时自动完成从间接编码到直接编码的切换；其二为Offset-HybrID，它可同时对带有直接编码偏移量的间接编码进行进化，从而彻底省去了手动切换的步骤。我们在三类具备可调规律性的问题上，将原始HybrID与这两种改进方案进行了对比实验。实验结果表明，Auto-Switch-HybrID与Offset-HybrID在不同类型的问题上均优于原始HybrID，从而为研究者解决各类挑战性工程问题提供了更多可选工具。其中Offset-HybrID算法尤为值得关注，因为它为自动且同步地融合间接编码与直接编码的最优特性指明了可行方向。