6G6Z1109: So+ware Agents and
Op8misa8on
Term 2, Lecture 8: Assignment, and
compara8ve analysis
Assignment help
• Your solu8on will require classes to represent a
GA individual, the popula8on, and the ordered
crossover operator (as with the TSP solu8on)
• It also needs the classes for the circle placement
algorithm (Bunch, Circle, and Point). You
should not need to make many changes to this
code…
• The main applica8on should create a Bunch
object for each of the three algorithms – this
allows you to easily display all three
Assignment help
• Your Bunch class should contain a
geneticPlace()method, which takes in all of the
parameters of the GA (that is, it should be en8rely self-
contained)
• It will be much easier to implement if you have already
successfully implemented the Population class (as
in a previous lab)
• Given that we are using an order-based encoding, it’s
no surprise than an individual’s genome should be a
list of integers – the ordering of the set of circles
• That is, a genome of “21345”, specifies circle 2 to be
placed first, followed by 1, 3, 4, then 5
Assignment help
• When evalua8ng an individual’s genome in the fitness
func8on, you should realise that you can actually reuse
the orderedPlace() method that we have already
encountered
• You can overload this method, by providing a version
that takes in an ordering (encoded as an array of
integers…) and places the circles in that order
• The fitness func8on in my model answer (located in
the Individual class) is extremely short; it simply
creates a temporary Bunch of circles, orders them
according to the genome, calls the method to compute
the boundary, and then returns this as the fitness…
Assignment help
• When doing a compara5ve analysis of your gene8c
algorithm (i.e., comparing with greedy search), it is
important to specify the parameters used, and
inves8gate the effect of varying these (see previous
lecture)
• Also, it is important to perform several runs of your
GA, and then take the average best fitness found, in
order to ensure that you get a representa8ve sample
• How many runs is “enough”? – probably around 30-50
• It is also interes8ng to plot the convergence of your
algorithm over 8me
R. Olson
Best
Worst
Average
Encodings
• How we encode a solu8on to our problem is
also vital to the success of the GA
• Ideally, our encoding will be expressed as a
linear string or sequence of items, such as
characters, integers, reals, etc.
• An encoding might directly represent the
objects that are evolving (e.g. strings of text),
or indirectly represent the presence or
absence of objects with certain adributes
Indirect encoding example
• Consider the following problem: we wish to
pack for our holiday, and we have a suitcase
with a specific capacity (luggage weight limit)
• We have a set of items, each of which has a
weight and a u5lity value (that is, how useful
we find it)
• We wish to find the set of items that
maximises our u8lity, whilst staying within the
weight limit
U8lity: 8
Weight: 4 U8lity: 5
Weight: 5
U8lity: 9
Weight: 7
U8lity: 10
Weight: 5
U8lity: 8
Weight: 4 U8lity: 5
Weight: 5
U8lity: 9
Weight: 7
U8lity: 10
Weight: 5
How do we encode a solu5on to this problem?
Choosing an encoding
• We need to work out what the problem is asking
of us…
• It needs us to find a subset of items, subject to
certain constraints
• That is, each item is either “in” or “out” of the
suitcase
• A solu8on is a candidate list of items, which is
then assessed according to the criteria
• In this case, if we order the items, a simple binary
encoding will suffice
U8lity: 8
Weight: 4
U8lity: 5
Weight: 5
U8lity: 9
Weight: 7
U8lity: 10
Weight: 5
We can now use a simple binary
encoding on the ordered list of items,
so 1001 represents “include toothbrush
and suncream”, whilst 0111 represents
“flip-flops, bikini and suncream”
U8lity: 8
Weight: 4
U8lity: 5
Weight: 4
U8lity: 9
Weight: 7
U8lity: 10
Weight: 5
We call a sequence the genotype, as it
represents an individuals “gene8c
code”. What a genotype represents or
builds is called the phenotype, and it is
this “body” that we assess or assign a
fitness value to.
A greedy algorithm
Calculate the profit-to-weight ra5o for each item
While (we can select an item)
Select item with highest PTWR that keeps us below capacity
A greedy algorithm
Calculate the profit-to-weight ra5o for each item
While (we can select an item)
Select item with highest PTWR that keeps us below capacity
Profit/weight
A greedy algorithm
Calculate the profit-to-weight ra5o for each item
While (we can select an item)
Select item with highest PTWR that keeps us below capacity
Capacity=9 Space=9
A greedy algorithm
Calculate the profit-to-weight ra5o for each item
While (we can select an item)
Select item with highest PTWR that keeps us below capacity
Capacity=9 Space=7
A greedy algorithm
Calculate the profit-to-weight ra5o for each item
While (we can select an item)
Select item with highest PTWR that keeps us below capacity
Capacity=9 Space=4
A greedy algorithm
Calculate the profit-to-weight ra5o for each item
While (we can select an item)
Select item with highest PTWR that keeps us below capacity
Capacity=9 Space=0
Total profit: 14
A gene8c algorithm
We use a simple binary encoding scheme, with a binary vector
x=[x_1, …, x_n] to represent n items, where x[i]=1 if the item is included
in the suitcase, and x[i]=0 if it is not
The fitness func8on for a given solu8on, x, is as follows:
We denote the profit of items by p[i], and the weights by w[i]
total weight = 0
for each item, x[i] // weigh items in suitcase
if x[i] = 1 then add w[i] to total weight
if total weight <= total capacity fitness = 0 for each item, x[i] // add profits together if x[i] = 1 then add p[i] to fitness return fitness else // over capacity return capacity-total weight A gene8c algorithm We use a simple binary encoding scheme, with a binary vector x=[x_1, ..., x_n] to represent n items, where x[i]=1 if the item is included in the suitcase, and x[i]=0 if it is not The fitness func8on for a given solu8on, x, is as follows: We denote the profit of items by p[i], and the weights by w[i] total weight = 0 for each item, x[i] // weigh items in suitcase if x[i] = 1 then add w[i] to total weight if total weight <= total capacity fitness = 0 for each item, x[i] // add profits together if x[i] = 1 then add p[i] to fitness return fitness else // over capacity return capacity-total weight Penalise “illegal” solu8on, by essen8ally giving it a nega8ve fitness Next lecture • Next week: (Remember, this lecture is next Monday) - advanced topics in GAs • This week’s lab: Knapsack GA (but only move onto this once you have finished your assignment!) This lab is s8ll important, though…