基于NSGA-III的众包设计服务资源优选方法研究

尹 超，石志立

(重庆大学 机械工程学院机械传动国家重点实验室，重庆 400000）

0 引言

随着社会生产力的不断发展，传统企业的创新模式已经越来越难以满足社会上对于各类产品的个性化需求，而同时社会上存在着众多可利用的设计资源，“众包设计”这一新型的创新模式应运而生。众包设计模式将海量的设计服务资源汇聚到众包设计平台，在服务需求方和服务提供方之间建立合作渠道，从而为各类设计需求方提供服务，充分发挥了群众的智慧[1,2]。

众包设计模式根据任务类型可以划分为简单任务型众包和复杂任务型众包两种模式。简单任务众包包括Logo设计、海报设计、UI设计、软件测试等需求，其特点为任务粒度小，并行性好，当前众包设计平台方主要采用的任务分配模式分为竞标型和一对一型；复杂任务众包则包括软件开发、家装设计、个性化定制产品等需求，其特点为任务粒度大、服务周期长、服务流程可解耦等，往往需要通过众包设计平台协调多个服务提供方共同完成，因而，研究众包设计任务的组合优选问题就成为提高众包设计模式可靠性与高效性的重要途径。现有的文献对不同类型制造资源的优化选择进行了探索，并取得了一定的成果。如文献[3]提出了一种考虑服务可靠性、可信性、组合复杂度、协同度、执行时间和执行费用的云制造资源综合QOS评价模型，并采用EEPSO算法对制造任务组合模型求解；文献[4]构建了面向资源供应方、服务需求方和平台运营方的制造资源服务组合模型，并采用云遗传算法求解；文献[5]考虑了制造资源虚假信息对服务组合优选的影响，并提出了基于可信度的制造资源优选方法；文献[6]建立了一种面向新产品开发的云服务资源组合优选模型，并采用灰色关联度分析方法对模型进行求解；文献[7]在定义制造云服务的基础上，提出了MCS混合粒度组合优选方法，构建了基于服务成本、服务质量和交易周期的多目标优化模型，并通过ε-SPEA2算法进行求解；文献[8]构建了面向航天复杂产品的制造系统体系架构，并提出了支持制造资源/制造能力的多视图描述和组合优选模型；文献[9]构建了包含时间、成本、能源消耗、可靠性、可维护性和服务评价的制造服务六维评价模型，并采用自适应混沌优化算法求解；文献[10]从资源服务、功能服务和流程服务三个层次对制造资源进行建模，通过构建服务执行时间、服务花费成本和服务用户评价三个方面的质量评估函数，并通过改进的NSGA算法对制造服务的优化组合模型进行求解。

上述文献关于制造资源的服务组合优选方法对研究众包设计服务组合优选具有一定的参考作用，然而众包设计服务资源具有增值性、边际性和共享性等典型知识资源特征[11]，在资源的匹配优选过程中难以对服务质量做出准确评判。当前关于众包设计服务过程中的服务资源组合优选研究较少，尚未建立比较完善的众包设计服务资源搜索匹配评价指标体系以及组合优选评价指标体系。因此，本文在以上研究成果的基础上，针对众包设计服务过程特点及服务需求方和服务方不同属性，对服务资源的评价指标体系和优选模型以及求解方法进行探索和研究，并结合实例进行验证。

1 众包设计服务模式及特点

1.1 复杂任务型众包设计服务模式

复杂任务型众包设计主要包括任务设计、任务推荐、服务匹配、服务组合、服务优选等流程，如图1所示。服务需求方在众包设计平台发布需求，并填写任务需求。众包设计平台根据任务需求文档和案例数据库对复杂任务需求进行分解，平台技术团队保证各子任务的低耦合性。平台将需求匹配的服务提供方加入待选资源，对各种不同的资源组合优选，得到最终的任务执行序列。

图1 复杂任务型众包设计服务模式

1.2 众包设计服务特点

众包设计服务模式通过将创新的来源由组织或企业内部扩展到组织外部的群众中，激发和融合拥有大量专业知识的大众群体的创造力，极大扩展了创新的知识来源。根据复杂任务型众包设计服务流程，可以总结出其具有如下典型特征：

1）服务组合性。复杂任务型众包设计服务模式中，单个复杂设计任务一般可以划分为多个阶段或流程，并且各阶段或流程具有较低耦合性，因此，可以通过将不同类型的众包设计服务提供方有序组合在一起，协作完成通过将不同的阶段或者流程分配给多个众包设计服务提供方协作完成，以提高设计效率和产品迭代速度。

2）依赖传递性。复杂任务型众包设计模式中由于多个设计服务资源共同完成整体流程，某一阶段的设计任务需要根据前一阶段的设计结果作为基础，因此服务需求方对各个环节的服务质量提出了较高要求，需要尽可能规避风险以免延误整体设计进度。

3）主客观性。众包设计服务模式中任务要求包含客观要求和主观要求，客观要求易通过各项测试得出结果；而各主观要求则必须考虑到服务需求方的个体倾向，因此，资源需求个体的评价倾向会影响服务资源个体对众包任务的接受和实施。

2 考虑供需双方约束的众包设计服务资源搜索匹配评价指标体系

在对众包设计服务资源的优选之前，需要先根据任务需求对服务需求方进行搜索匹配，但是在大多服务组合优选的研究中往往只考虑服务需求方的指标约束，而在众包设计服务模式中，任务需求的传递依赖性决定了服务提供方的重要地位，因此，本文结合众包设计服务模式特点和供需双方的需求属性，提出众包设计服务资源搜索匹配评价指标体系。

2.1 服务需求方约束指标

服务需求方是众包任务的发起方，因此在服务过程中占据主动地位。服务需求方通过和众包设计平台的技术团队协作对众包任务设计环节，主要包括任务属性确定、任务完成时间、任务激励机制，任务分解等。因此服务需求方对众包任务搜索匹配的约束指标主要包括：服务类型：包括功能设计、结构设计、外观设计、布局设计等，可以根据用户的任务需求，选择合适的服务类型；服务可用性：指当前众包设计服务资源能否在平台中提供服务，若不能，则不会被纳入匹配结果以及优化选择的范畴；历史信誉：指的是服务需求方对众包任务完成情况的历史评价，可以体现其服务方服务能力的高低。

2.2 服务提供方约束指标

经过众包设计平台分解后的各子任务会被推送到符合要求的服务提供方一端，然而考虑到该任务本身的综合收益风险比和服务需求方的满意倾向，服务提供方不会选择接受所有的众包任务服务请求。服务提供方对众包设计服务搜索匹配的约束指标主要包括：服务风险收益比：指的是接受服务承担的风险水平，若某一任务超过了服务提供方设置的风险收益比，则不会被匹配到；服务需求方的满意倾向：主要指任务提交后，雇主的评价倾向，由于可以根据历史评价记录获得。

2.3 复杂任务型众包设计服务优选评价指标体系

众包设计平台通过聚集各类分散的众包设计服务资源，可为广大服务需求方提供相应的设计服务，有效利用提高了各类设计业务效率。然而众包设计服务资源属于抽象的知识资源，传统的对实体资源的定量评价指标体系难以对众包设计资源准确评价。因此本文提出一种包括服务时间（T）、服务成本（C）、服务能力（Ca）和服务有效性（Re）的众包设计服务资源优选评价指标体系，如图2所示。

图2 众包设计服务资源优选评价指标体系

1）服务时间T

服务时间T主要包括众包平台上进行的任务分解、任务推荐、服务匹配的等待时间Tmatch，以及服务提供方完成任务耗费的时间Tseruice，还有众包平台同供需双方协调任务设计、专家技术团队对众包任务的技术审核等花费时间Tmanage，即T(S)=Tmatch(S)+Tservice(S)+Tmanage(S)其中S代表服务提供方，下文同义。

2）服务成本C

服务成本指服务需求方从提出需求到任务完成过程中所支付的费用,主要包括支付给服务提供方的佣金酬劳Cseruice和在众包设计服务过程中购买的增值服务花费Conline，如风控保险、专家咨询等，即C(S)=Cseruice(S)+Conline(S)。

3）服务能力Ca

服务能力主要衡量服务提供方在专业技能、服务经验、技术专利等知识方面的饱有量和共享度[12]。假设某服务服务提供方Sj包含的知识总数为sum(Sj)，其服务能力Ca(S)，知识饱有量为μj，知识共享度为uj，则Ca(S)=ωμμj+ωuuj，其中vj=sum(Sj)，ωμ和ωu分别为知识饱有量和知识共享度的权重，并且ωμ+ωu=1，m为众包设计服务过程中同类型的服务提供方总数，sum(Sj)代表服务提供方通过众包设计平台共享的知识总量。

4）服务可靠性Re

服务可靠性指的是服务提供方在面临突发情况时能按时完成任务的能力，主要包括服务提供方的任务成功率Resuccess、服务提供方的任务准时完成率Reontime以及服务方收到的历史评价记录Reevaluation，即，其中：Rei,j为服务提供方第i个满意度指标的第j次评估值，λi为服务提供方的第i个满意度指标的权重，并且0≤λi≤1,，n为服务提供方第i个满意度指标的评价次数。

2.4 众包设计服务资源组合优选模型

考虑到众包设计服务供需双方约束指标，因此，众包设计服务资源组合优选问题的多目标数学模型为：

式(1)中的tmax表示最大预期服务时间，cmax表示最大预期服务成本，Camin和Remin分别表示最小服务质量预期和最小服务可靠性预期。对于多目标优化选择模型中的各项指标的值，可以通过式(2)进行归一化。其中qj表示资源评价指标，分别表示资源评价指标的最大值和最小值。在众包设计服务资源评价指标中，服务时间和服务成本通过（2b）归一化；服务质量和服务可靠性通过（2a）进行归一化。

3 基于NSGA-III的众包设计服务资源组合优选算法

NSGA-III算法是在带精英策略的NSGA-II算法的基础上提出的一种新的多目标优化求解算法[13]。两者的算法求解框架大体相同，区别在于NSGA-II通过计算个体拥挤度距离对同一非支配等级的个体进行选择，认为拥挤个体距离越大也好，该方法适合求解2个或3个目标函数的优化问题，但是随着优化问题目标维数的增大，种群中非支配个体数量呈指数增大，并且通过拥挤度距离排序选择个体在非支配层上分布不均匀，容易陷入局部最优，影响算法的有效性和收敛性，应用NSGA-III算法的步骤如图3所示。

图3 NSGA-III算法流程

在众包设计服务资源优化选择模型中应用NSGA-III算法的关键在于种群基因编码、种群的自适应标准化和个体的保留操作。

1）种群的基因编码、交叉和变异

在遗传算法中，需要将目标问题的可行解编码成染色体，染色体上的各元素基因。通过对基因的选择、交叉、变异等操作，筛选出适应力更强的后代，最后一次迭代得到的种群即是目标问题的Pareto解集。在具体的应用场景中，可以根据使用者的需要和偏好选择，选择出对应的个体作为问题的最优解。本文中的染色体由众包设计服务资源个体序列组成，编码规则为十进制编码，例如设计服务资源组合CSR1,3-CSR2,1-CSR3,5-CSR4,4-CSR5,2，所对应的十进制编码为3-1-5-4-2，如图4所示；交叉策略采用重合点交叉，对随机选择的两个染色体，选择编码中对应位置相同的元素进行交换，若无重合点，则不进行交叉操作，重合点交叉的优点在于不会产生新的无效解，如图5所示；变异算子在个体中随机选择一个序号，用另一个随即产生的序号替代，如图6所示。

图4 基因编码

图5 交叉操作示意图

图6 变异操作示意图

2）种群的自适应标准化

种群标准化的目的是将参考点放在一个标准化的超平面上，首先将当前种群Si中个体的每一维目标的最小值构成当前种群的理想点集合-z，对种群St做平移操作使得理想点变为原点，将式(3)的最小值记为zi,max,使用M个极值点通过式(4)构成M维标准化空间；设置参考向量zt，并关联种群和参考点，关联操作具体见文献[14]。

式中ωi为坐标轴的单位方向向量；ai为每一维在对应坐标轴上的截距。

3）个体的保留

经过标准化关联操作后，可能出现一个参考点关联多个个体。将参考点j在集合Pt+1=St/Fl关联的个体的数量记为ρj；首先选择关联数目最少的参考点，若其ρj=0，则将离参考点对应的参考线最近的个体加入Pt+1，若临界区Fl中不存在个体与参考点关联，则将参考点删除；若ρj≥1，则从随机选择一个参考点并将关联的个体加入Pt+1。重复上述步骤直到种群的规模达到N。

4 实例验证

为了验证论文中的模型的算法的有效性，本节以复杂家电产品个性化众包设计平台中的电冰箱开发为背景。服务需求方在众包设计平台中提交新款个性化冰箱的设计需求，众包设计平台通过平台的创意征集板块，确定了需求的若干个新特点并加工形成设计文档；根据产品需求及特性将该个性化冰箱设计任务划分为如图7所示的五个子任务。其具体的评价指标值如表1所示，指标约束参数规定如下：tmax=500h,cmax=8000元，camin=0.7500，remin=0.8000。

表1 众包设计服务待选资源指标参数

图7 个性化冰箱设计流程图

众包设计服务优选模型中的各项参数由服务提供方和服务需求方决定，本文采用的各项参数如下表：N0=30，Pc=0.92,Pm=0.06,最大迭代次数maxFE=100，在上述实验环境下，通过Matlab编程对多目标优化模型进行求解运算。经过19次迭代后，程序在各目标上的适应度趋于稳定，到达收敛状态，各可行解在四个目标函数上适应度的平均值如图8所示。

图8 目标函数平均适应度值

众包设计服务资源优化模型求解结果如表3所示，根据实际设计情形分析，服务成本和服务质量在设计过程中占据相对重要，因此，令ω={0.3,0.2,0.3,0.2}，计算Pareto解集中的解的适应度值并排序，计算结果如表2所示，各指标向量采用式(2)归一化：

表2 众包设计资源综合评价

根据众包设计资源综合评价结果可以看出，在指标权重预设为ω的情形时，最优的服务组合为CSR1,3-CSR2,1-CSR3,5-CSR4,4-CSR5,4。实际应用中，可以根据不同的客观条件确定指标权重ω，进而得到相应的的众包设计服务资源组合序列。

5 结语

本文通过分析复杂任务型众包设计模式服务流程及特点，提出了一种考虑供需双方约束的众包设计服务资源搜索匹配评价指标体系，以及包含服务时间(T)、服务成本(C)、服务质量(Ca)和服务可靠性(Re)的众包设计服务资源优选评价指标体系，并对各项指标进行了量化评估；在此基础上建立资源优选的数学模型，通过NSGA-III算法对模型进行求解，验证了所提方法的有效性。下一步将针对众包设计服务资源全信息描述模型以及服务过程中的资源匹配算法展开研究。