Analysis of fitness landscape modifications in evolutionary dynamic optimization

In this work, discrete dynamic optimization problems (DOPs) are theoretically analysed according to the modifications produced in the fitness landscape during the optimization process. Using the proposed analysis framework, the following DOPs are analysed: problems generated by the XOR DOP generator, three versions of the dynamic 0-1 knapsack problem, one problem involving evolutionary robots in dynamic environments, and the random dynamics NK-model. The XOR DOP generator creates benchmark DOPs from any binary static optimization problem, which allows to explore the properties of the static problem in a dynamic environment. Three types of transformations occurring in the fitness landscapes are observed in the DOPs analysed here. They are caused by: (i) permutation of solutions in the search space; (ii) duplication of solutions; and (iii) adding deviations to the fitness of a subset of solutions. The XOR DOP generator creates a special type of permutation that is not found in the other investigated DOPs. In this way, a new benchmark problem generator is proposed here based on the analysis performed, allowing to produce DOPs with six types of fitness landscape transformations, including those similar to the problems investigated in this paper. When compared to the XOR DOP generator, new algorithms can be tested and compared in a wider range of dynamic environments using the new generator. It is important to observe that some of the fitness transformations analysed here, like those caused by the duplication of solutions, are not currently explored in the evolutionary dynamic optimization area.