EA-based problem solving environments have progressively evolved in the last two decades from explicit one-problem serial solvers to multi-solve rs platforms running on vast distributed heterogeneous resources. Significant efforts in the literature were devoted towards designing EA-based problem solving environments. Those research efforts were mainly directed to innovating new EAs with a parallel implementation (Cantu-Paz, 2000), and the counterpart for those research efforts were directed towards designing and constructing parallel computing environments (Weise, 2007) that could host parallel and distributed implementations of EAs. Still for the evolution of the problem solving paradigms, problem solving environments have not fully shifted to parallel and distributed models, and even up till today practices of serially implementing EAs problems of medium complexity are still noticeable. These practices prevailed in part due to the continuous increase in clock speeds, multicore processors, and problem nature. Yet, in the past few years, the significant increase in distributed resources, high bandwidth/ low latency networks and cheap data storage along with the wide expansion in problem scope and addressing new problem types that were not attainable before, all combined together strongly motivated to re thinking the strategy of designing EA-based problem solving environments. Various distributed computing paradigms were used as platforms for EA-based problem solving environments, (Munawar et al., 2008) gives a brief illustration of those paradigms. In this chapter we concentrate on a modern distributed computing paradigm, namely grid computing (Foster & Kesselman, 1999). In the recent years, grid computing acquired widespread attention from both research and industrial institutions, as it provides contextual establishment of open standard platforms for distributed computing (more details in section 2.1) Constructing an EA-based problem solving environment requires two main streams of working, one is the algorithm design and the other is the challenges associated with constructing a Grid based platform. The algorithm design is significantly affected when using distributed technologies, therefore many points should be taken into account when designing algorithms for distributed environments: fault tolerance, support of Open Access Database www.i-techonline.com