The significant advancements in grid computing provide a promising platform for parallel and distributed systems. However, achieving acceptable application performance in the grid environment remains a difficult engineering challenge. In particular for applications composed of services requiring some quality requirements to be fulfilled in order to satisfy the users needs. There is a growing need to support these applications as they perform unacceptably if platform resources are scarce or if the deployment is not carefully configured and tuned for the anticipated load. The fundamental problem we have at hand is of partitioning application services on to a distributed environment such that all services involved in the composition get sufficient resources to allow them to deliver at least the minimum required quality to be useful for the application. A subsequent problem is how to re-partition (reconfigure) or even adapt the application?s service set dynamically when the underlying resources of the grid environment change with time. In this paper we provide an overview of both service partitioning and reconfiguration and different elements that affect the search process and investigate the nature of the problem space. In addition, we also introduce a special type of evolutionary algorithms such as learning and other nature-inspired solution techniques that can handle the dynamic behaviour of such stochastic computational environment.