进化算法与混合动力系统优化：算法表示与主体流程

GP算法是遗传算法的一个分支，它采用了一种全新的个体描述方法，即运用层次化的计算机程序代替个体的字符串描述。根据个体的基本结构，可以将个体的表示方法分为三种：树状结构、线性结构和基于图形的结构。其中，最常用的是树状结构，即每个个体都是一个以树状结构来表示的计算机程序。

如图2-6所示，采用树状结构表示个体：NOT（IF（x₁ AND x₂）THEN NOT（x₃）E LSE（x₁ OR x₃））。表示GP个体的树状结构的层与结点均是可变化的，树的结点由终结点集、函数结点集中的元素组成。终结点集是将问题分级划分为子问题后最基本的解的成分，它是问题的原始变量。根结点和中间结点称为内部结点，它们是完成一定功能的函数，所有这些函数的集合构成函数结点集。该树的每一个非终结点从函数结点集中选择，树的每一个终结点从终结点集中选择。

GP算法的搜索空间是一个从已存在的结点函数递归产生所有可能的函数和结点空间。初始群体为计算机在搜索空间中随机搜索而生成的子程序或表达式，这些子程序或表达式采用一种动态的树状结构，第一代树的每一个结点均为随机生成。

遗传编程从提出一个高级别的问题指令开始，并试图产生一个计算机程序来解决这个问题。程序员通过完成这些定义好的准备步骤来和遗传编程系统进行高级别的问题指令沟通。《遗传编程：用自然选择让计算机编程》一书将一般类型的遗传编程分为五个主要的准备步骤：

1）定义进化程序的终止符集（如问题的独立变量、零参数函数和随机常数）；

2）准备被进化程序的初始函数集；

3）设计适应度（要适时衡量出种群中满足适应度的个体）函数与方法；

4）某些控制执行的参数；

5）指定的运行终止标准和方法。

前面两个准备步骤具体指出了创建计算机程序的要素，在一个多样化的由函数集和终止集组成的程序种群中，一个遗传编程的执行是一个竞争的搜索。

表2-1列出了符号回归问题的预备步骤。

图2-6 GP个体的树状表示法

表2-1 针对符号回归问题的GP预备步骤

对于此类问题（或个别其地问题），确认函数集和终止符集一般来说很简单。但是对一些问题，函数集可能不仅仅包括算术函数的加法、减法、乘法和除法，而且还包括额外分支操作的设置。终止符集可能包括程序的外部输入（独立变量）和数值常数。对于许多其他的问题，它们包括专门的函数集和终止符集。例如，如果目标是让遗传编程自动生成一个让机器人打扫满是障碍物的房间的程序，程序员必须告诉遗传编程什么是机器人能够做的。举例来说，机器人可能要能够执行一些功能，诸如移动、转弯和挥动拖把。如果目标是自动创建一个控制器，其函数集很可能包括积分器、微分器、引线、延迟、增益、加法器、减法器和相似物。终止符集可能包括参考信号和设备的输出。如果目标是自动建立一个模拟电路，函数集可能要让遗传编程能够用给定的元件组成电路，这些元件如晶体管、电容器和电阻器。一旦程序员确定了原始成分，就可以用于电路合成的问题。同样的函数集能够运用于自动合成一个放大器、计算电路、有源滤波器、电压参考电路或者通过这些元件构成的其他电路。(www.xing528.com)

第三个准备步骤关注的是如何评价进化个体的适应度，即引导进化的标准。这个适应度首要的机制是能够引导进化朝着进化目标前进。例如，如果进化目标是让遗传编程自动合成一个放大器，这个机制的适应度就会告诉遗传编程去合成一个放大传入信号的电路（如果相反，就会合成一个抑制低频率的信号传入的电路或是计算传入信号的平方根的电路）。前两个准备步骤定义搜索的空间，而适应度指出了搜索的预期目标。

第四个准备步骤主要是设定程序运行所需要的一些基本的参数，如进化种群的大小、遗传操作的概率、表示树的最大与最小深度等。

第五个准备步骤包括指定程序进化的终止标准。这个终止的标准可能包括一个运行的最多的后代数以及一个具体问题的成功判断。在实践中，当能够成功地产生一个最优的个体时适应度达到稳定的状态时终止进化。

一般而言，在程序员对问题的准备步骤完成之后，GP算法的流程图如图2-7所示，形式化描述如下：

1）在第0代，随机生成初始群体，其中个体是由表示问题的函数结点和终结点随机组合的计算机程序。

2）计算种群中个体的适应值。

3）按一定的策略对群体执行遗传操作，即采用复制、交叉和变异等遗传操作，产生一个新的群体。

4）如果满足终止标准，则结束进化，输出问题的正确解或近似解，否则转到步骤2）。

在遗传编程程序运行过程中，程序员是不能任意干预和影响的（虽然程序员可行判断运行是否终止）。

图2-7 GP的流程图

遗传编程以具有能够解决问题的函数和终止符组成的胚胎作为进化的开始（也称为个体）。原始种群由一组胚胎组成。

每一个种群中的个体程序执行完后，每一个种群中的个体程序就要和现有的同组个体进行衡量或比较（运用第三个准备步骤中提供的适应度）。对于所有问题，对个体运用事先定义好的方法测定产生的一个准确的数值，称为个体的适应度。个体的适应度的测定有很多不同的方式，例如：按照实际输出和预期要输出的差错量来确定，按照一个系统要求的时间和期望的目标状态。程序的执行有时会返回一个或是更多个直接的值。换句话说，程序的执行结果可能只包括对现实世界状态的没有用的值，也可能会返回有用的值。另外，执行此程序也可能会返回有用的值。对于许多实际的问题，衡量适应度有多方式，一般结合两个或更多不同的方式。

事实上，原始随机种群的创建是一个搜索空间的盲目随机搜索。第0代的个体程序一般具有很差的适应度，但也有可能存在一些具有潜力的个体。遗传操作包括交叉（两性重组）、突变、复制和变结构操作，用户可以根据需要只选择其中的一部分，应用合乎进化的选择策略、交叉方式与变异操作。这些遗传操作应用于那些依据适应度从原有种群中挑选出来的个体。在这些随机的选择过程中，优良的个体超过劣等的个体。不过，种群中最优良的个体并不一定被选择，种群中最低劣的个体也有可能被选中。当这些遗传操作在现有的种群中执行完以后，子种群（即新的种群）取代了现有的种群（即老种群）。

当进化达到终止的标准（第五个准备步骤中给出）后，遗传编程的运行才会停止。运行结束时搜索到的最优个体通常就是问题的解。