基于NSGAⅡ的多目标电子产品CTO订单推荐_韩海峰.pdf

第 40 卷第 3 期计算机应用与软件Vol.40 No 32023 年 3 月Computer Applications and SoftwareMar 2023基于 NSGA的多目标电子产品 CTO 订单推荐韩海峰叶恒舟*黄凤怡郝薇(桂林理工大学广西嵌入式技术与智能系统重点实验室广西 桂林 541006)收稿日期:2020 08 26。广西科技重大专项(桂科 AA19046004);广西嵌入式技术与智能系统重点实验室主任基金项目(2019-01-10);桂林理工大学科研启动基金资助项目(GUTQDJJ2002018)。韩海峰，硕士生，主研领域:智能优化。叶恒舟，教授。黄凤怡，硕士生。郝薇，硕士生。摘要根据用户的个性化需求向用户推荐物料清单是实现按订单配置的有效途径。由于涉及的物料较多，用户关注的目标也较多，电子产品的 CTO(Configure To Order)订单推荐面临挑战。以功能定位目标贴近度、功耗和成本为优化目标，将电子产品的 CTO 订单推荐建模为一个多目标优化问题，采用 NSGA获取 Pareto 非支配集，基于用户权重对非支配集排序，得到若干推荐订单。与单目标优化方法相比，多目标优化可以快速适应用户对权重的动态调整，也可以一次推荐多个备选订单。仿真实验证明了该算法推荐的优越性和具有较强的鲁棒性。关键词按订单配置订单推荐多目标优化NSGA中图分类号TP391TP18文献标志码ADOI:10 3969/j issn 1000-386x 2023 03 016CTO ODE ECOMMENDATION OF MULTI-OBJECTIVE ELECTONICPODUCTS BASED ON NSGAHan HaifengYe Hengzhou*Huang FengyiHao Wei(Guangxi Key Laboratory of Embedded Technology and Intelligent System，Guilin University of Technology，Guilin 541006，Guangxi，China)AbstractIt is an effective way to recommend BOM to users according to their individual needs Because there aremany materials involved and users pay more attention to the target，the configure to order(CTO)order recommendationof electronic products is facing challenges The target proximity of function orientation，power consumption and cost weretaken as optimization objectives The CTO order recommendation of electronic products was modeled as a multi-objectiveoptimization problem The NSGA was used to obtain Pareto non-dominated set，the non-dominated set was sortedbased on user weight，and the recommended order was obtained Compared with the single objective optimizationmethod，the multi-objective optimization could adapt to the dynamic adjustment of users weight quickly，and could alsorecommend multiple alternative orders at a time The simulation results show that the proposed algorithm is superior androbustKeywordsConfigure to orderOrder recommendationMulti-objective optimizationNSGA0引言随着客户对产品需求的不断提高，按订单配置(CTO)成为满足用户需求不确定性和复杂性的关键。CTO 模式虽然可为用户在产品选择方面提供多种选择，但这要求企业要能够利用产品结构之间的约束和配置规则等相关算法1 5 实现产品设计、工艺准备、组织生产，以满足用户的特殊需求。为快速有效地响应用户订单需求，文献 6在具有订单配置不确定的 CTO 系统中，采用启发式算法解决了在多个产品之间分配公共组件的问题。文献 7通过伸缩的灵活性来适应客户需求的变化，使用按工程订单的生产模式(Engineering To Order，ETO)采用适应性设计和产品平台设计来解决，但 ETO 模式从产品设计、工艺准备、采购、制造都是按订单操作，不可避免第 3 期韩海峰，等:基于 NSGA的多目标电子产品 CTO 订单推荐95地增加了产品的生产周期和成本。在与 CTO 模式相似的按订单装配(Assemble To Order，ATO)模式下，文献 8 考虑的是不确定需求和不确定装配能力的 ATO模式下的装配决策问题。与本文类似，文献 9从CTO 产品的经济和环境性角度考虑，提出了一种基于多生命周期的多目标产品配置设计方法，并使用 NS-GA应用在碳粉盒结构设计的案例中证明该配置方法的有效性，但它仅仅从企业利益和社会利益考虑，忽略了 CTO 产品是为了满足客户自身需求。文献 10从用户角度建立了电子产品 CTO 订单推荐的单目标优化模型，并使用改进的遗传算法求解该模型。传统的将多目标问题转化为单目标优化问题存在着权值分配主观性强11、目标函数复杂12、度量单位不一致和搜索效率低等问题。多目标优化算法具有较优的搜索效率和鲁棒性，在诸多领域运用广泛。文献 13针对传统优化算法的目标权重人为选择以及常规 NSGA的局部收敛等问题，提出将正态分布交叉(Normal Distribution Crossover，NDX)算子引入到 NS-GA中，借助 NDX 算子加强算法的全局搜索能力，优化出最佳的电网规划方案。文献 14针对传统动力学模型难以满足精度和稳定性要求，提出一种采用神经网络作为代理模型，建立以马氏距离和鲁棒性为不确定性量化指标的多目标优化模型，并使用 NSGA多目标进化算法求解。文献 15围绕柔性车间调度问题，针对 NSGA收敛性不足的缺陷，引入免疫平衡原理改进 NSGA的选择策略和精英保留策略，成功避免了局部收敛问题，提高了算法的优化性能。文献 16 在水管的经济性的前提下兼顾可靠性指标优化水管网，同时解决最优解分布不均匀使得算法陷入局部最优问题。综上所述，虽然 NSGA已经得到诸多应用，也已经提出了诸多改进方法，但在应用于具体某个优化模型时，仍有必要进行针对性的优化。本文围绕电子产品 CTO 订单，建立以功能定位目标贴近度、功耗和成本三项指标为目标优化模型，将 NSGA应用到电子产品 CTO 订单推荐多目标优化求解中去，通过用户对Pareto 非支配集的权重排序为用户实现电子产品的CTO 订单推荐。1多目标电子产品 CTO 订单推荐模型电子产品 CTO 订单推荐的目标是根据用户的个性化需求，为其推荐产品的配置清单，即为生产该产品所需要的每个配件推荐合适的品牌与型号。用户的个性化需求有些是局部的或者可以容易转化为局部约束，如内存应大于等于 4 GB、屏幕分辨率要不低于2 048 1 080、产品外观为黑色等。这类需求可以通过淘汰特定的配件的可行品牌或型号满足。因而，在构建 CTO 订单推荐模型时，仅需考虑全局性的个性化需求，如功能定位目标贴近度、成本和功耗等。设某电子产品的产品配置清单涉及 m 个配件，si为第 i 个配件的可选项个数(已经根据个性化需求的相关局部约束进行了筛选)，mij(i=1，2，m;j=1，2，si)为第 i 个配件的第 j 个可选项，xij(i=1，2，m;j=1，2，si)为一个 0 1 决策变量，当为第 i 个配件选择 mij时，xij=1，否则，xij=0。设 t1，t2，tu等 u 个指标被用来描述产品的功能定位目标，用 f(tk，mij)度量 mij与 tk的贴近度。记f(tk，0)=0，可用式(1)确定某个配置清单的功能定位目标贴近度，记为 f1。=uk=1wkmi=1sij=1f(tk，mijxij)(1)式中:wi为指标 ti的权重，ui=1wi=1。某个配置清单的成本由相应配件的成本及加工成本确定。记 cij为 mij的价格，c0为加工成本，则某个配置清单对应的成本 C 可由式(2)计算，记为 f2。C=mi=1sij=1cijxij+c0(2)记 pij为 mij的价格，则某个配置清单对应的功耗 P可由式(3)计算，记为 f3。P=mi=1sij=1pijxij(3)以最大化功能定位目标贴近度、最小化成本和能耗为优化目标，则多目标电子产品的 CTO 订单推荐模型(Multi-target Electronic Products CTO Order ecom-mendation，MEPCTO)可以描述如下:目标函数:Maxf1;Minf2;Minf3。约束条件:pij=1xij=1i=1，2，n(4)xij 0，1i=1，2，n，j=1，2，pi(5)式(4)和式(5)表明应为每种配件恰好选择一个选项。2MEPCTO 模型求解MEPCTO 模型是一种多目标优化模型，是 NP 难的。诸如非支配排序遗传算法(Non-dominated SortingGenetic Algorithm，NSGA)是求解这类模型的有效方96计算机应用与软件2023 年法。本文采用基于 NSGA17 19 求解 MEPCTO 模型，并采用分配权重的非支配集排序策略对求得的非支配最优解进行排序，该算法(CTO_NSGA)主要步骤流程如图 1 所示，主要包括:种群初始化、非支配排序、拥挤度计算、交叉变异和精英保留策略等。图 1基于 NSGA的电子产品 CTO 订单推荐流程2 1种群初始化种群染色体采用实数编码方式。一个染色体由十个基因组组成，共二十个实数编码，每两个编码为一个基因组，基因组的编码表示电子产品所选择的对应配件，初始种群的染色体基因组编码随机产生。2 2非支配排序对于每个染色体 q 设置一个集合 sq和一个变量nq，sq为染色体 q 支配的个体集合，nq记录染色体 q 被支配的个体数目。快速非支配排序步骤如下:(1)初始化种群，设置染色体q 对应的sq=，nq=0。(2)遍历种群 P 中的每个染色体 q，比较 f1、f2、f3函数，找出种群中 nq=0 的所有个体，并保存在当前集合 F0中，记录当前支配等级为 0。(3)遍历当前 F0层的所有染色体，从其支配的染色体集合 sq中选择染色体执行 nq=nq 1 操作，若nq=0，则将个体保存在下一个 F1中，记录当前支配等级为 1。(4)依次执行步骤(2)、步骤(3)操作，直至所有染色体完成分级。2 3拥挤度计算拥挤度是表示种群中个体周围的染色体的密集程度，每条染色体拥挤度是根据周围染色体的距离决定，距离越大表明该染色体所处区域密度越小。因此计算拥挤度是保证种群多样性的一个关键环节。染色体拥挤度的计算如下:id=fw(i+1)fw(i 1)fmaxw fminw(6)式中:fw(i)表示当前等级下的第 i 个染色体的第 w 个目标函数值;fwmax、fwmin分别为当前等级下的第 w 个目标函数的最大与最小值。当前等级的两端的个体的id=。当染色体非支配等级相同的时候，拥