Abstract:  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 converges slowly 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 from 51 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－of－the－art swarm intelligence algorithms also.