Many training simulations can benefit from increased levels of reality obtained through the use of intelligent autonomous agents. The optimization of multiple interacting agent programs is an open research problem. Evolutionary Algorithms allow for an efficient direct stochastic search of the (near) infinite space of all possible agent programs. This paper describes a proof-of-concept experiment for evolving autonomous agents in a two dimensional environment. Each of the agent types has its own goals to enhance or reduce the hostility of the environment, which are correlated to a fitness value. The results show that genetic programming can be successfully be employed to optimize the agent programs. With further work, agents should be able to operate in a virtual world to train first responders.