Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: We consider the question of the stability of evolutionary algorithms to gradual changes,<lb>or drift, in the target concept. We define an algorithm to be resistant to drift if, for<lb>some inverse polynomial drift rate in the target function, it converges to accuracy 1 − ǫ<lb>with polynomial resources, and then stays within that accuracy indefinitely, except with<lb>probability ǫ at any one time. We show that every evolution algorithm, in the sense of<lb>Valiant [19], can be converted using the Correlational Query technique of Feldman [9], into<lb>such a drift resistant algorithm. For certain evolutionary algorithms, such as for Boolean<lb>conjunctions, we give bounds on the rates of drift that they can resist. We develop some<lb>new evolution algorithms that are resistant to significant drift. In particular, we give an<lb>algorithm for evolving linear separators over the spherically symmetric distribution that is<lb>resistant to a drift rate of O(ǫ/n), and another algorithm over the more general product<lb>normal distributions that resists a smaller drift rate. The above translation result can be also interpreted as one on the robustness of the notion of<lb>evolvability itself under changes of definition. As a second result in that direction we show<lb>that every evolution algorithm can be converted to a quasi-monotonic one that can evolve<lb>from any starting point without the performance ever dipping significantly below that of<lb>the starting point. This permits the somewhat unnatural feature of arbitrary performance<lb>degradations to be removed from several known robustness translations.

Evolution with Drifting Targets