基于最小熵产生选择策略的遗传算法研究

高 晶 李元香 纪道敏 项正龙

(武汉大学计算机学院 湖北 武汉 430072)

0 引 言

遗传算法是由美国的Holland教授于1975年首先提出的一种借鉴达尔文的“优胜劣汰，适者生存”生物进化理论的随机优化算法[1]。它是一种启发式搜索和优化技术，可直接对结构对象进行操作，不需要对目标函数的连续性进行限定。主要特点是整个求解过程从群体出发，具有较高的鲁棒性和全局搜索能力，对优化问题的领域没有局限性，可扩展性强[2]。遗传算法被证明非常适合于高度非线性问题的优化，可以在复杂的多维搜索空间中找到全局最优解，在许多问题中都得到了广泛的应用，如背包问题、旅行商TSP问题、n皇后问题[3]等。近年来，从简单的PID控制，到复杂的最优控制[4]、自适应控制[5]等工程控制问题，遗传算法都有着较为成功的应用案例。现如今，随着人工智能热度的上升，遗传算法再次成为研究的热点，遗传算法等演化算法和人工智能相结合，可进行自然灾害的评估[6]、建立医学药物剂量预测模型[7]、规划最优路径[8]等。

遗传算法虽然应用广泛，但在解决较为复杂的问题时，由于它本身的随机搜索特点，依然存在收敛速度慢和过早收敛两方面的困扰[9]。Whitley[10]提出遗传算法中最重要的两个因素是“选择压力”和“种群多样性”。近年来，很多学者在遗传算法缓解“选择压力”、增加“种群多样性”上做了很多研究。Alabsi等[11]使用了稳态替换策略来缓解选择压力；王丽萍等[12]提出了角度惩罚距离精英选择策略防止精英选择产生过大的压力；Zhang等[13]通过适应度共享创造小生境进化环境，以此增加种群多样性；Li等[14]将遗传算法中的种群视为一个动力学系统，个体视为粒子，遗传操作视为离子的碰撞或移动，驱动所有粒子尽可能地运动来保持种群多样性。已有方法从多个角度缓解选择压力，从而保持种群多样性，但是，它们大多都是直接将函数适应值作为评价函数，这样很难从根源上缓解选择压力从而提高种群多样性。

为了解决直接将函数适应值作为评价函数而导致的选择压力过大问题，本文将函数适应值通过种群中的个体密度转化为群体熵产生，通过驱使群体熵产生最小从而求得最优的函数适应值。本文将遗传算法中的种群视为被外界强加固定压力的非孤立系统，种群在进化的每一代都看成非平衡定态。将物理学中最小熵产生[15]的概念引入到遗传算法中，利用非孤立系统在非平衡定态[16]下遵循最小熵增原理，对传统遗传算法的选择策略进行改进，提出了一种基于最小熵增原理的选择策略。在该策略中，采用个体密度来衡量种群多样性，用精英策略驱动种群朝熵产生[17]最小的方向快速下降。最后在背包问题和数值优化问题上验证了这种选择策略的有效性。

1 遗传算法和最小熵增原理

1.1 遗传算法

遗传算法是一种启发式算法，来源于达尔文的生物学原理，最早是由John Holland 引入的，为了解释自然系统的适应性过程，以及在类似基础上产生的人工系统。在自然界中，新生物通过进化来适应环境，遗传算法用类似的方式演化出给定问题的解。

为了得到优化问题的解决方案，遗传算法的流程如下：

1) 确定编码方式，初始化n个随机编码染色体的种群；

2) 计算种群中每个个体的目标函数，对个体进行评价；

3) 根据个体适应值，从种群中选择个体(一般适应值越好被选中的可能性越大)进行繁殖；

4) 交叉操作；

5) 变异操作；

6) 产生m个新个体；

7) 从m+n个个体中选择适应值最优的n个个体作为下一代种群；

8) 当满足最后的终止条件时，输出整个过程中找到的最优解，没达到终止条件时，重复2—7。

遗传算法以生物进化为原型，和传统的优化方法(枚举、启发式等)相比，整个求解过程从群体出发，具有较高的鲁棒性和全局搜索能力，能并行搜索多个峰值；求解过程和最终结果和问题领域以及初始化无关；使用概率机制进行迭代，具有随机性；算法具有较强的可扩展性，能灵活地和其他算法和策略进行融合，适合于求解复杂的优化问题。

1.2 最小熵增原理

一个孤立的热力学体系，随着内部粒子的自由运动，不论其初始处于何种状态，最终总会达到平衡状态。达到平衡状态后，体系的熵为极大值，最终体系中可以引起熵增的所有热力学流和热力学力均为零。但如果不是孤立体系，环境对体系施加某种限制。如保持一定的温度差或浓度差等，这时，体系不可能达到热力学平衡态。如果外界施加的条件是固定的，如一定的温度差或一定的浓度差，体系开始会因外界的限制条件而发生变化，但最后会达到一种相对稳定的状态，这种状态被称为非平衡定态。

熵产生是非平衡态热力学中非常重要的物理变量，在Prigogine等[18]提出的耗散结构中，把热力学第二定律由封闭体系推广到了敞开体系，把熵变分为了两个部分：(1) 由体系与环境的相互作用(物质和能量交换)而引起的，称为熵流；(2) 由体系内部的不可逆过程产生的，称为熵产生。熵产生的表达式为：

(1)

式中：Jk表示第k种不可逆过程的流；Xk表示第k种不可逆过程的推动力。

非平衡定态具有一些特殊的性质，Prigogine在1945年提出了非平衡定态的最小熵增原理：在接近平衡的条件下，与外界强加的限制相适应的非平衡定态的熵产生具有极小值。

2 最小熵增原理在遗传算法上的应用

2.1 热力学系统与遗传算法

借鉴热力学系统在趋于非平衡定态的过程中熵产生的变化规律，将遗传算法中的种群类比为加了固定压力差的热力学系统，两者之间的对应关系如表 1所示。

表1 热力学系统与遗传算法对应关系

2.2 改进的遗传算法

2.2.1原理描述

基本的遗传算法通过选择、交叉和变异从父代中生成子代，直接选取适应值最好的个体作为下一代种群。本文提出基于最小熵增原理的遗传算法(Minimum Entropy Production Genetic Algorithm, MEPGA)就是把非平衡定态下的熵产生最小的原理应用到遗传算法中新种群的选取中，以保证种群的多样性。其基本原理如下：用个体密度衡量种群多样性，当种群的多样性过低时，利用贪婪选择策略，从新产生的子代和父代个体中选择使群体熵产生最小的新种群作为下一代种群，以此来保证种群多样性，从而有利于跳出局部最优。

改进的遗传算法MEPGA的基本流程如下：

1) 确定编码方式，产生初始种群，设置种群大小N、进化代数、交叉变异概率等。

2) 对种群中的个体进行评估(计算个体的适应度值、计算个体的密度)。

3) 采用轮盘赌方法从父代种群中选择产生子代的个体。

4) 对选出的个体进行交叉、变异操作，产生M个子代。

5) 对M+N个个体先使用精英保留策略选取n′个适应度值最好的个体，然后对剩下的个体使用贪婪选择机制，逐个往n′个个体中加入剩下的个体，直到个体数达到N，始终保持种群的熵产生最小。

6) 判断是否达到迭代终止条件，迭代结束输出最优解个体和最优解值，否则重复2—5。

求解流程如图 1所示。

图1 改进的MEPGA流程图

2.2.2个体密度和群体熵

群体熵产生计算公式最终可转化为密度变化的计算，因此首先需要对群体中个体的密度进行定义。

定义1(绝对适应值)设S为搜索空间，f:S→R为目标函数，Xi是种群中的第i个个体。当求解的是最大优化问题时，e(Xi)=-f(Xi)；当求解的是最小优化问题时，e(Xi)=f(Xi)。

借鉴等级熵[19]的划分方式，对活跃窗口和等级进行如下定义：

定义2(活跃窗口)设Pt=(X1,X2,…,XN)∈SN为基于最小熵增原理遗传算法的第t代种群，Ot=(XN+1,XN+2,…,XN+M)表示由第t代种群产生的M个子代个体。第t代种群的活跃窗口wt由如下规则生成：1)w0=[l0,u0]，l0是初始种群中绝对适应值的下限，u0是初始种群中的上限。2)wt=[lt,ut]表示第t代的活跃窗口，wt+1=[lt+1,ut+1]表示第t+1代活跃窗口，其中lt+1=min(lt,min(e(Xj))),j∈(N+1,N+M)，ut+1=max(ut,max(e(Xj))),j∈(N+1,N+M)。

本文提出的基于最小熵增原理的遗传算法直接对活动窗口进行固定的均匀划分，划分份数为常数K，则种群在第t代第j个区间的范围可表示为：

根据Prigogine对热力学第二定律的推广，非孤立系统的熵产生是系统内各种流和产生这种流所对应力的乘积之和。对于一个两组分体系，在体系两端保持一定的温度差，由于热扩散现象，会引起体系的浓度差，此时体系中同时存在两种力：X热与X扩，和两种相应的流：J热流和J扩散流，所以熵产生可表示为：σ=J热流X流+J扩散流X扩。

当本文讨论的体系达到不随时间变化的非平衡定态时，热流J热流等于零，因此熵产生可表示为：σ=J扩散流X扩，扩散流的产生源于体系粒子密度的变化，压力导致密度差，因此对群体的熵产生可定义如下：

(2)

式中：ρi表示个体Xi的密度；ρ0是初始种群的个体密度均值；k是热力学中的常量。

2.2.3基于最小熵增原理的贪婪热力学替换

从父代种群Pt=(X1,X2,…,XN)的N个个体与产生的M个子代种群Ot=(XN+1,XN+2,…,XN+M)，共N+M个体中挑选出N个个体组成下一代种群Pt+1，使其具有的熵产生σ(Pt+1)最小。

按照贪婪的策略[22]逐个往下一代种群中填充使临时种群熵产生最小的个体，具体的算法实现如算法1所示。

算法1基于最小熵增的贪婪热力学替换

输入：第t代父种群Pt，第t代子种群Ot

输出：第t+1代种群Pt+1

1) 将父种群Pt和子种群Ot合并得到大小为N+M的中间种群P′t + 1

2) fori=1 toN

//采用贪婪策略逐个往Pt+1中填充个体，直到N个

3) forj=1 toN+M-i

//寻找本轮最优的个体

4) 计算将P′t + 1中的第j个个体加到Pt+1后的熵产生σ(Pt+1∪P′t+1[j])

5) 记录本次循环中使熵产生最小的个体Xj

6) end

7) 将个体Xj填充到Pt+1中，同时将其从中间种群P′t + 1中移除

8) end

2.2.4基于最小熵增原理的遗传算法

以上个体密度、群体熵产生和基于最小熵增原理的替换规则是本文改进遗传算法的主要构成部分。它们保证了种群能在保持一定多样性的前提下快速向群体熵产生最小的方向进化。本文提出的算法称为基于最小熵产生的热力学遗传算法，算法2给出了本文算法的主要流程。

算法2基于最小熵增原理的遗传算法(MEPGA)

输入：搜索空间和目标函数

输出：最优解

1) 确定个体编码，设置交叉和变异概率Pc和Pm，区间划分等级数K，迭代次数T

2) 随机生成N个个体作为初始种群P0，对P0中的个体进行评估

3) 计算初始活跃窗口w0

4) fori=0 toT

5) 通过轮盘赌从Pi中选择父代个体进行交叉、变异产生M个子个体

6) 评估M个子个体

7) 更新活跃窗口得到wi+1

8) 计算种群中个体的密度分布状况

9) 利用基于最小熵增的贪婪热力学选择机制，从N+M个个体中选择N个个体作为Pi+1

10) end

11) 将迭代过程中得到的使目标函数最优的个体作为最优解输出

上述算法中初始化时需要设置的参数和基于模拟退火的遗传算法[20]相比减少了温度，从而在迭代过程中也就不需要设置相关的冷却进度表[21]，简化了进化过程中参数的设置。为了平衡“选择压力”和“种群多样性”之间的关系，本文算法使用了种群中个体密度的分布对种群多样性进行度量，只有当种群多样性较低时才使用基于最小熵增的贪婪热力学选择机制进行后代的筛选，控制群体向熵产生最小的方向进化，以保证种群的多样性。

3 实 验

为了验证基于最小熵增原理遗传算法的适用性，并且希望通过实验获得该方法的进一步改进和推广思路，本文选取了几个典型的测试问题进行了实验验证，主要包括0-1背包问题和数值优化问题。除了本文提出的算法，主要对比的算法有简单遗传算法(Genetic algorithm, GA)、稳态遗传算法(Steady state genetic algorithm, SSGA)和小生境遗传算法(Niche genetic algorithm, NGA)。

3.1 测试函数和参数设置

数值优化问题选取了8个数值优化测试函数，分别是经典的测试函数Sphere函数、Rosenbrock函数、Rastrigin函数和Ackley函数，以及CEC 2013测试函数集[23]中的9、15、25和26号函数，分别记为f2、f3、f4、f5、f6、f7、f8、f9，这其中有单峰函数、多峰函数、多模函数和组合函数。表2为8个数值测试函数的表达式/名称和变量取值范围。

表2 数值优化测试问题

本文实验中运用第2节中描述的基于最小熵增原理的遗传算法，交叉概率Pc=0.9，变异概率Pm=0.2。对0-1背包问题f1分别选取50和100个物品个数进行实验验证。对数值测试函数分别在10维和20维下进行测试。每个测试问题都在上述参数设置下独立运行50次，取每次运行结果的平均值作为最终求解结果。

3.2 实验结果分析

将四种算法在相同参数下对不同的测试问题、不同的测试问题维度，独立运行50次，分别从最优解均值和最优解方差两个方面来对这两种算法的性能进行对比，最终的统计结果如表3所示。

表3 算法在背包问题上的结果统计

可以看出，MEPGA算法所求的最优解均值和方差在这四个算法中都占据优势，可见算法在寻找简单背包问题的求解上有一定改进效果。

表4为四种算法在数值函数问题中的测试结果，分析统计结果可知，MEPGA算法在所测的大多数数值函数问题上最优解的均值和方差都能得到较好的结果，在少数多峰多模问题上结果和改进的遗传算法(SSGA、NGA)没有明显优势，但比简单遗传算法(GA)所得结果好。所选测试问题覆盖范围广、有一定代表性，因此可以说明本文算法改进策略的有效性。

表4 算法在数值函数测试的结果统计

续表4

通过多次运行后的统计结果分析，本文中提出的算法在离散问题、数值优化问题(包括单峰、多模、组合函数等)上大多都能获得较好的结果，相较简单遗传算法(GA)而言，结果有了很大的改善。在少数测试函数上的处理结果和改善后的稳态遗传算法(SSGA)、小生境遗传算法(NGA)不分伯仲，但多数情况下还是比这两种算法效果要理想。由此可见，本文提出的选择策略在一定程度上能改善种群在进化过程中的选择压力，从而能够找到更好的解。

以下随机选取了实验过程中比较有代表性的几个测试问题在不同纬度下的收敛曲线图。图 2中分别是GA、SSGA、NGA和MEPGA在物品数n=50和n=100时的最优点的变化趋势。

图2 f1 最优点变化趋势

由图2中最优点的变化趋势来看，不管物品数是50还是100，MEPGA算法找到的最优解和其他三种算法相比更有优势，说明基于最小熵增原理的遗传算法在改进背包问题上是可行的而且能保持较好的种群多样性，能有效地跳出局部最优解从而搜索到全局最优解。

图3和图4是本文提出的算法和GA、SSGA、NGA分别在10维和20维的f6～f9数值测试函数上最优值的收敛轨迹。可以看出,MEPGA在数值测试问题上也有较明显的效果，而且比简单遗传算法(GA)、改进遗传算法(SSGA、NGA)搜索到的最优值更好。

图3 f6 ～f7测试函数 问题维数n=10

图4 f8 ～f9测试函数 问题维数n=20

从整体的实验效果来看，MEPGA在组合优化问题，单峰、多峰、多模、组合等数值优化问题上都有一定的适用性。从统计结果中四个算法运行的最优值均值可以看出，本文算法在大多测试函数上都能找到比其他算法更优的解，这很好地说明了本文的改进在一定程度上缓解了种群在进化过程中的选择压力，从而能更好跳出局部最优找到更优的解。统计结果中的最优值方差则反映了本文的改进策略具有更高的鲁棒性。

4 结 语

针对遗传算法在搜索过程中由于选择压力过大导致种群多样性丧失，从而容易陷入局部最优的问题，本文将热力学非平衡定态下的最小熵增原理应用到遗传算法的选择策略中，提出了一种基于最小熵产生的选择策略，能在种群快速收敛的同时保持种群的多样性，进而跳出局部最优。实验表明，改进后的算法MEPGA在0-1背包问题和单峰、多峰数值优化问题上均能得到比GA和改进的遗传算法更好的结果。这说明基于最小熵增原理的选择策略在缓解选择压力、保证种群平稳进化上是有一定效果的。由于本文使用的是贪婪选择机制，因此计算时间复杂度比较高。本文的后续工作将着重研究算法计算效率的改进，对基于最小熵产生原理选择策略做进一步完善。同时本文只是将基于最小熵增原理应用于简单的遗传算法，验证该策略的可行性，后续将尝试将该策略推广到其他演化算法，进一步验证本文中所提出改进策略的普适性。