基于改进混合蛙跳算法的CVRP求解
骆剑平 李霞* 陈泯融
深圳大学信息工程学院 深圳 518060
Improved Shuffled Frog Leaping Algorithm for Solving CVRP
Luo Jian-ping Li Xia Chen Min-rong
College of Information Engineering, Shenzhen University, Shenzhen 518060, China
摘要 该文提出基于实数编码模式的混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)求解容量约束车辆路径问题(Capacitated Vehicle Routing Problem,CVRP);把具有极强局部搜索能力的幂律极值动力学优化(Power Law Extremal Optimization,τ-EO)融合于SFLA,针对CVRP对τ-EO过程进行设计和改进。改进的τ-EO采用新颖的组元适应度计算方法;采用幂律概率分布来挑选需要变异的组元;根据最邻近城市表,采用幂律概率分布挑选变异组元的最佳邻近城市,执行线路间或线路内的变异。求解测试库中的实例,证明该改进算法有效。
关键词 :
智能优化 ,
进化算法 ,
混合蛙跳算法 ,
极值动力学优化 ,
车辆路径问题 ,
收敛性
Abstract :An improved Shuffled Frog Leaping Algorithm (SFLA) is proposed to solve the Capacitated Vehicle Routing Problem(CVRP)based on real-coded patterns. It is then combined with the power-law Extremal Optimization (τ-EO) to further improve the local search ability. The fitness for the components of an individual is carefully designed and the neighborhood for τ-EO mutation is established according to power-law probability distribution. Experimental results show that the proposed algorithm outperforms other heuristic algorithms base on PSO and GA.
Key words :
Intelligence optimization
Evolutionary algorithm
Shuffled Frog Leaping Algorithm (SFLA)
Extremal Optimization (EO)
Vehicle Routing Problem (VRP)
Convergence
收稿日期: 2010-04-01
基金资助: 国家自然科学基金(60772148)和高等学校博士点基金(200805900 001)资助课题
通讯作者:
李霞
E-mail: lixia@szu.edu.cn
[1]
金杉,金志刚. 基于量子狼群进化的多目标汇聚节点覆盖算法 [J]. 电子与信息学报, 2017, 39(5): 1178-1184.
[2]
黄友锐,陈珍萍,李德权,唐超礼,曲立国. 无线传感器网络二阶一致性时间同步 [J]. 电子与信息学报, 2017, 39(1): 51-57.
[3]
毕晓君,张磊. 基于自适应ε 截断策略的约束多目标优化算法 [J]. 电子与信息学报, 2016, 38(8): 2047-2053.
[4]
韩丹丹,闵乐泉,赵耿. 八维广义同步系统在伪随机数发生器中的应用 [J]. 电子与信息学报, 2016, 38(5): 1158-1165.
[5]
高迎彬,孔祥玉,胡昌华,张会会,侯立安. 一种广义主成分提取算法及其收敛性分析 [J]. 电子与信息学报, 2016, 38(10): 2531-2537.
[6]
温良,黄博妍,魏国,孙金玮,肖业贵. 基于泄漏残余误差分离器的窄带主动噪声控制系统 [J]. 电子与信息学报, 2016, 38(1): 180-186.
[7]
许川佩, 陈家栋, 万春霆. 基于云模型进化算法的硅通孔数量受约束的3D NoC测试规划研究 [J]. 电子与信息学报, 2015, 37(2): 477-483.
[8]
曹凯, 陈国虎, 江桦, 马欢. 自适应引导进化遗传算法 [J]. 电子与信息学报, 2014, 36(8): 1884-1890.
[9]
王俊, 赵宏志, 卿朝进, 唐友喜. 同时同频全双工场景中的射频域自适应干扰抵消 [J]. 电子与信息学报, 2014, 36(6): 1435-1440.
[10]
姜兴龙, 梁广, 刘会杰, 余金培. 一种新型的低轨存储转发通信星座设计方法 [J]. 电子与信息学报, 2014, 36(3): 676-682.
[11]
邹德旋, 高立群, 段纳. 用修正的差分进化算法确定光电模型参数 [J]. 电子与信息学报, 2014, 36(10): 2521-2525.
[12]
张浩军, 朱艳琴, 纪其进. 面向异构网络的动态负载均衡算法及其收敛性分析 [J]. 电子与信息学报, 2013, 35(9): 2247-2253.
[13]
李楠, 侯旋. 自适应量子前向对传算法研究 [J]. 电子与信息学报, 2013, 35(11): 2778-2783.
[14]
韩学兵, 张颢. 模型噪声中的稀疏恢复算法研究 [J]. 电子与信息学报, 2012, 34(8): 1813-1818.
[15]
刘国胜; 张国基. 高阶LOD-FDTD方法的数值特性研究 [J]. 电子与信息学报, 2010, 32(6): 1384-1388 .