Alberto Tonda
email: al-berto.tonda@gmail.com

Evelyne Lutton
email: evelyne.lutton@inria.fr

Giovanni Squillero
email: giovanni.squillero@polito.it

A Benchmark for Cooperative Coevolution

Keywords: Cooperative co-evolution, Group Evolution, Parisian Evolution, Benchmark Problem, Experimental Analysis

Cooperative co-evolution algorithms (CCEA) are a thriving sub-field of evolutionary computation. This class of algorithms makes it possible to exploit more efficiently the artificial Darwinist scheme, as soon as an optimisation problem can be turned into a co-evolution of interdependent sub-parts of the searched solution. Testing the efficiency of new CCEA concepts, however, it is not straightforward: while there is a rich literature of benchmarks for more traditional evolutionary techniques, the same does not hold true for this relatively new paradigm. We present a benchmark problem designed to study the behavior and performance of CCEAs, modeling a search for the optimal placement of a set of lamps inside a room. The relative complexity of the problem can be adjusted by operating on a single parameter. The fitness function is a trade-off between conflicting objectives, so the performance of an algorithm can be examined by making use of different metrics. We show how three different cooperative strategies, Parisian Evolution (PE), Group Evolution (GE) and Allopatric Group Evolution (AGE), can be applied to the problem. Using a Classical Evolution (CE) approach as comparison, we analyse the behavior of each algorithm in detail, with respect to the size of the problem capito.

Introduction

Cooperative co-evolution algorithms (CCEAs) share common characteristics with standard artificial Darwinist methods, i.e. Evolutionary Algorithms (EAs), but with additional components that aim at implementing collective capabilities. For optimisation purpose, CCEAs are based on a specific formulation of the problem where various inter-or intra-population interaction mechanisms occur. Usually, these techniques are efficient as optimisers when the problem can be split into smaller interdependent subproblems. The computational effort is then distributed onto the evolution of smaller elements of similar or different nature, that aggregates to build a global solution.

Besides precursory research lines, focused on co-evolution as a complex phenomenon leading to stable or unstable equilibria (complex systems, multi-agent systems) [START_REF] Axelrod | The Evolution of Cooperation[END_REF], first attempts to exploit a cooperative co-evolution paradigm for optimisation purposes have been made by Husbands and Mills [14], by De Jong [START_REF] Potter | A cooperative coevolutionary approach to function optimization[END_REF] and by Ahluwalia and Bull [START_REF] Ahluwalia | Co-evolving functions in genetic programming: Dynamic adf creation using glib[END_REF]. These approaches were heterogeneous, in the sense that co-evolution is implemented between separated sub-populations.

A few years later, inspired by the Michigan approach (John Holland's classifier systems [13]), a single-population co-evolution scheme, first called "Individual-GP" [9], then "Parisian Scheme", was developed in France for complex optimisation tasks [10].

Cooperative co-evolution is increasingly becoming the basis of successful applications [START_REF] Amaya | A memetic cooperative optimization schema and its application to the tool switching problem[END_REF]8,11,[START_REF] Potter | A cooperative coevolutionary approachto partitional clustering[END_REF][START_REF] Wiegand | Robustness in cooperative coevolution[END_REF], including learning [START_REF] Bongard | Active coevolutionary learning of deterministic finite automata[END_REF] and scheduling problems [15]. These approaches can be shared into two main categories: heterogeneous co-evolution that happens between a fixed number of separate populations [7, [START_REF] Panait | Archive-based cooperative coevolutionary algorithms[END_REF][START_REF] Popovici | The effects of interaction frequency on the optimization performance of cooperative coevolution[END_REF], and homogeneous co-evolution, that occurs within a single population [START_REF] Landrin-Schweitzer | Introducing lateral thinking in search engines[END_REF][START_REF] Vidal | New genetic operators in the fly algorithm: application to medical PET image reconstruction[END_REF][START_REF] Wu | Rethinking multilevel selection in genetic programming[END_REF].

The design and fine tuning of such algorithms remain however difficult and strongly problem dependent. A critical question is the design of simple test problem for CCEAs, for benchmarking purpose. A first test-problem based on Royal Road Functions has been proposed in [START_REF] Ochoa | Cooperative royal road functions[END_REF]. A second example is the NK-landscapes variant redesigned for CCEAs, known as NKC-landscapes [16]: however, Kauffman's work was more focused on the study of the dynamics of coevolution than on evolution as an optimization process.

We propose another simple problem, the lamps problem. The main difference with previous benchmarks is the absence of apriori information on the optimal number of individuals/partial solutions that should compose the global solution. As for many real-world problems, the number of individuals in the best group is unknown. Moreover, various instances of the problem, of increasing complexity can be generated by acting on a single ratio parameter. For these reasons we feel that the proposed benchmark, while simple to implement and calibrate, can still pose a challenge to cooperative coevolution algorithms. We show below how three CCEAs can be designed and compared against a classical approach, with a special focus on their behaviour with respect to the size of the problem. Preliminary results on this topic have been presented in [START_REF] Tonda | Lamps: A test problem for cooperative coevolution[END_REF].

The paper is organised as follows: the Lamps problem is described in section 2, then the design of three cooperative co-evolution strategies, Parisian Evolution, Fig. 1 Placement of a set of lamps. The aim is to enlighten all the square area. It is interesting to notice how a solution where some of the light of each lamp is wasted outside the area (left) overall performs better than a solution where the grayed lamp maximises its own performance (right).

Group Evolution, and Allopatric Group Evolution, is detailed in sections 3, 4 and 5 respectively. The experimental setup is described in section 6: four strategies are tested, a classical genetic programing approach, (CE for Classical Evolution), the Parisian Evolution (PE), the Group Evolution (GE) and the Allopatric Group Evolution (AGE). All methods are implemented using the µGP toolkit [START_REF] Sanchez | Evolutionary Optimization: the µGP toolkit[END_REF]. Results are presented and analysed in section 7, and conclusions and future work are given in section 8.

The Lamps problem

The optimisation problem chosen to test cooperative coevolution algorithms requires to find the best placement for a set of lamps, so that a target area is fully brightened with light. The minimal number of lamps needed is unknown, and heavily depends on the topology of the area. Lamps are all alike, modeled as circles, and each one may be evaluated separately with respect to the final goal. In the example, the optimal solution requires 4 lamps (Figure 1, left): interestingly, when examined independently, all lamps in the solution waste a certain amount of light outside the target area. However, if one of the lamps is positioned to avoid this undesired effect, it becomes impossible to lighten the remaining area with the three lamps left (Figure 1, right). Since lamps are simply modeled as circles, the problem may also be seen as using the circles to completely cover the underlying area, as efficiently as possible.

This apparently simple benchmark exemplifies a common situation in real-world applications: many problems have an optimal solution composed of a set of homogeneous elements, whose individual contribution to the main solution can be evaluated separately. Note that, in this context, homogeneous is used to label elements sharing the same base structure. Not only, but often the optimal solution is composed of not-optimal sub-solutions.

A similar toy problem has been sketched in [START_REF] Sanchez | Group evolution: Emerging synergy through a coordinated effort[END_REF]. Here the structure of the benchmark is improved and parametrised, and a modified fitness function increases the complexity and the number of local optima on the fitness landscape.

Size of the problem

It is intuitive that the task of enlightening a room with a set of lamps can be more or less difficult, depending on the size of the room and the cone of light of each lamp. If small sources of light are used to brighten a large room, surely a greater number of lamps will be required, and the number of possible combinations will increase dramatically.

With these premises, the complexity of the problem can thus be expressed by the ratio between the surface to be enlightened and the maximum area enlightened by a single lamp:

problem size = area room area lamp
as this ratio increases, finding an optimal solution for the problem will become harder.

It is interesting to notice how variations in the shape of the room could also influence the complexity of the task: rooms with an irregular architecture may require more intricate lamp placements. However, finding a dependency between the shape of the room and the difficulty of the problem is not trivial, and results might be less intuitive to analyze. Also, the cooperative coevolution algorithms do not search for or benefit from eventual symmetries in the problem. For all these reasons, the following experiments will feature square rooms only.

Fitness value

Comparing different methodologies on the same problem requires a common fitness function, to be able to numerically evaluate the efficiency of each approach.

Intuitively, the fitness of a candidate solution should be directly proportional to the area fully brightened by the lamps and inversely proportional to the number of lamps used, favoring solutions that cover more surface with light using the minimal number of lamps. The first term in the fitness value will thus be proportional to the ratio of the area enlightened by the lamps,

area enlightened total area

A further contribution is added, to help experts in evaluating the goodness of the grouping performed by the algorithms: the area brightened by more than one lamp is to be minimised, in order to have as little overlapping as possible. The second term will be then proportional to:

- area overlap total area
It is interesting to note that minimising the overlap also implies an optimisation of the number of lamps used, since using a greater number would lead to more overlapping areas.

The final fitness function will then be:

f itness = area enlightened total area -W • area overlap total area = = area enlightened -W • area overlap total area
where W is a weight associated to the relative importance of the overlapping, set by the user. Using this function with W = 1, fitness values will range between (0, 1), but it is intuitive that it is impossible to reach the maximum value: by problem construction, overlapping and enlightenment are inversely correlated, and even good solutions will feature overlapping areas and/or parts not brightened. This problem is actually multiobjective, the fitness function we propose corresponds to a compromise between the two objectives.

Parisian Evolution

Initially designed to address the inverse problem for Iterated Function System (IFS), a problem related to fractal image compression[10], this scheme has been successfully applied in various real world applications: in stereovision [6], in photogrammetry [12,[START_REF] Lutton | Parisian camera placement for vision metrology[END_REF], in medical imaging [START_REF] Vidal | New genetic operators in the fly algorithm: application to medical PET image reconstruction[END_REF], for Bayesian Network Structure learning [START_REF] Barrière | Bayesian network structure learning using cooperative coevolution[END_REF], in data retrieval [START_REF] Landrin-Schweitzer | Introducing lateral thinking in search engines[END_REF].

Parisian Evolution (PE) is based on a two-level representation of the optimisation problem, meaning that an individual in a Parisian population represents only a part of the solution. An aggregation of multiple individuals must be built to complete a meaningful solution to the problem. This way, the co-evolution of the whole population (or of a major part of it) is favoured over the emergence of a single best individual, as in classical evolutionary schemes.

This scheme distributes the workload of solution evaluations at two levels. Light computations (e.g. existence conditions, partial or approximate fitness) can be done at the individual's level (local fitness), while the complete calculation (i.e. global fitness) is performed at the population level. The global fitness is then distributed as a bonus to individuals who participate the global solution. A Parisian scheme has all the features of a classical EA (see figure 2) with the following additional components:

-A grouping stage at each generation, that selects individuals that are allowed to participate to the global solution. -A redistribution step that rewards the individuals who participate to the global solution : their bonus is proportional to the global fitness. -A sharing scheme, that avoids degenerate solutions where all individuals are identical.

Efficient implementations of the Parisian scheme are often based on partial redundancies between local and global fitness, as well as clever exploitation of computational shortcuts. The motivation is to make a more efficient use of the evolution of the population, and reduce the computational cost. Successful applications of such a scheme usually rely on a lower cost evaluation of the partial solutions (i.e. the individuals of the population), while computing the full evaluation only once at each generation or at specified intervals.

Implementation of the lamps problem

For the lamps problem, the PE has been implemented as follows. An individual represents a lamp: its genome is its position, a pair of real values (x, y), plus a third element, e, that can assume values 0 or 1 (on/off switch). Lamps with e = 1 are "on" (expressed) and contribute to the global solution, while lamps with e = 0 do not. Global fitness is computed as described in subsection 2.2. In generation 0 the global solution is computed simply considering the individuals with e = 1 among the µ initial ones. Then, at each step, λ individuals are generated. For each new individual with e = 1, its potential contribution to the global solution is computed. Before evaluation, a random choice (p = 0.5) is performed: new individuals are either considered in addition to or in replacement of the existing ones.

If individuals are considered for addition, the contribution to the global solution of each one is computed. Otherwise, the less performing among the old individuals is removed, and only then the contribution to the global solution of each new individual is evaluated. If the addition or replacement of the new individuals leads to an improvement over the previous global fitness, the new individual selected is rewarded with a high local fitness value (local f itness = 2), together with all the old individuals still contributing to the global solution. New expressed individuals (e = 1) that are not selected for the global solution are assigned a low fitness value (local f itness = 0). Non-expressed individuals (e = 0) have an intermediate fitness value (local f itness = 1).

Sharing follows the simple formula

f itness sharing(I k ) = local f itness(I k ) ∑ individuals i=0 sharing(I k , I i =k ) with sharing(I 1 , I 2 ) = 1 -d(I 1 ,I 2 ) 2•lamp radius d(I 1 , I 2 ) < 2 • lamp radius 0 d(I 1 , I 2 ) ≥ 2 • lamp radius
Lamps that have a relatively low number of neighbours will be preferred for selection over lamps with a bigger number of neighbours. In this implementation, sharing is computed only for expressed lamps (e = 1) and used only when selecting the less performing individual to be removed from the population.

Group Evolution

Group Evolution (GE) is a novel generational cooperative coevolution concept presented in [START_REF] Sanchez | Group evolution: Emerging synergy through a coordinated effort[END_REF]. The approach uses a population of partial solutions, and exploits nonfixed sets of individuals called groups. GE acts on individuals and groups, managing both in parallel. During the evolution, individuals are optimised as in a common EA, but concurrently groups are also evolved. The main peculiarity of GE is the absence of a priori information about the grouping of individuals. At the beginning of the evolutionary process, an initial population of individuals is randomly created on the basis of a high-level description of a solution for the given problem. Groups at this stage are randomly determined, so that each individual can be included in any number of different groups, but all individuals are part of at least one group.

The number of groups µ groups , the minimum and maximum size of the groups are set by the user before the evolution starts. The number of individuals in the population is a direct consequence of the specified values for groups.

Generation of new individuals and groups

GE exploits a generational approach: at each evolutionary step, a number of genetic operators is applied to the population. Genetic operators can act on both individu-als and groups, and produce a corresponding offspring, in form of individuals and groups.

The offspring creation phase comprehends two different actions at each generation step (see Figure 3):

1. Application of group genetic operators; 2. Application of individual genetic operators.

Each time a genetic operator is applied to the population, parents are chosen and offspring is generated. The children are added to the population, while the original parents are unmodified. Offspring is then evaluated, while it is not compulsory to reconsider the fitness value of the parents again. It is important to notice that the number of children produced at each evolutionary step is not fixed: each genetic operator can have any number of parents as input and produce in output any number of new individuals and groups. The number and type of genetic operators applied at each step can be set by the user.

Group genetic operators

Group Genetic Operators (GGOs) work on the set of groups. Each operator needs a certain number of groups as parents and produces a certain number of groups as offspring that will be added to the population. GGOs implemented in our approach are: Parent groups are chosen via tournament selection.

Individual genetic operators

Individual Genetic Operators (IGOs) operate on the population of individuals, very much like they are exploited in usual GA. The novelty of GE is that for each individual produced as offspring, new groups are added to the group population. For each group the parent individual was part of, a copy is created, with the offspring taking the place of the parent. This approach, however, could lead to an exponential increase in the number of groups, as the best individuals are selected by both GGOs and IGOs. To keep the number of groups under a strict control, we choose to create a copy only of the highest-fitness groups the individual was part of.

IGOs select individuals by a tournament selection in two parts: first, a group is picked out through a tournament selection with moderate selective pressure; then an individual in the group is chosen with low selective pressure. The actual group and the highest-fitness groups the individual is part of are cloned once for each child individual created: in each clone group the parent individual is replaced with a child. An example is given in Figure 3 (right): an IGO, selects individual C as a parent. The chosen individual is part of only one group, Group 1. The IGO produces two children individuals: since the parent was part of a group, a new group is created for each new individual generated. The new groups (Group 1' and Group 1") are identical to Group 1, except that individual C is replaced with one of its children, C' in Group 1' and C" in Group 1" respectively.

The aim of this process is to select individuals from well-performing groups to create new groups with a slightly changed individual, in order to explore the a near area in the solution space.

Evaluation

During the evaluation phase, a fitness value is associated to each group: the fitness value is a number that measures the goodness of the candidate solutions with respect to the given problem. When a group is evaluated, a fitness value is also assigned to all the individuals composing it. Those values reflect the goodness of the solution represented by the single individual and have the purpose to help discriminate during tournament selection for both IGOs and GGOs.

An important strength of the approach resides in the evaluation step: if there is already a fitness value for an individual that is part of a new group, it is possible to take it into account instead of re-evaluating all the individuals in the group. This feature can be exceptionally practical when facing a problem where the evaluation of a single individual can last several minutes and the fitness of a group can be computed without examining simultaneously the performance of the individuals composing it. In that case, the time-wise cost of both IGOs and GGOs becomes very small.

Slaughtering

After each generation step, the group population is resized. The groups are ordered fitness-wise and the worst one is deleted until the desired population size is reached. Every individual keeps track of all the groups it belongs to in a set of references. Each time a group ceases to exist, all its individuals remove it from their set of references. At the end of the group slaughtering step, each individual that has an empty set of references, and is therefore not included in any group, is deleted as well.

Implementation of the lamps problem

For the lamps problem, GE has been implemented as follows. One individual represents a lamp: its genome is its position, a pair of real values (x, y). The fitness of a single individual, which must be independent from all groups it is part of, is simply the area of the room it enlightens. The group fitness is computed as described in subsection 2.2.

Allopatric Group Evolution

The third proposed cooperative coevolution algorithm stems from the Group Evolution presented in the previous Section. While the flow of the algorithm is the same, however, two major improvements distinguish the Allopatric Group Evolution from the previously described methodology: allopatric group slaughtering and heuristic group genetic operators.

Allopatric group slaughtering

Allopatric speciation (from the ancient Greek allos, other, and patra, fatherland) is a speciation that occurs when biological populations of the same species become isolated, usually due to geographical changes, such as major changes in the landscape.

Taking inspiration from this natural phenomenon, the allopatric group slaughtering temporarily isolates from the main population all the offspring of a group. Subsequently, the offspring compete between themselves, and only the best resulting group is added back into the main population. A summary of the technique is presented in Figure 4.

Fig. 4 Allopatric slaughtering of groups. Group G and group H are chosen for reproduction in the same iteration. The operator applied to group G creates three children groups, with the allopatric tag γ, while the operator applied to group H creates five, with tag η. Among all the offspring that share the same allopatric tag, only the best group is added to the population: in the example, the fitness value of offspring H 3 might be higher than the value of G 2 ; nevertheless, G 2 is the best group among the offspring of G. This mechanism is aimed at improving diversity, trying to avoid the invasion of the main group population by the offspring of a particularly promising group, an event that could drive the evolution deep into a local optima.

Heuristic group operators

The second important difference between AGE and GE, is the presence of heuristic group operators. The aim of the operators is to exploit expert knowledge of the problem that cannot be incorporated inside the group or individual fitness function. In the current implementation, two heuristic operators substitute removal-mutation and add-mutation presented in Subsection 4.1.1. When an individual is chosen to be removed from or added to a group, instead of a simple random selection, an external heuristic selector chooses the best candidate, according to a metric specified by the user.

Heuristic operators might prove beneficial to the evolution, especially a run of the selector is not as computationally expensive as the evaluation of a group.

Implementation of the lamp problem

The setup is the same as in GE, with the only necessary addition of a heuristic to add or remove individuals from a group. For the lamp problem, we exploited the distance between individuals as an intuitive measurement of possible overlap. In particular, candidate individuals to be added to a group are evaluated on their distance from the nearest component of a group; while candidate individuals to be removed from a group are evaluate on the sum of the distances from the other components of the group.

Experimental setup

Before starting the experiments on the cooperative coevolution algorithms, a series of 10 runs for each problem size of a classical evolutionary algorithm is performed, to better understand the characteristics of the problem and to set parameters leading to a fair comparison. The genome of a single individual is a set of lamps, modeled as an array of N pairs of real values ((x 1 , y 1 ), (x 2 , y 2 ), ..., (x N , y N )), where each (x i , y i ) describes the position of individual i in the room. The algorithm uses a classical (µ + λ ) evolutionary paradigm, with µ = 20 and λ = 10, probability of crossover 0.2 and probability of mutation 0.8. Each run lasts 100 generations.

By examining these first experimental results, it is possible to reach the following conclusions: good solutions for the problem use a number of lamps in the range (problem size, 3• problem size); and, as expected, as the ratio grows, the fitness value of the best individual at the end of the evolution tends to be lower.

In order to perform a comparison with PE, GE and AGE as fair as possible, the stop condition for each algorithm will be set as the average number of single lamp evaluations performed by the classical evolutionary algorithm for each problem size. In this way, even if the algorithms involved have significantly different structures, the computational effort is commensurable. The number of evaluation ranges is 3, 500 for problem size = 3; 5, 000 for problem size = 5; 11, 000 for problem size = 10; 22, 000 for problem size = 20; and 120, 000 for problem size = 100.

PE setup

Due to the observation of the CE runs, µ = 3 • problem size, while λ = µ/2. The probability of mutation is 0.8 and the probability of crossover is 0.2.

GE and AGE setup

The number of groups in the population is fixed, µ groups = 20, as is the number of genetic operators selected at each step λ = 10. The number of in each group is set to vary in the range (problem size, 3 • problem size). The probability of mutation is 0.8, while the probability of crossover is 0.2, for both individuals and groups.

Implementation in µGP

The two CCEAs used in the experience have been implemented using µGP [START_REF] Sanchez | Evolutionary Optimization: the µGP toolkit[END_REF], an evolutionary toolkit developed by CAD group of Politecnico di Torino. Exploiting µGP's flexible structure, it is possible to replicate the behavior of very different EAs.

In particular, to implement PE, it is sufficient to operate on the fitness evaluator, setting the environment to evaluate the whole population and the offspring at each step. Obtaining GE behavior is slightly more complex, and requires the addition of new classes to manage groups. CE is simply µGP standard operation mode.

The individual-level operators chosen for the experience are singleParameter-AlterationMutation and onePointCrossover. The mutation operator acts on one or both coordinates of a single individual, modifying them according to a gaussian distribution and producing a single child. The crossover operator, on the other hand, starting from two individuals A = (x a , y a ) and B = (x b , y b ), creates two children individuals AB = (x a , y b ) and BA = (x b , y a ). For further information, see [START_REF] Sanchez | Evolutionary Optimization: the µGP toolkit[END_REF].

Results and Analysis

In a series of experiments, 100 runs of each evolutionary approach are executed, for a set of meaningful values of problem size. To exploit a further measurement of comparison, the first occurrence of an acceptable solution also appears in the results: here an acceptable solution is defined as a global solution with at least 80% of the final fitness value obtained by the CE. Table 1 summarises the results for significant values of problem size. For each evolutionary algorithm are reported the results reached at the end of the evolution: average fitness value, average enlightenment percentage of the room, average number of lamps, and average number of lamps evaluated before finding an acceptable solution (along with the standard deviation for each value).

Results distributions are compared with a standard Student t-test, with no assumptions on the homogeneity of the standard deviations. Entries in bold in Table 1 are significantly better (p < 0.05) than others in the same column, for the same problem size. Table 1 Average results for 100 runs, for each evolutionary approach. For problem size = 100, the distribution of AGE presents such a vast standard deviation that it is not distinguishable from the other three approaches (p > 0.05). Taking into account the remaining three distributions, GE is the best (p < 0.05). *Due to the times involved, data for problem size 100 is computed on 10 runs.

For each problem size, a box plot is provided in figure 5. It is noticeable how the performance of each evolutionary algorithm is very close for small values of problem size, while PE, GE and AGE gain the upper hand when the complexity increases.

In particular, PE obtains the best performance from problem size = 10 onwards. The extra information inserted allows the approach to obtain high enlightenment percentages even when the complexity of the task increases, as shown in Figure 6.

On the other hand, GE obtains enlightenment percentages close to CE, but on the average it uses a lower number of lamps, that leads to a lower overlap, as it is noticeable in Figure 8 and7.

When dealing with the number of lamp evaluations needed before reaching what is defined an acceptable solution, PE is again in the lead, see Figure 9.

In Figure 10, a profile of the best run for problem size = 100 for each algorithm is reported. PE enjoys a rapid growth in the first stages of the evolution, thanks to the extra information it can make use of, while GE proves more efficient than CE in the last part of the evolution, where exploitation becomes more prevalent. AGE shows several steep improvements, in correspondence of a particularly successful activation of the heuristic group operators.

As it is noticeable in Figure 11 (left), while the number of lamps evaluated before reaching an acceptable solution grows more than linearly for CE and GE, AGE shows a less steep growth and PE outperforms all the other algorithms. On the other hand, GE presents the lowest overlap for all values of problem size, see Figure 11 (right).

Conclusion and future work

The lamps benchmark has the major advantage to provide a set of toy problems that are simple, and for which the complexity can be characterised with a single real value (the surface ratio between room and lamp sizes). This formulation is very convenient to get some insight on the behaviour of algorithms with respect to the size of the problem.

The intuition that guided the development of Parisian Evolution, Group Evolution and Allopatric Group Evolution has been confronted to experimental analysis, to yield the following conclusions: Parisian Evolution is the most efficient approach in terms of computational expense, and scalability; Group Evolution yields better and more precise results, in a computational time that is similar to Classical Evolution; Allopatric Group Evolution shows a behavior that is intermediate between the two, obtaining some advantage over GE for higher complexities of the problem, but failing to meet Parisian Evolution's performance. In general, AGE solutions also present a considerable standard deviation, probably because the combination of heuristics and evolutionary operators drives the evolution in very different niches of the search space, depending on the single run. These differences can be explained by the nature of a priori information that has been injected into the algorithms. Parisian Evolution relies on a deterministic algorithm for selecting the group of lamps that are used as the current global solution at each generation, while Group Evolution does not make any assumption on it and let evolution decide which lamps can be grouped to build various solutions. Allopatric Group Evolution is a first attempt to make use of expert knowledge while avoiding a strong algorithmic choice, by adding information at the level of its heuristic genetic operators: the chosen metrics, however, show a variable performance, dependent on the size of the problem.

In some sense Parisian Evolution is making a strong algorithmic choice for the grouping stage, that acts as a constraint on the evolution of the population of lamps. It has the major advantage to reduce the complexity of the problem by providing solutions from the evolution of simpler structures (lamps instead of groups of lamps for both Allopatric and standard Group Evolution, or for Classical Evolution). It may be considered as a "quick and dirty" approach. Future work on this topic will investigate other possible compromises between heuristics and evolution: a promising option is an hybridisations between Parisian and Group Evolution, i.e. running a population of elements in the Parisian mode to rapidly get a good rough solution, and using the Group scheme to refine it. A more realistic modeling of the lamp's light could also be used, taking into account the gradual fading from the source; this approach would shift the problem from enlightening the room to ensure that each point of it receives at least a certain amount of light.

Acknowledgments

Aknowledgements for the funding received from the European Community's Seventh Framework Programme (FP7/2009-2013) under grant agreement DREAM n. 222654-2.

Fig. 2 A

 2 Fig. 2 A Parisian EA: a monopopulation cooperative-coevolution. Partial evaluation (local fitness) is applied to each individual, while global evaluation is performed once a generation.

Fig. 3 (

 3 Fig. 3 (Left) Individuals and Groups in a sample population of 8 individuals. While individual A is part of only one group, Individual B is part of 3 different groups. The effect of a Individual Genetic Operator, applied to individual C. Since individual C is part of Group 1, two groups are created and added to the population. (Right) Schema of Group Evolution algorithm. Groups are sets of individuals. At each step, new groups and individuals are produced. The slaughtering is performed at the level of groups, and in a second step individuals that are not included in any group are also removed.

problem size = 100 Fig. 5

 1005 Fig. 5 Box plots of fitness values for each problem size.

problem size = 100 Fig. 6

 1006 Fig. 6 Box plots of enlightenment percentage for each problem size.

problem size = 100 Fig. 7

 1007 Fig. 7 Box plots of number of lamps used for each problem size.

problem size = 100 Fig. 8 problem size = 100 Fig. 9 Fig. 10 Fig. 11 (

 100810091011 Fig. 8 Box plots of overlap percentage for each problem size.

  7. Bucci A, Pollacj JB (2005) On identifying global optima in cooperative coevolution. In: GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary, Washington DC, USA 8. Chen W, Weise T, Yang Z, Tang K (2010) Large-scale global optimization using cooperative coevolution with variable interaction learning. In: PPSN 2010, 11th International Conference on Parallel Problem Solving From Nature, September 11-15, Krakow, Poland, springer Verlag, Series: Lecture Notes in Computer Science, Vol. 6238 and 6239 9. Collet P, Lutton E, Raynal F, Schoenauer M (1999) Individual gp: an alternative viewpoint for the resolution of complex problems. In: GECCO99, Genetic and Evolutionary Computation Conference, July 13 -17, 1999, Orlando, Florida, USA. 10. Collet P, Lutton E, Raynal F, Schoenauer M (2000) Polar ifs + parisian genetic programming = efficient ifs inverse problem solving. Genetic Programming and Evolvable Machines Journal 1(4):339-361, october 11. De Jong ED, Stanley KO, Wiegand RP (2007) Introductory tutorial on coevolution. In: GECCO '07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, London, United Kingdom 12. Dunn E, Olague G, Lutton E (2005) Automated photogrammetric network design using the parisian approach. In: EvoIASP 2005, Lausanne, nominated for the best paper Award 13. Holland JH, Reitman JS (1978) Cognitive systems based on adaptive algorithms. In: Waterman DA, Hayes-Roth F (eds) Pattern directed inference systems, Academic Press, pp 313-329 14. Husbands P, Mill F (1991) Simulated co-evolution as the mechanism for emergent planning and scheduling. In: ICGA, Proceedings of the 4th International Conference on Genetic Algorithms, San Diego, CA, USA, pp 264-270 15. Husbands P, Mill F (1991) Simulated co-evolution as the mechanism for emergent planning and scheduling. In: Belew R, Booker L (eds) Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann 16. Kauffman SA, Johnsen S (1991) Coevolution to the edge of chaos: Coupled fitness landscapes, poised states, and coevolutionary avalanches. Journal of Theoretical Biology 149(4):467 -505

  generates offspring by selecting a group and one or more individuals inside it. Individuals are removed from the parent group. 4. replacement-mutation: generates offspring by selecting a group and one or more individuals inside it. Individuals are removed from the parent group, and replaced by other individuals selected from the population.

1. crossover: generates offspring by selecting two individuals, one from parent group A and one from parent group B. Those individuals are switched, creating two new groups; 2. add-mutation: generates offspring by selecting one or more individuals from the population and a group. Chosen individuals are added (if possible) to the parent group, creating a single new group; 3. removal-mutation:


Keywords: Knowledge Discovery, Grid-computing, Computational Intelligence, Scheduling

Scheduling in computational grids addresses the allocation of computing jobs to globally distributed compute resources. In a frequently changing resource environment, scheduling decisions have to be made rapidly. Depending on both the job properties and the current state of the resources those decisions

are different. Thus, the performance of grid-scheduling systems highly depends on their adaptivity and flexibility in changing environments. Under these conditions, methods from knowledge discovery yielded significant success to augment and substitute conventional grid-scheduling techniques. This paper presents a survey on approaches to extract, represent, and utilize knowledge to improve the grid-scheduling performance. It aims to give researchers insight into techniques used for knowledge-supported scheduling in large-scale distributed computing environments.

The ever-growing need for universally available computing and storage capacity is more and more satisfied by new architectures for networked interaction between users and providers of computing resources. The basic entity in this context is a compute site which constitutes an administrative domain that controls the access to one or more parallel computers or cluster installations. A typical example is an academic data center but also a cloud-computing provider. Today, research and industry realize grid-computing infrastructures for the coordinated utilization of globally distributed computing resources. Each site has its own local user community but jobs are migrated among resource providers. In such environments, submitted computing jobs are no longer bound locally. Each site has its own local user community but jobs are migrated between resource providers. The cooperation among such resource providers requires advanced scheduling concepts. For this purpose, different architectures with special demands on information exchange between the resource providers have been developed. These architectures differ in the way in which each provider participates in grid-scheduling decisions. Grids are dynamic environments with frequently changing heterogeneous resources. Their efficient operation requires scheduling decisions that are both situation-dependent and adaptive. Considering the status of a local system is crucial whenever a decision has to made either to accept foreign workload or not. Grid-scheduling systems require computational efficiency to cope with the high throughput that involves the execution of thousands of jobs per minute to be allocated among up to tens of thousands of processors. Thus, highly complex decision-making procedures are only applicable if they are real-time capable. Although often neglected in research, grid-scheduling is inherently an online problem as jobs are submitted over time and neither their precise runtimes nor future job submission times are known in advance. In the optimal case, user runtime estimations are available in advance but in practice these estimates are usually unreliable. As a consequence, grid-scheduling decisions are made on the basis of partial and uncertain information and the discovery and integration of the sparse knowledge available is essential. It is obvious that all these properties make grid-scheduling a very complex problem and thus hardly manageable. To address this problem, many gridscheduling solutions employ complex heuristics and evaluate their performance with respect to common global objectives such as the average response time over all jobs or the utilization of the machines. These heuristics often achieve good results but they rarely consider past decisions or previous states of the scheduling process. To overcome this disadvantage and to increase the robustness and performance of grid-scheduling algorithms, more recent approaches resort to knowledge discovery techniques. Knowledge discovery is the iterative process of selecting and pre-processing data, examining data, and interpreting extracted patterns. The goal is the extraction of knowledge to support an efficient decision-making. In the context of grid-scheduling, the knowledge discovery process results in rules defining the behavior of grid-schedulers. Such decisions depend on job properties (workload), resource configuration, previous computational demands, or other features. Metrics quantify the state of resources or the characteristics of jobs. Especially, methods summarized as computational intelligence are very powerful in this application area. This survey presents the state-of-the-art in knowledge discovery for grid-scheduling and categorizes the different approaches with respect to their type of models and learning schemes. As both knowledge discovery and grid-computing in general are comprehensive topics, the paper focuses on those aspects that are most relevant to their combination. The most relevant and influential papers on knowledge discovery in the context of grid-scheduling are selected and introduced on the basis of an extensive review of publications over the past five years. They are first analyzed with respect to similarities and differences and discussed afterwards. It appears reasonable to divide this discussion into grid-scheduling models, knowledge representation, knowledge acquisition, and knowledge application. This paper is organized as follows: First, a brief introduction to knowledge discovery is given and the main concepts of computational intelligence are described. In the core of this paper, the most prominent approaches to gridscheduling with knowledge discovery are discussed. Four key aspects are considered: 1) the grid-scheduling model, 2) the knowledge representation schemes, 3) the knowledge acquisition schemes, and 4) the methods to apply extracted knowledge to improve future scheduling decisions. In the conclusion, important future directions of this research field are pointed out.

Knowledge Discovery with Computational Intelligence

Before the application area of grid-scheduling is discussed, some basic principles of computational intelligence are introduced. Computational intelligence in general comprises evolutionary algorithms, neural networks, and fuzzy systems. This introduction restricts itself to evolutionary algorithms and evolutionary fuzzy systems, since they assume a major role for knowledge discovery in grid-computing.

Suggested reading

R. C. Eberhart and Y. Shi, Computational Intelligence: Concepts to Implementations 1 : They describe the integration of various natural and engineering disciplines to establish computational intelligence. The book further rests on a foundation of evolutionary computation but has also an emphasis on practical applications and computational tools. H.-P. Schwefel, Evolution and Optimum Seeking 2 : A fundamental book about evolutionary algorithms and evolution strategies. O. Cordón et al., Evolutionary Tuning and Learning of Fuzzy Knowledge Bases 3 : The book summarizes and analyzes the novel field of evolutionary fuzzy systems, paying special attention to evolutionary algorithms that adapt and learn the knowledge base of a fuzzy system. It also includes a good general introduction to fuzzy systems.

Evolutionary Algorithms

Evolutionary algorithms are general purpose optimization algorithms that mimic the natural process of the Darwinian evolution and are most successfully applied to nonlinear, global parameter optimization in high dimensional complex optimization problems. [START_REF] Engelbrecht | Computational Intelligence -An Introduction[END_REF] They operate on a population of individuals, which represent solutions to the optimization problem. Typical representations encode the problem as a real-valued vector or as binary string. Genetic operators such as mutation (a random change in genome) and recombination (combining two or more parent individuals' genomes) are applied to generate offspring that inherit traits from their individuals. In global selection the individuals compete against each other to determine the new parents of the next generation. The evolutionary loop is executed either for a fixed number of generations or until the best solution surpasses a threshold on the objective function.

Fuzzy Systems

Since their conceptualization in the early 1960ies, fuzzy systems have been widely and successfully applied to modeling, pattern recognition, data analysis, decision making and control system design. Fuzzy-systems are capable of decision making under partial or incomplete knowledge. The knowledge base is composed of a set of linguistic rules that relate antecedents to consequences. The fuzzy representation offers a number of advantages: The interpolative nature of fuzzy systems allows the partial and concurrent activations of rules and gradual transitions between them. The overall decision is easily synthesized by a set of IF-THEN rules expressed in linguistic terms that reflect the expert knowledge.

Evolutionary Fuzzy Systems

Conventional fuzzy systems are designed based on expert knowledge but lack the ability to learn rules or membership function from data. Neuro fuzzy system combine the rule based representation with the supervised learning schemes of neural networks. This enables the refinement or generation of rules from data for situations in which the experts decisions are imprecise or missing. Evolutionary fuzzy systems are suitable to tune or even learn a fuzzy system in case there are no direct training examples for supervised learning. The evolutionary algorithm optimizes rules or membership functions with respect to a global performance indicator, such as the closed loop behavior in case of a fuzzy controller, or the makespan or flow time of a workload trace in case of a fuzzy grid-scheduler. Special variants of evolutionary algorithms offer the advantage of multi-objective optimization which allows the simultaneous consideration of multiple potentially conflicting objectives. Since Smarr and Catlett 7 promoted the term meta-computing in 1992, research efforts focus on the design of architectures for the shared use of globally distributed resources. Today, the term grid-computing coined by Foster and Kesselman 5 is widely used. But even this term has been interpreted differently and went through a series of metamorphoses described by Altmann et al. [START_REF] Altmann | Taxonomy of grid business models[END_REF] . Any interpretation of the term is closely related to the specific requirements of alternative grid-computing infrastructures. Each community has its specific requirements on a grid-computing infrastructure. Thus, the grid-model varies significantly among different research works. Among the different architectures of a grid (data-grid, utility-grid, etc.) a computational grid is most widely used. In contrast to usual parallel systems, see Bertsekas and Tsitsiklis [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF] , it represents a large-scale distributed system based on a merger of regional, national, and global (heterogeneous) computing systems including data centers and other resources. The participants are connected by a high performance communication network. It thus permits the aggregation of autonomous resources in a dynamic and changing environment. Berman et al. [START_REF] Berman | Grid Computing: Making The Global Infrastructure a Reality[END_REF] give a description of all implemented architectures in form of a taxonomy. Beyond computational grids, which are in focus of most knowledge discovery approaches for grid-scheduling, there exist other models with a strong focus on data-, energy-, or collaboration management. [START_REF] Xhafa | Meta-heuristics for grid scheduling problems[END_REF] The models presented in this paper are motivated from real-world installations: The diversity of today grids is reflected by the manifold of the corresponding grid-models.

Grid-scheduling Models

Meta-scheduling Models

The most common grid-scheduling model is the meta-scheduling model where multiple distributed local schedulers are aggregated and supervised by a high-level scheduler instance, the meta-scheduler. Usually, the meta-scheduler also serves as a central recipient of user jobs and is responsible for their delegation to local schedulers. The metascheduler has complete access to the overall grid-state and allocates jobs to the location that currently provides the optimal conditions for their execution. Some models even abandon the concept of local schedulers and the meta-scheduler directly accesses the resources at the underlying computing sites. This global system view makes scheduling relatively easy as all participants are known and controllable. Due to the single submission and scheduling component, the system runs high risks of a full breakdown as it includes a single point of failure. Thus, this model is hardly scalable and unreliable.

A typical example of such an environment is described by Xhafa et al. [START_REF] Xhafa | Genetic algorithm based schedulers for grid computing systems[END_REF] . Their model assume a central grid-scheduler instance that has exclusive access to all underlying resources. These resources are assumed to be heterogeneous in speeds while their respective performance is summarized in terms of million instructions per second (MIPS). In their grid-environment, only sequential jobs are used which are not allowed to be interrupted during execution and they consider an offline scheduling problem where all jobs are known in advance. In another meta-scheduling model, the central scheduling component applies a runtimeprediction algorithm. [START_REF] Li | Mining performance data for metascheduling decision support in the grid[END_REF] This model requires an open information model such that the meta-scheduler has access to information on resource states, for example, the number of queued jobs or number of running jobs. However, the authors address an online scheduling problem which makes the knowledge discovery even harder as properties of further job submissions are unknown. Similarly, Prado et al. [START_REF] Prado | Genetic fuzzy rule-based meta-scheduler for grid computing[END_REF] follow a meta-scheduling approach and represent knowledge by a fuzzy system on the meta-layer. They assume homogeneous clusters in speed and other machine attributes and do evaluations with up to 3,000 parallel and sequential tasks. They also consider the online scheduling problem and apply their fuzzy approach even for previously unknown job submissions. Zhou et al. [START_REF] Zhou | A dynamic resource broker and fuzzy logic based scheduling algorithm in grid environment[END_REF] strictly stick to the grid-model supported by the common Globus Toolkit 4 (GT4) middleware [START_REF] Foster | Globus toolkit version 4: Software for service-oriented systems[END_REF] and develop a meta-scheduler model on this setup. They assume heterogeneous resources with local scheduler instances and choose an implementation on the basis of the additional services provided by GT4. The meta-scheduler is realized as a central resource broker and serves both as central submission component and information manager. The scheduler module steers the assignment of jobs to the different GT4 middleware installations. In another work of Yu et al. [START_REF] Yu | A fuzzy neural network based scheduling algorithm for job assignment on computational grids[END_REF] the same model assumptions are made. Finally, Prado et al. [START_REF] Prado | Knowledge acquisition in fuzzy-rule-based systems with particle-swarm optimization[END_REF] use a meta-scheduling concept with multiple heterogeneous re-source domains considering multiple virtual organizations. The internal organization of distributed resources is further specialized and adapted to real-world requirements where research groups may collaborate in virtual organization to share both knowledge and resources. However, the scheduling still follows the meta-scheduling paradigm as this component has access to internal information like used nodes or missed deadlines. The whole system is evaluated by simulations with up to 2,000 jobs from a real workload trace considering the online scheduling problem. The related works of Prado et al. [START_REF] Prado | Genetic fuzzy rule-based scheduling system for grid computing in virtual organizations[END_REF] assume a similar model and optimize the behavior of a central scheduling component.

Decentralized Scheduling Models

The decentralized scheduling architecture [START_REF] Grimme | Decentralized grid scheduling with evolutionary fuzzy systems[END_REF] requires no central coordinator as the gridschedulers directly interact and negotiate job allocations with each other. The resource sites act as a submission interface for their local users or user communities. The local resource management layer is supplemented with a grid-scheduling layer that takes over the task coordination and establishes the communication with other sites. Submitted jobs are either passed directly to the underlying local scheduling system or are migrated to other sites. The communication between sites is established via direct communication, which means that schedulers directly negotiate and exchange jobs. [START_REF] Schwiegelshohn | Competitive co-evolutionary learning of fuzzy systems for job exchange in computational grids[END_REF] This includes mechanisms for finding other sites and algorithms for managing lists of available exchange partners. If the migration of a job to a certain site is not possible, the scheduler decides to contact an alternative partner site for the execution of its job. This type of parallel peer-to-peer job allocation is of major importance as it scales properly even for very large world-wide grid installations. It is further more reliable than any meta-scheduling approach. Furthermore, Fölling et al. [START_REF] Grimme | Robust load delegation in service grid environments[END_REF] assume a restrictive information policy as local system states are exclusively accessible at the local sites. In real-world installations it is observable that critical information are kept classified as they might give hints about the operation efficiency of systems. In summary, the advantage of a distributed scheduling architecture is a much higher fault tolerance. The failure of a grid-level component or an entire site never results in a complete system breakdown. At most the overall performance of the grid decreases. Additionally, this architecture achieves a significantly better scalability for the same reasons. Large-scale grid-computing is only realizable by decentralized structures while obeying local autonomy. The disadvantage of decentralized structures originates precisely in the lack of a global grid-system view that makes scheduling more complicated. The decision to either accept or reject a foreign workload request highly depends on the status of the local scheduler and its current workload.

Other Scheduling Models

For completeness, also alternative grid-scheduling models used in the context of knowledge discovery are mentioned. In the work of Zeng et al. [START_REF] Zeng | Dynamic grid resource scheduling model using learning agent[END_REF] an agent-based grid-model without any hierarchy, scheduling roles, or even layers is assumed. They address the online scheduling problem with specific job workflows of sequential tasks and homogeneous resources. They are more interested in applying alternative knowledge discovery mechanism instead of investigating specific grid-scheduling models. Other models [START_REF] Farzi | Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[END_REF][START_REF] Abraham | Scheduling job on computational grids using fuzzy particle swarm algorithm[END_REF] assume heterogeneous grid-resources which are specified by cycles per time unit. In this way, different machine speeds are expressed. They assume further independent jobs while the processing times are given as total required cycles. Sequential jobs are scheduled in an open grid-environment without any hierarchies or site specific schedulers. Properties of different grid-scheduling models are summarized in Table 1. There are several requirements for knowledge representation in the context of scheduling decisions: The representation is supposed to capture the current complex state of a scheduling system in a comprehensive manner but it should restrict the number of features to describe the state to limit the dimension of the search space in scheduler optimization. The description must be sufficient to specify scheduling decisions with respect to the underlying grid-scheduling model. Furthermore, the output decision must be computable in an efficient way as scheduling often requires many online decisions in a short amount of time. In addition, the knowledge representation should be extensible or even generalizable. It must be possible to derive scheduling decisions for foreign states from already known states. The first and most common kind of knowledge representation is the fuzzy rulebase, that is, a set of fuzzy rules. The rule premise defines the local region of the state space to which the rule applies. The consequent associates a scheduling decision with the states represented in the premise. To compute the overall output of the fuzzy rulebase, the membership degree of every rule (real value ∈ [0, 1]) is used as weight for each rule's output scheduling decision. Examples for this kind of representation [START_REF] Mamdani | Application of fuzzy algorithms for control of simple dynamic plant[END_REF] are provided in several publications by Prado et al. [START_REF] Prado | Genetic fuzzy rule-based meta-scheduler for grid computing[END_REF][START_REF] Prado | Knowledge acquisition in fuzzy-rule-based systems with particle-swarm optimization[END_REF][START_REF] Prado | Genetic fuzzy rule-based scheduling system for grid computing in virtual organizations[END_REF] . As they assume a meta-scheduling model with a scheduler that schedules incoming jobs on independent computing sites, the authors describe their states as tuple of seven site-specific values. Such features are, for example, the number of free processing elements or the total lateness of all executed jobs within a site. Every rule output represents a factor that influences the controller output. In the inference system, a rulebase calculates the output for every site separately. Afterwards the site with the highest output is chosen for allocation. Similar grid-scheduling approaches [START_REF] Zhou | A dynamic resource broker and fuzzy logic based scheduling algorithm in grid environment[END_REF][START_REF] Yu | A fuzzy neural network based scheduling algorithm for job assignment on computational grids[END_REF] use fuzzy rules which only consist of two state variables. In those cases, the system state is represented as the processor-and memory utilization.

Other fuzzy based grid-scheduling algorithms [START_REF] Grimme | Decentralized grid scheduling with evolutionary fuzzy systems[END_REF][START_REF] Schwiegelshohn | Competitive co-evolutionary learning of fuzzy systems for job exchange in computational grids[END_REF][START_REF] Grimme | Robust load delegation in service grid environments[END_REF] make use of a Takagi-Sugeno-Kang (TSK) [START_REF] Takagi | Fuzzy identification of systems and its applications to modeling and control[END_REF] controller. Instead of using site-specific metrics which cover a large number of system states, only two different state values are allowed. As their decentralized grid-model comprises autonomously negotiating sites, the first feature is the summed resource requests of all queued jobs at the site. It estimates the workload the site has to process in the near future. The second value expresses a single job's parallelism to indicate the work that is added when accepting the job for execution. The output of a rule is the decision whether a job should be processed locally or negotiated for remote execution.

In contrast to these approaches, Abraham et al. [START_REF] Abraham | Scheduling job on computational grids using fuzzy particle swarm algorithm[END_REF] describe a fuzzy representation with so-called particles using a direct mapping of jobs to specific resources. This is only possible since all resources and jobs are known from the beginning in an offline scheduling problem. They optimize the assignment of jobs to specific resources. In the defuzzyfication (that is, calculating the output decision assuming fuzzy input values) the resource that gets the highest output decision values is chosen. In contrast to regular fuzzy systems, they do not apply any superposition of rules. A similar approach [START_REF] Farzi | Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[END_REF][START_REF] Xhafa | Genetic algorithm based schedulers for grid computing systems[END_REF] omits the vague representation as fuzzy sets in favor of using direct mapping of jobs to resources. A vector of machine indexes is used where each vector component specifies the machine on which a certain job should be scheduled on. Although this representation is simple and thus easy to update during the knowledge discovery process, it lacks the possibility to optimize different permutations of jobs on a specific machine. This leads to restrictions in the search space of possible scheduling solutions.

There are two different knowledge representation schemes which are motivated by the associated learning method: In the first one of Zeng et al. [START_REF] Zeng | Dynamic grid resource scheduling model using learning agent[END_REF] , the scheduling decisions are optimized by learning a value function which is typically employed in reinforcement learning. According to the value function, independent job agents identify an optimal policy for choosing the most beneficial resource agent among the competing resource agents. In the second more exotic knowledge representation, Li et al. [START_REF] Li | Mining performance data for metascheduling decision support in the grid[END_REF] store tuples of job characteristics like the user group, user name, number of requested processors, and resulting run-or wait times within a database. The knowledge base is extended as new job execution data is collected thus providing more accurate estimates of future jobs' runtimes.

Overall, there are many representations with their respective advantages and disadvantages but all of them strongly depend on the underlying grid-model, that is, state description, variables, and calculation of scheduling decisions, see also Table 2. An offline scheduling model with a priori knowledge about all jobs and resources allows fuzzy mapping of concrete jobs to concrete resources. In contrast, online gridscheduling problems with changing resources, unforeseeable workload bursts, or restrictions in information policy need state descriptions that characterize all future resource states and job characteristics. Knowledge representation and its learning process are closely coupled. The different knowledge acquisition schemes are presented in the next section. The knowledge acquisition process is responsible for generating and updating the knowledge representation. The solution space is defined by the state variables of the representation. The knowledge acquisition process explores this space searching for representation instances that are optimal with respect to a global objective. The learning performance and the solution quality not only depend on the objective but also on the optimization algorithm for search space exploration. In some of the aforementioned publications, perceptions from the scheduling system are stored in a database. [START_REF] Li | Mining performance data for metascheduling decision support in the grid[END_REF] In contrast to other approaches, the knowledge discovery is in such cases mere knowledge collection instead of refining knowledge representations.

Refinements are commonly realized applying methods from evolutionary optimization. Fölling et al. [START_REF] Grimme | Decentralized grid scheduling with evolutionary fuzzy systems[END_REF][START_REF] Schwiegelshohn | Competitive co-evolutionary learning of fuzzy systems for job exchange in computational grids[END_REF][START_REF] Grimme | Robust load delegation in service grid environments[END_REF] use an evolutionary learning algorithm to learn the fuzzy rulebase.

In their evolutionary fuzzy system, the shape of the membership functions and rule outputs are encoded as parameters. These parameters are evaluated for each individual in a dedicated simulation of the scheduling system. The objective expresses the achieved scheduling results. The method of Xhafa et al. [START_REF] Xhafa | Genetic algorithm based schedulers for grid computing systems[END_REF] is similar to the previous because they also use an approach from evolutionary computation, namely a genetic algorithm. They employ specific operators for recombination and mutation targeted to their particular offline scheduling problem. The authors basically evaluate four different crossover operators. They further try different rules for the exchange of sequences between two parent individuals. In addition, their mutation operators either switch single jobs among machines (mutually exchanging two jobs between two machines) or rebalance jobs between the machines. In this example, the objective function is a weighted combination of the two conflicting objectives makespan and flow time, while makespan is treated as main objective.

The makespan is equivalent to the completion time of the last job in the schedule (assuming the schedule starts at time 0). The flow time is defined as the span between the release time and the completion time of a job. Interchangeably, the term response time is used in the literature. A particular criteria is the average weighted response time (AWRT), in which a job's response time is weighted with its resource consumption, see Schwiegelshohn [START_REF] Schwiegelshohn | A system-centric metric for the evaluation of online job schedules[END_REF] . The wait time is the span between the submission time and the start time of the job. Prado et al. [START_REF] Prado | Genetic fuzzy rule-based scheduling system for grid computing in virtual organizations[END_REF] use the so-called Pittsburgh approach [START_REF] Smith | A Learning System Based on Genetic Adaptive Algorithms[END_REF] to evolutionary fuzzy systems. Each individual represents a whole rulebase that is updated using crossover and mutation operators similar to the approach of Fölling et al. [START_REF] Grimme | Robust load delegation in service grid environments[END_REF] . In addition, they present a concept for evolving rules with a Michigan approach [START_REF] Bonarini | Evolutionary learning of fuzzy rules: Competition and cooperation[END_REF] where single rules are evaluated with regard of their negative or positive influence on the scheduling performance. Those different approaches are then combined [START_REF] Prado | Genetic fuzzy rule-based meta-scheduler for grid computing[END_REF] to form a hybrid solution of updating the weights, that is, the influences of single rules. They use the Michigan approach for updating single rules and the Pittsburgh approach to update whole rulebases. Contrary to the previous publications, Abraham et al. [START_REF] Abraham | Scheduling job on computational grids using fuzzy particle swarm algorithm[END_REF] and Prado et al. [START_REF] Prado | Knowledge acquisition in fuzzy-rule-based systems with particle-swarm optimization[END_REF] optimize knowledge representations using particle swarm optimization. In this kind of optimization technique, the aforementioned individuals are replaced by particles. During the learning process, particles are neither recombined nor mutated like individuals in evolutionary algorithms. Each particle represents knowledge independently while they move through the search space. The movement is determined by a velocity matrix that has entries for each state representation of a particle. This velocity is comparable to mutation step-sizes applied in evolutionary optimization. The great advantage of this approach is that this optimization method is not generation-based anymore. All particles are simulated independently without any need for synchronization. This allows an easy parallelization and hence more evaluations per time unit are possible. The approach of Farzi [START_REF] Farzi | Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[END_REF] is very similar to the previously described particle swarm concept. The approach employs fishes as swarm members that encode allocations of jobs to resources. The algorithm mimics the natural behavior of fishes in a swarm-oriented learning algorithm. Fishes are chasing for food that represents the objective in terms of a combination of makespan and flow time. The fishes swim towards regions of higher food concentrations that are detected by swarm neighbors. Simultaneously, they spread across the near search space to guarantee divergence among solutions.

In another solution [START_REF] Zeng | Dynamic grid resource scheduling model using learning agent[END_REF] , a temporal difference reinforcement learning approach is used to optimize the value function that predicts the estimated reward of choosing a specific action in a certain situation. Different from other works, the knowledge is updated during the evaluation process. Every single chosen scheduling decision is evaluated and rewards or penalties are assigned afterwards. Hence, each evaluation influences the optimal value function directly. Nevertheless, this learning approach is an offline approach as the same workload is used in each iteration. The relevance, advantages, and disadvantages of the presented approaches are listed in Table 3.

It is important to distinguish the online/offline properties in the two domains knowledge acquisition and grid-scheduling. In offline grid-scheduling problems, all job properties are known from the beginning while in online problems future job submissions are not known in advance. In practice, all grid-scheduling problems are online problems but many offline problems are studied for algorithm development. For knowledge acquisition, offline learned knowledge might be applied to online grid-scheduling problems but only an online learning (or adjustment) approach is able to flexibly react to changing environments. To the best of our knowledge, there is no such online knowledge acquisition approach for grid-scheduling available yet. This section discusses how the acquired knowledge is utilized for decision making in the grid-scheduling process. Research mainly focuses on two different subjects: On the one hand, knowledge is used to design or improve grid-scheduling algorithms directly related to well-defined performance criteria. On the other hand, the interesting problem of grid-scheduling is rather used as benchmark problem while improving learning strategies is the main goal, see Table 4.

Designing Grid-scheduling Strategies

For assessing the schedule quality, it becomes necessary to refer to specific objective functions. Common examples are simple functions such as makespan or the sum of completion times [START_REF] Brucker | Scheduling Algorithms[END_REF] . In addition, practical objective functions are often hard to formulate, because they are meant to express a complex problem view [START_REF] Franke | Greedy scheduling with custom-made objectives[END_REF] . Objectives might even change over time if knowledge about the maximum achievable solution quality becomes available. [START_REF] Ernemann | Scheduling algorithm development based on complex owner defined objectives[END_REF] However, to show the advantages of knowledge usage in gridscheduling, simple objectives are mainly used. Zeng et al. [START_REF] Zeng | Dynamic grid resource scheduling model using learning agent[END_REF] minimize the makespan during the knowledge acquisition phase and measure the performance of the applied learning algorithm considering the convergence speed and makespan. They evaluate the robustness of their derived scheduling strategy on unforeseen events like machine unavailability or breakdowns. Also Xhafa et al. [START_REF] Xhafa | Genetic algorithm based schedulers for grid computing systems[END_REF] aim to minimize the makespan or the sum of response times in their approach. The derived knowledge base is used to plan or reschedule job allocations periodically while the objective functions are always obeyed.

Other developments also take the specific job attributes into account: Li et al. [START_REF] Li | Mining performance data for metascheduling decision support in the grid[END_REF] use the estimates of response times and runtimes to make better decisions at the metascheduling level. The derived knowledge is then used to choose the most appropriate execution site in the grid. For a new job, its similarity to other jobs in the database is determined and the closest match is used to estimate the wait time or runtime of the new job. The accuracy of the algorithm is evaluated with real workload traces. The work of Fölling et al. [START_REF] Grimme | Decentralized grid scheduling with evolutionary fuzzy systems[END_REF] comprises both a scheduling objective related knowledge learning phase and a subsequent application phase. During the learning phase on real workload data, the scheduling objective (AWRT) is optimized and corresponding rules are extracted for the knowledge base. Dynamically, they derive rules to steer the workload distribution among grid-sites. After the learning phase, the rulebase is applied to new data from the workload traces to show that the derived knowledge is applicable for other workloads. In a later publication [START_REF] Grimme | Robust load delegation in service grid environments[END_REF] , the authors show the robustness in changing grid-environments. Setups with previously unknown partners are evaluated to show the robust interaction between the autonomous sites. [START_REF] Li | Mining performance data for metascheduling decision support in the grid[END_REF] prediction predicting RT and WT online real failure in local scheduling Fölling et al. [START_REF] Grimme | Robust load delegation in service grid environments[END_REF] AWRT job negotiation online real Prado et al. [START_REF] Prado | Knowledge acquisition in fuzzy-rule-based systems with particle-swarm optimization[END_REF] makespan meta-scheduling online real Prado et al. [START_REF] Prado | Genetic fuzzy rule-based meta-scheduler for grid computing[END_REF][START_REF] Prado | Genetic fuzzy rule-based scheduling system for grid computing in virtual organizations[END_REF] AWRT meta-scheduling online real Farzi [START_REF] Farzi | Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[END_REF] makespan/RT single domain offline synth. grid-scheduling Abraham et al. [START_REF] Abraham | Scheduling job on computational grids using fuzzy particle swarm algorithm[END_REF] makespan/RT single domain offline synth. grid-scheduling RT = total response time WT = wait time AWRT = average weighted response time Using Grid-scheduling as a Test Problem While all above described works have a scheduling related point of view, the following works turn to the learning technique itself, see Table 5. Prado et al. [START_REF] Prado | Genetic fuzzy rule-based meta-scheduler for grid computing[END_REF] also aim to minimize the AWRT of all jobs but they additionally investigate the performances achievable by two differently learned fuzzy systems. They compare the Michigan and Pittsburgh approach for evolutionary fuzzy rule learning and show that their hybrid approach yields superior learning result. For this investigation, they focus on a fast convergence of the learning approach instead of deriving very robust rulebases. In another publication [START_REF] Prado | Knowledge acquisition in fuzzy-rule-based systems with particle-swarm optimization[END_REF] , they focus on convergence speed and show by experiments that swarm-optimization outperforms genetic algorithms. In a follow-up investigation [START_REF] Prado | Genetic fuzzy rule-based scheduling system for grid computing in virtual organizations[END_REF] , the same authors vary the number of involved sites as well as the number of overall available resources. Similar to the previously discussed approach, Fölling et al. [START_REF] Schwiegelshohn | Competitive co-evolutionary learning of fuzzy systems for job exchange in computational grids[END_REF] also try to improve the learning technique itself. They define a problem specific adaptation of the learning by dividing the overall problem into multiple subproblems. They adapt a co-evolutionary algorithm for the learning of fuzzy rules and they show that it achieves nearly the same results while reducing the learning time significantly. In other approaches, Farzi [START_REF] Farzi | Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[END_REF] and Abraham et al. [START_REF] Abraham | Scheduling job on computational grids using fuzzy particle swarm algorithm[END_REF] learn knowledge in the grid-scheduling context using techniques from computational intelligence, like special genetic algorithms and simulated annealing, to optimize both makespan and response times. Table 5 Overview: aspects of learning technique improvements.

Aspect

Farzi [START_REF] Farzi | Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[END_REF] Fölling et al. [START_REF] Schwiegelshohn | Competitive co-evolutionary learning of fuzzy systems for job exchange in computational grids[END_REF] Prado et al.

Conclusion

The subject of scheduling in computational grids has been approached from the viewpoint of knowledge discovery. It has been shown how grid-scheduling benefits from utilization of domain knowledge acquired from historical data of the grid. The approaches differ in terms of the learning methodology, the representation of the acquired knowledge and the way in which the knowledge improves the scheduling decisions in dynamic environments. It became obvious that grid-scheduling comprises many areas: The diversity of computational grids reflects itself in the manifold of scheduling problems and approaches to their solution. Recent developments have been presented in a structured way while their specific contributions to the area of knowledge discovery and decision learning have been pointed out. The conceivable grid-models have been distinguished and analyzed. It became apparent that scheduling in the fully decentralized model is more challenging but therefore perfectly suitable for knowledge usage. State-of-the-art knowledge representation are described and the concepts for knowledge acquisition in recent grid-scheduling architectures are reviewed. Hybrid methods from computational intelligence successfully combine fuzzy representations with randomized, heuristic global search methods. Learning in frequently changing environments is difficult and gridscheduling constitutes an inherent online problem with a partial horizon. Integrating knowledge gathered from past observations into the decision making is a means to improve scheduler performance. Experience with knowledge based grid scheduling shows that it is possible to transform and extrapolate existing knowledge to novel environments and workload scenarios. Even in a challenging application domain like grid-scheduling good decisions are made. As knowledge discovery obviously supports future grid-scheduling developments, some further directions are conceivable. The first possible improvement is related to the grid-model itself which is still a bleeding-edge technology in which technological drifts occur frequently. Since the approaches and developments in the past decade already cover diverse architectures, it is likely that future distributed computing architecture such as cloud-computing utilize similar techniques for knowledge acquisition. Current state of the art knowledge discovery techniques are equipped with an internal or external learning technique. As such, learning normally occurs in episodes or generations which assume a static or quasi-static environment. In the application phase, the acquired knowledge is helpful to make decisions in a changing environment. It is strongly desired to overcome this drawback and to head for the online learning of knowledge. As all grid-systems are online systems, the learning should be capable to adapt to changes in an online manner. Imagine a scheduler that starts with an initial heuristic, which is then gradually improved by learning from the experience of past decisions. In such a setup, knowledge discovery becomes much more practically feasible and relevant as real-world gridinstallations are equipped with a zero-configuration scheduler. This scheduler automatically adapts to the changing environment while simultaneously obeying the user preferences and constraints. As the overall grid is far too complex to be entirely monitored and controlled by human experts, the techniques for knowledge discovery and utilization discussed in this paper may play an important role in the development of next generation computing infrastructures.

  and C. Kesselman, The Grid: Blueprint for a New Computing Infrastructure 5 : Standard textbook about the grid-computing concept. It covers the past, present, and future of network infrastructures. M. Pinedo, Scheduling: Theory, Algorithms, and Systems 6 : Well established textbook on basic scheduling problems and their solutions.

Table 1

 1 Overview: grid-scheduling models.

	Model	Scheduling	Fault	Scalability Real-world	Application
		Design	Tolerance		Existence	Areas
	Central	easy	low	low	frequent	prod. grids
	Decentral	hard	high	high	rare	acad./research
	Other	easy	specific	high	research	specific, P2P
	Knowledge Representation Schemes
	Suggested reading

D. Ruan (editor), Intelligent Hybrid Systems: Fuzzy Logic, Neural Networks, and Genetic Algorithms 26 : Collection of contributed chapters covering basic principles, methodologies, and applications of fuzzy systems, neural networks, and genetic algorithms. A. B. Markman, Knowledge Representation 27 : Overview of types of knowledge representation techniques and their use in cognitive models. It is useful for students of psychology as well as researchers in related disciplines, for example, computer science.

Table 2

 2 Overview: pros and cons of different knowledge representations.

	Representation	Size of	Output	Update	Req.	Robust-
		Input Space Calculation Procedure Memory	ness
	Fuzzy system	small	easy	hard	small	high
	Direct mapping	large	easy	easy	large	very low
	Value function	small	easy	hard	small	low
	Database	large	hard	easy	very large	high
	Knowledge Acquisition Schemes
	Suggested reading

O. Maimon and L. Rokach, Data Mining and Knowledge Discovery Handbook 30 : Provides comprehensive algorithmic descriptions of data-mining and knowledge discovery methods, including classic methods plus the extensions and novel methods developed recently. Especially part IV addressing "Soft Computing Methods" is strongly recommended.

Table 3

 3

	Overview: pros, cons, and occurrence of knowledge acquisition schemes
	for grid-scheduling.
	Method	Real-world	Method's	Learning	Online
		Existence	Complexity	Speed	Adaption
	EFS (Pittsburgh)	frequent	low	slow	hard
	EFS (Michigan)	rare	high	slow	hard
	Particle swarm	rare	medium	fast (parallel) possible
	RL	very rare	medium	slow	possible
	EFS = Evolutionary fuzzy system
	RL = Reinforcement learning
	Advantages of Knowledge Application
	Suggested reading

Table 4

 4 Overview: different grid-scheduling design concepts.

	Concept	Objective	Knowledge used	Sched. Used
			for	Probl. Traces
	Zeng et al. 23	makespan	workflow negotiation	online synth.
	Xhafa et al. 11	makespan/RT	single domain	offline synth.
			grid-scheduling
	Li et al.

J. Blazewicz et al., Handbook on Scheduling: From Theory to Applications 34 : Although not related to grid-scheduling, this well established textbook introduced schedul-

Acknowledgment

The authors would like to thank Frank Hoffmann for his valuable comments and corrections.