Department of Engineering/Informatics, King’s College London Nature-Inspired Learning Algorithms (7CCSMBIM)
Assignment 1
This coursework is assessed. A type-written report needs to be submitted online through KEATS by the deadline specified on the module’s KEATS webpage.
Q1 Binary Genetic Algorithm by Hand
a) Write down the first 7 digits of your student ID as s1s2s3s4s5s6s7. Form an 8-digit number as s2s3s4s5s6s7b1b2 where the two digits b1b2 denote your day of birth. (5 Marks)
b) Write down the cost function with two variables: f(x,y) = −(s2 +s3)x2 +
(s4 + s5)xy − (s6 + s7)y2 − (b1 + b2). In the following, we are going to find the
optimal solution for the optimisation problem: min f (x, y) using binary genetic x,y
algorithm.
(5 Marks)
c) Population Initialisation: Create a population with 8 chromosomes and list them in a table with the headings of ‘n’, ‘Chromosome’, ‘Decoded x, y’ and ‘Cost’ where n denotes the chromosome number. It is assumed that both variables x and y are in the range of −(s1 +s2) and s+s6 +s7 where s de- notes the largest digit among {s1, s2, s3, s4, s5, s6, s7}. The 8 chromosomes are [s2, s3], [s4, s5], [s6, s7], [b1, b2], [s3, s2], [s5, s4], [s7, s6], [b2, b1] where the first and the second digits represent x and y, respectively. 5-bit binary representation is employed for each digit resulting in 10-bit binary number for each chromosome.
(10 Marks)
d) Natural Selection: Show the ranked population after the process of Natural Selection with Nkeep = 4 in a table with the heading of ‘n’, ‘Chromosome’, ‘Decoded x, y’ and ‘Cost’. (10 Marks)
e) Selection: Using the cost weighting technique, show the probability table with the heading of ‘n’, ‘Chromosome’, ‘Decoded x, y’, ‘Cost’, ‘Cn = cn − cNkeep+1 ’,
n
‘Pn’ and ‘ Pn’. (10 Marks)
i=1
f) Crossover: Show the population after the process of Single-Point Crossover.
The chromosomes are selected for crossover according to the probability table
in the Selection process. The first pair of parents are chosen according to the
random numbers { s2 , 1 − s2 }. The next pair of parents s2 +s3 +s4 +s5 +s6 s2 +s3 +s4 +s5 +s6
are the rest two chromosomes in the pool of Nkeep. If the remaining number
of chromosomes is more than two. Make a remark and randomly pick two as
the second pair of parents. The crossover point for the first pair of parents is
right after the round(s2+s3 )th bit and the crossover point for the second pair 2
of parents is right after the round(s4+s5 )th bit, where the operator round(·) 2
1
rounds off the value to the nearest integer. Different colours should be used to show clearly where each part of the chromosome goes to in the crossover process. Note: The left most bit of the chromosome is the first bit. (10 Marks)
g) Mutation: Show the population in a table with the heading of ‘n’, ‘Chromo- some’, ‘Chromosome after mutation’, ‘Decoded x, y’ and ‘Cost’. The mutation rate is μ = 0.25. Calculate the number of bits to be mutated (#mutation) and randomly choose #mutation bits of your choice. Highlight the mutated bits.
(10 Marks) Q2 Denote R1 as the remainder of s2+s3+s4 . Write a Matlab script to find the minimum
9
of the function R1 + 1 in Appendix using binary genetic algorithm. All variables are
in the range of −20 and 20. The precision of the solution should be up to 4 decimal places.
a) Show your calculation getting R1. (5 Marks)
b) Determine the number of bits for each variable for binary decoding. Explain
your answer. (5 Marks)
c) Run the procedure of binary genetic algorithm for 10 times with the combi- nations of population size (p or Npop): 10, 50 100 and μ : 0.1, 0.5, 0.9. 9 combinations in total. Obtain the best the worst costs of the 10 runs for each combination; the mean and the standard deviation of the best the worst costs for the 10 runs for each combination. Specify other control parameters of binary genetic algorithm used in this question, e.g., number of iterations, population size, Nkeep, methods of crossover and mutation, etc. List the results in Table 1 and Table 2. (20 Marks)
d) Comment briefly on the results obtained (with support/evidence) in terms of reliability and sensitivity of the binary genetic algorithm. (10 Marks)
2
“Runs” Number
p = 10 μ = 0.1
p = 10 μ = 0.5
p = 10 μ = 0.9
p = 50 μ = 0.1
p = 50 μ = 0.5
p = 50 μ = 0.9
p = 100 μ = 0.1
p = 100 μ = 0.5
p = 100 μ = 0.9
1
2
3
4
5
6
7
8
9
10
Mean
Standard Deviation
Best Cost
Worst Cost
Table 1: Statistics of 10 runs.
Mean of “Mean”
Standard deviation of “mean”
Mean of “Standard Deviation”
Standard deviation of “Standard Deviation”
Mean of “Best Cost”
Standard deviation of “Best Cost”
Mean of “Worst Cost”
Standard deviation of “Worst Cost”
N = 2 + s2 + s3 N
F1: |xi| + cos(xi) i=1
N
F2: |xi| + sin(xi)
i=1 N
F3: x2i i=1
N−1
F4: 100(xi+1 − x2i )2 + (1 + xi)2
i=1
Table 2: Overall Statistic.
Appendix 1: Test Functions
3
N
F5: 10N + (x2i − 10 cos(2πxi))
i=1
N x2i N
F6: 1 + 4000 − cos(xi) i=1 i=1
sin2 x2 + x2 − 0.5 12
F7: 0.5 +
F8: (x21 + x2)0.25 sin 30((x1 + 0.5)2 + x2)0.1 + |x1| + |x2|
F9: −x1 sin|x1 −(x2 +9)|−(x2 +9)sin|0.5×1 +x2 +9|
In the above test functions, all xi, i = 1, 2, · · · , N, are decision variables.
Marking: The learning outcomes of this assignment are that students will understand the fundamental principle of binary genetic algorithm (BGA) and appreciate the BGA performance through the evaluation of some benchmark functions. The assessment will look into the knowledge and understanding on the topics. When answering the questions, show/explain/describe clearly the steps with reference to the equations/theory/algorithms (stated in the lecture slides). When making comments, provide statements with support from the results obtained.
Purposes of Assignment: This assignment is designed to reinforce the understand- ing of Genetic Algorithm by going through every single step and to get an idea how it performs when applying the Genetic Algorithm to solve a numerical problem. After do- ing this assignment, students should be aware of the capability and limitations of Genetic Algorithm and thus know what to note when applying it.
1 + 0.1(x21 + x2)
4