We present an Evolutionary Planning and Replanning Algorithm, capable of producing Bounded Suboptimal solutions in an Anytime fashion. Combining Genetic Algorithm with anytime approach is uncommon. Anytime Genetic algorithm combines the benefits of an Anytime and an Evolutionary Algorithm to efficiently provide solutions to complex, Dynamic Search Problems. The results appear promising for shorter horizon problems, while for large horizon the search tends to behave like a standard GA. © (2012) Trans Tech Publications, Switzerland.