CSIS Department, University of Limerick, Ireland
Evol Comput. 2014 Summer;22(2):287-317. doi: 10.1162/EVCO_a_00111. Epub 2014 Feb 6.
Genetic programming (GP) coarsely models natural evolution to evolve computer programs. Unlike in nature, where individuals can often improve their fitness through lifetime experience, the fitness of GP individuals generally does not change during their lifetime, and there is usually no opportunity to pass on acquired knowledge. This paper introduces the Chameleon system to address this discrepancy and augment GP with lifetime learning by adding a simple local search that operates by tuning the internal nodes of individuals. Although not the first attempt to combine local search with GP, its simplicity means that it is easy to understand and cheap to implement. A simple cache is added which leverages the local search to reduce the tuning cost to a small fraction of the expected cost, and we provide a theoretical upper limit on the maximum tuning expense given the average tree size of the population and show that this limit grows very conservatively as the average tree size of the population increases. We show that Chameleon uses available genetic material more efficiently by exploring more actively than with standard GP, and demonstrate that not only does Chameleon outperform standard GP (on both training and test data) over a number of symbolic regression type problems, it does so by producing smaller individuals and it works harmoniously with two other well-known extensions to GP, namely, linear scaling and a diversity-promoting tournament selection method.
遗传编程（GP）粗略地模拟自然进化来进化计算机程序。与自然不同，个体在自然中通常可以通过一生的经验来提高适应性，而 GP 个体的适应性在其一生中通常不会改变，并且通常没有机会传递获得的知识。本文介绍了变色龙系统来解决这个差异，并通过添加一种简单的局部搜索来增加终身学习功能，该搜索通过调整个体的内部节点来进行操作。虽然不是第一次尝试将局部搜索与 GP 结合使用，但它的简单性意味着它易于理解且易于实现。添加了一个简单的缓存，利用局部搜索将调整成本降低到预期成本的一小部分，并提供了种群平均树大小给定的最大调整费用的理论上限，并表明随着种群平均树大小的增加，该上限增长非常保守。我们通过比标准 GP 更积极地探索来证明变色龙可以更有效地利用可用的遗传物质，并证明变色龙不仅在许多符号回归类型的问题上比标准 GP（在训练和测试数据上）表现更好，而且它通过产生更小的个体来实现这一点，并且与 GP 的另外两个著名扩展（即线性缩放和促进多样性的锦标赛选择方法）和谐地工作。
