摘要
布谷鸟算法(Cuckoo Search,CS)在求解连续问题方面得到较好的结果,但在处理离散问题方面解决方案较少且收敛速度过慢,针对此不足,以求解旅行商问题为代表,结合基于学习的混合邻域结构和概率接受准则,提出了一种新颖的改进的混合离散布谷鸟(Hybrid Discrete Cuckoo Search,HDCS)算法.HDCS算法通过向最佳个体学习和从问题学习来搜索解空间,将反序、插入、块移动、交换和双桥等多种算子组合构造不同的混合邻域,通过Levy飞行选择相应的邻域结构进行寻优,并引入模拟退火算法的Metropolis接受准则,能够以一定的概率接受劣质解,使算法不易陷入局部最优.为了验证算法的性能,将HDCS算法分别与其他基于CS算法、经典智能优化算法和新型群智能优化算法的3类方法进行比较,实验结果表明,HDCS算法不但优于其他基于CS的算法,同时也优于一些其他最新的群智能优化算法.
The cuckoo search（CS）algorithm is a new metaheuristic method which is proposed by Yang and Deb in 2009,inspired by the brood parasitism behavior of cuckoos.The cuckoos find the optima by the Levy flight.Levy flight has a heavy-tailed which make it search in the short area most time and jump to the long distance occasionally.Such characteristics of CS can enlarge the search areas,guarantee the diversity of solution,and make it not easy to fall into the local optimum.As a result,CS shows better performance in solving continuous problems,but there are few researches applying it to the discrete problems,at the same time those existing discrete strategies convergesslowly in the search processes.In order to solve this deficiency,a novel discrete hybrid Cuckoo Search（HDCS）algorithm,which combines learning-based hybrid neighborhood structure and probability acceptance criteria,is proposed for traveling salesman problem.Specifically,the HDCS algorithm searches the solution space by learning from the best and learning from problem at hand.HDCS uses reverse,insertion,block moving,swap and double bridge operator to generate different hybrid neighborhood structures,and levy flight is used to select those neighborhood structures.Furthermore,the Metropolis acceptance criterion of simulated annealing algorithm is introduced to allow accepting inferior solutions with certain probability,so the algorithm will not be strapped into local optima easily.In order to test the performance of HDCS,the paper chooses some benchmark instances which city quantity varies from51 to 13509,and compares it with three types of algorithms.They are another improved CS algorithm,the classical intelligent optimization algorithms,and the other new swarms intelligence algorithms.The experimental results show that HDCS algorithm is not only better than other cuckoo search based algorithms,but is better than some state-ofthe-art swarm intelligence algorithms also.
作者
林敏
刘必雄
林晓宇
Lin Min Liu Bixiong Lin Xiaoyu(School of Computer and Information Science,Fujian Agriculture and Forestry University, Fuzhou, 350002, Chin)
出处
《南京大学学报（自然科学版）》
CAS
CSCD
北大核心
2017年第5期972-983,共12页
Journal of Nanjing University（Natural Science）
基金
福建省自然科学基金(2015J01233)
福建省教育厅项目(JAT160143
JA12105)
