双种群自适应遗传算法及其在知识挖掘中应用

严太山，王 欣

（湖南理工学院信息科学与工程学院，岳阳 414000）

0 引言

知识规则挖掘是从规则数据集中发现有用新知识规则的过程，知识规则挖掘算法的好坏直接影响到所发现的新知识规则的好坏，目前人们用到的知识规则挖掘算法有多种［1-6］，如统计方法、神经网络、机器学习、粗糙集方法、遗传算法，等等。在这些算法中，遗传算法是基于“优胜劣汰、适者生存”的生物进化机理而建立的一种智能优化算法，凭借其强大的鲁棒性和全局搜索能力而倍受人们的青睐。但是，传统遗传算法是在一个种群中以固定的交叉率和变异率来工作的，对于一个给定的优化对象，为了找到合适的交叉率和变异率，往往需要经过反复试验，耗费大量时间，影响了算法的效率，而且在这种情况下，算法也难以满足种群多样性要求。诸多学者提出了各种自适应遗传算法［7-12］，但大多是从适应性参数设置方面进行研究的，其通常做法是使交叉率Pc、变异率Pm等遗传参数在进化过程中根据种群的实际情况动态调整大小，在不同程度上提高全局收敛率和寻优效率。但由于进化种群的单一性及遗传个体无性别区分，无法从根本上保证算法有效地调出局部最优。为此，本文提出一种具有雌、雄个体的双种群自适应遗传算法，并将该算法应用于实践教学质量评价知识规则挖掘，利用算法的全局寻优能力，在已有的实践教学质量评价知识规则库中进行寻优，得到隐含在其中的更为优秀的新知识规则，为提高实践教学质量评价的科学性提供保障。

1 双种群自适应遗传算法

1.1 算法思想

为了克服传统遗传算法因进化种群单一而无法确保跳出局部最优的问题，我们在遗传算法中引入“主导种群+辅助种群”双种群机制，并在主导种群、辅助种群中以不同的策略实现遗传个体的进化。为了减少选择操作的盲目性，引入生物界有性繁殖的特征，将遗传个体分为雄性个体和雌性个体两种性别类型，让异性个体进行交叉操作。由此建立一种双种群自适应遗传算法（dual population adaptive genetic algorithm，DPAGA）。该算法的基本思想是：以选择操作选中的个体作为新的进化种群——主导种群，未被选择操作选中的个体组成另一种群——辅助种群；主导种群在进化过程中执行自适应大概率交叉和小概率变异操作，辅助种群进化过程中执行自适应小概率交叉和大概率变异操作，在辅助种群的作用下，算法出现早熟时能有效跳出局部最优。

1.2 遗传操作

1.2.1 选择操作

在DPAGA算法中，采用两代竞争排序的选择方法来选择优秀遗传个体作为交叉操作的备选对象。为确保异性个体进行有效交叉，被选中的个体中雄性个体和雌性个体应在数量上保持相等，并分别按优劣顺序进行排序。这样更好地保持了进化过程中的遗传多样性，使优秀基因和模式不被破坏，有利于进化过程朝着全局最优解方向发展。

1.2.2 交叉操作

DPAGA算法中，进行交叉操作的两个个体是按优劣顺序配对的两个异性个体。交叉方式为单点自适应交叉，其主导种群交叉率Pdc和辅助种群交叉Pac分别按以下方式进行自适应调整：

1.2.3 变异操作

DPAGA算法的变异操作为自适应变异，其主导种群变异率Pdm和辅助种群变异率Pam分别按以下方式进行自适应调整：

公式（1）～（4）中，fdmax及famax分别表示主导种群、辅助种群的适应度最大值，fdavg及faavg分别表示主导种群、辅助种群的适应度平均值，f'表示两交叉个体适应度的最大值，f表示变异个体的适应度值，Pdc1及Pdc2分别表示主导种群交叉率的最大值和最小值，Pac1及Pac2分别表示辅助种群交叉率的最大值和最小值，Pdm1及Pdm2分别表示主导种群变异率的最大值和最小值，Pam1及Pam2分别表示辅助种群变异率的最大值和最小值。

1.3 算法流程

DPAGA算法流程如图1所示。

图1 DPAGA算法流程

2 基于DPAGA的实践教学质量评价知识规则挖掘方法

2.1 实践教学质量评价指标体系构建

在高等教育人才培养体系中，实践教学一直是一个重要环节。高校在加强实践教学日常管理的同时，还需要定期对实践教学质量进行客观的评价。进行实践教学质量评价，首先需要构建合理的评价指标体系。实践教学质量评价指标体系要符合教学实际，体现实践教学的特点、目标和要求，同时要遵循教学评价指标体系的导向性原则、科学性原则、全面性原则、稳定性与动态性兼顾的原则［13-15］。当然，评价指标体系中的指标数量要合适，而不是越多越好，因为随着指标数的增加，计算量会呈指数急剧上升。我们通过对大量的实践教学评价数据进行分析，并结合本校的实践教学实际，构建了一套较完善的实践教学质量评价指标体系。该指标体系的一级指标有4个，它们分别是实践教学过程、实践教学效果、实践教学环境和实践教学保障，这些一级指标下面一共有20个二级指标，如图2所示。

图2 实践教学质量评价指标体系

其中，x1～x4分别表示实验室建设是否完善、人均实践面积的大小是否合适、实践场地和设备的实用性、实践场地与设备的利用率；x5～x8分别表示生师比例是否合理、实践学分占比是否恰当、实践教学安全保障是否到位、常规管理制度是否有效执行；x9～x14分别表示教学过程安排是否合理、教师教学态度是否认真、教师教学方法是否得当、实践教学内容与理论衔接程度、教学内容的实用性和前沿性；x15～x20分别表示是否提高了学生学习积极性、是否培养了学生创新意识、是否培养了学生操作能力、是否促进了学生对理论知识的掌握、学生实践报告完成情况、学生考核结果是否满意。

2.2 知识规则表示与编码

与其他知识规则表示方法相比，产生式规则表示方法具有符合人类认知特征、格式简单、直观自然等突出的优越性，使得它成为应用最广泛的一种知识规则表示方法，非常适合于实践教学质量评价。产生式知识规则在结构上是由前提和结论两部分组成的，其形式描述如下：

IF E1（A1,A2,…,Am）and E2（A1,A2,…,Am）and…and En（A1,A2,…,Am）THEN H（结论）。其中，Ei（A1,A2,…,Am）（1≤i≤n）是以Ai（1≤i≤m）为属性的前提条件，H表示结论。

我们采用0-1编码方式对知识规则进行编码，每个评价指标及评价结论均有优、良、中、差四个评价等级，四个评价等级的标记及编码如表1所示，知识规则编码结构如图3所示。

表1 评价等级的标记及编码

图3 知识规则个体编码结构

图3中，S为知识规则个体的性别编码，对于雄性个体，S=1；对于雌性个体，S=0；Ui为知识规则个体的第i个前提属性值（即第i个评价指标等级）的编码；由于全部条件不一定均被包含到规则中去，所以对每个前提属性需设置一个标志位Flagi，如果条件i被规则包含，则Flagi=1；否则，Flagi=0；C为知识个体结论属性值（评价等级）的编码。

2.3 知识规则评价与检验

我们选取的实践教学质量评价知识规则的评价目标包括正确度、覆盖度和可信度，利用这些评价目标的线性组合来进行知识规则适应度评价。正确度、覆盖度和可信度的定义分别为

（1）正确度

（2）覆盖度

（3）可信度

公式（5）～（7）中，U为测试数据集，ri为待评价的知识规则，为U的一个子集，其所有元素均与ri相匹配，为Ω的基数；W为U的另一子集，其所有元素的前提条件与ri相匹配，为Ω的基数，为U中与已有知识规则前提条件相匹配的元素个数最大值，Tri为知识规则库中满足ri条件完备的应有规则条数，TC为知识规则库中结论的种数。

DPAGA算法运行之后，进行反复迭代运算，产生新的个体。对于算法挖掘出的新知识规则个体，需要进行有效性检验，如果规则rj被知识规则库中已有的规则包含，或者与已有的规则相矛盾，则rj无效，予以删除。有效性检验完成之后，再根据适应度值的大小，挑选那些优秀的新知识规则个体加入到实践教学质量评价知识规则库中。

3 算例

实践教学质量评价知识规则库即测试数据集，其部分知识规则个体如表2所示。按照0-1编码方式对知识规则个体进行编码，利用评价目标的线性组合对知识规则个体进行适应度计算，编码和适应度计算结果如表3所示。

表2 实践教学质量评价知识规则库

表3 知识规则编码及其适应度评价

我们应用改进遗传算法DPAGA分别进行知识规则挖掘，DPAGA参数设置为：T=200，M=100，Pdc1=0.9，Pdc2=0.6，Pac1=0.1，Pac2=0.001，Pdm1=0.1，Pdm2=0.001，Pam1=0.5，Pam2=0.1。为分析DPAGA产生的新知识规则有效性，选取DPAGA第5次迭代运算后得到的结果，此时挖掘出的新知识规则个体编码如表4所示，相应的知识规则个体如表5所示。在DPAGA算法挖掘出的八条新知识规则中，经过有效性检验，发现其中两条被知识规则库中的现有规则包含了，它们分别是新规则N2被知识规则库中的现有规则3包含，新规则N6被知识规则库中的现有规则16包含；另有两条与知识规则库中的现有规则相矛盾，它们分别是新规则N5与知识规则库中的现有规则14相矛盾，新规则N7与知识规则库中的现有规则6相矛盾，这四条规则是无效的知识规则，应被删除。只有规则N1、N3、N4和N8是有效的新知识规则，按照上述适应度评价方法计算得到N1、N4的适应度值均为0.961450，N3的适应度值为0.914062，N8的适应度值为0.726775。

表4 新知识规则编码

表5 新知识规则

通过把新知识规则N1、N3、N4和N8的适应度值与知识规则库的现有规则相比较，可以看出N1、N3、N4的适应度值较大，它们是较优秀的新知识规则，因此这三条新知识规则将被加入到实践教学质量评价知识规则库中，使知识规则库得以更新。

4 结语

本文以主导种群和辅助种群为基础，结合有性繁殖思想，提出了一种双种群自适应进化遗传算法，避免了传统遗传算法的种群单一性和遗传个体无性别区分的缺陷，解决了传统遗传算法交叉率、变异率难以找到最佳值的问题，增强了遗传算法的全局寻优能力，提高了遗传算法的寻优效率。为得到隐含在实践教学质量评价知识规则库中的优秀知识规则，提高实践教学评价的科学性，将双种群自适应进化遗传算法应用于知识规则挖掘。实例结果表明，利用改进遗传算法进行知识规则挖掘是有效的，能够快速挖掘出优秀的新知识规则，为实践教学质量评价的公平、公正提供保障。