CS计算机代考程序代写 ant algorithm Department of Engineering/Informatics, King’s College London Nature-Inspired Learning Algorithms (7CCSMBIM)

Department of Engineering/Informatics, King’s College London Nature-Inspired Learning Algorithms (7CCSMBIM)
Assignment 2
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.
In the following questions, s1s2s3s4s5s6s7 denotes the first 7- digits of your student ID. Please write down your student ID. Show the steps in your calculations when you answer the questions (As an example, you may refer to the solutions of tutorial questions).
Q1. Explain how tournament selection works in the selection process of the binary genetic algorithm with an example.
[5 Marks]
Q2. The binary genetic algorithm with Nkeep = 0 and μ = 0.1 is employed to minimise the function f(x, y) = xy. The representation of chromosome is [x, y] where 10 ≤ x ≤ (10 + s1 + s2 + s3) and −5 ≤ y ≤ (−5 + s4 + s5 + s6). Each decision variable is represented by a 4-bit binary string. The initial population is given in Table 1.
Chromosome 10001100 01101011 01111010 01010100
Table 1: Initial population in Q2. a. Obtain the probability table for cost weighting selection.
b. Considering a random number generator that a sequence of random numbers {0.7, 0.2, 0.8, 0.6, 0.9, 0.2, 0.1} (the left most number is generated first) is generated, which two chromosomes will be selected as parents to undergo crossover?
[5 Marks]
c. Based on the selected parents in Q2.b, obtain the offspring when double-point crossover is employed where the first crossover point is after the 3rd and the second crossover point is before the 7th bit of the chromosome.
[5 Marks]
d. How many bits in the population will be mutated if elitism is NOT implemented?
Questions continues on Next Page
1
[25 Marks]
[5 Marks]

Q3. Thebinarygeneticalgorithmisusedtomaximisethefunctionf(x,y)=(x−y)2 subjecttoa constraint that x ≥ 10y.
a. Formulate as minimisation problem and determine the penalised cost function.
[10 Marks]
b. Considering that 5 ≤ x ≤ 5+(s1 +s2 +s3) and −10 ≤ y ≤ 10+(s4 +s5)(s6 +s7), determine the number of bits for each variable such that a precision of 2 decimal places is achieved. Determine the representation of chromosome and the total number of bits of it.
[10 Marks]
Q4. (1 + 1)-ES and (1, 1)-ES are employed to minimise the function f (x1 , x2 ) = x1 − x2 . The mutation process is given as below:
′
Offspring: xj(t)=xj(t)+σj(t)Nj,j=1,2,
′ 􏰀 s1+s2 􏰁 Strategyparameter: σj(t)=0.5 1+s +s +s σj(t),j=1,2,
123
where t denotes the generation number, Nj = j(3−j) for all t. Assuming x1(t) = 2, x2(t) = −1, σ1(t) = 0.1 and σ2(t) = 0.3 at the tth generation, determine the population and strategy parameter at the next generation for both (1 + 1)-ES and (1, 1)-ES.
Questions continues on Next Page
2
[20 Marks]

Q5. A graph of 5 nodes is shown in Figure 1. The information of the edge distance (dij) and pheromone concentration (τij (t)) at the tth generation is given along each edge in the format of “dij,τij(t)”. The Simple Ant Colony Optimisation with 2 ants is employed to find the shortest path from source node 1 to destination node 5. Each node is allowed to be visited once.
1
2 s3,1.5 3
20, 0.2 5
4
Figure1: Agraphof5nodes. si =si +1foralli.
a. Determine the cost f(xk(t)) of two ants: x1{1,2,4,5} and x2{1,4,2,3,5}.
b. Based on Q5.a, determine the pheromone concentrations τ24(t+1) and τ45(t+1) where the 􏰀􏰁
pheromone concentrations are evaporated according to τij(t) ← 0.5 1 + s1+s2 s1 +s2 +s3
2
andareupdatedaccordingtoτ (t+1)=τ (t)+􏰃∆τk(t), ij ij ij
Marking: The learning outcomes of this assignment are that students understand the fundamental concepts and working principle of various biologically inspired methods and are able to apply them to solve numerical questions. The assessment will look into the knowledge and understanding on the topics. When answering the questions, show/explain/describe clearly the steps and concepts with reference to the equations/theory/algorithms (stated in the lecture slides).
Purposes of Assignment: The purpose of this assignment is to recall and reinforce the algorithms learnt from lectures and apply them on some numerical problems. After doing this assignment, students should get better ideas how each algorithm work.
Final Page
[5 Marks]
τij(t)
k=1 􏰂 1 if edge (i,j) occurs in path xk(t),
∆τk(t)= f(xk(t))
ij 0 otherwise.
3
[10 Marks]
s1, 0.7
s4, 1.7
s5, 1.6
s2, 1.1
s6, 2.2
s7, 0.9