Iustin Benche
CIS 571 - Final Project, Spring 2001
Neural Networks and Genetic Algorithms
What problems are better solved by a genetic algorithm, and why?
In this project we tried to get some answers for a few theoretical questions: What kind of problems are better solved by a genetic algorithm, and why? What are the landscapes on which genetic algorithm outperforms other methods? Can genetic algorithms be used for discovery of optimal neural networks architectures?
After discussing some experimental results obtained by the authors of (2), the paper also presents some experimental results using SANE, (Symbiotic, Adaptive Neuro-Evolution) (3), a Java package used to evolve (through genetic algorithms) a population of neurons to form a neural network for the sequential decision task.
The primary paper discussed here is "Some Combinatorial Landscapes on which a Genetic Algorithm Outperforms Other Stochastic Iterative Methods" (2). The bibliography also includes several packages for neural networks and/or genetic algorithms (3,4,5,6), a general presentation of "Genetically Evolved Neural Networks" (7), and one of the best books about genetic algorithms, "An Introduction to Genetic Algorithms" (1).
A genetic algorithm starts with a set of one or more individuals and applies selection and reproduction operators to "evolve" an individual that is successful, as measured by a fitness function.
function GENETIC-ALGORITHM(population, FITNESS-FN)
returns an individual inputs: population, a set of individuals FITNESS-FN, a function that measures the fitness of
an individual repeat parents <- SELECTION(population, FITNESS-FN) population <- REPRODUCTION(parents) until some individual is fit enough return the best individual in population, according
to FITNESS-FN
Applying GAs to a specific problem:
What is the fitness function?
How is an individual represented?
How are individuals selected?
How do individuals reproduce?
GA are used in searching for a solution class of problems. The idea is to efficiently find a solution to a problem in a large space of candidate solutions. Since GA is a method for finding optimal or good solutions by examining only a small fraction of the possible candidates, in can be better compared with hill-climbing or simulated annealing techniques, than to algorithm that search in the entire search space, like depth-first search or A*.
By maintaining a population of individuals, which can come from different regions of the search space, GA will not fall into the drawbacks of hill-climb algorithms:
local maxima
plateaux
ridges
Description
A number of subsets of a large set S are each given a cost. The task is to choose a collection of these subsets which:
covers the set S (every element of S appears in at least one of the chosen subsets);
contains no redundant subset; such that removing any one of the chosen subsets will violate property 1;
has minimal total cost.
Examples: airline crew scheduling, bus-driver scheduling.
This problem is NP-complete, there isn't any known poly-time algorithms to solve it.
Description of encoding
| Element 1 | Element 2 | Element 3 | ... | Element n |
Each element i of the set S has associated with it a list of those subsets which contain i. If gene i has value v, it means that the v-th member of this list is a candidate set to be included in the covering of S.
The chromosome is interpreted left to right, starting at gene 1. Gene 1 indicates a set which includes (covers) element 1 and this set is added to the initially empty cover. This set may cover other elements too, so the genes for those other elements are 'switched off'.
Landscape of search space
Slight changes to a chromosome can considerably alter the pattern of genes which become expressed. This has two important consequences: first, there is a somewhat unstable local landscape structure, and second, each chromosome carries around with it a collection of dormant genes which may be revived by mutation at any stage. The landscape contains gaps, discontinuities, ridges.
On the other hand, changes to a chromosome in genes which represents subsets not included in the cover has no influence in the fitness of the candidate. This can be seen as a broad plateaux in the landscape of the search space.
Experimental results
Using the same representation of the problem, GA outperforms hill climbing and simulated annealing algorithms.
There is a much larger collection of problems on which a GA has been found superior to either simulated annealing and hill-climbing, but it is rarely clear that this arises as a result of interesting aspects of the landscape, rather than being a very difficult to explain epiphenomenal effect.
Neural Networks and Genetic Algorithms
Many studies have shown that artificial Neural Networks have the capability to learn the underlying mechanics of time series, or, in the case of trading applications, the market dynamics. However, it is often difficult to design good artificial Neural Networks, because many of the basic principles governing information processing in artificial Neural Networks are hard to understand, and the complex interactions among network units usually makes engineering techniques like divide and conquer inapplicable. When complex combinations of performance criteria (such as learning speed, compactness, generalization ability, and noise resistance) are given, and as network applications continue to grow in size and complexity, the human engineering approach will not work and a more efficient, automated solution will be needed.
Genetic Algorithm is reminiscent of sexual reproduction in which the genes of two parents combine to form those of their children. When it is applied to problem solving, the basic premise is that we can create an initial population of individuals representing possible solutions to a problem we are trying to solve. Each of these individual has certain characteristics that make them more or less fit as members of the population. The most fit members will have a higher probability of mating than the less fit members, to produce offspring that have a significant chance of retaining the desirable characteristics of their parents. This method is very effective at finding optimal or near optimal solutions to a wide variety of problems, because it does not impose many of the limitations required by traditional methods. It is an elegant generate and test strategy that can identify and exploit regularities in the environment, and converges on solutions that were globally optimal or nearly so.
Genetic Algorithms have been increasingly applied in artificial Neural Networks design in several ways: topology optimization, genetic training algorithms and control parameter optimization. In topology optimization, Genetic Algorithm is used to select a topology (number of hidden layers, number of hidden nodes, interconnection pattern) for the artificial Neural Network which in turn is trained using some training scheme, most commonly back propagation. In genetic training algorithms, the learning of a artificial Neural Network is formulated as a weights optimization problem, usually using the inverse mean squared error as a fitness measure. Many of the control parameters such as learning rate, momentum rate, tolerance level, etc., can also be optimized using Genetic Algorithms. In addition, Genetic Algorithms have been used in many other innovative ways, for instance, creating new indicators based on existing ones, selecting good indicators, to evolve optimal trading systems and to complement other techniques such as fuzzy logic.
Applications of GA in neural networks
evolving weights in a fixed network (learning)
evolving learning parameters
evolving network architectures
Description of the encoding
| Node 1 | Node 2 | Node 3 | ... | Node n |
Each Node contains a bit indicated that the neuron is present in the architecture, followed by the weights of the connection to that neuron. Each weights has also a bit indicated that that connection will be used or not.
| 0/1 | 0/1 w1 | 0/1 w2 | ... | 0/1 wn |
The representation of the neural network is very similar to the presentation of the set covering problem. If the bit indicating the presence of the neuron is set to 0 (by mutation or crossover), the weights which follows will also by skipped. This indicates gaps in the landscape of the search space. Also, because some weights will be invalidated, mutation occurring on those bits will have no effect to the overall fitness of the network, and this can be viewed as a broad plateaux. We can conclude that the landscape will have the same characteristics (local minima, discontinuities, gaps, broad plateaux) as the landscape of the set covering problem.
We expect that GA will perform well on this problem. However, even though the results obtained with SANE are encouraging, we cannot say anything about the performances of this approach until we'll have some results of another algorithm applied on this problem, with the same representation of the network. Such results are not present in this project.
SANE = Symbiotic, Adaptive Neuro-Evolution
SANE evolves (through genetic algorithms) a population of neurons to form a neural network for the sequential decision task. Symbiotic evolution promotes both cooperation and specialization in the population, which results in a fast, efficient genetic search and discourages convergence to suboptimal solutions.
JavaSANE is a research project developed at the University of Texas at Austin by David Moriarty and Cynthia Matuszek. After downloading the package from (3), the quickest way to get JavaSANE up and running in a new domain is as follows:
- Change the values in NUM_INPUTS and NUM_OUTPUTS in Config.java to the appropriate number of inputs and outputs for your network. You should also tweak the values for maximum number of connections, number of hidden neurons and population sizes, to make sure they're intelligent with respect to your domain.
- Rewrite the function Evaluate_net in Domain.java, which takes a neural net as a parameter and returns its "fitness value." The fitness value is a numerical value; whether your network is trying to maximize or minimize this value is set in Config.java, and the scale of the value matters only with respect to other fitness values--all JavaSANE does is compare the fitness values of different networks. (The definition for a network is in Network.java.) Any support functions, etc. for Evaluate_net should go into Domain.java as well.
- Once Evaluate_net is defined, you can run JavaSANE and it will try to find networks that optimize the value returned by your function. It will take care of creating and evolving the network for you.
In the package, a README file provides instructions about the menu interface, or the command line options. A menu is presented if no arguments are given to sane on the command
line. Because the menu gives you no way to evolve a network, it is most useful for analyzing networks after evolution.
JavaSANE tries lots of different networks, choosing better ones to breed based on the evaluations you return; these networks are saved as files with the names 000best.bin through 999best.bin. The command line to do this:
java {programname} {popfile} {# generations} {seed #}
Example:
java Sane POPFILE 100 12345
To choose the best network file that's been created:
java Sane x
This will write a value into analyze.out, which is the value Domain.Evaluate_net returns for the best network. It will also write into report.txt a bunch of lines that list a specific network file, and the best return value the network had found so far when that file was evaluated
We used SANE successfully to evolve neural networks only for small problems.
Here are the modified files for 2-XOR problem: Config.java , Domain.java , and for 3-XOR problem: Config.java , Domain.java .
Melanie Mitchell (1998). An Introduction to Genetic Algorithms, MIT Press.
Dave Corne, Peter Ross (1995). Some Combinatorial Landscapes on which a Genetic Algorithm Outperforms Other Stochastic Iterative Methods, "Evolutionary Computing; AISB Workshop, Sheffield 1995, Selected Papers", ed. T.Fogarty, Springer-Verlag Lecture Notes in Computer Science
David Moriarty (1994). Learning Sequential Decision Tasks: The SANE System, http://www.cs.utexas.edu/users/nn/pages/research/neuroevolution.html#sane
Jochen Fröhlich. Neural Net Components in an Object Oriented Class Structure, http://rfhs8012.fh-regensburg.de/~saj39122/jfroehl/diplom/e-index.html
JANNT: JAva Neural Network Tool, http://www.compapp.dcu.ie/~tdoris/BCK/
Peter Andersen, Niels Damgaard, Ulrik Skyt, Neural Networks Study Group. Final Report, http://www.brics.dk/~damgaard/NNSG/report/
Genetic Algorithms and Genetically Evolved Neural Networks, http://sunflower.singnet.com.sg/~midaz/Introga.htm