齐 战,李茂军,莫 红,肖雨荷,刘 芾

(长沙理工大学电气与信息工程学院,湖南长沙 410114)

1 引言

进化算法是受生物进化和遗传过程启发的一种自组织、自适应的人工智能技术,是解决工程技术中组合优化问题的一种智能算法,在线性、二次、强凸、单峰或其他特定领域中求取给定问题的最优解[1].遗传算法(genetic algorithm,GA)、粒子群优化算法(particle swarm optimizer,PSO)、差分进化(differential evolution,DE)、遗传编程、社会学习算法和化学反应算法等都是常见的进化算法,然而进化算法存在早熟收敛等问题,在许多优化问题中表现不佳[2],因此许多学者通过定义并行计算模型[3]、混合算法[4]等来设计更有效的进化算法.

基于状态空间模型遗传算法(genetic algorithm based on state-space model,GABS)是李茂军教授在文献[3]中正式提出的一种新型进化算法,具有参数设置少、操作简单、搜索能力强、计算精度高和收敛速度快等特点.符宏艳等[5]利用GABS有效地解决了电力市场竞价问题,跟GA相比能更快的搜索到最优解.李雪等[6]将GABS应用于公交调度问题,仿真结果表明GABS优化效果比GA更好.虽然该算法应用效果较好,但是该算法的全局收敛性未得到严密的数学分析.王鼎湘等[7]利用齐次有限马尔可夫链对GABS进行分析,得到了GABS不具有全局收敛性的结论,并提出一种通过改进GABS的状态进化矩阵来确保算法具有全局收敛的方法,但这种改进方法在每一次迭代时都需要更新状态进化矩阵,而文献[5]和文献[8]仿真结果表明,在状态进化矩阵不变的情况下算法也有很好的寻优效果.

状态进化矩阵是种群进化的关键操作算子,相比于状态进化矩阵每一次迭代都需要更新的情况,状态进化矩阵固定不变显然减少了算法搜索的计算量.本文通过分析GABS在状态进化矩阵固定不变情况下的寻优过程,为算法建立吸收态马尔可夫过程模型,从可达状态集的角度证明了GABS不具有全局收敛性.基于此提出了一种改进的状态空间模型遗传算法(modified GABS,MGABS),最后证明并验证了MGA BS具有全局收敛性.

2 问题描述及GABS

可以将连续域内的一个实数优化问题描述为

GABS是一种基于状态空间模型的实数编码进化算法,引入进化算法的基本思想[3]:上一代种群通过状态进化矩阵的作用产生新的种群,新种群和上一代种群再通过优胜劣汰的选择操作生成下一代种群,整体上使下一代种群更接近问题的最优解.算法通过不断迭代,使种群中的个体不断朝最优解方向进化,最终得到问题的最优解或次优解.新种群的构造算法表达式如下:

式中:X(k)表示第k代种群,它是一个N ×L的矩阵,该矩阵的每一行表示一个个体,每个个体包含L个决策变量,即种群规模为N,实数编码长度为L,将初始种群记为X(0);G是状态进化矩阵,其构造方式如下:

利用GABS求解式(1)所描述问题的步骤如下:

步骤1在可行域内随机生成种群规模为N的初始种群X(0);

步骤2依据式(3)生成状态进化矩阵G;

步骤3依据式(2)来产生新的种群X(k+1),将X(k+1)与X(k)结合形成选种池;

步骤4计算选种池内所有个体的适应度;

步骤5在选种池内选取适应度最高的N个个体组成下一代群体X′(k+1),置X′(k+1)为X(k);

步骤6满足终止条件,转步骤7,否则转步骤3;

步骤7算法终止.

3 GABS随机过程及模型

GABS进化搜索与选择操作的求解过程,从本质上可以视为X(k)的状态随机变化过程.GABS属于连续优化算法,因此,为GABS建立状态连续变化的随机过程模型,下面给出定义[9].

定义1GABS在第k次迭代的种群记为X(k),称为GABS对应的随机过程.状态空间Y满足∀X(k)∈Y.

定理1GABS所对应的随机过程(∀X(k)∈Y)具有马尔可夫性.

证GABS的状态进化矩阵G固定不变,由第k代种群X(k)与G相乘产生新种群X(k+1),从X(k)与X(k+1)形成的选种池中筛选出适应度高的个体组成下一代种群X′(k+1).故满足∀Y1⊆Y和k=0,1,2···,有P{X′(k+1)∈Y1|X(0),···,X(k)}=P{X′(k+1)∈Y1|X(k)}.因此,在第(k+1)代的状态X′(k+1)仅由第k代的状态X(k)所决定,即具有马尔可夫性. 证毕.

定义2给定来自状态空间Y的随机过程,Y ∗称为最优状态空间,满足Y ∗⊂Y,而且对于∀X∗(k)∈Y ∗至少有一个解x∗∈X∗(k)是优化问题的最优解.

为了解决GABS 是否具有全局收敛性的问题,引入吸收态马尔可夫过程的定义[10-11].

定义3给定一个马尔可夫过程(∀X(k)∈Y),Y ∗⊂Y为最优状态空间,若P{X′(k+1)/∈Y ∗|X(k)∈Y ∗}=0 (k=0,1,2,···),则称为吸收态马尔可夫过程.定义3说明吸收态马尔可夫过程一旦达到了最优状态空间,即X(k)∈Y ∗,那么便一直停留于最优状态空间.精英保留策略对改进进化算法的全局收敛能力具有重大作用,许多具有精英保留的进化算法是全局收敛的[12-13],这些算法都可以建模为吸收态马尔可夫过程.GABS选种池的选择操作是将上一代种群和新种群中的最优个体选择出来作为下一代种群,自然在每次迭代中保留了当前最优解,因此定义3的模型同样适用于GABS.

定理2GABS对应的随机过程为吸收态马尔可夫过程.

证GABS选种池内的选择操作将上一代种群和新种群中的优秀个体选择出来作为下一代种群,因此每一次迭代的最优个体都会被选择并复制到下一代.所以,GABS一旦在第k次迭代后搜索到最优解x∗∈X(k),那么第(k+1)次迭代的种群X′(k+1)中也包含最优解x∗,即x∗∈X′(k+1).由定义2 可知X(k)∈Y ∗,X′(k+1)∈Y ∗,那么可得P{X′(k+1)/∈Y ∗|X(k)∈Y ∗}=0.由定义3知满足吸收态马尔可夫过程性质. 证毕.

若GABS在第k次迭代达到最优状态空间,表示算法搜索到了问题的最优解,若=1,表示算法可以迭代无穷多次后收敛于最优状态空间Y ∗,引入GABS全局收敛的定义[11].

GABS突破传统进化算法的计算模式,通过状态进化矩阵的作用产生新种群,搜索新的区域,再通过选择操作使得算法朝最优解方向搜索,最终搜索得到最优解或次优解.由于算法搜索方向的单一性和优胜略汰的选择操作使得算法收敛速度非常快,但同时也会存在缺陷,即种群中所有个体往最优解方向进化时,便缺少了个体间差异性,易陷入局部最优.

另外,由引理1知初始种群的上下界限制了后代种群的可达状态,使得后代种群可达状态在初始种群决定的某一确定的区间内,但此区间为可行域的子集,若全局最优解不在此区间内,那么种群中的个体永远不可能达到最优解的状态,由定理3知GABS不可能收敛到全局最优解.特别的,当全局最优点位于可行域的边界及其附近时,由于随机生成的初始种群的上下界区间为[αl,βl]可能是可行域[al,bl]的真子集,那么算法就不可能搜索到位于可行域边界的全局最优解,所以GABS 不具有全局收敛性,导致了GABS 的寻优结果不稳定,这是算法的另一个弊端.

综上,算法是否能搜索到理论最优完全取决于迭代时的全局最优位置及初始种群的状态分布,而且算法易陷入局部最优.

4 MGABS及其全局收敛性

从可达状态集角度得到GSBS不具有全局收敛性,因此针对此算法提出一种特殊变异机制,改进思想是:使得算法在迭代前期扩张GABS的可达状态集,无论全局最优解在可行域任何位置,算法能够达到最优状态,且在迭代后期提高算法的收敛精度.提出两种变异策略:

1) 随机选出P个适应度差的个体并平均分成两组(若不能均分可将多余个体分到第2组),再将这两组个体的每一位决策变量分别转移至式(4)指定区间的随机位置.具体操作如下:的随机数,m=1,2,···,P,l=1,2,···,L.

设总迭代次数为K,当k≤时,采用策略1),否则采用策略2).在算法迭代前期适用式(4),即在区间内随机生成的两组个体分别代替适应度差的两组个体,扩张了算法的可达状态集,同时提高了搜索范围和种群多样性,避免算法陷入局部最优.在算法迭代后期适用式(5),提高了种群朝最优解搜索的速度,因此提高了算法的收敛精度.

改进GABS的算法步骤如下:

步骤1在可行域内随机生成种群规模为N的初始种群X(0);

步骤2依据式(3)生成状态进化矩阵G;

步骤3依 据 式(2)产 生新的 种群X(k+1),将X(k+1)与X(k)结合形成选种池;

步骤4计算选种池内所有个体的适应度;

步骤5在选种池内选取适应度最高的N个个体组成下一代群体X′(k+1),置X′(k+1)为X(k);

步骤6从X(k)中选出适应度较差的P个个体,若k≤,采用变异策略1),否则采用变异策略2);

步骤7满足终止条件,转步骤8,否则转步骤3;

步骤8算法终止.

定义6通过以上步骤改进的GABS称为改进的状态空间模型遗传算法,简称为MGABS.

容易知道定义1-5 对于MGABS 都是适合的,定理1-2 对于MGABS 仍然成立.为了便于描述,称为MGABS对应的随机过程,称为MGABS在第k次迭代的可达状态集.

引理2MGABS对应的随机过程Y ∗为最优状态空间,则MGABS满足∃k′≥0,当k >k′时,∩Y ∗=∅.

引理3源于文献[14-15]研究进化算法时的类似结论,这里再次证明是为了给出算法全局收敛的一个判断准则.

定理4MGABS具有全局收敛性.

5 MGABS有效性验证

5.1 测试函数

为了更全面了解MGABS在解决各式各样问题上的性能,本文在不同的测试函数上测试MGABS,引入16个经典测试函数[16-17]进行测试与分析.这16个测试函数可分成3组,每组函数具有不同的特性,以充分测试改进算法的优化搜索性能.具体函数如表1所示,其中:x∗是全局最优点,f(x∗)是全局最小值.函数f1～f5设为第1组,函数f6～f10设为第2组,函数f11～f16设为第3组.

表1 16个测试函数Table 1 16 benchmark functions

第1组测试函数是De Jong研究函数优化问题时精选出来的5个测试函数,可全面检验改进算法的性能.第2组测试函数选取5个20维函数,其中函数f6,f7和f9是非线性多峰函数,具有许多个极小值点;函数f8,f10则是单峰函数.第3组测试函数是全局最优点位于可行域边界或边界附近的一组函数,其中函数f14,f15和f16的全局最优解位于可行域的边界上,通过第2节分析可知GABS不具备全局收敛性,是因为它难以搜索到全局最优点位于边界或者边界附近的函数的全局最优值,所以选取了6个此类函数来验证改进算法MGABS的全局搜索能力.

5.2 参数设置

为了充分验证MGABS的有效性和先进性,本文引入其他两个热门的全局优化进化算法:异构综合学习粒子群优化算法[18](heterogeneous comprehensive learning particle swarm optimizer,HCLPSO)和改进基于适应度的自适应差分进化算法[19](enhanced fitness-adaptive differential evolution algorithm,EFADE),两个算法的代码均在Suganthan教授的主页下载.本文所有算法均在MATLAB R2014a环境下进行测试.

GABS只有种群规模和进化代数(总迭代次数)两个参数,只需设置好这两个参数即可,因此将GABS和MGABS种群规模均设为50,进化代数均设为200.不管问题的复杂度和维度如何变化,种群规模和进化代数均不变化,以此来增加算法搜索难度.MGABS需要随机选择P个适应度差的个体并变异,P值将在下一节讨论.为了减少算法的运算时间,开始测试前依式(3)构造并生成状态进化矩阵再将之存储于内存,测试实验开始时从内存里调出即可.为了公平地比较4个算法的性能,将HCLPSO的粒子数设为50,进化代数设为200,最大适应度评价次数(the maximum number of function evaluations,FEs)设为10000.同将EFADE种群规模和进化代数也分别设为50和200,其他参数则默认.

5.3 变异个体数讨论

为了更好地平衡算法的搜索能力,变异个体数P为MGABS重要参数.MGABS种群规模为50,于是将P值设置为2,5,10,15,20,25,30,35和40.独立搜索16个函数中最具代表性的6个函数f1,f5,f9,f10,f11,f14各50次,比较平均值和方差,结果如表2所示.

表2 不同P值讨论Table 2 Discussion of differentP values

表2中可以看出,当P值较小时结果不理想,是由于算法陷入了局部最优;当P值太大时亦不理想,是变异个体太多影响了收敛的速度和精度.因此对所有函数而言,P值设为15～35时具有良好的计算结果.特别的,当P值设为20～30时,函数f1,f5,f9,f10的平均值和方差均优于其他的情况.当P值为15时函数f11的结果是最好的,而对于函数f14,P值为35时有较好的优化效果.综上,本文将P值设为25.

5.4 对比实验

为了减少算法搜索结果的随机性,对于每个测试函数,4种算法均要优化搜索50次,使用50次搜索的平均寻优值,4种算法寻优结果见表3.其中平均值表示50次搜索结果的平均寻优值,最小值则表示最小寻优值,方差表示50 次寻优值的方差,时间表示平均运算时间,单位为秒,准确率为50次搜索中找到最优解次数的比例(求解精度设为10-5).

表3 4种算法搜索函数的结果比较Table 3 Comparison of four algorithm search results

从表3可以看出,GABS与MGABS的平均运算时间远少于其他2个算法.这因为GABS与MGABS两个算法均利用式(2)进行种群的更新,也即利用矩阵乘法进行并行计算,由于MATLAB的矩阵运算是公认的非常准确、非常迅速,因此算法每一次迭代的运算时间非常快.而其他两种算法则需要在每一次迭代过程中依据其各自的更新策略对每个个体进行更新与选择,因此种群规模越大,其运算速度越慢,导致运算速度远不及GABS与MGABS.

第1组测试函数:从表3准确率可以看出,在求解精度为10-5的情况下,除了第4 个存在噪声的函数以外,MGABS,HCLPSO和EFADE均能搜索得到第1组函数的最优解,而GABS则表现较差.从平均值和方差的角度来看,EFADE结果比其他算法更优,说明其收敛精度是最好的,MGABS的表现比之稍稍逊色.在最小值比较中,MGABS和EFADE获得3次最好,GABS和HCLPSO获得2次最好,但GABS其他指标均较差,说明GABS搜索结果不稳定.比较4种算法的结果表明,EFADE对于第2个函数优化效果是最好的,但其运算时间也是最久的,MGABS则次之,但运算速度非常快.总之,MGABS在非常快的运算速度之下,仍具有较好的运算精度和准确率,HCLPSO与EFADE的运算时间比之多出一个数量级,因此其综合性能最优,但和其他3个算法一样,对函数f4的搜索结果较差,说明4种算法均不具备抗干扰能力.

第2组测试函数:对于所有函数而言,MGABS优化效果是最出色的,这归功于MGABS的变异策略2,尽管种群规模和进化代数较小,算法仍具有非常快的收敛速度和收敛精度,其他3种算法则陷入局部最优,搜索函数的结果不理想.因此,MGABS对此类复杂的高维非线性函数优化效果最明显.

第3组测试函数:从表3数据可以看出,MGABS对函数f12,f14,f15的优化效果较好,但由于原算法的限制(不具备全局收敛性),MGABS对其他3个函数的优化结果则略逊于EFADE,但相比于原算法GABS,其优化结果有了很大的改善,并且其运算时间远少于EFADE.可以通过增加种群规模进一步提高MGABS的性能,且运算时间不会有较大的提升.

6 结论

本文建立了基于状态空间模型遗传算法的数学模型,并从理论上分析了它的局限性,从而提出一种改进的状态空间遗传算法,并证明了其具备全局收敛性,测试结果同时也说明了改进算法的理论是正确有效的,改进的基于状态空间模型遗传算法表现出了运算速度快、收敛速度快、全局搜索能力强、计算精度较高、稳定性较好等特点,提高了算法的适应性,总体表现优于其他算法.本文算法最大的特性是运算时间短,具有较好的应用前景,下一步将研究此算法在实时系统中的应用.