de Jong Edwin D
Institute of Information and Computing Sciences, Utrecht University, PO Box 80.089, 3508 TB Utrecht, The Netherlands.
Evol Comput. 2007 Spring;15(1):61-93. doi: 10.1162/evco.2007.15.1.61.
Coevolution has already produced promising results, but its dynamic evaluation can lead to a variety of problems that prevent most algorithms from progressing monotonically. An important open question therefore is how progress towards a chosen solution concept can be achieved. A general solution concept for coevolution is obtained by viewing opponents or tests as objectives. In this setup known as Pareto-coevolution, the desired solution is the Pareto-optimal set. We present an archive that guarantees monotonicity for this solution concept. The algorithm is called the Incremental Pareto-Coevolution Archive (IPCA), and is based on Evolutionary Multi-Objective Optimization (EMOO). By virtue of its monotonicity, IPCA avoids regress even when combined with a highly explorative generator. This capacity is demonstrated on a challenging test problem requiring both exploration and reliability. IPCA maintains a highly specific selection of tests, but the size of the test archive nonetheless grows unboundedly. We therefore furthermore investigate how archive sizes may be limited while still providing approximate reliability. The LAyered Pareto-Coevolution Archive (LAPCA) maintains a limited number of layers of candidate solutions and tests, and thereby permits a trade-off between archive size and reliability. The algorithm is compared in experiments, and found to be more efficient than IPCA. The work demonstrates how the approximation of a monotonic algorithm can lead to algorithms that are sufficiently reliable in practice while offering better efficiency.
协同进化已经产生了令人满意的结果，但其动态评估可能会导致各种问题，从而使大多数算法无法单调推进。因此，一个重要的开放性问题是如何朝着选定的解决方案概念取得进展。协同进化的一个常规解决方案概念是将对手或测试视为目标而得到的。在这种称为帕累托协同进化的设置中，期望的解决方案是帕累托最优集。我们提出了一个为这个解决概念保证单调性的存档。该算法称为增量帕累托协同进化存档（IPCA），它基于进化多目标优化（EMOO）。凭借其单调性，即使与高度探索性的生成器相结合，IPCA也能避免倒退。在一个既需要探索又需要可靠性的具有挑战性的测试问题上证明了这种能力。IPCA维持对测试的高度特定选择，但测试存档的大小仍然无界增长。因此，我们进一步研究如何在仍提供近似可靠性的同时限制存档大小。分层帕累托协同进化存档（LAPCA）维持有限数量的候选解决方案和测试层，从而允许在存档大小和可靠性之间进行权衡。在实验中对该算法进行了比较，发现它比IPCA更高效。这项工作展示了单调算法的近似如何能导致在实践中足够可靠同时效率更高的算法。
