Monitoring of Cloud services is vital for both service providing organizations and consumers. The service providers need to maintain the quality of service to comply their services with the QoS parameters defined in SLA's such as response time, throughput, delay through continuous monitoring of services. The dynamic monitoring involves prediction of SLA violations and subsequent adaptation of the service compositions. The task of adaptation is in fact the task of discovering another plausible composition in the face of services recorded to have generated QoS violations. QoS- Driven Utility based service composition approach considers the individual user's priorities for QoS parameters and determines the overall utility measure of the service composition for the end user. In this work we present the problem of service composition adaptation as a multi-objective assignment optimization problem, which in turn is a NP-hard problem. The evolutionary algorithm GA with Tabu has been formulated as a Memetic and Pareto optimal approach for the adaptation problem and analyzed for efficiency in solving the problem.