Performance evaluation of evolutionary heuristics in dynamic environments

Abstract

In stationary optimization problems, it is assumed that no changes occur with respect to the problem solved during the course of computation. However many real-world optimization problems are non-stationary (dynamic) and subject to changes over time with respect to the objective function, the decision variables or the environmental parameters. For dynamic optimization problems the goal of an optimization algorithm is no longer to find a stationary solution, but to continuously track the changing or moving optimum in the problem space. In this thesis, we present a complete and an extensive performance evaluation of leading evolutionary optimization techniques in dynamic environments. We have examined and implemented a set of 13 evolutionary optimization techniques on a common platform by using the moving peaks benchmark and by varying important problem parameters. Two new algorithms which are the hybridization of the leading techniques in the literature have been proposed in this thesis. Based on the experimental study, it was observed that the hybrid methods outperform the related work with respect to quality of solutions for various parameters of the given benchmark problems. Additionally, a new comparison metric which is based on signal similarity is proposed and used for performance evaluation of algorithms. The comparison study is based on both artificial problems including moving peaks problems and some of the real-world problems such as scheduling. We have also implemented five evolutionary algorithms which have been designed to solve dynamic job shop scheduling problem. The algorithms are compared in both deterministic and stochastic scheduling environments. The results have shown that there is no algorithm that is best for all environmental conditions.