Ant Colony Optimization (ACO) algorithms often suffer from criticism for the local optimum and premature convergence. In order to overcome these inherent shortcomings shared by most ACO algorithms, we divide the ordinary ants into two types: the utilization-oriented ants and the exploration-oriented ants. The utilization-oriented ants focus on constructing solutions based on the learned experience like ants in many other ACO algorithms. On the other hand, inspired by the adaptive behaviors of some real-world Monomorium ant species who tend to select paths with moderate pheromone concentration, a novel search strategy, that is, a completely new transition rule is designed for the exploration-oriented ants to explore more unknown solutions. In addition, a new corresponding update strategy is also employed. Moreover, applying the new search strategy and update strategy, we propose an improved version of ACO algorithm—Moderate Ant System. This improved algorithm is experimentally turned out to be effective and competitive.