Offers of public IAAS providers often vary: new providers enter the market, existing ones change their pricing or improve their offering. Decision on whether and how to improve already deployed platforms, either by reconfiguration or migration to another provider, can be seen as a NP-hard optimization problem. In this paper, we define a new realistic model for this Migration Problem, based on a Multi-Objective Optimization formulation. An evolutionary approach is introduced to tackle the problem, using specific operators. Experiments are conducted on multiple realistic data-sets, showing that the evolutionary approach is viable to tackle real-size instances in a reasonable amount of time.