旅行商问题的混沌混合离散蝙蝠算法

戚远航,蔡延光,蔡 颢,汤雅连,吕文祥

(1.广东工业大学自动化学院,广东广州510006;2.奥尔堡大学健康科学与技术系,丹麦奥尔堡9220)



旅行商问题的混沌混合离散蝙蝠算法

戚远航1,蔡延光1,蔡 颢2,汤雅连1,吕文祥1

(1.广东工业大学自动化学院,广东广州510006;2.奥尔堡大学健康科学与技术系,丹麦奥尔堡9220)

针对现有离散蝙蝠算法在求解旅行商问题时存在的收敛速度较慢、收敛率不高等问题,提出了混沌混合离散蝙蝠算法.该算法采用混沌初始化策略提高算法的寻优能力,引入2-Opt技术增强算法的局部搜索能力、加快算法的收敛速度.大量的仿真实验表明:所提出的算法在求解小规模TSP时能快速收敛到已知最优解;在求解大规模TSP时能在较短的时间内收敛到偏差0.4%以内的最优解.

旅行商问题;混沌初始化;蝙蝠算法;2-Opt

1 引言

旅行商问题(Traveling Salesman Problem,TSP)是组合优化中的一个著名难题.其求解算法很多,如遗传算法、蚁群算法、粒子群算法[1].

蝙蝠算法(Bat Algorithm,BA)是Xin-She YANG在2010年提出的一种元启发式算法[2].李枝勇等[3]提出了离散型蝙蝠算法求解最小比率旅行商问题,A Rezaee Jordehi[4]提出了混沌蝙蝠群算法.但是,现有离散蝙蝠算法在求解TSP时存在着收敛速度较慢、收敛率不高等问题.

本文提出了混沌混合离散蝙蝠算法(Chaotic Hybrid Discrete Bat Algorithm,CHDBA).CHDBA采用混沌初始化策略提高算法的寻优能力,引入2-Opt技术增强算法的局部搜索能力、加快算法的收敛速度.在大量的仿真实验中:与离散型蝙蝠算法[3](Discrete Bat Algorithm,DBA)、混合粒子群算法[5](Hybrid Particle Swarm Optimization,HPSO)相比,CHDBA在求解小规模TSP时能快速收敛到已知……