进化计算中的适应度函数

进化计算是模仿生物界芸芸众生在无限多样的纷繁环境中生灭、繁衍(凋亡)、发展(退化)的仿生计算技术。按照达尔文的进化学说,生物能否在宏观上朝正方向进化,取决于生物与环境的适应程度,即生物体能否在与环境组成的共同系统中充分利用环境的资源,有效消除环境的不利影响,在共同系统中可持续地发展。因此,与环境的适应程度是决定进化方向性的重要因素。实践证明,与环境的适应程度的界定十分复杂,有些种群在发展的初期能够很好地适应环境,然而当环境发生变化后,原先适应环境的特征却演变为与环境对立的阻碍共系统(co-systems)维系的瓶颈。又如一些种群的某些性征,其生存发展是以破坏环境资源为代价的,这种破坏在其行为发展的初始状态是能够保持共系统的平衡态势且有助于种群的进化,但当破坏行为达到或突破平衡态的容忍极限时,适应性发生逆转,共系统的关系由相生转化为相克,导致种群面临危机。凡此种种,说明适应性具有如下特征:

(1)决定性:适应程度决定了种群能否繁衍,能否导致产生有利于正向进化的性征出现。

(2)动态性:不同时刻同一性征对环境表现出的适应并不相同,在某些情形下甚至会出现相反的结果;另外,当性征导致共系统出现平衡失稳时,适应性发生逆转。

(3)环境依赖性:种群的某些性征对于不同环境的适应性相差迥异,在某些特定环境下高度适应的种群,在环境发生变化时可能出现难以生存的情况。

作为模拟生物系统的仿生计算工具,进化计算中同样面临着刻画解与所处变量空间能否适应的问题。应该说这个问题在某种程度上是进化计算的核心,它决定了进化计算的方向——其他的所有调整(复制、交叉、变异、移民等)都是基于对解点对变量空间(环境)适应程度的评价做出的。因此,适应度函数的构建是一件十分重要的工作。

从文献来看,研究者对适应度函数的研究开展的相对较少[9－11],且现有的研究往往多考虑局部的适应性,而较全面的较系统的工作很少。从这一意义上而言,适应度函数的构造这一重要课题被长期的忽略了。就已有的研究文献而言,研究者虽然根据某些情况,基于某种考虑,开展了一些研究,但尚未对适应度函数作出全面深刻的分析,因而难以面对众多层出不穷、变幻无常的寻优问题。下面作者试图在此方面开展一些工作。

本节适应度函数类的构建主要针对如下问题:

上述问题对X的取值无连续的要求,并且目标函数的表达式有可能不明确(如只知道输入输出数据对的动态系统参数优化问题)。下面作者应用在多目标决策研究中提出的定性定量指标规范化的思路方法[12,13,14],讨论构造单个目标函数适应度函数、多目标适应度函数集结等问题。

2.3.1　单个目标函数适应度函数的基本类型

设C 1、C 2分别为自变量取最小、最大值时的适应度(若为多目标情形,C 1、C 2可不尽相同;同时,关于C 1、C 2的选取,须由人工完成——通常可设C 1、C 2∈[0,1],而且可随着进化进程的改变作相应调整,即C 1、C 2有时可能具有动态性。);个体原始值为f(x)(不失一般性,本节图中假设f(x)≥0),适应度为y;max{f}、min{f}分别表示当前代目标最大及最小值。

2.3.1.1　适应度是个体原始值的递增函数时的基本函数类型

1)直线型适应度函数(如图2.3所示)

特点:适用于个体原始值在不同起点等量变化,适应度值也等量变化的情形。其一种函数表达式如下:

2)减速优型适应度函数(如图2.4所示)

特点:适用于适应度值的增速随个体原始值的提高递减的情形(即难度随原始值的提高递减的情形)。其一种函数表达式及有关参数如下:

其中,由y(max{f})＝c 2可得

图2.3　直线型适应度函数

图2.4　减速优型适应度函数

3)加速优型适应度函数(如图2.5所示)

特点:适用于适应度值的增速随个体原始值的提高增加的情形(即难度随原始值的改进增加的情形)。其一种函数表达式及有关参数如下:

4)变趋势型(1)适应度函数(如图2.6所示)

特点:适用于适应度值的增速随个体原始值的增加先递增后递减的情形,即难度随个体原始值的改进先递增后递减的情形。如控制系统的上升时间指标(可用速率表征),若达到一定程度后再作进一步改进意义不大,原因是太快以后会影响其他控制品质;当快到危害整体性能时,适应度函数的单调性将不复存在。其一种函数表达式及有关参数如下:

图2.5　加速优型适应度函数

图2.6　变趋势型函数(1)

5)变趋势型(2)适应度函数(如图2.7所示)

特点:适应度值的增速随个体原始值的增加先递减后递增的情形,即难度随个体原始值的改进先递减后递增的情形。

其一种函数表达式及有关参数如下:

2.3.1.2　适应度是个体原始值的递减函数时的基本函数类型

1)直线型适应度函数(如图2.8所示)

特点:适用于个体原始值在不同起点等量变化,适应度值也等量变化的情形。其函数表达式及有关参数如下:

图2.7　变趋势型函数(2)

图2.8　直线型适应度函数

2)加速优型适应度函数(如图2.9所示)

特点:适用于适应度值的增速随个体原始值的减小而增加的情形,即难度随原始值的改进增加的情形。其一种函数表达式及有关参数如下:

3)减速优型适应度函数(如图2.10所示)

适用于适应度值的增速随个体原始值的减少递减的情形(即难度随原始值的改进递减的情形)。其一种函数表达式及有关参数如下:

图2.9　加速优型适应度函数

图2.10　减速优型适应度函数

4)变趋势型(1)适应度函数(如图2.11所示)

特点:适用于适应度值的增速随个体原始值的减小先递增后递减的情形(即难度随指标原始值的减小先递增后递减的情形)。其一种函数表达式及有关参数如下:

5)变趋势型(2)适应度函数(如图2.12所示)

特点:适用于适应度值的增速随个体原始值的减小先递减后递增的情形(即难度随指标原始值的改进先递减后递增的情形)。其一种函数表达式及有关参数如下:

图2.11　变趋势型函数(1)

图2.12　变趋势型函数(2)

2.3.1.3　适应度是个体原始值的非单调函数时的基本函数类型

对应于这种情形,有如下几种子情形及相应处理方式:

(1)目标定为“适度”、“均衡”等时,适应度函数以中间某区域(或退化为一点)为优。此时适应度函数形态呈现山峰状。其表达式由情形1和情形2中的表达式集结而成。

(2)目标定为远离“指定区”时(如结构设计中的共振易发频段、控制系统中的震荡或发散区等),适应度函数以远离中间某区域(或退化为一点)为优。此时适应度函数形态呈现山谷状。其表达式同样由情形1和情形2中的表达式集结而成。

需要说明的是,由于问题的复杂性,上述两种子情形中经集结而成的表达式往往不一定具有对称性。

2.3.2　多目标适应度函数

在单目标适应度函数确定后,可利用多目标决策的理论与方法对单目标适应度函数进行集结。这里仅给出两种简单方法:

(1)若各目标线性独立,则可用加权和法将各单目标适应度函数集结成多目标适应度函数:

上式中的w k,y k(k＝1,…,n)分别是第k个目标的权重和适应度函数。上述方法的关键在于确立目标无关性和权重。

(2)若各目标不满足线性独立,可用逼近于理想解的排序方法(TOPSIS法)。即借助于一多目标决策问题的“理想解”和“负理想解”去排序[15]。这里所谓理想解是一设想的最好的适应度向量,它的各个适应度分量都达到最优,而一负理想解是另一设想的最坏的适应度向量,它的各个适应度分量都达到最劣。然后应用实际适应度向量与理想解、负理想解的相对加权距离作为衡量适应的标准。具体算法见文献[15]。

关于多目标决策中集结各单目标求非劣解或排序,还有许多方法,这里限于篇幅,不再详述。

评价个体对不断变化的环境的适应程度是一个十分复杂的问题,决不能简化从事。作者提出的适应度函数类的构造,是这方面的有益尝试。它为正确应用进化计算解决多目标优化或决策问题提供了一条思路。