In order to solve the premature convergence problem of the basic Ant Colony Optimization algorithm, a promising modification based on the information entropy is proposed. The main idea is to evaluate stability of the current space of represented solutions using information entropy, which is then applied to turning of the algorithm's parameters. The path selection and evolutional strategy are controlled by the information entropy self-adaptively. Simulation study and performance comparison with other Ant Colony Optimization algorithms and other meta-heuristics on Traveling Salesman Problem show that the improved algorithm, with high efficiency and robustness, appears self -adaptive and can converge at the global optimum with a high probability. The work proposes a more general approach to evolutionary-adaptive algorithms related to the population's entropy and has significance in theory and practice for solving the combinatorial optimization problems.