M-精英协同进化分子动理论优化算法

范朝冬，章兢，易灵芝

(湘潭大学 信息工程学院，湖南 湘潭 411105)

1 引言

优化问题是科学研究和工程应用中的一个热点问题，寻求快速、稳健、有效的优化技术是各行各业长期探讨的课题，其中智能优化算法因实现简单、运算速度快、优化效果好，已引起国内外学者的广泛关注。依据原理的不同，现有的智能优化算法大致可分为3类：①基于遗传进化机制的优化算法，如遗传算法[1]、进化策略[2]、进化规划[3]等；②基于生物群体智能的优化算法，如微粒群算法[4]、猴群算法[5]、人工蜂群算法[6]等；③基于物理现象或规律的优化算法，如类电磁机制优化算法[7]、中心力算法[8]、万有引力算法[9]等。由于物理学的高度发展，模拟物理现象或物理规律的优化算法因具有理论来源清晰、算法模型简单、规范且寻优效果较好等诸多优点，正逐渐成为优化算法研究的热点。

鉴于基于物理规律优化算法的诸多优点，通过模拟分子机制，笔者于2013年首次提出了分子动理论优化算法(KMTOA)并将其应用于函数优化问题[10]。KMTOA能较好地兼顾收敛性和种群多样性，在快速收敛的同时能尽量避免陷入局部极值，表现出良好的优化性能。2014年，笔者将其与斜分 Otsu法相结合以对氧化铝回转窑火焰图像进行分割，取得了理想的分割效果[11]。KMTOA虽然具备良好的优化性能，但仍然存在一些不足，如缺乏局部搜索机制，求解精度有待提高；当前最优值为局部极值时，算法可能发生错误引导。

协同进化思想能充分地考虑种群与种群间、种群与环境间在进化过程中的相互协调关系，通过协同进化以改善各自性能，已成为智能优化领域的研究热点[12,13]。精英通常指种群中适应值较高的个体，这些个体对整个种群的进化起着重要的引导作用[14,15]。慕彩红等基于M个精英来建立团队，提出了M-精英协同进化算法并将其应用于函数优化，取得了较好的效果[16,17]。因此，本文针对KMTOA的不足，提出了一种M-精英协同进化分子动理论优化算法(MECKMTOA,M-elite coevolutionary KMTOA)。该算法采用M个精英代替单个精英来实现引导操作，以减小发生错误性引导的概率；基于学习与协作机制，精英能学习其他精英的先进知识而对自身进行优化搜索，从而提高算法的收敛精度；设计了一种自适应的波动算子，以防止算法陷入按维早熟。实验结果表明，MECKMTOA不仅具备更好的求解精度和算法稳定性，而且能更好地求解高维函数问题。

2 分子动理论优化算法及其不足

2.1 算法简介

在基于群体的优化算法中，算法由可行域中的一组随机点出发，依据随机点的目标函数值，通过一定的搜索策略使其收敛到问题的最优解。依据不同的原理各种算法采用了不同的搜索策略，其中KMTOA是受分子动理论的启发而提出的一种全局优化算法。该算法将问题的每个解视为一个分子，各分子在当前最优分子的吸引或排斥作用下运动而完成搜索过程；为增强算法跳出局部极值的能力，对于不受力的分子，通过模拟分子热运动而进行随机扰动。基于分子相互作用和热运动机制，KMTOA在搜索过程中能较好地兼顾收敛性和种群多样性。

设分子总数为N，问题维数为D，分子i的位置和质量分别为xi和mi，当前最优分子的位置和质量分别为分别表示分子受当前最优分子吸引、排斥和不受力的概率；当分子不受力时，对其进行随机扰动以增强算法的全局搜索能力。KMTOA可简要描述如下[10]。

2.2 算法存在的不足

KMTOA仅依靠种群中的当前最优分子来实现寻优操作，故算法在优化过程中易出现图1所示的情形：当前最优分子xBest为一局部极值，其他分子受其引导向该局部极值收敛，从而造成了算法的错误收敛。虽然波动算子使算法具有跳出局部极值的能力，但是波动率和变异率都很小，且变异是随机的，故算法跳出局部极值的过程是艰难而漫长的。可见，KMTOA仅依靠当前最优分子来引导搜索过程，存在一定的片面性。虽然当问题仅含一个极值时，算法效率较高；但是当问题包含多个局部极值时，该机制将严重影响算法的效率。

图1 KMTOA的错误性引导

定义 1在算法迭代过程中，如种群中的所有分子均满足

则称算法陷入按维早熟。其中，x·j表示种群中所有分子的第j维分量所构成的向量，max(x·j)和min(x·j)分别表示种群中所有分子第j维分量的最大、最小值，ε为一极小量。

由式(6)可知，当算法陷入按维早熟时，种群中的所有分子在某一维上的差异极小。此时，分子在其他维上仍然可能继续进化，故算法此时也许尚未发生真正的早熟，但如任其发展，则算法极有可能发生早熟。正是为了区别于传统概念上的早熟，本文将其称为按维早熟。由KMTOA的实现过程可知，当陷入按维早熟时，要使分子在该维上出现差异(即跳出按维早熟)是较为困难的。此外，KMTOA还缺乏局部寻优机制，其寻优精度有待提高。

3 改进的分子动理论优化算法

3.1 基于能力的团队构建算子

在M-精英协同进化算法中，每个精英团队的规模都相等[16,17]，这与自然界中优胜劣汰的生存法则严重不符。自然界中能力强的个体在竞争过程中将处于优势地位，往往占据更多的资源，能够繁殖更多后代[18]，故其团队规模也相对较大。在优化过程中，精英的能力越强，则意味着问题的解在其附近的可能性越大。因此，对于能力较强的精英，应组建规模较大的团队，以便引导更多分子进行优化搜索，这对提高算法效率具有重要意义。基于上述思想，本文设计了一种基于能力的团队构建算子，将每个精英的能力定义为

其中，M表示精英种群的规模，xworst和f(xworst)分别表示当前种群中的最差分子及其函数值。根据精英能力的定义，其团队规模可计算如下

其中，Membersi表示精英i所能构建团队的规模，Popsize表示种群规模。可见，精英的目标函数值越小，其能力越强，能够组建团队的规模就越大，引导分子搜索到最小值的可能性也就越大。

3.2 基于学习机制的精英协作算子

在KMTOA中，由于缺乏相应的局部搜索机制，当求解复杂问题时，其求解精度往往难以令人满意。对此，当团队成员属于精英种群时，基于学习机制设计了一种协作算子。该算子通过在精英间交换信息以引导精英对其邻域进行搜索，从而实现局部搜索。基于学习机制的精英协作算子定义如下

其中，i≠j,xik表示精英i的第k维分量，N(0,1)为服从标准正态分布的随机变量，D为解向量的维数，ui为协作过程完成后所得到的临时个体。

得到精英xi的临时个体ui后，可分别按式(10)、式(11)对精英xi、xj进行更新。

由上式可知，如临时个体ui对精英xi进行了更新，则ui将不会对xj进行更新，这样做是为了防止种群快速收敛到同一个值而造成算法早熟。

3.3 防按维早熟的波动算子

当用KMTOA求解复杂性问题时，算法可能出现按维早熟。由KMTOA的实现过程可知，当出现按维早熟时，算法主要依靠波动算子来跳出局部极值；但是KMTOA中的波动率和变异率都比较小，这就决定了算法跳出局部极值的可能性较小。对此，本文设计了一种防按维早熟的波动算子，该算子依据种群在当前维上的差异来对变异率进行计算；如差异较小，则该维变异率较大，以使分子能以较大的概率发生变异而保持种群多样性。防按维早熟的变异率计算公式为

3.4 基于分子动理论的引导算子

当团队成员xj来自普通种群时，精英xi通过引导操作引导普通分子进行优化搜索。在引导过程中，精英分别依据吸引率Pattraction、排斥率Prepulsion和波动率Pwave来判断对分子进行何种引导，具体操作如下：①当精英对普通分子进行吸引操作时，按式(1)计算其相应的引力加速度；②当精英对普通分子进行排斥操作时，按式(2)计算其相应的斥力加速度；③当普通分子进行随机扰动时，分别按式(12)、式(3)计算其相应的变异率和波动加速度。

计算出普通分子的加速度aj后，根据式(4)计算其速度Vj，并计算其临时个体Tmp为

根据临时个体Tmp，分别按式(14)、式(15)对精英xi和普通分子xj进行更新

由上式可知，只有当临时个体Tmp比精英xi好时，Tmp才会取代xi而成为新的精英；而无论如何，临时个体Tmp都会取代xj而成为新的普通分子。这么做一方面能够避免精英退化，另一方面又能较好地维持普通种群的多样性。

3.5 算法流程

MECKMTOA的算法流程如图2所示。

4 算法收敛性分析

定理1在算法运行过程中，MECKMTOA的种群序列｛Xt,t≥ 0 ｝为有限齐次Markov链。

证明 MECKMTOA采用实数编码，如设定精度为ε，则解空间S可视为的离散空间，故种群序列有限；由算法过程可知，第t+1代的种群Xt+1仅与其上代种群Xt有关。因此，种群序列为有限齐次的Markov链。

图2 MECKMTOA算法流程

定义2设f为S上的目标函数，f*为全局最优值，则最优解集s*可表示为

5 数值仿真与分析

为便于与 KMTOA比较，选择文献[10]中的f6～f2015个经典测试函数作为测试对象(记为F1～F15)，对MECKMTOA的性能进行测试。测试实验分为4个部分：第1部分为M取值及相关算子的合理性分析实验，主要讨论M的取值及各算子对算法性能的影响；第2部分为纵向比较实验，对改进前后算法的性能进行比较，以验证改进措施的有效性；第3部分为横向比较实验，将MECKMTOA与组织进化算法(OEA, organizational evolutionary algorithm)和M-精英协同进化算法(MECA,M-elite coevolutionary algorithm)等协同进化算法进行比较；第 4部分为高维及超高维函数测试实验，测试MECKMTOA解决高维及超高维问题的能力。所有实验运行的硬件平台均为：Intel(R) Celeron(R) 1.50 GHz的CPU，2 GB内存，Windows 7操作系统，编程语言为Matlab R2011a。

5.1 M及相关算子合理性分析

为测试精英数量M及各算子对 MECKMTOA性能的影响，分别选用F5、F6和F9这3个复杂函数对MECKMTOA进行测试。为便于后续与文献[16]中的MECA和OEA进行比较，MECKMTOA的种群规模取100，算法的最大迭代次数取3 000，每种情况下算法均独立运行50次，实验结果取50次测试的平均值。

5.1.1M取值分析

为测试精英种群的规模M对MECKMTOA的影响，首先从种群规模范围内选取部分值作为M的取值，以确定M的大致取值范围，然后在该范围内对M的取值做进一步的讨论。参照文献[16]，分别取M=3,5,10,15,20, 30,40,50,70,90，对 MECKMTOA的不同结果进行比较以确定M的大致取值范围。由表1可知：对于函数F5、F6和F9，当M取值小于10时，算法的优化效果较好；当M大于10时，算法的求解结果随M的增大而越来越差，故M的理想取值应小于10。

为讨论M的具体取值，对M=1,2,3,4,5,6,7,8,9,10时，MECKMTOA的不同结果进行了比较，比较结果如表2所示。由表2可知：对于函数F5、F6和F9，M取4～6的值时算法能取得较好的效果；M过大或过小，都将对算法的性能造成影响；当M取5左右时，MECKMTOA的实验结果相对较好。

表1 M对MECKMTOA的影响1

表2 M对MECKMTOA的影响2

为分析M取值的合理性，借鉴文献[19]阈值Q的分析方法，对F1～F15在M分别取1,2,…,10时的不同情况进行测试，并运用最小二乘法对测试结果的均值及其平均标准差进行拟合。拟合结果如下，其拟合曲线分别如图3和图4所示。

图3 M取不同值时，平均适应值拟合曲线

图4 M取不同值时，平均标准差拟合曲线

拟合结果表明：当M分别取5.170 9和5.026 0时，平均适应值和平均标准差能取得最小值。M过大、过小都会影响算法效果，这是因为M过大，种群过于分散，不利于算法收敛；M过小，则种群多样性差，易造成欺骗性引导。又因M取值为整数，故在后续的所有实验中均取M=5。拟合结果有力地验证了前文的分析。

5.1.2 相关算子分析

为改善算法的性能，本文设计了基于学习机制的精英协作算子、基于能力的团队构建算子及防按维“早熟”的波动算子。为验证各算子对算法性能的影响，用MECKMTOA1表示MECKMTOA中剔除了精英协作算子的算法，用MECKMTOA2表示MECKMTOA中固定了团队规模的算法，用MECKMTOA3表示MECKMTOA中采用了传统波动算子的算法，4种算法对函数F5、F6和F9的测试结果如表3所示。由表3可知，3个算子中基于能力的团队构建算子对MECKMTOA的影响最小，但因基于能力的团队构建算子能召集更多的成员对优秀分子附近进行搜索，故该算子对提高算法收敛的速度和精度具有一定影响；基于学习机制的精英协作算子通过在精英间进行交换信息，对精英附近进行搜索，故对提高算法的收敛精度具有重要影响；防按维早熟的波动算子能根据每维的情况自适应地调整变异率，能较好地防止算法陷入局部极值，如去掉该算子，则算法的性能将大幅下降。综合考虑，3个算子能从不同的角度对算法的性能进行改进，故同时采用该3个算子的MECKMTOA最为理想。

表3 各算子对MECKMTOA的影响

表4 MECKMTOA与KMTOA的性能对比

5.2 改进前后算法性能比较

为测试MECKMTOA的性能，将MECKMTOA与 KMTOA进行比较。2种算法的种群规模均为100，最大迭代次数均为3 000，吸引率、排斥率、波动率等与文献[10]中一致，每个算法独立运行50次，选用 50次结果中的最小值、最大值、平均值和标准差4项指标对算法的性能进行比较，比较结果如表4所示。由表4可知：对于F1等KMTOA能取得最优值的函数，MECKMTOA也均能取得最优值；对于F2等KMTOA未能取得最优值的函数，虽然MECKMTOA也未能取得最优值，但是其求解精度具有明显改善，如对于F2、F14等函数，MECKMTOA的求解精度甚至比KMTOA高几个数量级。此外，由比较结果还能看出MECKMTOA几乎在各项指标上均优于KMTOA。

5.3 与其他协同进化算法的性能比较

为进一步验证MECKMTOA的性能，将其与文献[16]中的MECA和OEA这2种协同进化算法进行比较。实验选取本文与文献[16]所共有的 8个测试函数作为测试对象，表5为3种算法的比较结果，其中MECA和OEA的数据选自文献[16]。由表5可知：除F5和F9外，MECKMTOA能对所有的函数求得最优值；对于F5，虽然 MECKMTOA未能求得最优值，但其求解精度仍比MECA和OEA高1～2个数量级；在8个测试函数中，MECKMTOA只有对f14的求解结果比MECA和OEA差。故总体考虑，MECKMTOA在求解精度、算法稳定性等方面比MECA和OEA具有更好的效果。

5.4 高维及超高维函数测试

为检验 MECKMTOA求解复杂问题的能力以及问题复杂度的增加对算法性能的影响，用MECKMTOA 分别求解高维(维数为 10～1 000)和超高维(维数1 000以上)条件下的F10和F13，并将其求解结果与文献[20]中的免疫记忆克隆规划算法(IMCPA, immune memory clonal programming algorithm)及无记忆功能的免疫记忆克隆规划算法(nIMCPA)进行比较。算法终止条件为为算法当前的最优值，ε为算法的收敛精度。参照文献[20]，对于高维函数，平均函数评价次数取算法 10次运行的平均值；对于超高维函数，平均函数评价次数取算法 5次运行的平均值；IMCPA和nIMCPA的数据选自文献[20]，“—”表示没有进行该实验。

由表6可知：与IMCPA和nIMCPA相比，在相同的收敛精度下，MECKMTOA所需的平均函数评价次数相对较少；随着维数的增加，MECKMTOA、IMCPA和nIMCPA的平均函数评价次数均有所增长，但MECKMTOA的平均函数评价次数增长的相对缓慢。比较结果表明：MECKMTOA即使在超高维条件下仍能表现出良好的性能，且其性能不随问题维数的增加而迅速下降。

6 结束语

表5 MECKMTOA与MECA及OEA的比较

表6 高维及超高维函数测试结果

针对KMTOA存在的不足，通过引入精英和协同进化思想，提出了一种M精英协同分子动理论优化算法。该算法采用M个精英，减小了传统算法发生错误性引导的概率，改善了算法的收敛效率；精英通过协作算子，学习先进知识以改善自己，提高了算法的收敛精度；防按维早熟的波动算子因能自适应地调节波动率，能有效地防止算法发生早熟。为分析M的取值对算法性能的影响，讨论了M的不同取值情况，确定了其大致取值。为验证各算子的合理性，分析了各算子对算法所造成的影响。与KMTOA的纵向比较表明，MECKMTOA的改进策略是有效的；与MECA和OEA这2种协同进化算法的横向比较结果表明，MECKMTOA的协同引导机制具有明显优势；对高维及超高维函数的测试结果表明，MECKMTOA具备求解复杂性问题的能力，且其性能受问题维数的影响相对较小。综合考虑，MECKMTOA具备较强的优化性能，有望应用于复杂问题的求解，具有重要的理论研究意义和工程应用价值。

[1] LIN C H, CHOY K L, HO G T S, NG T W. A genetic algorithm-based optimization model for supporting green transportation operations[J].Expert Systems with Applications, 2014, 41(7): 3284-3296.

[2] DONG W Y, ZHOU M C. Gaussian classifier-based evolutionary strategy for multimodal optimization[J]. IEEE Transactions on Neural Networks & Learning Systems, 2014, 25(6): 1200-1216.

[3] KHATOD D K, PANT V, SHARMA J. Evolutionary programming based optimal placement of renewable distributed generators[J]. IEEE Transactions on Power Systems, 2013, 28(2): 683-695.

[4] MIRJALILI S, LEWIS A, SADIQ A S. Autonomous particles groups for particle swarm optimization[J]. Arabian Journal for Science and Engineering, 2014, 39(6): 4683-4697.

[5] ZHENG L. An improved monkey algorithm with dynamic adaptation[J].Applied Mathematics and Computation, 2013, 222(1): 645-657.

[6] 张冬丽，唐英干，关新平. 用改进的人工蜂群算法设计AVR系统最优分数阶PID控制器[J].自动化学报，2014, 40(5): 973-979.ZHANG D L, TANG Y G, GUAN X P. Optimum design of fractional order pid controller for an avr system using an improved artificial bee colony algorithm[J]. Acta Automatica Sinica, 2014, 40(5): 973-979.

[7] ZHANG C J, LI X Y, GAO L WU Q. An improved electromagnetism-like mechanism algorithm for constrained optimization[J]. Expert Systems with Applications, 2013, 40(14): 5621-5634.

[8] FORMATO R A. Central force optimization with variable initial probes and adaptive decision space[J]. Applied Mathematics and Computation, 2011, 2(17): 8866-8872.

[9] MIRJALILI S, LEWIS A. Adaptive gbest-guided gravitational search algorithm[J]. Neural Computing and Applications, 2014, 25(7):1569-1584.

[10] FAN C D, OUYANG H L, ZHANG Y J,et al. Optimization algorithm based on kinetic-molecular theory[J]. Journal of Central South University, 2013, 20(12): 3504-3512.

[11] 范朝冬, 张英杰, 欧阳红林等. 基于改进斜分Otsu法的回转窑火焰图像分割[J]. 自动化学报, 2014, 40(11): 2480-2489.FAN C D, ZHANG Y J, OUYANG H L,et al. Improved Otsu method based on histogram oblique segmentation for segmentation of rotary kiln flame image[J]. Acta Automatica Sinica, 2014, 40(11):2480-2489.

[12] JIAO L C, WANG H D, SHANG R H,et al. A co-evolutionary multi-objective optimization algorithm based on direction vectors[J]. Information Sciences, 2013, 228(10): 90-112.

[13] LI H C, FANG L. Co-evolutionary algorithm: an efficient approach for bilevel programming problems[J]. Engineering Optimization, 2014,46(3): 361-376.

[14] CHEN P H. Two-level hierarchical approach to unit commitment using expert system and elite PSO[J]. IEEE Transactions on Power Systems,2012, 27(2): 780-789.

[15] YOUSEFIKHOSHBAKHT M, DIDEHVAR F, RAHMATI F. An efficient solution for the vrp by using a hybrid elite ant system[J]. International Journal of Computers Communications & Control, 2014,9(3): 340-347.

[16] 慕彩红, 焦李成, 刘逸.M-精英协同进化数值优化算法[J]. 软件学报, 2009, 20(11): 2925-2938.MU C H, JIAO L C, LIU Y.M-elite coevolutionary algorithm for numerical optimization[J]. Journal of Software, 2009, 20(11): 2925-2938.

[17] 慕彩红, 焦李成, 刘逸.M-精英协同进化算法及其在 V-BLAST系统中的应用[J]. 电子与信息学报, 2009, 31(10): 2443-2448.MU C H, JIAO L C, LIU Y.M-elitist evolutionary algorithm and its application to v-blast system[J]. Journal of Electronics & Information Technology, 2009, 31(10): 2443-2448.

[18] 秦进, 李歆. 一种简单的资源受限的群体演化模型[J]. 复杂系统与复杂性科学, 2009, 6(2): 82-86.QIN J, LI X. A simple model of population evolution with limited resource[J]. Complex Systems and Complexity Science, 2009, 6(2):82-86.

[19] 范朝冬, 欧阳红林, 肖乐意. 基于空间截面投影的Otsu图像分割算法[J]. 通信学报, 2014, 35(5): 70-78.FAN C D, OUYANG H L, XIAO L Y. Otsu thresholding method based on projection of cross section for image segmentation[J]. Journal on Communications, 2014, 35(5): 70-78.

[20] 杜海峰, 公茂果, 焦李成等. 用于高维函数优化的免疫记忆克隆规划算法[J]. 自然科学进展, 2004, 14(8): 925-933.DU H F, GONG M G, LIAO L C,et al. Immune memory clonal programming algorithm for high dimension function optimization[J].Progress in Natural Science, 2004, 14(8): 925-93.