Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

My big idea: Ancient Brain


CA114      CA170

CA668      CA669      Projects

GAs - Discussion

Comparison with State-Space Search / Neural Networks

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

Neural Networks - we have measure of error E.
Here we don't. Absolute fitness gives us less info than an E measure.

More on this in Comparison of Neural Net and GA.

Representing the function v. Maximising the function

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

Here, we're 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 our 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 any step size 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.

Using GAs as just yet another tool

Useful for optimising n parameters, all of which influence each other.

Useful for scheduling that minimises some cost function. e.g. Timetabling of lectures/exams. Minimise no. of clashes (options). Minimise no. of exams on consecutive days, etc.

Sample applications of Genetic Algorithms

Genetic Algorithm Traveling Salesman Problem with Javascript.
Starts with randomised cities and random path. Gets better each generation. Nice!
Original page by Jeff Heaton is gone but Javascript still works in Internet Archive.

ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.