Revision 9c4c6ddbee3d17c1d44987031a95410a57217708 (click the page title to view the current version)
Changes from 9c4c6ddbee3d17c1d44987031a95410a57217708 to d74f0de5d9c48590fcdadb7c83e28ada294931af
---
title: Optimisation and GA
categories: session
---
# Reading
The textbook chapters are available at BlackBoard.
+ Haupt and Haput Chapter 1 (cursory)
+ we will not dwell on the various optimisation algorithms discussed here
+ the general background is important though
+ R&N Chapter 4.1-4.2 give a briefer introduction to the same material
+ Haupt and Haput Chapter 2
+ The main point here is the binary GA, which is summarised as Matlab code
at the end of the chapter
+ There are many variants of each constituent step, including cross-over,
matchmaking, and mutation
# Briefing
+ Optimisation is a general problem
- intelligent agents optimise actions
- functions are optimised in all kinds of decision making
+ Two classic approaches
- exhaustive approaches - exploritng the entire solution space is rarely tractible
- iteratively improving a tentative solution is easily stuck in local maxima
+ Population based methods
- multiple tentative solutions scattered over the search space
- reduces the risk of getting stuck in a local optimum,
while avoiding exhaustive search
- many variants
+ Most basic - look up R&N Chapter 4.1-4.2
+ Genetic algorithms
- overview of the demo implementation
# Exercises
I have provided a demo implementation of GA and Local Beam Search on
[github](https://github.com/hgeorgsch/pygax).
Your goal should be to
1. Gain some experience with these algorithms on different problems,
exploring the limitations of each one.
2. Learn to adapt the GA by changing selection, crossover, and mutation.
3. Understand how the algorithms work in general.
It is recommended to work together, and possibly split tests between
you to compare more results. Feel free to test other variations than
those proposed below. Make sure you keep a log of the tests that you
make, so that you can compare performance.
## First exploration
Have a look at the code and the test scripts. Check that they work
on your system. What functions are optimised in the test scripts?
Answer the following questions by testing,
1. What is the run time of each algorithm? Is there a lot of variation?
2. How many iterations (generations) and how large population is necessary
to get accurate results?
3. Are the results consistent between runs? Or do you tend to get different,
random solutions each time? How much does this depend on the generation count
and population size?
4. Which algorithm is better, GA or Local Beam?
Is the answer the same for both functions?
## Basic Hill Climbing
Setting the population size to one, Local Beam Search degenerates
to ordinary Hill Climbing.
1. Test this Hill Climbing algorithm a couple of times on the F5 function
(as used in `testBeam.py`).
2. Do you get consistent results?
3. Does the number of iterations make a difference?
4. What is the major limitation of Hill Climbing?
## Varying the cost function
1. Make a new test script, changing the cost function.
You can use one of the test functions from Haupt and Haupt Appendix I
(published on BB), or your own.
2. Can you find functions where the GA performs badly?
Where Beam Search is bad?
3. Do the two algoritms struggle on the same or different cost functions?
## Varying the representation
The binary GA uses quantised solutions, representing each floating point
number with a small number of bits.
1. Can you improve the performance by changing the number of bits used
per dimenstion? (This is the third argument to the `BinaryRepresentation`
constructor.)
2. How is the trade-off between run time and accuracy when you change the number
of bits.
## Variations of the GA
1. Discuss, what alternatives are there to the default mating, crossover, and
mutation functions?
mutation functions? Many examples are given in Chapter 2 of Haupt&Haupt.
2. Implement and test a few such alternatives.
3. Can you improve the performance on any of the test functions by using such
alternative constituent functions?
## Learning a string
Let us take an entirely different kind of problem.
The cost function is `stringlearn1` from `TestFunctions`.
We are searching for a string of length `stringlearn1length`.
1. Make a representation class which maps character strings to binary strings
- you can limit the alphabet to upper and lower case letters (52 characters),
digits, space, and full stop, for a total of 64 characters.
- replicate the API of the `BinaryRepresentation` class as far as it is relevant.
- note that the GA uses the `getFloat` method without assuming that the return
value is floating point numbers. If you keep the method name, returning a string,
`GA` will still work with the new representation.
2. Set up a test with a GA seeking to minimise `stringlearn1` over all strings of
length `stringlearn1length`.
3. Are you able to learn the string correctly and get cost zero?
Try different variations of the GA as well as different population sizes and
numbers of generations.
## Discuss
1. How does the demo software work for you?
2. Should any improvements be made?
# Debrief
Reflection.
- What worked well?
- What worked badly?
- What have you learnt?
- What more do you need to learn?
