Multi-agent systems require coordination of sources with distinct expertise to perform complex tasks effectively. In this paper, we use a co-evolutionary approach of using genetic algorithms (GAs) to evolve multiple individuals who call effectively cooperate to solve a common problem. We concurrently run a GA for each individual in the group. We experiment with a room painting domain which requires cooperation of two agents. We have used two mechanisms for evaluating an individual in one population: (a) pair randomly with members from the other population, (b) pair it with members of the other population a shared memory containing the best pairs found so far. Both the approaches were successfull in generating optimal behavior patterns. However, our preliminary results exhibit a slight edge for the shared memory approach.