遗传算法应用和限制

在遗传编程 (GP) 系列的这一点上，我们已经了解了什么是遗传编程以及它如何表示信息、遗传算子如何在进化算法中工作，以及通过符号回归进化排序程序。

在这里，我们将深入了解这项技术在发展过程中可以实现的目标。

遗传编程的实际考虑

要理解我们系列的最后一章，让我们记住我们在本系列的第一部分中讨论的 XOR 示例：

GP发现的XOR问题的完美解决方案： (defun 程序 () （与（或 X1 X2） （不是（和 X1 X2）） ) ) 

清单 1。 异或结果。

我们也回顾一下上一篇文章中的符号回归示例：

 区间 (0 <=x <=pi/2) 中 sin(x) 的多项式逼近 (defun 程序 () (+ (* (* (* X X) X) (* 0.2283 -0.6535)) X） ) 简化上述程序产生以下等价方程： polysin(x) =-.1492 x
3
 + x 结果：

清单 4。 符号回归。

请注意，此处显示的 XOR 和符号回归示例在评估时都返回单个值。

这个特性不一定是限制，因为函数或终端在执行时肯定有可能产生副作用。这通常是排序程序的情况，它包含一个函数，该函数具有交换向量中的一对元素的潜在副作用。在实践中，出现副作用是很常见的。其他一些有用的副作用示例是将一个变量分配给另一个变量或改变机器人面向的方向。

我们的函数集可能包括条件函数，这些函数为进化的程序提供了决策能力。条件函数有选择地评估它们的参数。例如，考虑一个元数为 3 的函数，例如 (if arg1 arg2 arg3)。该函数通过评估第一个参数进行评估，如果结果为真，则评估第二个参数；否则，评估第三个参数。迭代构造也是可能的，因为函数可以多次评估其参数之一。然而，由于需要限制迭代次数和嵌套级别以避免出现对个体的评估可能花费过长时间的情况，因此引入了额外的复杂性。已经做了一些工作来允许递归公式，尽管在这方面的成功有些有限。

尽管 GP 系统的结果往往是类似 LISP 的程序，但不需要在 LISP 中实现 GP 系统。许多系统是用 C 或 C++ 实现的。可以采用程序树的线性化表示，并且可以避免动态内存的开销以及昂贵的垃圾收集。适应度函数的效率值得特别关注，因为它通常是一个瓶颈，因为它在每一代中被调用的次数很多。 Advances in Genetic Programming 中可以找到一篇讨论各种实现技术的优秀论文 （在下面的建议阅读部分引用）。

与其他机器学习范式（例如神经网络）一样，存在过度拟合训练数据（GP 测试用例）的可能性。当解决方案有效地“记住”数据时，可能会发生过度拟合，因此提供的只是一个精心设计的查找表。帮助减少这种影响的一种简单方法是使用简约因子。简约因子通常是乘以程序树中节点数的一小部分，其结果被合并到适应度函数中。这个想法是奖励更小、可能更通用的解决方案。此外，我们鼓励您使用适当的实验设计技术。例如，如果您正在尝试开发一个预测模型，最好将适应度评估限制为可用数据的一个子集。这样，剩余的数据就可以衡量所得模型的预测性能。

与进化算法的情况一样，GP 不保证找到精确的解决方案，甚至不提供可接受的解决方案。从一次运行到另一次运行，结果可能会有很大差异。通常，该过程过早地收敛于局部最小值。性能高度依赖于问题的复杂性，其表征为函数和终端的选择，以及适应度函数的性质。

基因编程的应用

遗传编程已成功应用于以下领域的问题：

• 电路设计
• 组合优化
• 控制系统
• 曲线拟合/回归分析
• 数据压缩
• 经济预测/财务建模
• 获取游戏策略
• 数学序列归纳
• 神经网络设计
• 模式识别与分类
• 随机数生成
• 机器人导航
• 符号整合与分化
• 立体设计

基因编程的未来方向

根据问题的复杂程度，可能需要多次运行 GP 才能找到可接受的解决方案（如果可以找到的话）。理想情况下，我们希望 GP 随着问题复杂性的增加而“扩大”。寻找实现这一目标的好方法是一个活跃的研究领域。与传统编程一样，通过子例程构建更高级别表示的概念是解决此问题的一种方法。在遗传编程 II , Koza 讨论了可以发现可重用子例程的方法，并展示了支持分层模块化程序解决更复杂问题的能力的结果。

正如我们所见，GP 将遗传算法的自组织特征与 S 表达式的表示能力和通用性结合起来。这种方法的优雅将问题规范简化为提供特定领域的适应度函数以及适当的函数和终端集。适用于各种问题，GP 仍然是研究的沃土。

仍处于起步阶段，未来的突破可能会让我们更进一步，实现能够编写自己的程序的系统的圣杯。

推荐阅读

• Kinnear, Jr., K. E. (ed.)。 遗传编程的进展 .马萨诸塞州剑桥：麻省理工学院出版社，1994 年。
• Knuth, D. E. 计算机编程的艺术，第 3 卷，排序和搜索 .马萨诸塞州雷丁：Addison-Wesley，1973 年
• Koza, J. R. 遗传编程 .马萨诸塞州剑桥：麻省理工学院出版社，1992 年。
• Koza, J. R. 遗传编程 II .马萨诸塞州剑桥：麻省理工学院出版社，1994 年。
• Montana, D. J.“强类型遗传编程”。 BBN 技术报告 #7866，1993 年 5 月。
• Mitchell、Melanie，遗传算法简介 ，麻省理工学院出版社，1998 年。