In this paper we study a model to feature selection based on Ant Colony Optimization and Rough Set Theory. The algorithm looks for reducts by using ACO as search method and RST offers the heuristic function to measure the quality of one feature subset. Major results of using this approach are shown and others are referenced. Recently, runtime analyses of Ant Colony Optimization algorithms have been studied also. However the efforts are limited to specific classes of problems or simplified algorithm’s versions, in particular studying a specific part of the algorithms like the pheromone influence. From another point of view, this paper presents results of applying an improved ACO implementation which focuses on decreasing the number of heuristic function evaluations needed.