  Evolution in changing environments is an important, but little studied aspect
of the theory of evolution. The idea of adaptive walks in fitness landscapes
has triggered a vast amount of research and has led to many important insights
about the progress of evolution. Nevertheless, the small step to time-dependent
fitness landscapes has most of the time not been taken. In this work, some
elements of a theory of adaptive walks on changing fitness landscapes are
proposed, and are subsequently applied to and tested on a simple family of
time-dependent fitness landscapes, the oscillating NK landscapes, also
introduced here. For these landscapes, the parameter governing the evolutionary
dynamics is the fraction of static fitness contributions f_S. For small f_S,
local optima are virtually non-existent, and the adaptive walk constantly
encounters new genotypes, whereas for large f_S, the evolutionary dynamics
reduces to the one on static fitness landscapes. Evidence is presented that the
transition between the two regimes is a 2nd order phase transition akin a
percolation transition. For f_S close to the critical point, a rich dynamics
can be observed. The adaptive walk gets trapped in noisy limit cycles, and
transitions from one noisy limit cycle to another occur sporadically.
