Evolutionary Neural Networks: Design Methodologies
By ai-depot | March 24, 2003
Evolution of Architecture
A neural network’s performance is highly dependant on its structure. The interaction allowed between the various nodes of the network is specified using the structure only. An ANN structure is not unique for a given problem, and there may exist different ways to define a structure corresponding to the problem. Depending on the problem, it may be appropriate to have more than one hidden layer, feedforward or loopback connections, or in some cases, direct connections between the input and output layer. Hence, deciding on the size of the network is also an important issue. Too small a network will prohibit it from learning the desired input to output mapping; too big a one will fail to match inputs properly to previously seen ones and lose on the generalization ability.
Determining an optimal network topology has always been a problem. It is even impossible to prove that a given structure is optimal. Most often the structure is determined by trial and error methods. Different combinations of nodes and connections are tried out so that it gives maximum level of response within the given constraints. Such methods rely on overall performance of the network, so parts of the network that contributed well are difficult to identify. EAs can be helpful in this case, with their natural makeup of exchanging information. The search space here is also too big, similar architectures may have quite difference performance; different architectures may result in similar performance. This makes EAs a better candidate as opposed to algorithms which start with a maximal (minimal) network and then deletes (adds) layers, nodes or connections when necessary during training.
The genotype representation of a neural architecture is critical to the working of an evolutionary ANN design system. Considerations have to be taken so that the optimal structures are representable in it, meaningless structures are excluded, genetic operators yield valid offspring, and the representation do not grow in proportion to the network. Ideally, the representation should be able to span all potentially useful structures and omit unviable network genotypes. The encoding scheme also constrains the decoding process. For example, a neural network requiring a recurrent structure should have a representation expressive enough to describe recurrent networks. Also the decoding mechanism should be able to read this representation and transform it into an appropriate recurrent network.
Low level or direct encoding techniques mostly specify the connections only. Indirect encodings are more like grammatical rules; these rules suggest a context free graph grammar according to which the network can be generated. Direct encoded genotypes increase too fast in length with a growing network. Thus, the maximum topological space has to be limited by the user. This may exclude the fittest structure in the lot, or may result in networks with special connectivity patterns.
The performance of a network structure cannot be judged until it has been trained. Usually, the network is trained for a fixed number of steps and the performance is measured on an “evaluation set” data. By using different sets of data for training and evaluation, networks with better generalization abilities are given a preference in evolution.
One of the major challenges with evolving ANNs is to find a meaningful way to crossover disparate topologies. Usual genetic operators will fail to preserve the structural innovations occurring as part of the evolutionary process. Some kind of a speciation is required so that individuals compete primarily within their own niches, and not with the population at large. We shall now see a method, NeuroEvolution of Augmenting Topologies (NEAT), which uses methods for historical markings, speciation, and incremental growth from minimal structure for efficient evolution of network structure.
NeuroEvolution of Augmenting Topologies (NEAT)
A genotype in NEAT is made up of several connection genes. A connection gene contains information like the two nodes at the ends of the connection, the weight, and a special attribute called the innovation number. Apart from the connection genes, layer information (input, output, or hidden) regarding the nodes is also made a part of the genome.
Figure 5: Genome represenation in NEAT.
An effort has been made to keep track of the historical origin of each gene, so that genes which do not follow from the same ancestor do not compete against each other. This has been achieved by assigning a global innovation number to each gene; this number is incremented each time a new gene appears. It should also be taken care that the offspring inherits the same innovation number on each gene. This allows that historic information is passed on over generations throughout the process of evolution.
The innovation number helps NEAT counter the problem of competitions between fundamentally different topologies. During the process of recombination, genes with same innovation number are lined up against each other; the ones from the more fit parents are inherited. Genes that do not find an innovation number match (disjoint or excess genes) in the other parent are passed on to the offspring.
Figure 6: Crossover in NEAT.
Mutation in a neural architecture can happen in two ways - by adding a connection gene, or by adding a node gene. Two unconnected nodes can be connected by adding a new connection gene to the genome. An existing connection can also be spilt into two and a new node can be introduced in between. The old connection is disabled and two new connection genes are added. New nodes and connections can be very easily included into the structure using this methodology.
Figure 7: Mutation in NEAT.
The selection of parents for mating determines what kind of topological features gets transferred to the offspring. If random selections are made then it is possible that structural innovations get lost during the breeding process. NEAT handles this problem by dividing the whole population into species depending on their topological similarities, and then mating the best performing individuals from each species to generate the offspring. The number of offspring generated depends on the overall fitness of the whole species in comparison to that of the others.
NEAT divides the population into different species on the basis of a compatibility distance measure. This measure is generally derived from the number of disjoint and excess genes between two individuals. If an individual’s distance measure from a randomly selected one is less than a threshold value, then both individuals are placed into the same species. Once the classification is done, the original fitnesses are adjusted by dividing by the number of individuals in the species. A species grows if this average adjusted fitness is more than the population average, otherwise it shrinks in size. By doing so, NEAT does not allow any particular structure dominate over the whole population, but at the same time allows for the growth of the better performing ones.
Tags: evolutionary algorithm, genetic algorithm, neat, neural network
Category: tutorial |
