1.1.3 遗传规划

上述遗传算法和演化策略都可以在高维、非线性、非凸的搜索空间中求解近似的最值，并且不受数学模型限制，已被广泛应用，但是需要确定长度的编码和确定的计算机程序来求解确定的问题。然而，现实问题的搜索空间的形状、维度等可能具有不确定性，随时空条件的变化而变化，例如交通网络中的道路通行效率不仅受到固定的道路宽度的影响，还会随道路上的车流量的变化而变化。面对现实问题的不确定性和遗传算法等进化算法的局限性，遗传规划（Genetic Programming，GP）应运而生，由Koza于1992年提出。

1.算法基本思想

在机器学习中，许多看似不同的问题，其解决方案都可以被表示为给定输入就输出预期结果的计算机程序（即原始函数和终端的分层组合），这些程序的大小和结构不确定。尝试使用类似遗传算法染色体表示的固定长度的字符串来表示大小和结构动态变化的层次结构是困难、不自然且过于严格的。遗传规划提供了一种方法，可以找到未指定大小和结构的计算机程序来解决或近似解决问题。

从本质上看，遗传规划构造的是一个能够构造算法的算法，进化的基本单位是新的算法和新算法的参数，而不同于遗传算法等优化算法仅仅进化模型的可变参数，即问题的决策变量。遗传算法是一种优化算法，无论算法发生何种形式的优化，算法或度量都是预先设定好的，而优化算法所做的工作就是尝试为其找到最佳参数。与优化算法一样，遗传规划也需要一种方法来评估解的优劣程度。但与优化算法不同的是，遗传规划中的解并不只是一组用于给定算法的参数，相反，在遗传规划中，算法结构及其所有参数都是需要通过搜索来确定的。

2.算法流程

遗传规划的流程图和伪代码与遗传算法相同，如图1-5所示。

遗传规划的解的表示，即程序的构成，有两个基本要素：终端集和函数集。终端集是构成程序的所有变量和常数等符号的完备集合。函数集是构成程序的基本函数的完备集合。遗传规划的解的初始化由终端和函数的随机组合构成。例如，图1-8展示了两个计算机程序个体 Z/ 0.37+0.89* X 和（0.21+ Z ）*（（ Y -0.53） / 0.04），其中终端集包括{0.37，0.89，0.21，0.53，0.04， X ， Y ， Z }，均位于叶节点，函数集包括{+，-，*， / }，均位于非叶节点。

遗传规划的解通常是在许多适应值案例中进行评估的，就像计算机程序需要根据多个测试用例的输出来调试一样，适应值案例集合必须能代表整个问题，就像计算机程序需要适应的整个“环境”一样。一个解能正确处理的案例越多，则越优秀。

遗传规划的终止条件，通常是达到指定最大迭代次数，或在达到最大迭代次数前种群中存在个体程序的输出结果能100%符合问题的解。

交叉算子在每个个体上分别选择其中一条边对解进行切割，产生的个体片段重新组成形成子代，交叉算子的个体片段和子代个体分别如图1-9和图1-10所示。