论文部分内容阅读
物流能够保证商品的流通,因此它是商品经济的动脉。车辆路径问题作为物流活动中的优化问题,更是具有深远的研究价值。群智能优化算法作为一类新兴的优化算法,虽然具有较好的寻优性能,但是面临复杂度不断升级的问题,求解性能也面临挑战。基于上述背景,本文对混合蛙跳算法及其在带容量约束的车辆路径问题中的应用进行研究,主要研究内容如下:(1)分析混合蛙跳算法的结构弊端,提出一种基于解空间跳跃和信息交互强化的混合蛙跳算法求解函数优化问题。算法在局部搜索中增加了子群次优解和次劣解的交互,强化内部信息交互;设计了反向跳跃机制,降低劣解生成概率,增强算法开发能力;对子群最优解进行变异,保证种群多样性;通过子群最优解交叉加深子群间交互,引入反向跳跃思想防止种群加速同化。选取23个不同类型的测试函数,验证策略的有效性和所提算法的性能,实验结果表明所提策略均能改善算法性能;与4种性能优越的算法对比,所提算法的整体性能优于对比算法,表现出了较好的求解精度和稳定性。(2)根据旅行商问题的特点,提出了一种基于启发信息的混合蛙跳算法求解旅行商问题。该算法设计了基于启发信息的个体生成算子,能够同时从优解和劣解中提取有效信息;采用反向轮盘赌策略,实现种群的多样性;设计了基于独立最优子群的算法框架,强化算法开发能力,平衡各子群搜索能力;变异并优化局部最优解,有助于跳出局部最优;强化局部搜索,提升求解精度和速度。共用31个标准测试实例,分别验证个体生成算子和改进策略的有效性以及所提算法的性能,实验结果表明个体生成算子和改进策略是有效的;与8种对比算法相比,本文所提算法在求解旅行商问题时具有更好的精度和稳定性。(3)分析带容量约束的车辆路径问题和旅行商问题的异同点,以上述基于启发信息的混合蛙跳算法为框架,修改了个体解码方式,将约束条件从车辆的容量转化为使用车辆的数量;设计与违反约束程度成正相关的惩罚函数,在算法迭代中淘汰不可行解;删除原有的强化局部搜索策略,在个体解码环节中,对每个车辆的路径分别进行局部搜索。采用45个不同规模的实例作为测试集,与近期具有代表性的4种算法进行对比实验,实验结果表明所提算法在带容量约束的车辆路径问题上具有更高的求解精度。