遗传算法函数寻优性能影响因素分析-基于正交试验的方法

ComputerEngineeringandApplications计算机工程与应用

2015，51（6）1

博士论坛

遗传算法函数寻优性能影响因素分析

——基于正交试验的方法

李书全，吴秀宇

LIShuquan,WUXiuyu

天津财经大学商学院管理科学与工程系，天津300222

DepartmentofManagementScienceandEngineering,SchoolofBusiness,TianjinUniversityofFinanceandEconomics,Tianjin300222,China

LIShuquan,http://wendang.chazidian.computerEngineeringandApplications,2015,51（6）：1-5.

Abstract：Geneticalgorithmiswidelyappliedtofunctionoptimization.It’sveryimportanttoselecttheappropriateparame-tersfortheperformanceoffunctionoptimization.Thispapertakesfourclassicalfunctionsasexamples,andanalyzesfiveparameters’impactsongeneticalgorithmperformanceonfunctionoptimizationbasedonorthogonaltest.Theresultsshowthat：thegreatestinfluencingfactoronsearchingtimeismutationprobability,thesecondispopulationsize,theotherthreecrossoveroperator,crossoverprobabilityandencodinglengthareless;thethreefactorsthatinfluenceiterationtimesaremutationprobability,populationsizeandencodinglength,andtheinfluenceofcrossoverprobabilityandcrossoveroperatorareless.Thispaperanalyzestheprinciplesofparameterscombinationforgeneticalgorithmoptimalperformance.Keywords：geneticalgorithm;orthogonalexperiment;optimizationperformance;influencingfactors

摘要：遗传算法在函数寻优领域得到了广泛应用，选取合适的参数对提高遗传算法寻优性能至关重要。以四个经典函数为例，基于正交试验原理分析了遗传算法五个参数对其寻优时间和迭代次数的影响。结果表明：对寻优搜索时间影响最大的参数为变异概率，其次为种群大小，交叉算子的选择、交叉概率和编码长度影响相对较小；对寻优迭代次数影响较大的三个参数为变异概率、种群大小和编码长度，而交叉概率和交叉算子的选择影响相对较小。分析了使遗传算法性能最优时参数组合的原则。

关键词：遗传算法；正交试验；寻优性能；影响因素

文献标志码：A中图分类号：TP301.6doi：10.3778/j.issn.1002-8331.1409-0091

1引言数据挖掘等领域[4-6]。但其数学基础不足、收敛性理论

遗传算法是模仿自然界生物进化机制而产生的随欠缺、欺骗问题、搜索效率及时间复杂性等问题一直是机全局搜索方法，它是由美国Michigan大学的Holland人们关注的重点[7]。函数寻优是遗传算法应用较为广教授及其学生提出[1]，经DeJong[2]、Goldberg[3]等人的进泛的领域之一，近年来，遗传算法得到不断改进，但遗一步研究与应用逐渐成为了一种实用、高效、鲁棒性强传算法要求众多参数（如种群大小、编码长度、交叉概的优化技术。遗传算法以其独特的优点被广泛应用于率、变异概率等）的合理设置是影响其寻优性能的关键函数寻优、生产调度、自动控制、模式识别、机器学习与问题[8-9]。此外，也有学者分析了交叉算子选择对遗传基金项目：国家自然科学基金（No.71171140）；天津财经大学研究生科研资助计划（No.2014TCB05）。

作者简介：李书全（1957—），男，博士，教授，博士生导师，研究领域为人工智能与信息技术；吴秀宇（1991—），男，博士研究生，研究

领域为人工智能与项目管理。E-mail：xywu2014@http://wendang.chazidian.com

收稿日期：2014-09-05修回日期：2014-11-20文章编号：1002-8331（2015）06-0001-05

CNKI网络优先出版：2014-12-02，http://wendang.chazidian.com/kcms/doi/10.3778/j.issn.1002-8331.1409-0091.html

22015，51（6）ComputerEngineeringandApplications计算机工程与应用

算法整体性能影响[10-12]。上述研究使得人们认识到不同变动导致的和试验误差引起两部分，更加准确地判定各参数对遗传算法性能有不同的影响程度，但大多是基于因素对测试指标影响的显著性，也常用于正交试验的结单个参数的对比与分析，在实际应用时往往由于不能找果分析，本文采用计算机仿真模拟，不存在传统意义上到各个参数的最优组合而无法实现寻优性能的最大人为的试验误差，因此在结果分析时采用极差分析的方化。基于正交试验的方法，选取了四个测试遗传算法性法。极差分析方法的评价标准是计算各因素各水平下能的经典函数，分析种群大小、编码长度、交叉算子、交的极差值Ri，其计算公式为：

叉概率和变异概率5个参数对遗传算法函数寻优性能Ri=max{ki1ki2kij}-min{ki1ki2kij}（1）的综合影响规律，寻找影响其寻优性能的关键因素及其其中k

参数组合，为实际应用遗传算法进行函数寻优提供理论ij为第i个因素在第j个水平下试验结果的平均支持。值，计算公式为：

k1n

ij=åYk-Yˉ（2）

k=1

2正交试验设计其中n为第i个因素在第j个水平下试验的次数，Yk为

2.1正交试验原理每次试验的结果，Yˉ为所有试验结果的平均值。

正交试验是以概率论、数理统计和实践经验为基础根据上述方法计算出的各因素的极差值越大，说明的，能够高效处理多因素优化组合问题的科学计算方该因素的变化对测试指标影响的程度越大；反之，因素法[13-15]。正交试验利用标准化的正交试验表设计试验方的极差值越小，其对测试指标的影响程度越小。根据各案，从大量试验方案中选取具有代表性的试验，将试验极差的大小可得到使测试指标最优的因素组合。因素与水平的组合均匀分布，保证各因素和各水平的均

匀分散性和整齐可比性，同时极大降低了试验次数[16]。3遗传算法函数寻优性能因素分析

如对于三个因素每个因素具有二个水平的问题进行全

因素试验需要进行8次（2×2×2）试验，但通过正交表进3.1因素及水平的选择

行4次试验即可，表示为L4(23)；对于4个因素每个因影响遗传算法性能的参数有很多，如编码方式、适

应度函数的选择、初始种群、选择算子、交叉算子及其

素具有3个水平的问题进行全因素试验需要进行81次概率、变异算子及其概率、终止条件等。每个因素又具（3×3×3×3）试验。但通过正交表进行9次试验即可，表

示为L4有不同的取值，在进行因素及水平确定时应尽量根据

9(3)。根据各因素水平数的相等与否可以将正前人及相关领域的研究经验确定。结合相关文献，本交试验表分为同水平正交表和混合水平正交表，前者各文选取对遗传算法性能影响较大的5个因素作为试验因素的水平数相等，后者各因素的水平数可以不同。本因素进行分析，分别是：种群大小、编码长度、交叉算子、文进行5个因素每个因素具有4水平的试验，选取标准交叉概率和变异概率。至于因素的水平确定，根据前人的同水平正交试验表为L5

16(4)，即进行16次试验即可，的研究经验，种群大小一般取为20~100之间，交叉概率

相对于全因素试验需要进行1024次（4×4×4×4×4）试验一般为0.4~0.99之间，变异概率一般为0.01~0.1之间，为次数大大减少。配合正交试验的方法，本文选取的因素及其水平如表1

2.2试验结果分析方法所示。

正交试验常用的结果分析方法有极差分析法和方3.2函数及性能指标的选择

差分析法，极差分析法又称直观检验法，通过计算各因在进行仿真分析之前，选择合适的寻优函数是准确素各水平下测试指标的平均值和极差，并绘制各因素不测试遗传算法交叉算子性能的关键之一，本文选取具有同水平下指标的趋势图，以此分析影响测试指标的关键相当复杂度的四种经典函数进行仿真试验的分析，如因素和最优组合，其计算简便、易懂，常用于正交试验的表2所示。其中，DeJong函数为多元单峰函数，其只有结果分析；方差分析法将测试指标的变化分为影响因素一个极小值点为（0，0，0，…，0），函数极值为0；Rosenbrock

表1正交试验因素及水平

水平因素

种群大小M编码长度L交叉算子C交叉概率Pc变异概率Pm

12018单点交叉0.400.01

24020两点交叉0.600.04

36022多点交叉0.800.07

48024洗牌交叉0.990.10

李书全，吴秀宇：遗传算法函数寻优性能影响因素分析

2015，51（6）3

表2正交试验设计方案及试验结果

方案MLCPDeJong函数Rosenbrock函数Rastrigin函数六峰驼背函数

cPmt/sgent/sgent/sgent/sgen

1111110.08354.416.53013898.30.956689.70.227185.4

2122220.06137.51.006715.30.202122.80.06140.4

3133330.09753.61.014600.90.340182.60.10963.2

4144440.12064.92.1071232.11.008528.20.186109.5

5212340.09244.10.924482.80.448211.10.11761.0

6221430.07033.40.861410.70.23399.20.07236.7

7234120.07627.91.001377.30.23379.30.08030.7

8243210.10136.114.5335746.70.756293.10.19280.6

9313420.07221.80.690221.70.20554.50.07222.7

10324310.09125.410.6643582.40.450140.50.08324.4

11331240.09335.61.045410.90.487161.60.10140.0

12342130.07527.90.844328.80.28391.30.0930.0

13414230.11427.50.824216.30.37982.90.13632.1

14423140.14435.91.244319.00.617136.40.19244.9

15432410.06519.79.7223378.50.386115.60.11132.8

16441320.07521.80.692212.40.17544.70.08222.8

函数为二元非凸函数，它是一个典型的难极小化的病态数随机分配到正交表中的5列，每一行对应一个因素组函数，函数虽然在定义域内只有一个全局最小点，但其在合，即一个试验方案。每一方案4个函数的测试结果在全局最小点临近的狭长区域内取值变化极为缓慢，因此表2的最后8列。选择算子采用随机遍历选择，函数测常被用作评价算法的搜索性能；Rastrigin函数为二元多试在Matlab2012a软件上运行。

峰函数，其有许多局部极小值点，但只有在（0，0）处达到3.3.2结果分析

全局最小；六峰驼背函数（six-humpcamelbackfunction）根据试验结果，分别以遗传算法寻优上述4个经典有6个局部最小值点和2个全局最小值点。寻优函数的函数搜索时间和迭代次数为例，分析各因素对遗传算法公式如公式（3）~（6）所示。将遗传算法进行函数寻优时性能的影响。

精度达到10-5时的搜索时间t（单位：s）和最小迭代次对DeJong函数寻优搜索时间和迭代次数的极差数（gen）作为测试遗传算法寻优性能的指标，对每一个分析结果如表3所示，由表3可知，对DeJong函数寻优测试反复进行30次，取其平均值作为试验结果。搜索时间影响程度较大的指标依次为：变异概率、交叉

DeJong函数：算子选择、种群大小、交叉概率、编码长度。由于搜索minf1(x)=ån

x2

i(-10xi10)（3）时间越小说明寻优性能越好，所以得出最优因素水平

x=1组合应是测试指标均值最小的组合：种群大小（60）、编

Rosenbrock函数：

222码长度（22）、交叉算子（两点交叉）、交叉概率（0.99）、变minf2(x,y)=100×(y-x)+(x-1)

(-10xy10)（4）表3DeJong函数寻优搜索时间和迭代次数的极差分析

因素MLCP

Rastrigin函数：cPm

t/s0.0010.001－0.0090.006－0.004

minf3(xy)=20+x2+y2-10(cos2πx+cos2πy)k1gen17.1311.4810.8311.056－1.569

(-10xy10)（5）kt/s－0.0040.002－0.0160.003－0.018

2

六峰驼背函数：gen－0.094－2.419－3.169－1.294－8.219

t/s－0.006－0.0060.0150.000

minf=(4-2.1x2+x4k0.000

3

4(xy))x2+xy+(-4+4y2)y2gen－7.794－1.2691.3810.7560.131

(-10xy10 )（6）kt/s0.0110.0040.011－0.0070.023

4gen－9.2442.2060.956－0.5199.656

3.3正交试验设计及结果分析Rt/s0.0170.0100.0310.0130.041

3.3.1正交试验设计igen26.3754.6254.5502.35017.875

因为模型参数之间相互独立，故不考虑参数之间的因素t/sPm>C>M>Pc>L

排序genM>P

交互作用，根据因素及水平的取值确定选取同水平正交m>L>C>Pc

最优t/sM3L3C2Pc4Pm2

试验表为L5

16(4)，得到试验方案如表2所示，将试验参组合genM4L2C2Pc2Pm2

42015，51（6）ComputerEngineeringandApplications计算机工程与应用

表4Rosenbrock函数寻优搜索时间和迭代次数的极差分析因素MLCPcPmkt/s1.1830.7610.8010.9248.8811gen2103.2691696.3941724.6941722.4694643.094kt/s0.349－0.537－0.8570.371－3.1342gen－254.006－751.531－782.031－236.081－1626.706kt/s－0.670－0.7850.389－0.657－3.0953gen－872.431－816.481－286.306－788.756－1619.206kt/s－0.8610.563－0.332－0.636－2.6514gen－976.831－128.381－656.356－697.631－1397.181Rt/s2.0441.5461.6581.58112.015igen3080.1002512.8752506.7252511.2256269.800因素排序t/sPm>M>C>Pc>L

genPm>M>L>Pc>C

最优组合t/sM4L3C2Pc3Pm2

genM4L3C2Pc3Pm2

异概率（0.04）。表5Rastrigin函数寻优搜索时间和迭代次数的极差分析

同理得出DeJong函数寻优迭代次数的各因素的因素MLCPcPm极差分析结果，对DeJong函数寻优迭代次数影响程度kt/s0.1800.0500.0160.0750.190

1

较大的指标依次为：种群大小、变异概率、编码长度、交gen191.23169.95659.20659.581120.131叉算子选择、交叉概率。由于迭代次数越少说明寻优性kt/s－0.030－0.071－0.1170.009－0.243

2gen－18.919－64.869－54.394－24.494－114.269

能越好，所以得出最优因素水平组合应是测试指标均值kt/s－0.091－0.0850.033－0.094－0.138

3

最小的组合：种群大小（80）、编码程度（20）、交叉算子gen－77.619－54.819－22.944－44.869－75.594（两点交叉）、交叉概率（0.6）、变异概率（0.04）。kt/s－0.0580.1080.0710.0110.193

4gen－94.69449.73118.1319.78169.731

对Rosenbrock函数寻优搜索时间和迭代次数极差

分析的结果如表4所示，由表4得出，对Rosenbrock函数Rt/s0.2710.1930.1880.1690.436

igen285.925134.825113.600104.450234.400

寻优搜索时间影响程度较大的指标依次为：变异概率、因素t/sPm>M>L>C>Pc种群大小、交叉算子选择、交叉概率、编码长度。最优组排序genM>Pm>L>C>Pc合为种群大小（80）、编码程度（22）、交叉算子（两点交最优t/sM3L3C2Pc3Pm2

组合genM4L2C2Pc3Pm2

叉）、交叉概率（0.8）、变异概率（0.04）。对Rosenbrock函数迭代次数影响程度较大的指标依次为变异概率、种群概率、交叉算子选择、编码长度。最优组合为种群大小大小、编码长度、交叉概率、交叉算子选择。最优组合为（60）、编码程度（22）、交叉算子（两点交叉）、交叉概率种群大小（80）、编码程度（22）、交叉算子（两点交叉）、交（0.8）、变异概率（0.04）。对六峰驼背函数迭代次数影响叉概率（0.8）、变异概率（0.04）。程度较大的指标依次为种群大小、变异概率、编码长度、

对Rastrigin函数寻优搜索时间和迭代次数的结果表6六峰驼背函数寻优搜索时间和迭代次数的极差分析如表5所示，由表5可知，对Rastrigin函数寻优搜索时间因素MLCPcPm影响程度较大的指标依次为变异概率、种群大小、编码kt/s0.0270.0190.0020.0280.034

1gen46.05021.72517.65019.17527.225

长度、交叉算子选择、交叉概率。最优组合为种群大小

（60）、编码程度（22）、交叉算子（两点交叉）、交叉概率kt/s－0.004－0.017－0.0240.003－0.045

2gen－1.325－16.975－12.525－5.300－24.425

（0.8）、变异概率（0.04）。对Rastrigin函数迭代次数影响kt/s－0.033－0.0190.022－0.021－0.017

3

程度较大的指标依次为种群大小、变异概率、编码长度、gen－24.300－11.900－0.725－10.725－13.075交叉算子选择、交叉概率。最优组合为种群大小（80）、kt/s0.0110.0180.002－0.0090.030

4gen－20.4257.150－4.400－3.15010.275

编码程度（20）、交叉算子（两点交叉）、交叉概率（0.8）、Rt/s0.0600.0380.0460.0490.079

i

变异概率（0.04）。gen70.35038.70030.17529.90051.650

对六峰驼背函数寻优搜索时间和迭代次数的结果因素t/sPm>M>Pc>C>L如表6所示，由表6可知，对六峰驼背函数寻优搜索时间排序genM>Pm>L>C>Pc

最优t/sM3L3C2Pc3Pm2

影响程度较大的指标依次为变异概率、种群大小、交叉组合genM3L2C2Pc3Pm2

李书全，吴秀宇：遗传算法函数寻优性能影响因素分析

2015，51（6）5交叉算子选择、交叉概率。最优组合为种群大小（60）、参考文献：编码程度（20）、交叉算子（两点交叉）、交叉概率（0.8）、[1]HollandJH.Adaptationinnaturalandartificialsystems[M].变异概率（0.04）。Michigan：TheUniversityofMichiganPress，1975.

综合以上遗传算法对四种经典函数寻优性能的分[2]DeJongK.Ananalysisofthebehaviorofaclassof析，可以得出对寻优搜索时间影响最大的参数为变异概geneticadaptivesystems[D].UniversityofMichigan，1975.率，而根据单峰函数和多峰函数的不同特点，其他因素[3]GoldbergDE.Geneticalgorithmsinsearch，optimization影响程度呈现出不同的规律，对前者影响较大的因素有andmachinelearning[M].[S.l.]：AddisonWesleyPublishing种群大小和交叉算子的选择，对后者影响较大的因素为Company，1989.种群大小，其他因素影响程度相对较小，总体而言，变异[4]雷英杰，张善文，李续武，等.遗传算法工具箱及其应用[M].概率和种群大小对寻优搜索时间影响较大。对寻优迭西安：西安电子科技大学出版社，2005.代次数影响较大的参数为变异概率、种群大小和编码长[5]玄光南，程润伟.遗传算法与工程设计[M].北京：科学出版度，而交叉概率和交叉算子的选择影响相对较小。牡，2000.

在因素最优组合的选取方面，变异概率在4次试验[6]ChoenniS.Designandimplementationofagenetic-based结果中的最优水平比较稳定，均为第2水平，即变异概algorithmfordatamining[C]//Proceedingsofthe26th率的选取为0.04；交叉算子的选择也比较稳定，均为第2InternationalConferenceonVeryLargeDataBases.[S.l.]：水平，即交叉算子选择两点交叉时遗传算法性能最优；MorganKaufmannPublishersInc.，2000：33-42.染色体编码长度在第2和第3水平时为最优水平，其编[7]戴晓晖，李敏强，寇纪淞.遗传算法理论研究综述[J].控制与码长度为20和22；种群个体为第3和第4水平时遗传算决策，2000（3）：263-268.法性能最优，说明个体数目不宜过小，选择60~80之间[8]丁承民，张传生，刘贵忠.正交试验遗传算法及其在函数优为宜；交叉概率的确定没有明显规律，但第1水平的交化中的应用[J].系统工程与电子技术，1997（10）：58-61.叉概率始终没有出现在最优组合里，说明交叉概率的选[9]弭宝福，徐梅，王福林，等.交叉概率对遗传算法运算速度影择不宜过小，在0.6~0.99之间为宜。响的测试与分析[J].数学的实践与认识，2013（22）：180-183.

[10]SyswerdaG.Uniformcrossoveringeneticalgorithms[C]//

4结束语ProceedingsoftheThirdICGA.SanMateo，CA：Morgan

Kaufman，1989：2-9.

本文基于正交试验的原理与方法，以4个经典函数[11]徐洪泽，陈桂林，张福恩.遗传算法的单双点杂交方法对为例，分析了遗传算法相关参数对其函数寻优性能的影比研究[J].哈尔滨工业大学学报，1998，30（2）：64-67.响规律。结果表明，在给定的寻优精度条件下，不同参[12]熊军，高敦堂，沈庆宏，等.遗传算法交叉算子性能对比研数对遗传算法函数寻优搜索时间和迭代次数影响程度究[J].南京大学学报：自然科学版，2004（4）：432-437.有所不同，对搜索时间影响较大的参数为变异概率、初[13]贾超，张凯，张强勇，等.基于正交试验设计的层状盐岩地下始种群大小；对迭代次数影响较大的参数为变异概率、储库群多因素优化研究[J].岩土力学，2014（6）：1718-1726.初始种群大小和编码长度。另外，文章分析了遗传算法[14]李炎隆，李守义，丁占峰，等.基于正交试验法的邓肯-张E-B函数寻优性能最大化时相关参数的确定原则。模型参数敏感性分析研究[J].水利学报，2013（7）：873-879.

遗传算法在函数寻优方面的广泛应用促进了其相[15]田玉柱，吕建虎，陈平.基于正交试验的菜椒产量影响因关参数的发展与改进[17]，这又为进一步提高遗传算法性素的分析[J].数理统计与管理，2011（1）：173-177.能提供了条件，但由于很多算法改进缺乏一定的理论基[16]刘瑞江，张业旺，闻崇炜，等.正交试验设计和分析方法研础和特定背景的限制，传统算子在实际应用中仍占有较究[J].实验技术与管理，2010（9）：52-55.大的位置，如何进一步分析传统算子与改进算子在实际[17]李书全，孙雪，孙德辉，等.遗传算法中的交叉算子的述应用时的优化组合将是未来研究的方向之一。评[J].计算机工程与应用，2012，48（1）：36-39.