基于改进NSGA-Ⅱ算法的科技服务链推荐

陈冬林，王 蕾，刘 晶

(1.武汉理工大学经济学院，2.湖北省电子商务大数据工程技术研究中心，湖北武汉 430070)

2014 年10 月，国务院印发了《关于加快科技服务业发展的若干意见》（以下简称《意见》），提出了重点发展研究开发、技术转移、检验检测认证、创业孵化、知识产权、科技咨询、科技金融、科学技术普及等专业科技服务和综合科技服务，并强调“发展全链条的科技服务，形成集成化总包、专业化分包的综合科技服务模式”。在该《意见》和相关政策的促进下科技服务业蓬勃发展，大量科技服务机构和科技服务滋生。与此同时，用户需求日趋复杂化和链式化，单一科技服务往往难以满足用户的需求。因此，为响应国家号召和满足用户复杂需求，需组合单一科技服务构建综合科技服务链。然而，海量的科技服务使得用户难以选择合适的科技服务来构建综合科技服务链。在这种背景下，进行综合科技服务链推荐相关研究，向用户推荐满足其复杂需求的最佳科技服务链具有重要意义。

1 相关研究工作

目前，“科技服务链”［1-2］这一概念仅在少量文献中出现过，科技服务链的相关研究处于萌芽阶段。但科技服务链推荐与云制造服务组合优化较为相似，二者均以构建满足某复杂任务需求的最优服务链为目标，且均需考虑线上和线下场景，本质上都是多目标优化问题。在现有关于云制造服务组合优化的研究中，Bouzary 等［3］使用分类算法和TFIDF 算法检索候选服务，并使用元启发式算法获取最佳服务组合；Wang［4］等考虑了云制造服务之间的相关性，提出了一种多目标文化基因算法，可有效消除不可行的搜索空间和提供高QoS 服务组合；Yuan 等［5］构建了以时间、可组合性、质量、可用性、可靠性和成本为指标的服务质量评价指标体系，采用灰色关联分析法求解云制造服务组合模型；杨欣等［6］建立了考虑不确定性以及能耗的双目标规划模型，并采用改进的NSGA-II 算法对模型进行求解；陈友玲［7］等建立了考虑供需双方要求的约束模型，并使用改进的NSGA-II 算法对模型进行求解；Yang等［8］构建时间、成本、可靠性、可用性综合最优的服务质量评估模型，通过动态蚁群遗传混合算法求解最优云制造服务组合；Hong［9］等提出了一种综合的基于质量相关性的云制造服务描述模型，通过基于遗传算法的最优服务选择方法对模型进行求解；Zhou 等［10］构建了以时间、成本、可靠性和可用性为评价指标的评价模型，运用混合人工蜂群算法求解出最佳服务组合；马文龙等［11］构建服务质量计算模型，运用改进蚁群算法求解云制造动态服务组合优化问题；Lartigau 等［12］基于质量评估模型，同时考虑云服务的地理位置，通过改进的人工蜂群算法求解出最优的云制造服务组合。

上述研究在很大程度上解决了云制造服务组合优化问题，而科技服务链推荐过程与云制造服务组合优化过程具有很大相似性，因此上述模型和方法对解决科技服务链推荐问题具有很高的参考价值。但目前，少有研究使用上述模型和方法来求解科技服务链推荐问题。从模型方面来看，云制造服务组合优化模型仅考虑时间、成本、可靠性等通用指标，并未考虑云制造服务组合中不同类型服务的特有属性。服务的特有属性是区分不同类型服务的核心特性，是衡量服务质量最有力的指标，也是用户进行服务选择时最关注的指标。科技服务链推荐模型需依据不同类型科技服务所具有的特有属性来进行服务质量评估，从而确保科技服务链最大程度上满足用户对特定科技服务的要求。比如检验检测服务需要考虑检验结果有效率，以确保检验结果被其他机构认可；知识产权服务需要考虑其安全性，以保证知识产权信息不被泄露。从算法方面来看，NSGA-II算法是目前求解云制造服务组合优化问题较为常用的算法，但已有研究未考虑云制造服务组合优化过程中因候选服务数量有限而容易产生重复服务链的问题，因此需要在NSGA-II 算法中引入去重操作去除重复服务链，以提高算法的收敛性和多样性，从而提高Pareto 解集的准确性，进而提高推荐结果的准确性。

综上所述，本文借鉴云制造服务组合优化相关研究，结合科技服务的行业特色，建立考虑科技服务特有属性的质量评价指标体系，构建时间、成本、服务质量总体最优的数学模型，运用引入去重操作的NSGA-II 算法求解模型，得到一组Pareto 解集。最后，基于用户偏好构建以时间、成本和服务质量为指标的评价函数，对Pareto 最优解集中的服务链进行排序，为用户推荐最优服务链，从最大程度上满足服务需求方对时间、成本和服务质量的要求。

2 综合科技服务链推荐模型构建

在科技服务业中，用户对科技服务链的需求往往产生于科技成果的形成与转化过程，该过程的实现基于创新链的各活动环节［13］，会涉及多项科技服务，从而形成科技服务链。服务需求方对科技服务链的总完成时间、总成本以及总质量存在一定要求。为在最大程度上满足服务需求方的上述要求，下文将以基于创新链的科技成果形成与转化过程为背景，构建考虑服务特有属性并以用户需求为约束的科技服务链推荐模型。

2.1 综合科技服务链推荐问题描述

如图1 所示。综合科技服务平台由科技服务提供方、科技服务平台运营方和科技服务需求方3 类主体构成。科技服务提供方在科技服务平台注册后将闲置的研究开发、技术转移、检验检测等科技服务发布到综合科技服务平台上；科技服务需求方根据自身的科技成果形成与转化目标提交任务需求，科技服务平台运营方基于创新链的活动环节将任务分解成N个子任务，并为每个子任务匹配服务，形成满足任务需求的最优综合科技服务链；最后，由服务链中每个服务对应的提供方共同完成总任务。

图1 综合科技服务平台

从任务的提交到完成包含科技任务分解、科技子任务搜索匹配、科技服务链推荐、科技服务执行4 个阶段。在任务分解阶段，科技服务平台基于创新链的活动环节将服务需求方提交的任务T分解为N个子任务ST，是ST 的第i个子任务，i=1，2，…，N；在搜索匹配阶段，科技服务平台为每个搜索匹配一个候选服务集其中为子任务的第j个候选服务，M为子任务的候选服务个数；在科技服务链推荐阶段，科技服务平台为服务需求方生成一组Pareto 最优服务链，计算出每条服务链各评价指标的值并根据服务需求方对服务链各评价指标的偏好挑选最优综合科技服务链以执行总任务T，最优综合科技服务链可表示为：其中在服务执行阶段，服务需求根据推荐的服务链调用服务以完成相应子任务。

2.2 综合科技服务链推荐的多目标数学模型

为求解出最优综合科技服务链，本文基于用户需求，构建以时间、成本、服务质量总体最优的多目标推荐模型，同时将用户对时间、成本、服务质量的要求作为模型的约束条件。

2.2.1 考虑特有属性的服务质量约束

服务质量(Q)由科技服务的共有属性以及不同服务的特有属性共同决定。共有属性是所有服务都具备的属性，如可靠性和可用性；特有属性指某一类服务特有的最能够反映该服务质量且最受用户关注的属性。在科技服务业中，本文定义的科学技术普及、科技咨询、检验检测、科技金融、研究开发、创业孵化、技术转移和知识产权的特有属性分别为科普经费、有效咨询率、检验结果有效率、融资总额、新开发产品或服务数、新孵企业数、技术人才数量以及安全性。上述服务属性的定义及符号表示如表1 所示。

表1 服务属性定义表

表1 （续）

2.2.2 时间约束

2.2.3 成本约束

科技服务链的结构主要有顺序结构、并行结构、循环结构和选择结构四种，如图2 所示。其中顺序结构为最基本的结构，其他三种结构均可以通过一定方式等效转换成顺序结构。因此，本文以顺序结构的科技服务链作为科技服务链推荐的研究对象。

图2 科技服务链结构

综上所述，综合科技服务链推荐模型的目标函数如下：

（1）总完成时间最小化。

（3）总质量最优化。

为了计算每一条服务链的总质量，同时消除属性变化的不一致性，需对每一个候选服务的服务属性值进行归一化处理。本文采用文献［7］中归一化方法：

然后将服务链中所有候选服务的质量求和取均值，得到服务链的总质量Q。

则服务链总质量最优可以表示为：

2.3 数学模型

根据上述目标函数和约束条件，科技服务链推荐模型可以描述如下：

公式（8）表示该模型以时间最短、成本最小、服务质量最高为目标，公式（9）、公式（10）、公式（11）分别表示需求方对服务链的时间、成本和服务质量的约束。公式（12）表示对于每一个子任务只能选取一个候选服务。

3 综合科技服务链推荐算法求解与服务链评估

本节对科技服务链推荐问题的求解算法和科技服务链评估函数进行介绍。

3.1 算法选择及改进

本文提出的综合科技服务链推荐是一个多目标优化问题，而NSGA-II 算法是目前使用较广的求解多目标优化问题的算法之一。NSGA-II 降低了算法难度，提高了种群进化水平，但在求解科技服务链推荐问题时，由于候选服务数量限制，种群中容易产生重复服务链，降低种群多样性。因此，本文对基本的NSGA-II 算法进行改进，设计了有效的整数编码方式，引入了去重操作，改进后的算法称为i-NSGA-II 算法。

首先对编码方式进行改进，采用整数编码构建与科技服务相对应的个体。例如，一项科技任务可分解成5 个子任务，每个子任务有5 个候选服务，当候选科技服务链为其对应的整数编码即为［5,8,14,16,22］。在基本的NSGA-II 算法中引入去重操作［14］，剔除重复的服务链保留独特的服务链，一方面可降低冗余计算量，提高算法收敛速度；另一方面，可提高算法的收敛性和多样性，从而提高Pareto 解集的准确性，进而提高推荐结果的准确性。

i-NSGA-II 算法求解科技服务链推荐模型的流程如图3 所示。

图3 推荐流程图

3.2 综合科技服务链评估函数

为了根据用户偏好对求得的Pareto 最优解集进行排序，从而向用户推荐最满足其需求的服务链，本文构建以时间、成本和服务质量为指标的评估函数对Pareto 解集中的各服务链进行评估。首先使用1.2.1 中归一化公式对每条Pareto 最优服务链的时间、成本和服务质量进行归一化处理，消除不同量纲的影响，然后按一定权重将三个指标加权，得到第i条服务链的评价函数：

式中 表示第i条服务链的评价值，分别表示第i条服务链的时间、成本和服务质量经过归一化所得的值。为服务需求方根据自身偏好设置的权重值。最后，根据服务链评价值对服务链排序，将评价值最高的服务链推荐给服务需求方。

4 算例论证

本文设计了算法测试实验和算例论证实验，以验证模型的可行性，测试i-NSGA-II 算法的各项性能。

4.1 实验数据与环境

以猪八戒网中某公司需要研发一个替代纸质作业本，具备读写、批注、文件传输的电子作业本的科技服务项目为例，对本文所提出的综合科技服务链推荐模型、算法及评估函数进行验证。服务需求方向科技服务平台提交电子作业本开发任务需求，科技服务平台根据创新链的活动环节将任务分解为如图4 所示的5 个子任务，在科技咨询环节为该公司寻找提供可行性分析服务的咨询机构，为项目撰写可行性研究报告；在创业孵化环节为该公司寻找撰写商业计划书的机构；在科技金融环节为该公司匹配融资中介助力其融资；在研究开发环节为该公司寻找提供相关技术的机构；在检验检测环节为其寻找可为电子作业本进行品质检测的检测机构，为上述子任务搜索匹配对应的候选服务集。候选服务相关参数依据猪八戒网和其他科技服务网站的相关数据确定，如表2 所示。服务需求方的相关信息为：总时间不超过25 天，总成本不超过80 000 元，服务质量不低于0.8。根据上述信息构建算例模型。实验环境：MATLAB R2018b 软件，Windows10，3.60GHz，16GB RAM。

图4 科技成果形成与转化任务分解图

表2 候选服务相关参数

对于每一个候选服务，首先对其服务属性值进行归一化处理，然后将候选服务的特有属性与可用性、可靠性按进行加权，得到该候选服务的质量，质量的取值范围为［0,1］。

4.2 算法测试

首先，本文选取常用的多目标优化测试函数ZDT1，ZDT2 以种群数为100，迭代次数为500 对i-NSGA-II 算法进行测试，图5 为本文算法求解ZDT1 函数和ZDT2 函数所得的 Pareto 最优前沿与其理论上的 Pareto 最优前沿的分布图，“-”为理论解，“*”为算法求解出来的解。可以看出，本算法能收敛到各类问题的 Pareto 最优前沿并且分布较均匀。

图5 ZDT1 函数测试结果

然后，采用Deb 等［15］给出的两个算法评价指标：收敛性和多样性，来评估Pareto 解集的准确性和i-NSGA-II 算法的性能。

（1）收敛性指标γ。在测试函数已知的Pareto最优前沿上均匀地取一些点（下文实验取 500 个点），计算由算法获得的解与这些点之间距离的最小值，所有最小距离的平均值就是收敛性指标：

式中，Z为算法所获得的Pareto 解集，为理论上的Pareto 解集。收敛性指标γ越小，算法逼近Pareto 最优解集的程度越好。

（2）多样性指标Δ。将种群中所有个体按某个目标函数值的大小有序地分布在目标空间上，是Z中连续两个非劣解向量的欧式距离为的均值，分别表示集合中的极值解和Z的边界解之间的欧式距离。

极值解指某一目标函数值最大而其它目标函数值最小的解。当算法获得的非劣解完全均匀地分布在均衡面上，这时Δ=0。因此，Δ指标能反映非劣解能否均匀地分布在整个均衡面上。

分别使用NSGA-II 和i-NSGA-II 算法对ZDT1，ZDT2 测试函数进行求解，以种群数为100，迭代次数分别为50,75,100 各运行30 次，求得2 种算法对2 个测试函数收敛性和多样性的均值，如图6 和图7所示。实验结果表明，与 NSGA-II 相比，i-NSGAII 对2 个测试函数的收敛性和多样性都较好，因此i-NSGA-II 求得的解更逼近最优解，从而更能满足服务需求方的要求。

图6 多样性均值对比图

图7 收敛性均值对比图

4.3 算例求解及分析

在上述实验环境下，分别采用NSGA-II 算法和i-NSGA-II 算法按种群规模最大迭代次数，交叉概率变异概率对算例模型进行求解。实验结果分别如图8 和图9 所示，图中每一点代表一个Pareto 最优解，可以看出i-NSGA-II 算法和NSGA-II 算法求解模型所得的满足用户要求的服务链的数量分别为100 个和16 个，i-NSGA-II 算法能够求得更多满足用户需求的服务链。因此，i-NSGA-II 算法在求解科技服务链推荐模型上优于NSGA-II 算法。

图8 NSGA-II 求解所得Pareto 解集

图9 i-NSGA-II 求解所得Pareto 解集

首先采用公式（3）（4）对i-NSGA-II 算法求得的Pareto 解集中各候选服务链的时间、成本和服务质量进行归一化处理，再按照服务需求方综合考虑时间、成本、服务质量，只考虑时间，只考虑成本，只考虑服务质量四种偏好情况对i-NSGA-II 算法求得的Pareto 最优服务链进行排序，则四种情况的时间、成本、服务质量对应的权重分别为W1=(1/3,1/3,1/3)，W2=(1,0,0)，W3=(0,1,0)，W4=(0,0,1)，表3 展示了每种情况下经过排序所得的5 条最优服务链的信息。

表3 考虑不同权重的科技服务链评估结果

从结果来看，综合考虑时间、成本、服务质量的情况与只考虑时间的情况对比，前者求得的服务链的平均成本小于后者、平均服务质量高于后者；综合考虑时间、成本、服务质量的情况与只考虑成本的情况对比，前者求得的服务链的平均时间小于后者、平均服务质量高于后者；综合考虑时间、成本、服务质量的情况与只考虑服务质量的情况对比，两种情况求得的服务链的平均时间相同、平均成本前者小于后者。此外，服务需求方可以根据自身偏好重新向综合科技服务平台提交权重要求，综合科技服务平台只需根据新的权重重新对Pareto 解集中的服务链进行排序，而无需重新进行Pareto 最优服务链选择，节约了大量时间，使得服务链的选择更具灵活性。

5 结束语

本文针对科技服务业中科技服务链推荐问题，构建了以科技服务特有属性、可靠性和可用性为指标的服务质量评价指标体系，建立了考虑科技服务特有属性的科技服务链推荐模型，在NSGA-II 算法中引入去重操作对算法进行改进，并使用改进的算法对科技服务链推荐模型求解，得到一组Pareto 最优服务链，最后构建科技服务链评估函数对服务链进行评估和排序，向用户推荐最符合其需求的服务链。实验结果证明，本文提出的i-NSGA-II 算法求得的满足服务需求方要求的服务链的数量远多于NSGA-II 算法求得的合格解的数量，i-NSGA-II 算法在收敛性和多样性上也优于NSGA-II 算法，因此i-NSGA-II 算法求得的Pareto 最优服务链的准确性也较高。此外，服务链评估函数允许服务需求方根据自身偏好灵活更改权重要求。未来，科技服务链将集成更多科技服务，会愈发复杂。后续研究应该结合科技服务的应用场景，考虑不同结构的科技服务链，同时构建更加完善的科技服务链质量评价指标体系，提高推荐精准度，进一步推动科技服务业的发展。