This thesis presents a novel algorithm called ant colony optimization with dual pheromone tables (ACODPT) for improving the quality of ant colony optimization (ACO). The proposed algorithm works by adding a so-called ¡§negative¡¨ pheromone table to ACO to avoid the problem of ACO easily falling into local optima. By using the ¡§negative¡¨ pheromone table to eliminate the most impossible path to search for the new solution, the probability of selecting the remaining paths is increased, and so is the quality. To evaluate the performance of the proposed algorithm, ACODPT is compared with several state-of-the-art algorithms in solving the clustering problem. The experimental results show that the proposed algorithm can eventually prevent ACO from falling into local optima in the early iterations, thus providing a better result than the other algorithms in many cases.