遗传算法在用户感知评估建模中的应用

摘要：在建立用户感知评估变量结构模型的基础上，利用遗传算法对KQI-QoE关系进行动态自适应建模，并与线性回归方程、指数回归方程、抛物线回归方程以及对数回归方程等传统的拟合方法进行了对比。实际用户感知和评估体系的拟合结果表明，遗传算法在用户感知建模方面具备良好的自适应搜索最优解的能力。这为进一步研究和完善用户感知评估体系提供了新的方法和途径。

关键词：移动；数据业务；用户感知；评估建模；遗传算法

随着通信技术的发展，移动通信网络可以为用户提供越来越丰富的移动业务和应用，如彩信、网页浏览、WAP、流媒体、网络游戏等，这些业务为移动运营商提供了持续增长的收入来源。因此，如何评估和提升移动通信业务的用户体验质量（即用户感知），成为全球各大运营商关注和研究的重点，同时也是运营商在激烈的市场竞争中吸引用户、保持和扩大盈利的关键。

目前，评估用户感知通常有两种方法：一种是通过用户调查获取用户的实际体验质量；另一种则是通过测量用户所应用业务的性能，即关键业务质量指标（KQI），推算出用户的实际体验质量。两种方法各有利弊。通过用户调查获取用户感知，优点是可以得到实际的用户感知；缺点是无法实现实时监控，滞后性较大，并且每次用户调查都将耗费较大的人力、物力和时间。通过KQI推算用户感知，只需在建模期间提供用户调查得到的实际用户感知数据，然后利用该数据和相应的KQI指标建立KQI-QoE数量关系模型，即可形成一套稳定的实时监测系统。建成之后，无须再进行用户调查，操作维护简单，效费比高；其缺点是KQI-QoE模型的不合理性将对推算出的用户感知造成误差。如果能够构建出合理的KQI-QoE数量关系模型，显然采用第2种方法更具吸引力。因此，文章重点研究了KQI-QoE数量关系模型的构建方法。

常用的回归分析模型包括：线性回归方程、指数回归方程、抛物线回归方程以及对数回归方程。当待拟合数据具备其中某一种模型的特性关系时，采用相应的模型方程进行曲线拟合，则可以得到良好的趋势曲线，误差也较小。但是，对于KQI-QoE这类未知特性的数据，如果利用以上固定的模型方程进行曲线拟合，则很可能无法得到准确的趋势曲线，而且误差可能也较大[1-3]。

遗传算法是模仿生物遗传学和自然选择机理，在一定的解空间中搜索最优结果的算法，是对生物进化过程进行的一种数学仿真，也是进化计算的一种最重要的形式。若采用遗传算法，则无需给出特定回归模型方程，可进行自适应拟合，因而适用于对未知关系特性的数据模型拟合。

1 用户感知评估相关的

基本概念

在移动通信业务应用领域，用户感知评估就是获得用户对某种业务的应用感受情况，它涉及两个基本概念：一个是用户感知，另一个是KQI。

一般情况下，我们所说的“用户感知”指的是用户或客户的体验质量（QoE），也就是用户实际感受到的服务网络和业务的服务质量（QoS）。例如，用户感受到的语音或图像的清晰程度、文件收发的快慢等。

而用户对某一特定业务的质量的感受又是多方面或多个类别的，例如，对于语音电话业务，用户的感受主要有4个方面：

·电话是否能接通，即拨号后是否能听到回铃声。

·电话接通所需要等待的时间长短。

·电话接通后是否会异常断线，也就是掉话。

·打电话期间的语音质量如何，如语音是否清晰、是否会断断续续、是否存在较大的通话时延等。

因此，QoE指标分为子项感知度和整体感知度，子项感知度与用户对业务某一方面的应用感受相一致；整体感知度是用户对某一业务应用的综合体验质量，是该业务对应的所有子项感知度的综合反映。

KQI就是服务提供商实际提供的QoS，可通过测量或统计得到，它反映了业务或应用的端到端性能。一个或一组KQI指标能够直接地表征业务某一方面的性能，如时延特性、网页浏览流畅度等[4]。

2 用户感知评估变量结构

模型

用户感知评估变量结构模型定义了用户感知评估涉及哪些结构变量，以及这些变量之间的逻辑关系。这是构建数学描述模型的基础。

用户感知的评估是针对某一种业务进行的。由第1节中所举语音电话例子，可以看出，对于任一种业务，均可根据用户的感受，划分为多个类别的性能。一个类别的性能既对应了一个子项感知度指标，又对应了一个或一组KQI指标。业务的端到端性能指标将影响相应类别的用户感知（即子项感知度），而用户对该业务的整体感知则受各种类别的用户感知综合影响。

基于上述分析，我们建立了如图1所示的用户感知评估变量结构模型，变量的影响关系是自下而上的，具体表现为：

·一个类别的端到端业务性能对应了一个子项感知度指标和一组KQI指标。

·KQI指标的好坏直接影响了相应子项感知度的好坏。

·子项感知度的好坏直接影响了整体感知度的好坏。

因此，从用户感知评估的角度，模型的输入变量是待评估业务的KQI指标，输出变量是该业务的子项感知度和整体感知度。

下面我们将根据这个结构模型，运用遗传算法建立确定性的KQI-QoE数量关系模型。

3遗传算法应用设计

采用遗传算法进行自适应曲线拟合，是从问题的解空间中一个随机产生的种群开始进化的。这个种群则由一定数目的函数表达式组成，每一个函数表达式则代表着一个个体，同时也有可能是我们所想得到的具体数学模型[5]。

个体也就是染色体，它由一定数目的基因组成，基因的不同和组合方式的不同则决定了个体的特性。因此，使用遗传算法，首先需要实现将函数表达式从表现型到基因型的映射，也就是编码。

3.1 编码方式

常用的编码方式有二进制编码、二叉树编码、实数编码等，对于函数拟合问题，最常用的编码方式是二叉树编码，即把组成群体的所有个体采用一种动态的树状结构来表示。图2是一个二叉树的示例，它表示了函数f（x， y， z）=（y ^ 6）*ln（x）+exp（z）。

这棵树的结点由根节点、中间节点和终结点组成，每个节点就是一个基因。

根结点和中间结点统称为内部结点，通常是运算符；终结点则为自变量和函数常数项。树结构表达的函数则是待求函数形式的一个可能的解[6]。

3.2 算法流程

遗传算法的实现流程如图3所示，包含以下几个步骤：

（1）定义解空间，并进行种群初始化，产生由一定数量个体二叉树组成的种群。

（2）对种群个体的相关适应度进行评估。

（3）从当前群体中选择一定数量适应度高的个体。

（4）对选取的二叉树个体进行杂交操作。

（5）对种群中的个体进行相关变异操作。

（6）种群更新，即将完成杂交和变异后的子代个体替代父代种群中适应度低的个体。

3.3 种群初始化

解空间由预测模型涉及的运算符集、自变量符号集和数据集的复合。其中，运算符集则包含了模型涉及的加、减、乘、除等各类函数运算符；自变量符号集则包含了模型可能涉及所有自变量；数据集则是模型涉及的各类常数的最大取值范围，例如常数项、指数项、系数项等。

解空间定义之后，随机产生一定数量的二叉树个体，并且将会按如下原则对每个个体的二叉树节点进行填充：

·对于内部节点，均随机由运算符集中选择一个函数符号填充。

·对于终结点，则首先随机选择是自变量还是数据项，若是自变量，则随机从自变量符号集中随机选择一个自变量填充。

·若是数据项，则在常数项取值范围内随机选择一个常数填充。

3.4 个体适应度评估

种群进化的目标是使得拟合曲线的误差尽量最小，因此我们采用最小二乘法的原则，选择残差平方和作为个体的适应度函数。对于某一个体，其计算公式如下：

其中，N表示样本数；

[yi]表示因变量；

[f（?）]表示[yi]由[x1，…，xm]表示的个体函数表达式；

3.6 杂交算子

对选择复制出来的个体进行杂交。杂交的规则如下：

·对父代个体进行两两随机配对，形成杂交配对池；每一对父体均在一定概率条件下进行杂交。

·对于杂交的两个父代个体，各自分别随机选择一棵子树，然后交换子树，得到相应的子代个体。

·对于根深大于最大树根深度限值的子代，则把超过部分最大根深限值的枝叶全部直接剪除；然后，将剪除后的最末一层的中间节点改为终结点，填充方式与种群初始化方式相同。

3.7 变异算子

父代个体在一定概率条件下进行变异操作，具体规则如下：

·对需要变异的个体，在所有节点中随机选择其中的一个作为变异分界节点，对该节点及其所有分支进行变异。

·对于内部节点，则在运算符集中随机选择其他元素进行替换，替换值不同于原值。

·对于终结点，则在自变量符号集或数据集中随机选择一个进行替换，替换值允许等同于原值。终结点的填充方法与种群初始化方式相同。

3.8 种群更新

种群更新就是将父代个体中适应度最差的若干个体用变异后产生的子代个体进行替代。

为了保证每一代中的最好个体都能保留到下一代中，则直接将最好个体替代父代中的最差个体。

3.9 终止条件

终止条件可仅设定为以下3种中的任一种；或3种条件都设定，只要其中一项满足条件即终止：

·达到繁殖最大次数。

·达到算法程序运行的最大时长。

·种群中最优个体的残差平方和小于或等于某一给定值。

4建模结果分析

文章根据中国某市的网页浏览业务实际用户调查数据与KQI统计指标，分别采用遗传算法和传统回归方程对原始数据进行拟合，建立了相应的数学模型，并按照最小二乘法的原则，对这些模型的残差平方和进行了对比分析[7]。

建模目标为：建立网页打开成功率满意指数KQI-QoE数学模型。QoE指标网页打开成功率满意指数对应的KQI指标仅一项，为网页打开成功率。建立的数学模型应为一元函数。

遗传算法的参数设定为：运算符集为{+，-，*，/，^，exp，log}，自变量符号集X={x}，数据集c={-10

如表1所示，为遗传算法与其他传统回归算法建立的数学模型及其残差平方和运算结果对比，相应的曲线对比则如图4所示。

由上述对比可以看出，遗传算法所建立的数学模型残差平方和最小，拟合度优于其他算法。

此外，一般对于曲线拟合，遗传算法的繁衍次数还可以取得更大，例如10 000到100 000次，随着繁衍次数的增加，模型的拟合度也将随之提高。因此，虽然我们仅通过1 000次繁衍得到的数学模型已经具有较好的拟合度，但通过增加繁衍次数仍有较大的提升空间。

5结束语

文章在建立用户感知评估构架模型的基础上，采用遗传算法对QoE-KQI数量关系进行了动态自适应建模，并与线性回归方程、指数回归方程、抛物线回归方程以及对数回归方程等传统的拟合方法进行了对比。文中给出的一维变量关系拟合结果表明，遗传算法在用户感知建模方面具备良好的自适应搜索最优解的能力，所拟合的模型要明显优于传统方法。而且由于遗传算法无须像传统方法一样事先给出特定的关系模型，使其更适合于建立多变量相互影响的关系模型，这也更有益于进一步研究和完善用户感知评估体系，从而运营商提升用户感知管理水平。

这棵树的结点由根节点、中间节点和终结点组成，每个节点就是一个基因。

根结点和中间结点统称为内部结点，通常是运算符；终结点则为自变量和函数常数项。树结构表达的函数则是待求函数形式的一个可能的解[6]。

3.2 算法流程

遗传算法的实现流程如图3所示，包含以下几个步骤：

（1）定义解空间，并进行种群初始化，产生由一定数量个体二叉树组成的种群。

（2）对种群个体的相关适应度进行评估。

（3）从当前群体中选择一定数量适应度高的个体。

（4）对选取的二叉树个体进行杂交操作。

（5）对种群中的个体进行相关变异操作。

（6）种群更新，即将完成杂交和变异后的子代个体替代父代种群中适应度低的个体。

3.3 种群初始化

解空间由预测模型涉及的运算符集、自变量符号集和数据集的复合。其中，运算符集则包含了模型涉及的加、减、乘、除等各类函数运算符；自变量符号集则包含了模型可能涉及所有自变量；数据集则是模型涉及的各类常数的最大取值范围，例如常数项、指数项、系数项等。

解空间定义之后，随机产生一定数量的二叉树个体，并且将会按如下原则对每个个体的二叉树节点进行填充：

·对于内部节点，均随机由运算符集中选择一个函数符号填充。

·对于终结点，则首先随机选择是自变量还是数据项，若是自变量，则随机从自变量符号集中随机选择一个自变量填充。

·若是数据项，则在常数项取值范围内随机选择一个常数填充。

3.4 个体适应度评估

种群进化的目标是使得拟合曲线的误差尽量最小，因此我们采用最小二乘法的原则，选择残差平方和作为个体的适应度函数。对于某一个体，其计算公式如下：

其中，N表示样本数；

[yi]表示因变量；

[f（?）]表示[yi]由[x1，…，xm]表示的个体函数表达式；

3.6 杂交算子

对选择复制出来的个体进行杂交。杂交的规则如下：

·对父代个体进行两两随机配对，形成杂交配对池；每一对父体均在一定概率条件下进行杂交。

·对于杂交的两个父代个体，各自分别随机选择一棵子树，然后交换子树，得到相应的子代个体。

·对于根深大于最大树根深度限值的子代，则把超过部分最大根深限值的枝叶全部直接剪除；然后，将剪除后的最末一层的中间节点改为终结点，填充方式与种群初始化方式相同。

3.7 变异算子

父代个体在一定概率条件下进行变异操作，具体规则如下：

·对需要变异的个体，在所有节点中随机选择其中的一个作为变异分界节点，对该节点及其所有分支进行变异。

·对于内部节点，则在运算符集中随机选择其他元素进行替换，替换值不同于原值。

·对于终结点，则在自变量符号集或数据集中随机选择一个进行替换，替换值允许等同于原值。终结点的填充方法与种群初始化方式相同。

3.8 种群更新

种群更新就是将父代个体中适应度最差的若干个体用变异后产生的子代个体进行替代。

为了保证每一代中的最好个体都能保留到下一代中，则直接将最好个体替代父代中的最差个体。

3.9 终止条件

终止条件可仅设定为以下3种中的任一种；或3种条件都设定，只要其中一项满足条件即终止：

·达到繁殖最大次数。

·达到算法程序运行的最大时长。

·种群中最优个体的残差平方和小于或等于某一给定值。

4建模结果分析

文章根据中国某市的网页浏览业务实际用户调查数据与KQI统计指标，分别采用遗传算法和传统回归方程对原始数据进行拟合，建立了相应的数学模型，并按照最小二乘法的原则，对这些模型的残差平方和进行了对比分析[7]。

建模目标为：建立网页打开成功率满意指数KQI-QoE数学模型。QoE指标网页打开成功率满意指数对应的KQI指标仅一项，为网页打开成功率。建立的数学模型应为一元函数。

遗传算法的参数设定为：运算符集为{+，-，*，/，^，exp，log}，自变量符号集X={x}，数据集c={-10

如表1所示，为遗传算法与其他传统回归算法建立的数学模型及其残差平方和运算结果对比，相应的曲线对比则如图4所示。

由上述对比可以看出，遗传算法所建立的数学模型残差平方和最小，拟合度优于其他算法。

此外，一般对于曲线拟合，遗传算法的繁衍次数还可以取得更大，例如10 000到100 000次，随着繁衍次数的增加，模型的拟合度也将随之提高。因此，虽然我们仅通过1 000次繁衍得到的数学模型已经具有较好的拟合度，但通过增加繁衍次数仍有较大的提升空间。

5结束语

文章在建立用户感知评估构架模型的基础上，采用遗传算法对QoE-KQI数量关系进行了动态自适应建模，并与线性回归方程、指数回归方程、抛物线回归方程以及对数回归方程等传统的拟合方法进行了对比。文中给出的一维变量关系拟合结果表明，遗传算法在用户感知建模方面具备良好的自适应搜索最优解的能力，所拟合的模型要明显优于传统方法。而且由于遗传算法无须像传统方法一样事先给出特定的关系模型，使其更适合于建立多变量相互影响的关系模型，这也更有益于进一步研究和完善用户感知评估体系，从而运营商提升用户感知管理水平。

这棵树的结点由根节点、中间节点和终结点组成，每个节点就是一个基因。

根结点和中间结点统称为内部结点，通常是运算符；终结点则为自变量和函数常数项。树结构表达的函数则是待求函数形式的一个可能的解[6]。

3.2 算法流程

遗传算法的实现流程如图3所示，包含以下几个步骤：

（1）定义解空间，并进行种群初始化，产生由一定数量个体二叉树组成的种群。

（2）对种群个体的相关适应度进行评估。

（3）从当前群体中选择一定数量适应度高的个体。

（4）对选取的二叉树个体进行杂交操作。

（5）对种群中的个体进行相关变异操作。

（6）种群更新，即将完成杂交和变异后的子代个体替代父代种群中适应度低的个体。

3.3 种群初始化

解空间由预测模型涉及的运算符集、自变量符号集和数据集的复合。其中，运算符集则包含了模型涉及的加、减、乘、除等各类函数运算符；自变量符号集则包含了模型可能涉及所有自变量；数据集则是模型涉及的各类常数的最大取值范围，例如常数项、指数项、系数项等。

解空间定义之后，随机产生一定数量的二叉树个体，并且将会按如下原则对每个个体的二叉树节点进行填充：

·对于内部节点，均随机由运算符集中选择一个函数符号填充。

·对于终结点，则首先随机选择是自变量还是数据项，若是自变量，则随机从自变量符号集中随机选择一个自变量填充。

·若是数据项，则在常数项取值范围内随机选择一个常数填充。

3.4 个体适应度评估

种群进化的目标是使得拟合曲线的误差尽量最小，因此我们采用最小二乘法的原则，选择残差平方和作为个体的适应度函数。对于某一个体，其计算公式如下：

其中，N表示样本数；

[yi]表示因变量；

[f（?）]表示[yi]由[x1，…，xm]表示的个体函数表达式；

3.6 杂交算子

对选择复制出来的个体进行杂交。杂交的规则如下：

·对父代个体进行两两随机配对，形成杂交配对池；每一对父体均在一定概率条件下进行杂交。

·对于杂交的两个父代个体，各自分别随机选择一棵子树，然后交换子树，得到相应的子代个体。

·对于根深大于最大树根深度限值的子代，则把超过部分最大根深限值的枝叶全部直接剪除；然后，将剪除后的最末一层的中间节点改为终结点，填充方式与种群初始化方式相同。

3.7 变异算子

父代个体在一定概率条件下进行变异操作，具体规则如下：

·对需要变异的个体，在所有节点中随机选择其中的一个作为变异分界节点，对该节点及其所有分支进行变异。

·对于内部节点，则在运算符集中随机选择其他元素进行替换，替换值不同于原值。

·对于终结点，则在自变量符号集或数据集中随机选择一个进行替换，替换值允许等同于原值。终结点的填充方法与种群初始化方式相同。

3.8 种群更新

种群更新就是将父代个体中适应度最差的若干个体用变异后产生的子代个体进行替代。

为了保证每一代中的最好个体都能保留到下一代中，则直接将最好个体替代父代中的最差个体。

3.9 终止条件

终止条件可仅设定为以下3种中的任一种；或3种条件都设定，只要其中一项满足条件即终止：

·达到繁殖最大次数。

·达到算法程序运行的最大时长。

·种群中最优个体的残差平方和小于或等于某一给定值。

4建模结果分析

文章根据中国某市的网页浏览业务实际用户调查数据与KQI统计指标，分别采用遗传算法和传统回归方程对原始数据进行拟合，建立了相应的数学模型，并按照最小二乘法的原则，对这些模型的残差平方和进行了对比分析[7]。

建模目标为：建立网页打开成功率满意指数KQI-QoE数学模型。QoE指标网页打开成功率满意指数对应的KQI指标仅一项，为网页打开成功率。建立的数学模型应为一元函数。

遗传算法的参数设定为：运算符集为{+，-，*，/，^，exp，log}，自变量符号集X={x}，数据集c={-10

如表1所示，为遗传算法与其他传统回归算法建立的数学模型及其残差平方和运算结果对比，相应的曲线对比则如图4所示。

由上述对比可以看出，遗传算法所建立的数学模型残差平方和最小，拟合度优于其他算法。

此外，一般对于曲线拟合，遗传算法的繁衍次数还可以取得更大，例如10 000到100 000次，随着繁衍次数的增加，模型的拟合度也将随之提高。因此，虽然我们仅通过1 000次繁衍得到的数学模型已经具有较好的拟合度，但通过增加繁衍次数仍有较大的提升空间。

5结束语

文章在建立用户感知评估构架模型的基础上，采用遗传算法对QoE-KQI数量关系进行了动态自适应建模，并与线性回归方程、指数回归方程、抛物线回归方程以及对数回归方程等传统的拟合方法进行了对比。文中给出的一维变量关系拟合结果表明，遗传算法在用户感知建模方面具备良好的自适应搜索最优解的能力，所拟合的模型要明显优于传统方法。而且由于遗传算法无须像传统方法一样事先给出特定的关系模型，使其更适合于建立多变量相互影响的关系模型，这也更有益于进一步研究和完善用户感知评估体系，从而运营商提升用户感知管理水平。