试验设计在遗传算法参数配置中的应用

范家旭　徐铭洁　孙晓华　陈雪平

摘要：遗传算法是受生物进化论的启发而产生的，其是一种高效的随机搜索与优化算法，具有很好的收敛性，简单通用。试验设计是使用频率最高的统计方法之一，其中正交设计是利用标准化正交设计表进行试验而迅速找到优化方案。均匀设计是考虑让试验点在试验范围尽量均匀地分布，因此试验次数少。本文将这两种试验设计方法应用在遗传算法的参数优化配置中，模拟结果表明采用设计方案后可以提高遗传算法的收敛速度及寻优性能。

关键词：遗传算法；试验设计；正交设计；均匀设计

中图分类号：O212.6 文献标识码：A 文章编号：2095-7394（2016）02-0005-06

遗传算法由Bagley J.D于1967年提出，其借鉴生物进化过程中优胜劣汰、适者生存的机理来寻求最优解。正交设计是利用正交设计表进行多因素多水平试验的一种高效的试验设计方法。均匀设计是利用均匀设计表进行试验的方法，让试验点完全从均匀性出发，大大减少试验次数，缩短试验周期。

在遗传算法中常常有不同的参数可以选择，本文将采用试验设计方法来对参数进行最优搭配。全文共分四部分，第一节介绍遗传算法，包括遗传算法的背景、基本要素和原理、流程等；第二节介绍试验设计，包括正交设计和均匀设计；第三节介绍均匀试验设计和正交试验设计在遗传算法参数优化中的应用；第四节为总结。

1 遗传算法简介

1.1 遗传算法的基本要素

遗传算法（GA）是受达尔文的进化论的启发，其核心思想是“物竞天择，适者生存”。在繁殖过程中，生物体会发生基因交叉，基因突变等现象，适应度低的个体会被逐步淘汰，适应度高的个体会越来越多。这样经过N代的进化后，保存下来的个体适应度就会变高。下面先介绍遗传算法中的几个基本概念。

（1）参数编码：将解空间的解数据转换成基因型串结构数据。

（2）初始种群设定：先随机产生N个初始串结构数据，每个串结构数据称为一个个体，Ⅳ个个体构成一个群体，以此N个串结构数据作为初始种群开始迭代。

（3）适应度函数设计：在遗传算法中，适应度函数表明了个体或解的优劣性。

（4）遗传操作设计：包括了三个基本遗传算子：选择、交叉和变异。

（ⅰ）选择：从种群中选出优良个体，使它们的优良基因遗传给下一代；

（ⅱ）交叉：两条染色体之间通过交叉而重组，形成两条新的染色体；

（ⅲ）变异：对在种群中选中的个体以一定的概率随机的改变串结构数据中某个串的值。

1.2 遗传算法的基本原理

利用遗传算法求解最优化问题，首先应对可行域中的点进行编码，然后在可行域中随机挑选一些编码组成第一代编码组，并计算每个解的目标函数值即编码的适应度。接着，利用选择机制挑选编码作为繁殖前的样本，且应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。并进行复制、交叉和变异操作，直到结束条件得到满足为止。其基本过程如下：

（1）随机生成一定数目的初始群体，每个个体编码为对应染色体的基因；

（2）定义并计算每个个体的适应度函数，适应度函数值越小，个体越优良，但适应度值不得为负；

（3）执行选择操作；

（4）执行交叉操作；

（5）执行变异操作；

（6）选择并输出最佳个体及其代表的最优解并结束运算，否则转（3）。

2 试验设计

试验设计主要讨论如何合理地安排试验以便对试验数据进行有效分析。本文选择其中两种方法进行分析：正交设计和均匀设计。

2.1 正交设计

正交试验设计是一种研究多因素多水平的试验设计方法，利用“正交表”进行整体设计、综合比较、统计分析。其特点是：“均匀分散，整齐可比”。用部分试验代替全面试验，通过对部分试验结果的分析，从而了解全面试验的情况。是一种高效、经济、快速的试验设计方法。

正交试验常记为Ln（q^p），是利用规格化的正交表安排试验，再分析试验数据的方法。n为试验次数，即正交表行数；q为因素的水平数，即列中出现不同数字的个数；p为最多能安排的因素数，即正交表的列数。正交表按水平数可分为二水平正交表：L₄（2³）、L₈（2⁷）、L₁₂（2¹¹）、L₁₆（2¹⁵）等；三水平正交表：L₉（3⁴）、L₁₈（3⁷）、L₂₇（3¹³）等；四水平正交表：L₁₆（4⁵）等；五水平正交表：L₂₅（5⁶）等。例L₉（3⁴），如表1所示。

2.2 均匀设计

均匀设计是使试验点在所考察的试验范围内尽量均匀地分布，对于一个水平数为q的正交试验，至少要进行q²次试验。若不考虑整齐可比，只考虑均匀性，可以从全面试验中挑选比正交试验设计更少的试验点作为代表进行试验。

均匀设计表是均匀设计的一种规格化的表格，是用数论方法编制的，并用U_n（q^m）表示，简称u表。表示有n行m列，每列的水平数是q。其特点是对任意的n都可以构造均匀设计表，并且行数n与水平数q相同。对另一类均匀设计表U^*_n（q^m），此表避开了当n为奇数时，最后一行全为n的情况。例U^*₆（6⁶），如表2所示。

每个均匀设计表都有相对应的使用表，优先使用均匀度偏差较小的表。

3 试验设计在遗传算法参数优化中的应用

影响遗传算法搜索优化效果的因素有很多，通过比较筛选，本文选择种群规模Ⅳ、交叉概率P_c、变异概率P_m这3个参数作为优化对象；为了兼顾精度与试验速度，确定每个因素的水平数为6个，各参数常用的取值范围为：N（40～260）、P_c（0.25～0.85）、Pm（0.01～0.09）。

3.1 均匀设计在参数优化中的应用

3.1.1 选择合适的均匀设计表

根据因素和水平优先选取均匀设计表U^*₆（6⁴）。

3.1.2 实验安排及结果

本文选取Schaffer2 Function函数和Rastrigin函数进行函数测试。

（1）Schaffer2Function

（2）Rastrigin函数

对于Schaffer2 Function函数，由表3可知，在GA参数优化的均匀设计表中最佳参数组合为第6组，即种群规模N为260，交叉概率只为0.75，变异概率P_m为0.04，此时最优解为0.0013，平均解为0.0013。由表4可知，对于Rastrigin函数而言，最佳参数组合为第6组，即种群规模N为260，交叉概率P_c为0.75，变异概率P_m为0.04，此时最优解为0.0095，平均解为0.0125。

3.2 正交设计在参数优化中的应用

3.2.1 选择合适的正交表

在遗传算法参数优化问题中，满足条件的最小正交表为L₂₅（5⁶）。（注：由于没有6水平的正交表，故本次试验选择5水平）

3.2.2 试验安排及结果

对于Schaffer2 Function函数，由表5可知，采用正交设计法后，GA参数优化的最佳参数组合为第25组，即种群规模N为200，交叉概率P_c为0.75，变异概率P_m为0.04，此时的最优解为0.0013，平均解为0.0013；由表6可知，Rastrigin函数最佳组合为第11组，即种群规模N为120，交叉概率P_c为0.25，变异概率P_m为0.03，此时的最优解为0.0095，平均解为0.0098。在文献中，Ras-trigin函数的最优解为0.0134，而正交设计法配置的参数结果最优为0.0095，明显小于其最优解，由此可见采用试验设计法能在一定程度上优化遗传算法的结果。

3.3 结论

从表7可以看出，对于Schaffer2 Function函数，不论是均匀设计还是正交设计，用试验设计进行GA参数配置所得的最优解和平均解都优于随机产生的参数。

从表8中可以看出，对于Rastrigin函数，不论是均匀设计还是正交设计，用试验设计进行GA参数配置所得的最优解和平均解都优于随机产生的参数，而正交设计所的结果又比均匀设计的更精确。

此外，两种试验设计设定参数的遗传算法都收敛得很快，而随机调整法最慢。这也进一步证明将试验设计应用在遗传算法的参数优化配置中可以提高遗传算法的收敛性及寻优性能。

4 结语

由于遗传算法中种群大小N，交叉概率只，变异概率P_m等参数在进行实验室都是随机产生的，故本文对遗传算法参数优化配置进行了研究。分析Schaffer2 Function函数和Rastrigin函数的模拟结果可以看出，不论是通过正交设计还是均匀设计配置的参数所得到的测试结果都明显优于随机产生的参数的测试结果。因此，将试验设计应用在遗传算法的参数优化配置中会提高遗传算法的收敛性及寻优性能。

责任编辑 祁秀春