L5 - Encoding / Representation Flashcards
Define what is meant by encoding?
Encoding is the way in which we represent solutions such that they can be analysed, interpreted and evolved by algorithms.
We want to encode our solution as a number of genes or nodes within a certain length.
What is encoding / representation considered one of the biggest issues in Evolutionary Computing?
There can be a huge variety of encodings of solutions to a problem. Thus, the choice of encoding determines the search space.
Also, a chosen encoding schema will generate a different fitness landscape than another.
What are some types that we can encode our solutions with?
Integers, Real Numbers, Binary Strings.
What does it mean if we have a K-ary encoding of length L?
It means that for every element in the list, the gene can be a value between 0 and K.
Given the solution [A,B,C,D,E,F] in the TSP where K = A to F and the program contraint is only visiting each node once. Perform a single gene mutation such that the child is an invalid solution. Why is the child invalid?
[A,B,C,D,E,D]
We have visited gene D twice. Given the problem constraints of the TSP, this is not a viable solution.
Given the solution [A,B,C,D,E,F] and K is the A to F, perform a swap gene mutation such that the child is a valid solution.
[A,B,F,D,E,C]
Swapped F and C to generate a mutated solution.
When performing a Crossover mutation on 2 solutions, in what scenario would the child solutions be rendered invalid?
If in both solutions, we visit one of the genes multiple times, thus, not accounting for all the possible genes within K.
What are the 2 solutions to a 1 point cross over generating invalid child solutions?
- Implement a better crossover function.
- Implement a crossover with a fix.
What is meant by solution validity in regards to the problems constraints?
A problem will have constraints that the solutions must adhere to. For example, in the TSP, each node must be visited once and only once. Thus, any solution must contain all values of K once and only once.
Define the following mutation functions:
Single Mutation
Swap Mutation
Crossover Mutation
Single Mutation : Choose a gene at random and swap it for some random K.
Swap Mutation : Swap 2 genes within the solution.
Crossover : Given 2 parents, create 2 child solutions from swapping the tails of solutions at certain points. This can be 1-point, 2-point, or uniform using a binary mask.
Define indirect encoding… Give an example of how indirect encoding would be used on generating a timetable for exams.
Indirect encoding defines a process of generating solutions based on a set of rules.
For example, when generating an exam timetable, we want exams of specific modules not to be on the same date or consecutive days. Thus, we define a process which generates solutions based on these rules.
Define the difference between Direct and Indirect encoding?
Direct Encoding : Parameters / Genes of a solution are directly input in a one to one mapping. This direct approach is often used in simpler solutions.
Indirect Encoding : Solutions are generated and encoded based on a set of rules. This is a more abstract approach for more complex problems where we want to encode away from solutions with undesirable features.
What are the pros and cons of direct and indirect encoding?
Direct:
- Fast interpretation, Simpler.
- Doesn’t reduce search space area of interest.
Indirect:
- Cuts down size of search space, remove solutions with undesirable features.
- Slow interpretation.
Give an example of a real world encoding problem…
The nozzle.
Split the nozzle into sections Z1 and Z2, such that L was Z1 + Z2. Each section could fluctuate in diameter between 0.1 and 2, thus K was 2.
From this, we can see how the real world object of a nozzle could be broken down into the core components of K and L of a genetic solution.
