## 4 The Concept of GORBA for Fast Rescheduling
### Evolutionary Optimization
#### 4.2.1 Gleam  
We use the Evolutionary Algorithm GLEAM (General Learning Evolutionary Algorithm and Method), as it has already been applied successfully to other combinatorial problems like the planning of collision-free robot movements [31; 32], TSP-like problems [33] or other scheduling tasks [31]. A complete description of GLEAM, its extensions, and its applications can be found in [31]. In contrast to many other EAs, GLEAM allows the aggregation of parameters belonging semantically together in one gene. A gene is the elementary unit of a chromosome, which may be shifted within the chromosome or the parameters of which may be altered by the corresponding mutation operators. This allows an easy and flexible mapping of the problem parameters to the genes of the chromosome, which is called _gene model_ within the context of GLEAM. Furthermore, there is an evolvable meta-structure for each chromosome, called _segmentation_. The lower part of Figure 1 shows an example of a segmented chromosome of simple genes without parameters representing grid jobs and one more complex gene with one parameter, the RAS-gene. The details of this example are explained later. The segments serve as the basis for some macro mutations suited among others for combinatorial optimization:  
* inversion: reversion of the internal order of the genes of a segment.
* segment shifting: a segment is shifted as a whole.
* segment merging: if non-adjacent segments are merged, the operation includes segment shifting.
* segment mutation: all genes of a segment undergo parameter mutation with a given probability.  
Figure 1: Example of a segmented chromosome organized as a linear list. It is based on gene model GM2. It represents a legal schedule of the two workflows above as explained in the text. The position of the RAS gene is arbitrary and of no importance. In the lower right corner an example of a gene of GM1 representing a grid job needing three resources is given.  
Segment boundaries are also used as crossover points for the standard 1- and _n_-point crossover operators, which include a genetic repair that ensures that every offspring does not lack genes in the end. Thus, segments can only be passed to the offspring as a whole. The idea behind this concept is to allow the establishment of meaningful building blocks of partial solutions, which are inherited.  
Instead of the frequently used panmictic population, which is characterized by the ability of each individual to choose any other individual as a partner, the population of GLEAM is based on a diffusion model of overlapping local neighborhoods [22]. The individuals are located on a ring implying a _geographical_ neighborhood with the individuals on both sides. Partner selection and offspring acceptance take place only within the neighborhoods. Figure 2 shows an example of small neighborhoods, also called _demes_, with a size of four neighbors. Since demes overlap, as shown in Figure 1, genotypic information can spread. As this spreading is much slower than with panmictic populations, niches of more or less similar individuals can emerge, develop, disperse, meet each other, and compete. Thus, genotypic diversity is preserved over a longer period of time. Furthermore, neighborhood models like this one cause an adaptive balance between exploration and exploitation resulting in faster, more robust runs compared to their panmictic counterpart [22,34,35].