—Elasticity [19] is a key feature for cloud infrastruc-tures to continuously align allocated computational resources to evolving hosted software needs. This is often achieved by relaxing quality criteria, for instance security or privacy [8] because quality criteria are often conflicting with performance. As an example, software replication could improve scalability and uptime while decreasing privacy by creating more potential leakage points. The conciliation of these conflicting objectives has to be achieved by exhibiting trade-offs. Multi-Objective Evolutionary Algorithms (MOEAs) have shown to be suitable candidates to find these trade-offs and have been even applied for cloud architecture optimizations [21]. Still though, their runtime efficiency limits the widespread adoption of such algorithms in cloud engines, and thus the consideration of quality criteria in clouds. Indeed MOEAs produce many dead-born solutions because of the Darwinian inspired natural selection, which results in a resources wastage. To tackle MOEAs efficiency issues, we apply a process similar to modern biology. We choose specific artificial mutations by anticipating the optimization effect on the solutions instead of relying on the randomness of natural selection. This paper introduces the Sputnik algorithm, which leverages the past history of actions to enhance optimization processes such as cloud elasticity engines. We integrate Sputnik in a cloud elasticity engine, dealing with performance and quality criteria, and demonstrate significant performance improvement, meeting the runtime requirements of cloud optimization.