Swarm Intelligent (SI) algorithms draw their inspiration from the interaction of individuals of social organisms. One such algorithm, Ant Colony Optimization (ACO) [1], utilizes the foraging behavior of ants to solve combinatorial optimization problems. Although ACO performs well in a static environment, it has been pointed out that ACO does not perform as well as other heuristics in dynamic situations such as routing. This paper proposes a new algorithm, entitled Evolutionary Ant Colony Optimization (EACO), that combines ACO with elements of Genetic Algorithms (GA). By adding evolution, the EACO algorithm allows the individual ants to develop their own characteristics, thereby removing the homogeneity inherent within ACO. Our results demonstrate the potential of this approach in a dynamic environment.