GAs - Discussion

So what is the status of a GA?
It is clearly some kind of heuristic - an attempt to find a good solution in a short time, with no guarantee of finding the global best solution.

Comparison with State-Space Search / Neural Networks

With State-Space Search, we often have a heuristic "distance from goal".
With GA, we have no idea how far away we might be from the optimal solution.

With Neural Networks, we have a measure of "error" for many inputs.
With GA, we do not have any "error" value. A "fitness" value gives us less information than an "error" value.

More on this in Comparison of Neural Net and GA.

Representing the function v. Maximising the function

With neural networks, we are trying to match an n-dimensional Input with the correct Output. i.e. Represent the function over its range.
Requirements: Correct Outputs for many representative Inputs (over entire range).

With GA, we are trying to find the n-dimensional Input that leads to the highest Output. i.e. Maximising the function.
We don't need to build up a representation of the function.
Requirements: Given any Input, tell me the Output.

Could we combine these?
Do a GA search, and, as we go along, build up a network to represent the map.
Problem is we won't be representing it in same detail over the whole range. We spend more time (get more detail) on the higher peaks.
We get random coverage at the start, but it quickly becomes non-random.

Changing fitness landscape

Sometimes the fitness landscape changes over time.
e.g. Fitness is how you do at playing chess against the other individuals.
They are improving over time.

The GA can track changing fitness landscape, in that each generation has to re-prove its fitness.
Problem is that things like pm and pc and temperature must be increased again.
Also instead of starting with a random scattering of individuals, we may be starting with them all concentrated in a small, sub-optimal area of the landscape.

How do you detect if the fitness landscape has changed?

Random number generators

Typically, we need a random (or pseudo-random) number generator to randomly initialise our population, and also to make probabilistic decisions thereafter.

If we use the same "seed" each time we run, then each run of evolution will be exactly the same.
So seed based on clock time or something.

Using GAs as just another tool

One could ignore AI-type problems, and just use a GA as a tool to optimising n parameters, all of which influence each other.

e.g. Use a GA for scheduling that minimises some cost function. Such as timetabling of lectures/exams. Minimise no. of clashes (options). Minimise no. of exams on consecutive days, etc.

Sample applications of Genetic Algorithms

Another text search GA demo.
JavaScript demo online.
Fitness is closeness to the string "Hello, world".