Learning and Anticipation in Online Dynamic Optimization

In this chapter we focus on the importance of the use of learning and anticipation in (online) dynamic optimization. To this end we point out an important source of problem-difficulty that has so far received significantly less attention than the traditional shifting of optima. Intuitively put, decisions taken now (i.e. setting the problem variables to certain values) may influence the score that can be obtained in the future. We indicate how such time-linkage can deceive an optimizer and cause it to find a suboptimal solution trajectory. We then propose a means to address time-linkage: predict the future (i.e. anticipation) by learning from the past. We formalize this means in an algorithmic framework and indicate why evolutionary algorithms (EAs) are specifically of interest in this framework. We have performed experiments with two benchmark problems that feature time-linkage. The results show, as a proof of principle, that in the presence of time-linkage EAs based on this framework can obtain better results than classic EAs that do not predict the future.