This paper presents a new genetic algorithm (GA) using the edge assembly crossover (EAX) to remedy a problem of the genetic algorithm with EAX (GA-EAX) for traveling salesman problems (TSPs). GA-EAX is one of the most powerful approximation algorithms. GA-EAX executes two search stages sequentially. The first search stage improves tours locally in the population, preserving a diversity of the population. The second search stage takes the population of the last generation of the first search stage as an initial population and improves tours globally to find better tours than the first stage does. GA-EAX has reportedly succeeded in updating the world records of 100,000-city-scale instances. However, GA-EAX fails to find optimal solutions or known best ones with a high probability on some several-thousand-city-scale instances. In order to overcome the problem of GA-EAX, we propose an improved GA-EAX that employs a new switching condition of the two search stages taking account of a rate of failing to improve tours and a multi-start strategy for the second stage. Through some numerical experiments, we confirmed that the proposed method succeeds in finding the optimal solutions or the known best ones with up to five times higher probabilities than the original GA-EAX. Furthermore, the proposed method succeeds in reducing the number of generations to find the optimal solutions or the known best ones by up to 24.7% in comparison with the original GA-EAX.