Wagner Markus, Neumann Frank, Urli Tommaso
Optimisation and Logistics, University of Adelaide, Adelaide, Australia
DIEGM, Università degli Studi di Udine, Udine, Italy
Evol Comput. 2015 Winter;23(4):583-609. doi: 10.1162/EVCO_a_00149. Epub 2015 Apr 14.
In genetic programming, the size of a solution is typically not specified in advance, and solutions of larger size may have a larger benefit. The flexibility often comes at the cost of the so-called bloat problem: individuals grow without providing additional benefit to the quality of solutions, and the additional elements can block the optimization process. Consequently, problems that are relatively easy to optimize cannot be handled by variable-length evolutionary algorithms. In this article, we analyze different single- and multiobjective algorithms on the sorting problem, a problem that typically lacks independent and additive fitness structures. We complement the theoretical results with comprehensive experiments to indicate the tightness of existing bounds, and to indicate bounds where theoretical results are missing.
在遗传编程中，通常不预先指定解决方案的大小，较大规模的解决方案可能会带来更大的益处。这种灵活性往往以所谓的膨胀问题为代价：个体不断增长，却未给解决方案的质量带来额外益处，而且这些额外的元素可能会阻碍优化过程。因此，相对容易优化的问题无法由可变长度进化算法处理。在本文中，我们分析了针对排序问题的不同单目标和多目标算法，排序问题通常缺乏独立且可加的适应度结构。我们通过全面的实验对理论结果进行补充，以表明现有界限的紧密程度，并指出理论结果缺失的界限。
