(19)中华 人民共和国 国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110681313.8 (22)申请日 2021.06.18 (65)同一申请的已公布的文献号 申请公布号 CN 113343573 A (43)申请公布日 2021.09.0 3 (73)专利权人 烽火通信科技股份有限公司 地址 430000 湖北省武汉市东湖高新 技术 开发区高新四路6号 (72)发明人 李帆　赵培超　曹文涛　 (74)专利代理 机构 深圳市六加知识产权代理有 限公司 4 4372 代理人 向彬 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/00(2006.01)G06Q 10/04(2012.01) G06Q 10/06(2012.01) (56)对比文件 CN 10210490 0 A,2011.06.22 CN 112584417 A,2021.0 3.30 CN 103812671 A,2014.0 5.21 CN 103607309 A,2014.02.26 WO 20121 13279 A1,2012.08.3 0 US 2009187939 A1,20 09.07.23 赵琳敬等. 《基 于变异交叉方程与进化选择 机制的回溯优化改进算法》 . 《计算机 应用研究》 .2019, 王海龙等. 《回溯搜索优化 算法研究进 展》 . 《湖北工程学院学报》 .2018, 审查员 陈欢 (54)发明名称 基于回溯搜索算法的用户感知度评估方法 与电子设备 (57)摘要 本发明公开了一种基于回溯搜索算法的用 户感知度评估方法， 包括： S1、 定义QoE变量结构 模型， 输入变量为待评估业务的KQI指标， 输出变 量为该业务的综合用户感知度； S2、 采用二叉树 编码关系预测模型； S3、 改进BSA算 法适应于运算 符的交叉变异策略， 包括基于变异步长实现的变 异方式， 提供单点因子、 组合因子结合变异方式； S4、 基于映射值Map实现交叉策略， 提供单点、 多 点交叉因子保留策略。 针对KQI ‑QoE数值关系模 型构建研究， 以提高关系模型质量和构建效率， 并应用于物联网平台下挂设备业务场景的用户 体验度评估。 本发明还提供了相应的电子设备。 权利要求书2页 说明书9页 附图6页 CN 113343573 B 2022.03.29 CN 113343573 B 1.一种基于回溯搜索算法的用户感知度评估方法， 其特 征在于， 包括 步骤： S1、 定义QoE变量结构模型， 输入变量为待评估业务的KQI指标， 输出变量为该业务的综 合用户感知度； 所述 步骤S1中Q oE变量结构模型为： 已知N组样本数据， 则具有T个子项感知度的综合用户感知评估问题的目标函数表示如 下： 其中， yit*表示第i个样本的第t子项感知度， yit表示由自变量评估得到的第i个样本的 第t子项感知度， xit1表示第i个样本的第t子项 感知度的第一个关键质量指 标， 依次类推， ft 为子项感知关系预测模型； S2、 采用二叉树编码关系预测模型； 具体为： 将T个子项树看作问题的一个可行解， 其 中， 每个子项树t采用二叉树编 码， 且二叉树满足以下模型约束： (1)二叉树满足最大深度约 束； (2)二叉树由运算符、 自变量、 常数组成； (3)二叉树的每个结点元素选择范围为运算符、 自变量或常数； (4)二叉树根结点、 中间结点必须为运算符， 终结点必须为自变量或常数； (5)二叉树对应子项预测模型的适应度值 不小于预设值； S3、 改进BSA算法适应于运算符的交叉变异策略， 包括基于变异步长实现的变异方式， 提供单点因子、 组合因子结合变异方式； 包括： 初始化种群、 选择I操作、 变异操作、 交叉操 作、 合法化操作、 选择II操作， 其中， 初始化两个种群， 分别为Pold和Pinit， 种群规模大小均为 S， 种群中的每 个个体包括T个子项预测模型； 其中： 所述变异操作具体为： 通过Pold指导Pinit个体变异， 即预测模型的变异， 产生大小为S的 变异种群Pmut， 以增强预测模型的多样性， 根据统计变异步长实现预测模型变异， 并依据变 异因子类型不同， 定义适应于预测模型的变异约束， 以增强变异个体质量； 统计变异步长过 程满足以下约束： 变异因子位置相同不互换； 不同类别的元素不互换， 即运算符为一类、 自 变量和常数为一类； 一元与二元运算符直接互换必然产生不合法， 则利用组合变异因子互 换； 变异因子映射位置长度超出位置最大值， 则同种类型因子中选择任一不同于原值的元 素替换； 所述合法化操作包括直接裁剪法、 最小合法树法以及随机新二叉树法， 其中： 直接裁剪 法， 直接裁剪超出限制部分， 并将原终结点x11和x12直接替换成裁剪后二叉树终结点； 最小 合法树法， 随机生成最小二叉树， 即深度为1的二叉树替换不合法部分二叉树； 随机新二叉 树法， 舍弃当前不 合法二叉树； S4、 基于映射 值Map实现交叉 策略， 提供 单点、 多点交叉因子保留策略。 2.如权利要求1所述的基于回溯搜索算法的用户感知度评估方法， 其特征在于， 所述选 择I操作具体为： 通过随机概率， 判断种群Pold是否需要继续保持现有的种群信息， 若不需要保持现有种 群信息， 则使用种群Pinit更新当前种群Pold， 所述随机概率包括 随机数a和b服从[0,1]范围 内的正态分布， 分别记作a～U(0,1)， b～U(0,1)； 随机改变种群Pold中的个体顺序， 即预测模型顺序。 3.如权利要求1所述的基于回溯搜索算法的用户感知度评估方法， 其特征在于， 所述选权　利　要　求　书 1/2 页 2 CN 113343573 B 2择II操作包括： 将试验种群Ptrial中具有较好适应度 值的试验个体， 用于淘汰种群Pinit中适应度较差的 预测模型， 比较子项 适应度， Fitness(Pinit k,t)表示Pinit中的第k个预测模型在子项t的适应 度值， Fitness(Ptrial k,t)表示Ptrial中的第k个预测模型在子项t的适应度值， 如果Fitness (Ptrial k,t)优于Fitness(Pinit k,t)， 则使用Ptrial中的第k个预测模型在子项t的方案淘汰对 应的Pinit中的第k个预测模型在子项t的方案； 否则保留原 有Pinit中的第k个预测模型在子项 t的方案不变， 最后形成更新后的大小仍然为S的种群Pinit。 4.如权利要求1所述的基于回溯搜索算法的用户感知度评估方法， 其特征在于， 所述交 叉策略包括： 将变异操作得到的变异种群Pmut作为与种群Pinit中个体的交叉对象， 即预测模 型的交叉对象， 产生 大小为S的交叉试验种群Ptrial， 进一步增强种群多样性， 提 供单点、 多点 交叉因子保留策略， 在一定程度上保留个 体特征， 即预测模型部分特 征。 5.如权利要求4所述的基于回溯搜索算法的用户感知度评估方法， 其特征在于， 所述交 叉策略的过程具体为： 创建映射值Map， 产生两个[0 ‑1]范围的随机数d和e， 并分别记作d～U(0,1)， e～U(0, 1)， 若d<e， 计算交叉概率Pmixed、 [0‑1]随机数、 元素个数的乘积， 并向上取整， 决定映射元素 个数； 若d>e， 计算[0 ‑1]随机数、 元素个数的乘积， 并向上取整， 决定映射元素的索引， 初始 映射值Map均为1， 两种不同的映射方式增强了交叉 策略的随机性、 交叉 结果的多样性； 通过Pinit、 Pmut以及对应的映射值Map创建试验种群Ptrial， 对应值为0的元素所在二叉树 分支保持不变， 剩余的元素按照变异的预测模型进 行交叉变化， 以产生试验个体， 即试验预 测模型。 6.一种电子设备， 其特 征在于， 包括： 至少一个处 理器； 以及， 与所述至少一个处 理器通信连接的存 储器； 其中， 所述存储器存储有可被所述至少一个处理器执行的指令， 所述指令被所述至少一个处 理器执行， 以使所述至少一个处 理器能够执 行权利要求1 ‑5任一项所述的方法。权　利　要　求　书 2/2 页 3 CN 113343573 B 3