《Future Internet》:An Effective Cooperative Coevolution–Differential Evolution Algorithm for Improving the Performance and Robustness of Ridesharing Systems with Trust Requirements
编辑推荐:
尽管全球共乘服务不断增长,与其他交通方式相比,共乘的采用率仍然较低。影响考虑共乘意愿的五个重要因素包括时间/成本、服务体验、交通/环境、隐私和安全。社交网络中的信息可为改善共乘服务的服务体验和可信度提供潜在价值。然而,基于参与司机和乘客的信任要求及其他约束来优
尽管全球共乘服务不断增长,与其他交通方式相比,共乘的采用率仍然较低。影响考虑共乘意愿的五个重要因素包括时间/成本、服务体验、交通/环境、隐私和安全。社交网络中的信息可为改善共乘服务的服务体验和可信度提供潜在价值。然而,基于参与司机和乘客的信任要求及其他约束来优化共乘决策的问题,因其较高的计算复杂度,给求解算法的开发带来了挑战。此外,考虑信任要求的共乘优化问题通常是非凸、非线性且具有离散决策变量的,这使得精确方法不适用。元启发式方法可用于求解非凸、非线性、离散约束优化问题。本文的目标是开发一种有效的求解算法,以改善具有信任要求的共乘系统的性能。为实现该目标,研究人员将合作协同进化(Cooperative Coevolution, CC)方法与差分进化(Differential Evolution, DE)方法相结合,开发了一种DE算法变体。为验证新算法在求解具有信任要求的共乘优化问题时的有效性,研究人员开展了实验,并将新算法所得结果与其他16种竞争算法的结果进行了比较。基于实验结果的对比表明,所提算法在性能和鲁棒性方面显著优于其他竞争算法。CC–DE算法在所有测试用例上均取得最高平均适应度值,而其他算法至多在80%的测试用例上取得最高平均适应度值。CC–DE算法在所有测试用例上均实现适应度函数值标准差为零,而其他算法至多在80%的测试用例上实现标准差为零。对于两个最大的测试用例,CC–DE算法在性能上分别以至少9.246%和12.9867%的优势优于其他算法。
一、研究背景与问题
全球共乘服务虽在增长,但与其他交通方式相比采用率仍然较低。行为与心理层面的障碍主要包括信任与安全担忧、意图–行为差距、隐私和个人空间损失、绕路不便、服务可靠性与等待时间。其中,信任被认为是影响共乘服务采用的关键因素。已有研究表明,社交网络信息可用于改善服务体验和安全性,因此基于参与者之间信任水平来优化共乘决策成为重要研究问题。
信任要求的引入使共乘优化问题需要同时考虑座位供需流平衡、非负成本节约、每个司机在决策期内至多一个投标被接受、司机和乘客的最低信任水平约束以及二元决策变量等约束。此类问题通常可建模为约束整数规划或约束混合整数规划,且具有非凸、非线性的特点,精确求解方法不适用,因此需要设计有效的元启发式算法。已有研究多将两种差分进化(Differential Evolution, DE)策略与自适应机制任意组合来求解信任共乘问题,但将单一DE策略与其他机制结合能否提升性能仍待验证。本研究的目标是将合作协同进化(Cooperative Coevolution, CC)与DE结合,从而提高信任共乘系统的性能与鲁棒性。
二、研究内容与结论
研究人员提出了合作协同进化–差分进化(CC–DE)算法。该算法利用CC方法将大规模决策变量随机分组,每个子群体独立进化,并通过上下文向量(context vector)进行协作评价;采用Deb提出的无参数可行性规则构造适应度函数,以处理各类约束;随后通过DE的变异与交叉操作生成试验向量,并将其转换为二元向量后计算适应度。为验证有效性,研究人员在十组测试用例上将CC–DE与六种标准DE算法、NSDE算法、六种SaNSDE变体、粒子群优化(Particle Swarm Optimization, PSO)、萤火虫算法(Firefly algorithm, FA)以及ALPSO算法共16种竞争算法进行比较,评价指标包括平均适应度值、适应度值标准差、平均进化代数和平均运行时间。
实验结果表明,CC–DE在性能和鲁棒性上显著优于其他竞争算法。CC–DE在所有测试用例上均取得最高平均适应度值,其他算法至多在80%的测试用例上取得最高值;CC–DE在所有测试用例上适应度标准差均为零,其他算法至多在80%的测试用例上达到零标准差。在最大两个测试用例上,CC–DE的性能分别至少提升9.246%和12.9867%。该研究证明了将CC与单一DE策略结合能够获得比双策略自适应SaNSDE算法更优的性能与鲁棒性,为求解大规模信任共乘优化问题提供了一种高效稳定的方法。
三、主要关键技术方法
研究用到的主要技术方法包括:第一,合作协同进化分解与随机分组,将高维决策变量划分为多个子组件,降低求解复杂度;第二,Deb可行性规则约束处理方法,通过无参数适应度函数同时衡量目标值和约束违反程度;第三,DE变异交叉与二进制转换机制,以实数试验向量构造完整候选解并映射为二元决策变量;第四,Friedman统计检验用于比较17种算法的整体差异。实验中十组测试用例基于特定区域情景生成,数据可公开获取,信任水平数据与信任要求按模拟场景设定。
四、研究结果
在性能比较中,CC–DE在小规模测试用例上与对比算法接近或相同,但随着问题规模增大而显著优于六种DE算法、六种SaNSDE变体以及PSO、FA、ALPSO和NSDE。Friedman检验的p值为0.0001128,CC–DE平均排名5.70,为17种算法中最佳。
在鲁棒性比较中,CC–DE在全部十组测试用例上适应度标准差均为零,而多数算法在最大规模测试用例上出现较大波动。Friedman检验表明17种算法鲁棒性具有显著差异,CC–DE平均排名最佳。
在收敛速度比较中,CC–DE在中大规模测试用例上收敛明显更快,例如测试用例8至10仅需170.11、556.1和392.8代,而多数对比算法需要数千甚至数万代。整体上SaNSDE变体平均排名最快,CC–DE排名第六,仍优于多数传统算法。
在运行时间比较中,CC–DE在大多数测试用例上平均运行时间优于对比算法,其平均运行时间排名第一,Friedman检验p值为7.23×10
?8。研究还发现,禁用CC机制后性能明显下降,且问题维度越大性能损失越明显;CC–DE对种群规模10、30、50不敏感,对生成参数也不敏感。
五、讨论与结论
研究指出,社交或信任共乘算法开发的核心挑战包括高计算复杂度、匹配约束和信任水平要求,元启发式方法擅长处理这类非凸、非线性的离散优化问题。本研究的发现是,将单一DE策略与CC结合所提出的CC–DE算法,在性能和鲁棒性上优于由两种DE策略与自适应机制组合而成的六种SaNSDE算法。研究局限性在于实验基于特定区域生成的十组测试实例,尚未在真实运营共乘平台上验证;所提方法基于静态共乘条件,需修改后才能处理动态共乘问题。未来可研究将CC与其他进化计算方法结合以进一步提升性能与鲁棒性。结论是,与16种竞争算法相比,CC–DE在性能与鲁棒性指标上显著更优;但由于采用随机分组的分治策略,其收敛速度相对较慢。