Genetic algorithmd flashcards
Define the term Mutation Rate
○ Frequency
○ Mutation is a genetic operator, referring to accidental errors in copying of
genetic information
○ Required to maintain genetic diversity/prevent premature convergence
State one advantage and one disadvantage that genetic algorithms have
compared to a brute force approach [2]
Advantages:
- Quicker/takes less time to reach optimal solution/time taken for brute
force increases exponentially
- Efficiency is a measure of the average execution time necessary for
an algorithm to complete work on a set of data
Disadvantages:
- Brute force is easier to implement/code;
- Brute force could be implemented in every problem;
- Brute force hypothetically guarantees you find a solution because you
go through each solution, in genetic algorithms the solution might not
be guaranteed to be global optimal/could be local optimum
Explain the term Fitness Function and describe why it is easy to define for the
situation in the case study but may not be so easy in other situations. [4]
Fitness function: a function which takes a solution as an input, and returns a
fitness value, which is the measure of how well the solution solves the
problem/meets criteria defined by the problem
○ Easy for the case study because: shorter the tour, higher the fitness
○ Might not be easy in other situations: criteria defining fitness is harder to
determine/more parameters and variables to consider/fitness is more
subjective
○ Give example: think of the robot walking idea…is it the best solution because
it walks the quickest/most fluid/farthest?
Explain decisions, and their associated conditions, that genetic algorithms
might use to determine if the algorithm has reached convergence. [4]
○ Convergence is the point at which solutions generated by further
iterations/crossovers do not increase the fitness of the solution
○ Conditions:
○ Further iterations do not improve fitness
○ Fitness has reached a threshold/minimum value which is required
○ A maximum number of generations has been produced
Outline one decision, AND as its associated condition, that is made by an
evaluation sub-program in a genetic algorithm. [2 marks]
Should a tour be included in the mating pool
IF the fitness function returns a value that is greater than a determined value THEN
add the tour to the mating pool.
Has the algorithm reached convergence
IF the fitness function returns a value that shows no significant change over several
generations THEN convergence has been achieved and a termination condition
should be set.
Fenna is wanting to implement one of the crossover algorithms discussed in
the cases study. Evaluate the use of arrays, collections, linked lists and binary
trees as possible data structures for her implementation.
Arrays
Collections
Arrays and collections would both make good choices. Items and subsections can
be randomly accessed which in turn means elements can be easily moved/swapped
to/from other arrays/collections. This is not possible with other data structures listed.
Arrays would provide faster access times and be more memory efficient, thus helping
a GA to run faster. The length of tours is constant and can be defined once – there
is no need to change the size of the structure holding the tour. Collections allow for
their size to be changed at runtime but this costs processing speed.
Array are would be more complicated to code as lower level operations would need
to be coded where as these tend to come bundled as part of a collection.
Linked Lists
Are useful when data must be inserted/removed quickly. The nature of crossover
algorithms is such that individual items and subsections of a tour must be repeatedly
copied to/from adjacent tours. The number of steps required to do this in a LLis
much greater then that required in array/collection.
Binary trees
Are useful when data needs to be searched quickly and/or sorted hierarchically.
The nature of GA involves trialling large numbers of possibilities therefor sort items is
not possible or practical.
Identify the inputs that a fitness function takes, and the outputs it gives.[2
marks]
It takes a tour/genetic sequence as input.
It outputs a value that acts as a measures of how good the tour/sequence is with respect to
the problem.
The fitness function in the genetic algorithm that addresses the travelling
salesman problem is relatively straightforward to execute. Explain reasons
why fitness functions in genetic algorithms that address other scenarios may
be much more computationally expensive. [3 marks]
Fitness function in TS problem must determine distance between individual cities then add
them up. This is relatively straightforward to do – computationally.
In more complex scenarios – for instance GA used in designing aerodynamic items – the
computations/calculations the fitness function must perform will involve running complex
simulations (e.g. simulating wind tunnels or other physical phenomena) which in turn require
a great deal of computation.
Given a single iteration of one GA will require the fitness function to be run numerous times
on a single population, and given that there will be multiple iterations this will be very
computationally expensive.
Large amounts of memory and high numbers of calculations will be required.
Explain what the mutate sub-program does in a genetic algorithm.[2 marks]
○ Mutation is the process of making a small, “random” change to the genetic
sequence of a tour/chromosome.
○ Its purpose is to introduce and maintain diversity in the mating pool.
○ Mutation assists a genetic algorithm explore (as opposed to exploit) the
problem space.
