Cooperative co–evolutionary neural networks

1 Introduction

To date, the usefulness of artificial neural networks (ANNs) has been proven many times. They have been successfully applied to many various problems, e.g. approximation, identification, feature extraction, reinforcement learning. By virtue of their unquestionable advantages, particularly high effectiveness, they are currently of great interest of specialists from different domains. Doctors, military, navigators, geologists, economists, automation specialists and others make use of computer applications with embedded ANNs.

Most neural solutions used practically are monolithic, i.e. they cannot be decomposed into separated or loosely connected sub–ANNs, each with its own task. Such architecture of ANNs is sufficient when solving simple or medium difficulty problems, however, more complex tasks are often too difficult for monolithic ANNs. To improve performance of ANNs and to cope with more demanding problems, two solutions are in use, i.e. ensemble–based and modular [26, 27]. Without resort to a strict definition, in the former case, we deal with a set of unconnected networks, each of which is separately trained as one of the solutions to a common problem. To obtain output of the entire ensemble, different methods are applied, including linear [9] and nonlinear combination [25] of individual outputs, weighted average of outputs [17] or various voting schemes [3].

Like ensembles of networks also modular approaches consist of sub–ANNs or modules. This time, however, sub–ANNs do not need to be totally separated, loose interconnections between individual sub–ANNs are allowed in this case. Unlike networks in the ensemble–based approach, each module sub–ANN is responsible for performing a different task. In the ensembles of networks, each member of the ensemble can be, in principle, an independent solution to a problem (often a poor solution) whereas in the modular approach each sub–ANN solves only a piece of a whole problem and it cannot operate independently. To generate a complete response of an entire modular system, an integrating mechanism must be used, typically an integrating sub–ANN.

The MANNs which are the main area of interest of the current paper have features which make them a very attractive tool compared to the monolithic ones. The most important of them are as follows.

First, because of decomposition of a whole problem into sub–problems which are usually simpler to solve separately than the original problem, MANNs consisting of sub–ANNs assigned to different sub–problems are typically simpler in terms of construction than their monolithic counterparts [7].

Second, MANNs are often more robust to damages (damage can generally be interpreted as loss of the ability to perform a given sub–task, e.g. due to a change of external conditions) of some their elements than conventional ANNs. In the latter case, elimination of a single element of the architecture (neuron or connection) negatively influences functioning of an ANN, practically in its all work regimes. In contrast, damage of one module in a MANN rarely implies the total malfunctioning of the entire network. Usually, in such a case, the remaining modules work properly and, in consequence, the ANN can partially perform its tasks. Moreover, repair of the system does not require exchanging the whole ANN, in the case of MANNs, only replacement of a malfunctioned module is necessary [13].

Third, when decomposition of a problem into sub–problems is known in advance, modules assigned to individual sub–problems can be separately prepared for their tasks. Since, as mentioned above, sub–problems are usually simpler than the entire problem, the whole process of constructing the MANNs is faster and more effective than the analogical process when applying the monolithic ANNs. Greater ease in preparing the MANNs to a task may also be a consequence of adjusting architectures and training methods of individual modules to their sub–tasks. For example, some modules may be trained in an unsupervised manner whereas the others with the use of a reinforcement learning algorithm. In the case of the monolithic ANNs, such an approach is impossible.

Four, splitting ANNs into structurally smaller pieces makes them simpler to analyze. The monolithic ANNs are often treated as black boxes. Obtaining information about the role of individual neurons or connections is usually impossible or at least very difficult. The MANNs are different in this respect. In their case, separate analysis of behavior of individual modules enables insight into functioning of entire networks.

And five, the modular architecture is a feature of vast majority of creatures formed in the natural way. For example, the human brain is composed of functionally and structurally different modules which combined together form a very complicated nervous system.

When the structure of a problem to be solved is known beforehand, it is possible to manually design a MANN –architecture of the network must reflect the structure of the problem. Each sub–problem extracted from the original problem is associated with a separate module. When decomposition into sub–problems assumes a parallel processing in different modules, it is also necessary to design an integration mechanism. Responses of all the modules must be somehow combined into response of the entire ANN. The manual design of a MANN assumes moreover that all the modules are separately prepared for a dedicated task.

When modular architecture cannot be determined manually, automatic design approaches must be used. One possibility is to apply techniques from the range of evolutionary computation. An example application of neuro–evolution (NE) to form MANNs can be found among other things in [4-6, 16]. Cooperative Co–Evolutionary Neural Networks (CCENN) which is the main topic of the current paper is a new NE method predisposed also to build MANNs. There are a number of CCENN features which differ it from other NE methods used for the same purpose. The most distinctive of them are:

Architecture of MANNs is very flexible and adjusts to a problem. This is a consequence of the fact that it depends mainly on decisions made during evolutionary process. Evolution decides about the number, architecture and the way of cooperation between modules. The role of a man–designer is limited practically only to determining maximum number of hidden neurons in each module.

CCENN originates from Assembler Encoding with Evolvable Operations (AEEO) [24], i.e. a generative NE method which encodes ANNs in the form of linearly organized programs consisting of operations implemented as simple ANNs. In AEEO, the task of each program with ANNs–operations is to fill a special matrix defining a resultant ANN with values. Once the matrix is produced, it is then transformed into a network. To evolve the programs and their ANNs–operations, Cooperative Coevolutionary Genetic Algorithm (CCEGA) is used [18, 19].

CCENN practically works as AEEO, i.e. it also uses a set of cooperating ANNs, the ANNs are also responsible for modification of a simple data structure, and the entire set of ANNs also evolves according to CCEGA. Both methods differ, however, in two key elements. First, ANNs–operations in AEEO constitute only an intermediate element between the resultant ANN and its genotype whereas in CCENN, the set of ANNs is a final modular solution. In AEEO, ANNs–operations modify a matrix which is next converted into an ANN whereas in CCENN, ANNs operate on a vector whose individual items correspond to outputs of a whole modular system. Second, in AEEO there are not any limitations on architecture of the resultant ANN. It can be both monolithic or modular. The final architecture of the ANN depends on the ANNs–operations and a problem to be solved. Meanwhile, in CCENN, all ANNs are inherently modular. Each ANN always consists of separated sub–ANNs, each of which is responsible for a different sub–task.

Since the main reason for construction efforts which led to CCENN was the need for an effective method for controlling a team of underwater vehicles (UVs), the first tests verifying effectiveness of the method were carried out on a variant of the predator–prey problem in which roles of predators and a prey were played by UVs. The influence on selection of a type of the testing problem had also its modularity. In the predator–prey problem, the task is to control a team of the predators whose common goal is to grasp the prey. This task can be decomposed into a number of sub–tasks, each of which corresponds to a separate predator.

All the tests with CCENN were carried out in the same conditions as those presented in [24]. This made it possible to compare CCENN with AEEO and Neuro–Evolution of Augmenting Topologies (NEAT), i.e. one of the most successful NE method of recent years. Making NEAT a point of reference for CCENN had yet another purpose. Since NAET is a well understood and widely applied method [1, 29], it is a perfect indication of the complexity of the testing problem used in the experiments which because of UVs is not a standard problem.

The paper is organized as follows: Section 2 is a presentation of CCENN, Section 3 is a description of AEEO and NEAT, Section 4 is a report on the experiments, Section 5 is an analysis of experimental result, and Section 6 is a summary.

2 Cooperative co–evolutionary neural networks

As already mentioned, in CCENN, the resultant MANN is composed of a set of unconnected sub–ANNs and a vector of numbered output registers. The task of the sub–ANNs is to collectively produce output of the MANN and to enter it into the registers. Each register corresponds to a different output and is updated independently of other registers. A single run of the set of the sub–ANNs generates a value for one register. In consequence, to obtain complete output of the entire MANN, the sub–ANNs need to be run a number of times 1 . In each run, only one sub–ANN is entitled to modify a register. In order to select an active sub–ANN, a negotiation process between all the sub–ANNs is carried out. A sub–ANN with the greatest negotiation strength is allowed to set value of a selected register (see Fig. 1). A detailed algorithm of CCENN is presented in Fig. 2.

The maximum number of inputs in each sub–ANN is the same and corresponds to the size of input space of a problem to be solved. The exact number of inputs depends on decisions made during the evolutionary process and, in consequence, it can be different for each sub–ANN. In addition to inputs corresponding to the problem, each sub–ANN also includes an extra input which indicates the number of the register to be currently modified. As mentioned above, the complete output of the entire MANN is produced in a number of iterations. The number of iteration which corresponds to the number of the register to be modified is every single time fed into the extra input of each sub–ANN. The remaining inputs, in all the iterations, are supplied with the same input signals.

Like the number of inputs also the number of hidden neurons has its maximum value, the same for all sub–ANNs. As before, the exact number of hidden neurons is determined in the evolutionary way and it can be different for each sub–ANN.

Two outputs of each sub–ANN are used for two different purposes. The first one informs about the negotiation strength of sub–ANN whereas the second one determines a value which is inserted to a register once the sub–ANN wins competition with other sub–ANNs.

At first glance, the set of sub–ANNs evolved in CCENN may be viewed as an ensemble of networks. As in the ensemble–based approach we deal with unconnected networks which make common decisions via the negotiation process. However, as already mentioned, in the ensemble of networks each sub–ANN can constitute a separate solution to a whole problem, it is separately prepared to perform a whole task, and thereby, it can work independently of other sub–ANNs. In CCENN, we deal with a different situation. In this case, each sub–ANN is responsible for a different sub–task and it cannot work without other sub–ANNs. The output of the whole system is not a combination of all sub–ANN outputs as is the ensemble approach. In CCENN, each sub–ANN has its own sub–task which corresponds to a different output register and/or to a different input state.

CCENN makes it possible to flexibly divide a problem into sub–problems and to associate a separate sub–ANN to each of them. The division of the problem takes into account both input and output space (which sub–ANN is active in a given situation depends on the output register to be currently modified and the present state of a problem to be solved), and what is more important, it is completely dependent on decisions made during the evolutionary process. A human being has no influence on the number of sub–tasks (the number of sub–tasks is equivalent to the number of sub–ANNs which changes within the evolution, see further), and neural solution assigned to each of them (the division of the whole problem space between individual sub–ANNs depends on their negotiation strengths). All decisions crucial for effectiveness of MANN are the consequence of the evolutionary processes which in CCENN proceeds according to CCEGA.

In CCEGA proposed by Potter and De Jong [18, 19], each part of a solution evolves in a separate population. To form a complete solution, selected representatives (usually, the best ones) of each population are combined together. Application of this evolutionary scheme in CCENN consists in evolution of individual sub–ANNs in separate populations. The number of the sub–ANNs in a complete MANN corresponds to the number of populations (see Fig. 3). Each population delegates exactly one representative sub–ANN to each MANN. During the evolution, MANNs expand gradually. In the beginning, they contain only one sub–ANN from one existing population. When the evolution stagnates, i.e. lack of progress in fitness of generated solutions is observed over some period, the set of populations containing sub–ANNs is enlarged by one population. This procedure extends all MANNs by one sub–ANN. Each population can also be replaced with a newly created population. Such situation takes place when the influence of all sub–ANNs from a given population on fitness of generated solutions is definitely lower than the influence of sub–ANNs from the remaining populations (the population can be replaced when, for example, its fitness, measured as the average fitness of all sub–ANNs from the population, is definitely lower than fitness of the remaining populations).

In individual populations, the evolution proceeds according to Canonical GA [8]. At the genotypic level, each sub–ANN is represented in the form of a variable length binary string consisting of two parts. The first short part defines topology of sub–ANN whereas the second part includes its parameters (see Fig. 4). Construction of a sub–ANN proceeds in three phases. First, the topology is determined based on the information contained in the first part of the chromosome. To this end, binary values from this part are directly copied into Network Definition Matrix (NDM), a single bit corresponds to a single item in the matrix. When the number of bits is insufficient to completely fill in the matrix, the whole sequence of bits is used again. In the next phase, the parameters from the second part of the chromosome are successively introduced into NDM. In this case, only items equal to one are modified. The remaining items, i.e. items equal to zero, remain intact. As before, transfer of the parameters is performed in a loop until all the items in NDM have a value assigned (see Fig. 5). In the last phase, NDM is transformed into a sub–ANN. To this end, the matrix has to store all the information necessary to construct the network. This information is included both in the size and individual items of the matrix, scaled always to the range <-1, 1>. The size of NDM determines the maximum number of neurons in the ANN whereas individual items of the matrix define weights of interneuron connections, i.e. item NDM[i, j] determines a link from neuron i to neuron j. Apart from the basic part, NDM also contains additional columns that describe parameters of neurons, e.g. type of neuron (e.g. sigmoid, radial, linear), and bias (see Fig. 6) [20].

During evolution, each sub–ANN is combined with selected sub–ANNs from the remaining populations to form a complete MANN. The MANN is put to an evaluation test whose result is used to fix fitness for all components of the entire network. After evaluation of all sub–ANNs from population, a tournament selection is used to chose parental sub–ANNs for reproduction. To form offspring sub–ANNs, the parental chromosomes are subject to three different genetic operations, i.e. one–point crossover, mutation and the so–called cut–splice.

In CCENN, the implementation of crossover which does not modify the length of chromosomes is used. A single crossover point is the same in both parents and there are no restrictions as for its selection. With regard to the probability of crossover, it is constant throughout the evolutionary process.

The probability of mutation is determined individually for each chromosome. Initial probabilities are fixed at the very start of each evolutionary run and then they are adjusted to the number of sub–ANNs, and the current state of the evolutionary process.

As already mentioned, in CCENN, MANNs expand with the passage of time. Initially, each MANN includes only one sub–ANN to which next sub–ANNs are successively added if the evolution cannot accomplish progress in performance over an assumed time. At the initial phases of evolution, when all MANNs include only one sub–ANN, slight modifications introduced to sub–ANNs by means of mutation do not cause greater changes in behavior of their MANNs. The situation changes when MANNs have two, three or more sub–ANNs. This time, insignificant modifications in all the sub–ANNs can mean huge changes in operation of their MANNs. This, in turn, can cause large bounds in fitness of MANNs created in consecutive co–evolutionary cycles and, in consequence, great difficulties with evolution of effective MANNs.

In order to prevent such problems, CCENN adjusts the level of mutation to the number of sub–ANNs contained in MANNs. The magnitude of mutation determined at the beginning of the evolutionary process refers only to MANNs containing one sub–ANN. When MANNs have more sub–ANNs, the probability of mutation determined for MANNs including one sub–ANN is divided by the number of sub–ANNs currently used in the MANNs.

The probability of mutation is also adjusted to a current state of the evolutionary process. In the case of stagnation of the evolution over an assumed period, the mutation is gradually augmented. The goal is to escape from the point where the evolution is stuck. The process of augmenting mutation is immediately stopped once the first symptoms of exit from the stagnation point are observed. The end of the stagnation is connected with returning to a previous value of mutation.

The improvement of the best result achieved so far is the second situation when the probability of mutation is changed. This time, however, mutation is reduced to an assumed value. The main goal of such a procedure is to meticulously search the area close to the currently best solution. When further improvement of the result to not occur for a longer time, mutation is getting back to a previous value.

In CCENN, the only operator responsible for the change of the length of chromosomes is the cut–splice. It adds or removes a single segment of binary genes from the very end of chromosome. Thus, in one generation, increase (or decrease) of the chromosome size is restricted to a single block of genes.

3 Methods compared to CCENN

4 Experiments

In order to test effectiveness of CCENN, experiments on the predator–prey problem were carried out. In the experiments, the task of each ANN was to control 2 a team of UVs–predators whose common goal was to capture a single UV–prey behaving by a simple deterministic strategy. The experiments were carried out in simulation and in the configuration with one prey and three chasing predators. Both the predators and the prey were implemented as UV “Ukwial” (see Fig. 10) [12]. The behavior of all the vehicles was simulated by means of a discrete time model described in [22].

In the experiments, the predators and the prey lived in a common artificial environment. To represent the environment, a square of size 100x100 meters was used (see Fig. 11). To simplify calculations, both the predators and the prey could not submerge under the surface of the water. The environment did not contain any obstacles, moreover, in order to ensure infinite space for the predators and the prey and for their struggles, it was open at each side. Thus, every attempt to move beyond upper, lower, right or left border of the square caused the object making such an attempt to move to the opposite side of the environment [22].

The predators were controlled by a single MANN whose task was to determine movement direction for each of them. At each time step, the MANN decided about change of the current course of each vehicle. The course could be changed by: 0,5,10,…,355 degrees (it is necessary to note that decisions of the MANN determined only a final state of the vehicles which they ultimately should reach, the actual course after the maneuver and duration of the complete maneuver depended on current parameters of each vehicle). Speed of the predators was constant during the tests and amounted to 0.5 m/s.

In the experiments, two types of the prey were used, i.e. a simple and an advanced prey. The strategy of the simple prey forced it to stand still when no predator was closer to it than its range of vision (the range of vision of the prey amounted to 50 meters) and to move directly away from the nearest predator otherwise. In contrast to the simple prey, the advanced one always took into account all visible predators. As before, it started to move only when some predators were noticed. To determine direction of a next move, the first activity of the advanced prey was to calculate a single position representing all predators being in its close proximity. The closer the predator was to the prey the greater was its influence on the calculated position. In the following step, the “common” position of the predators was treated as the position of the closest (virtual) predator and the strategy of the simple prey was used thereafter [22]. The strategies of the simple and the advanced prey are formally presented below: π simple ( t ) = { StandStill if d i pred ( t ) > 50 i = 1 . . | P | arg max a ∈ A d arg min i = 1 . . | P | d i pred ( t ) pred ( t , a ) otherwise(2) where

t - time step,

P - set of predators,

A - set of actions of prey and predators (different courses),

d i pred ( t ) - distance between prey and ith predator in step t,

d i pred ( t , a ) - distance between prey and ith predator if in step t action a to be performed. π advanced ( t ) = { StandStill if d i pred ( t ) > 50 i = 1 . . | P | arg max a ∈ A d k pred ( t , a ) otherwise(3) where

k - indicates representative of all predators in prey range of vision, “common” position of representative is equal to 1 | P 50 ( t ) | ∑ i | P 50 ( t ) | W i ( t ) p i pred ( t ),

P₅₀ (t) - set of predators in range of vision of advanced prey in step t,

p i pred ( t ) - position of ith predator in step t,

W _i  (t) - weight of ith predator in step t, for example, W i = ∑ j | P 50 | - i d j pred ∑ j | P 50 | d j pred, where P₅₀ - i is set of predators in range of vision of prey except ith predator.

When moving each prey could select the same actions as the predators. The speed of the preys also amounted to 0.5 m/s. Since speed of the predators was the same as speed of the escaping prey, they could not simply chase it to grasp it. We assumed that the prey was captured if the distance between it and the nearest predator was lower than 10 meters.

In all the experiments, MANNs had six inputs (plus extra input for the number of output register to be currently modified) and three outputs. The number of outputs corresponded to the number of predators. In turn, the number of inputs was twice the number of predators. Each output gave commands to one predator, in turn, each input informed about vertical or horizontal distance between the prey and one of the predators[22].

5 Analysis of the results

The results presented in the previous section confirm advantages of modular solutions against monolithic ones. In AEEO, all ANN–operations have to strictly cooperate to produce a single solution to a problem. Accomplishing such cooperation is a very complex task. Because they operate on the same NDM and, in consequence ANN, one wrong ANN–operation is enough to destroy efforts of the others. The same situation is in NEAT. This time, one faulty gene representing a connection between cooperating neurons may decide about effectiveness of the entire neural solution.

Meanwhile in CCENN each sub–ANN is a solution to a separate sub–problem. In consequence, the task of CCENN can be viewed as searching for a number of solutions to different problems which separately are easier to solve than the entire problem. Splitting the whole solution into many smaller ones makes the task of CCENN easier compared to AEEO and NEAT.

Better performance of MANNs during the learning tests compared to monolithic ANNs evolved by AEEO and the opposite situation during the generalization tests may result from different sizes of the former and the latter. The maximum size of the monolithic ANNs, regardless of the number of ANN–operations constructing them, amounted to four hidden neurons. Meanwhile, MANNs often included even five or six sub–ANNs. Of course, very simple effective networks with only two or three modules and with very clear division of responsibilities between individual sub–ANNs were also generated, however, they were in the minority. Most of the MANNs were more complex. They were very effective in the learning phase, however, when their tasks differed from those encountered during the evolutionary process they sometimes failed due to overfitting to the learning data.

It seems that the reason for the situation above was the minimum architecture of the sub–ANNs, without hidden neurons. Since individual sub–ANNs contained only input and output neurons, it was very difficult to evolve effective modular architectures including, for example, two or three sub–ANNs. The small size of the sub–ANNs forced evolution to decompose the testing problem into a greater number of small sub–problems, each of which corresponded to a separate simple sub–ANN. Unfortunately, large fragmentation of the problem space, made during the evolutionary process, appeared to be sometimes ineffective, which led, in turn, to a poor generalization of a part of MANNs. Division of responsibilities between many simple sub–ANNs appropriate for the learning tasks turned out to be sometimes poorly effective in the generalizing ones.

Even though most MANNs were more complex than the monolithic networks generated by AEEO, they still were considerably simpler than those evolved by NEAT which because of gradual growth during the evolutionary process, usually, included many hidden neurons. This fact and significantly better preparation for a task during the learning phase contributed to a definitely better generalization of MANNs in relation to their counterparts evolved by NEAT.

Throughout the experiments, there were few cases when the testing problem was decomposed into sub–problems in the way which seems to be the most natural for human being, i.e. when each predator, regardless of the situation, is controlled by a separate sub–ANN or a set of sub–ANNs. The example of such a situation is presented in Fig. 14 (e). The figure mentioned corresponds to decomposition of the problem into five sub–problems (five sub–ANNs). Control of the first predator is split into four different sub–problems solved by four sub–ANNs (the first column in the matrix). Each sub–ANN controls the predator in other conditions. The last sub–problem is associated with control of the second and the third predator (the two last columns in the matrix). This sub–problem is solved by a single sub–ANN.

In most cases, however, decomposition of the problem was slightly more complicated (assuming that each sub–ANN corresponds to a different elementary sub–problem). Often, individual sub–ANNs were responsible for more than one predator. They were run in many different situations (for many different areas of the input space) in which they simultaneously controlled one, two or sometimes even three predators. However, sub–ANNs also evolved whose responsibility was reduced to only one predator and one definite situation in the artificial world (see e.g. Fig. 14 (a) and sub–ANN no. 4). Example decompositions of the testing problem into sub–problems made by CCENN are depicted in Figs. 14 and 16.

Different complexity of sub–problems resulted in different complexity of the sub–ANNs. Even though most sub–ANNs had rather simple architecture (see Fig. 15) with at most a few connections to output neurons, sub–ANNs with the maximum possible number of neurons also occurred. The complexity of the architecture could make the sub–ANNs mentioned overfitted to the learning data and, in consequence, be a next reason for problems of some MANNs with generalizing knowledge acquired during the evolutionary process.

6 Summary

The paper presents Cooperative Coevolutionary Neural Networks, i.e. the method for evolving MANNs. The experiments reported in the paper compared CCENN with its prototype dedicated to building monolithic ANNs and with NEAT, i.e. a state–of–the–art method of recognized reputation. The comparison tests carried out in simulation showed that CCENN outperforms the rival methods in evolving neuro–controllers for a team of underwater vehicles. However, the experiments also revealed that the method is sensitive to the size of modules. As the experiments showed, inappropriate size may lead to ineffective decomposition of a problem to be solved, too complex architectures of MANNs and, in consequence, a poor generalization.

Direct encoding of sub–ANNs is another weak point of CCENN which makes it appropriate for evolving rather simple MANNs. To evolve ANNs consisting of complex sub–ANNs, CCENN requires long chromosomes that can be, however, a serious obstacle in generating effective neural solutions. To avoid the problems with the poor generalization and to increase scalability of CCENN, the method will be modified in two points. Both the modifications will be tested within the framework of the future research.

The first modification assumes that the size of each sub–ANN will undergo evolution, i.e. it will be encoded in chromosome. In the current variant of CCENN, all sub–ANNs have the same size fixed by a designer which in some situations may lead to excessive fragmentation of a problem and, in effect, to too large number of sub–ANNs in the final neural solution. Making the size of the sub–ANNs dependent on decisions of evolution aims at rendering the method more flexible and able to optimal decompositions of a problem into sub–problems.

In the new variant of CCENN, a new method for encoding individual sub–ANNs will be also applied. Currently, each sub–ANN is encoded directly in chromosome whose the first part encodes topology whereas the second part parameters of the sub–ANN. In the new variant of the method, the solution used in AEEO will be used, i.e. each sub–ANN will be constructed by a network encoded directly in chromosome. The networks responsible for constructing sub–ANNs will be build and will work in the same way as ANN–operations in AEEO. It seems that such an approach should increase scalability of CCENN and thereby make the method more effective in constructing complex MANNs.