Artificial evolution of computer software (evolutionary neural networks, genetic programming, evolutionary fuzzy systems, etc.) has been shown to generate software that in many cases is more performant than that designed by engineers. Evolved software performs well under the same conditions used during evolutionary training. However, in situations where unpredictable change may affect normal operation, evolved systems often fail. In this paper we describe a new approach for evolving software that remains adaptive and is therefore very robust to unpredictable change after evolution. To illustrate the idea, we present the case of evolutionary robots that quickly and reliably adapt online to several types of new situations, including sensory, environmental, and mechanical change, while still performing their task. The core of the methodology consists of evolving the mechanisms of parameter adaptation instead of the parameters themselves. We shall conclude by showing how this methodology can be applied to a variety of other situations beyond robotics.