Several Issues In Evolutionary Dynamic Optimization

Evolutionaryalgorithms(EAs)havebeenwidelyandsuccessfullyappliedtomanyareas, such as planning (e.g., routing, scheduling), design (e.g., signal processing), sim-ulationandrecognition,controlandclassification(e.g.,machinelearning,patternrecog-nition). TraditionalEAs mainly focuson static problemsthough most problemsin prac-tice change over time. For example, the objective function, the problem instance or theconstraints may change at any time. The task now is to find the optimal solution to thegiven problem at every moment. Due to convergence, traditional EAs have difficultiesin making adaptation to environmental changes.To tackle the convergence issue, a natural way is to maintain a certain level ofdiversity during the run of the algorithm. One simple and effective method is the im-migrant scheme, which works by replacing a predefined portion of individuals of thecurrent population with some immigrants. According to the mechanism of generatingimmigrants, we classify existing immigrant schemes into two categories, namely directimmigrant schemes and indirect immigrant schemes. Then we empirically analyze andcompare their behaviors in dynamic environments. The experimental results show thatin most cases direct immigrant schemes beat indirect immigrant schemes regarding theperformance while are beaten with respect to the robustness. Based on the analyses, wepropose a hybrid immigrant scheme, which is shown by experimental results to havegood tradeoff between performance and robustness.Furthermore, we investigate the effect of the replacement rate of an immigrantscheme on the performance, where the experimental results show that for different im-migrant schemes, different problems, different environments, and different stages ofthe search, the optimal value of replacement rate varies. To alleviate the burden of fine-tuning the replacement rate, we propose a self-adaptive mechanism for the replacementrate, which automatically adapts the value of the replacement rate according to the ef-fect of the current immigrants. It is shown by the experimental results that the proposedapproachcanachievegoodperformancefordifferentimmigrantschemes, problemsandenvironments, and thus avoid the tedious work of fine-tuning parameters.However, the traditional tracking-moving-optima (TMO) goal may not be properin practice. We point out several limitations of pursuing the TMO goal in real-worldapplications,andproposetofindasequenceofsolutionswhicharerobustovertime. Werefer to the process of finding such solutions as robust optimization over time (ROOT). Then we describe ROOT's differences from and similarities to dynamic optimizationand robust optimization, and analyze its properties on a discrete dynamic optimizationproblem. Based on the analysis, we propose a measure to evaluate the robustness inthe time domain, and design a framework with fitness approximation and predictionto solve ROOT. Besides, we propose a set of test problems and evaluation criteria forcomparingalgorithms'performance. Throughexperiments, weshowthatouralgorithmcan reliably find robust solutions over time.Finally, we focus on a given set of problems, and set the optimization goal to befinding multiple robust solutions to the given problems. We call the process of findingsuch solutions robust optimization with multiple solutions (ROMS), and describe itssignificance in practical use, as well as its differences from and similarities to dynamicoptimization,robustoptimizationandROOT.Inaddition,wepresentaformaldefinitionfor ROMS, based on which we propose a 2-phase based approach to solve it. Thenwe put forward a set of test problems, and validate the effectiveness of the proposedapproach in solving ROMS.