Ant Colony Optimization (ACO) is a modeling of the search behavior of ants based on their pheromone communication. When a Traveling Salesman Problem (TSP) is solved by ACO algorithms, ants come to generate similar round tours by positive feed back mechanism as the search proceeds. Therefore, it is difficult to get out of a local optimum. In order to solve this problem, we propose a method for effective diversification of search. In this method, as the frequency that ants passed through an edge becomes large, other ants come not to pass through the edge. As a result of experiments, it was confirmed that the quality of the acquired solutions improves by the diversification mechanism.