WEEK 3 Flashcards
What is generalised assignment problem
If you have n workers and m jobs to complete, what encoding would you use?
Minimise the total overall time to complete all jobs
Solutions to generalised assignment problem
Encoding of n integers, each with a range 1-m jobs (each index is a worker, contains a job)
The opposite, every index is a job and inside is a worker.
How might you encode a timetable
Generate a string of 8 numbers between 1 and 16 for 4x4 grid, each index is an exam, and its value is the position in the grid
Fitness is clashes + consecs.
How can we deal with clashes in a timetable
Mutation with indirect encoding
Use clash free slots for each value at each index.
i.e. if 2nd index is 10, use 10th clash-free slot for exam 2.
Have groups of clashing exams we can look up.
Direct vs indirect encoding
Direct modifies a variable in the problem e.g. exam time
Indirect modifies the variables of a constructive heuristic e.g. clash-free exam time.
Benefits of direct encoding
Straightforward genotype (encoding) -> phenotype mapping
Easy to estimate effects of mutation
Fast interpretation of chromosome
Benefits of indirect encoding
Easier to exploit domain knowledge
Possible to encode away undesirable features
Cuts down size of the search space
Slower interpretatin
Neighbourhoods are highly rugged.
How was the antenna genome encoded?
105 bit chromosome
x1, y1, z1, x2, y2, z2 ..n
each x-y-z coord is represented by 5 bits (4+sign bit)
7 points so 3x7x5 = 105
How do we evolve programs with EAs?
Generate random programs
Evaluate programs using training data
Selectively modify population of programs using crossover and mutation etc
If a good program is found, finish.
How do we do fitness evaluation for a genetic program?
The chromosome is a program, to evaluate, we have to run it and test its behaviour over a range of potential inputs.
What do we need to make random programs
Function set F + - / IF
Terminal set T X, Y, real numbers
Associated syntax rules.
+ can have 2 children from F or T
How do we mutate a GP?
Choose a subtree at random, generate a new subtree in its place (biased towards nodes with high depth)
Subtree is equivalent to choosing a node.
5 major preparatory steps for GP
Determining the set of terminals
Determining the set of functions
Determining the fitness measure
Determining the parameters for the run
Determining the criterion for terminating a run
