## 4 The Concept of GORBA for Fast Rescheduling
### Adaptive Memetic Algorithms  
The less strategy parameters an algorithm needs to be adjusted, the fewer mistakes can be made and the less experience of the user is required. This is why adaptivity was added to MAs at an early stage [40, 41, 51, 52] and the research in this field is still going on, see e.g., [53]. In our memetic extension of GLEAM, called HyCLEAM (Hybrid General Purpose Evolutionary Algorithm and Method) [24, 25, 31, 40, 48], three types of MAs are included besides the basic algorithms:  
* The simple Memetic Algorithm, where one meme is used without any adaptivity, see also Figure 4,
* The Adaptive Single-memetic Algorithm (ASMA) consisting of one meme, the application of which is adjusted adaptively, and
* The Adaptive Multimeme Algorithm (AMMA), where both, meme selection and their application are controlled adaptively. \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Overrun**} & \multicolumn{3}{c}{**Actual RAS**} \\ \cline{2-4}  & **Cheapest** & **Fastest** & **Preference** \\ \hline cost & preference & cheapest, preference & cheapest \\ time & fastest, preference & preference & fastest \\ \hline \hline \end{tabular}
\end{table} 
Table 1: RAS alternatives depending on two overrun situations of the actual schedule. The abbreviation _fastest_ means the usage of the fastest of the earliest available resource (RAS-1), _cheapest_ the same with the cheapest of the earliest available resource (RAS-2), and _preference_ means RAS-3, where RAS-1 or RAS-2 is selected according to a user-given preference of the application job. The adaptation is based on _costs_ measured in additional evaluations caused by the meme and on the _benefit_ of local search measured as relative fitness gain _rfg_ as given in (6), where _fLS_ is the fitness obtained from the local searcher LS applied to the offspring with the fitness _fevo_. Fitness values are normalized in the range of 0 and _f_max, which turns every task into a maximization problem. _f_max can be regarded an upper estimation of the fitness. \[\textit{rfg}= \begin{cases}\frac{f_{LS}-f_{evo}}{f_{\max}-f_{evo}}&\text{ if }\ f_{LS}>f_{evo}\\ 0&\text{else}\end{cases}  \tag{6}\]  
In case of multiple memes, an initially equal selection probability is assigned to every meme. These probabilities _p_\({}_{i}\) are adjusted from time to time according to Equation (7). \[p_{i}=\frac{1}{\sum_{i=1}^{n}\frac{\textit{rfg}(LS_{i})}{eval(LS_{i})}}\cdot \frac{\textit{rfg}(LS_{i})}{eval(LS_{i})} \tag{7}\]  
where \(n\) is the number of local searches (LS), _rfg_(\(LS_{i}\)) is the sum of the relative fitness gains of a particular _LSi_, and _eval_(\(LS_{i}\)) is the sum of evaluations needed to achieve these fitness improvements, both recorded since the last adjustment. The same approach is used to tune strategy parameters of memes by selecting one out of a given set. This cost-benefit-based adaptation procedure is described in detail in [24]. Thus, the only remaining strategy parameter of the MA is the choice between the LS application to the _best_ or _all_ offspring per pairing, called _best_- and _all-improvement_. For both adaptive algorithms, there is an adaptive variant of the _all-improvement_, which always applies the LS to the best offspring of a mating, while its siblings are treated with an adaptively controlled likeliness. Hence, it is left to adaptation how many offspring are locally improved according to the benefit gained and the additional costs induced. Figure 5 shows the pseudo code of the AMMA with the adaptive memetic part indicated by a dark grey background. The Boolean strategy parameter _all_improvement_ distinguishes between best- and adaptive all-improvement. The adaptations of the probabilities for meme selection, strategy parameters of a meme, and for adjustment of _p_all_ are indicated in the color blue. In contrast to many other local searchers, the application of all shifting LS introduced requires one additional evaluation each regardless of their strategy parameters and the LS-RAS may require two.