Department of Informatics, King’s College London Biologically Inspired Methods (6CCS3BIM/7CCSMBIM)
Assignment 2
This coursework is assessed. A type-written report and an animation (in total two files) need to be submitted online through KEATS by the deadline specified on the module’s KEATS webpage.
1 Problem Description
The mountain car problem is shown in Fig. 1. In this figure, it shows that a car is stuck in a valley. The goal is to escape the valley by claiming up the right hand side of the valley, i.e., to reach the flag at the top of the valley. Due to the limited engine capacity, the full power of the car is not sufficient to overcome the gravity driving the car to the goal. A solution is to drive the car left and right to build up potential energy to climb up the hill.
Figure 1: A diagram of mountain car problem.
Model:
where k = 0, 1, 2, …, ∞, denotes the time instance; para2 is a constant scalar; v(k) denotes the car velocity at time instant k; p(k) denotes the position (in the x axis) in time instant k; bound[·] is a bounding function which maintains the value of input argument within limit; a denotes the action; y(t) = 0.45 sin(para2 × p(t)) + 0.55 is the height of the car in the hill (in the y axis).
v(k + 1) = bound[v(k) + 0.001 × a − 0.0025 × cos(para2 × p(k))] (1) p(k + 1) = bound[p(k) + v(k + 1)] (2)
1
In this problem, we consider three possible actions, a ∈ {−1,0,+1} where a = 1 means full throttle to the right, a = 0 means zero throttle and a = −1 means full throttle to the left.
Assume that the velocity v(t) is in the range of v and v, i.e., v(t) ∈ [v,v] and the position p(t) is in the range of p and p, i.e., p(t) ∈ [p,p]. As a result, referring to (1) and (2), when the bounding function bound[·] applies, it caps the values of v(t + 1) and p(k + 1) at the boundary so as
v(t+1)=v ifv(t+1)
i.e., p(t) = p, it velocity v(t) is reset to zero.
2 Preparation of Matlab Files
Unzip the zip file “Assignment2 Matlab.zip”. You will get the folder structure as shown in Fig. 2. The mountain car described in Section 1 is implemented in “MountainCarModel.m”.
Assignment2 Matlab CreatAnimation
MountainCar.avi
MountainCarModel.m
New CreatAnimation.m
New GenerateData.m
New Render MountainCar.m para gen.m
Pos.mat Model
MountainCarCost.m
MountainCarModel.m para gen.m
Figure 2: Folder Structure
Remark: The two Matlab files “para gen.m” in Fig. 2 are not interchangeable.
The “model” folder contains all the files needed for the mountain car problem. Follow the following steps before answering the questions.
1. Denote s1s2s3s4s5s6s7 as your 7-digit student ID. 2
(3)
(4) An extra condition that an inelastic wall is located at p. If that car reaches the wall,
p(t+1)=p ifp(t+1)
2.
3.
In the Matlab command window, type “para gen(s1s2s3s4s5s6s7)” and then hit “En- ter”. For example, assuming your student ID is 1234567, type “para gen(1234567)”. Note: Before running this command line, point the Matlab working folder to the folder “Model” in Fig. 2.
In Step 2, Matlab will produce the parameters in the Matlab command prompt. For example, “para gen(1234567)” will produce the following:
%==========================================
para2 = 3.422;
V_LU = [-0.06136, 0.06136];
P_LU = [-1.052, 0.526];
init_v = 0;
init_p = -0.459;
T_P = 0.526;
%==========================================
Open the file MountainCarModel.m” and read the remark section which explains the meaning of these parameters. In brief,
• “V LU” is a row vector of velocity bounds, i.e., the first and second values are v and v, respectively.
• “P LU” is a row vector of position bounds, i.e., the first and second values are x and x, respectively.
• “init v” is the initial velocity, i.e., v(0).
• “init p” is the initial position, i.e., p(0).
• “T P” is the target postilion, i.e., the position of the goal in Fig. 1. In this assignment, it is set to be T P = x.
Copy the above generated parameters and replace the corresponding parameters in the file “MountatinCarCost.m”
Questions
3
4.
We will use the biologically inspired methods to solve the mountain car problem. The aim is
• A1: to generate a sequence of 100 actions, i.e., a for 100 time steps in (1), for the car to climb up the hill and reach the goal.
subject to the requirements below:
• R1: minimum moving distance (in x axis) • R2: minimum total throttle power
• R3: reaching the goal as quick as possible • R4: without hitting the wall on the left
3
Q1. Write down your 7-digit student ID as s1s2s3s4s5s6s7.
Q2. Determine and explain the cost function and decision variables. (20 Marks)
Q3. Determine and explain the constraints. (20 Marks)
Q4. Determine and explain the penalised cost function used to achieve problem goal and requirements. Explain how it works. (20 Marks)
Q5. Using “MountainCarCost.m” (with parameters updated in Step 4 of Section 2) as a template, add the penalised cost function and obtain the optimal solution using binary genetic algorithm, continuous genetic algorithm, (1+1) evolution strategy and particle swarm optimisation. Run 10 times for each algorithm. Put statistical results in a table with the format in Table 1, which shows the best cost, the worst cost, the mean and standard deviation of all costs for each algorithm. Show the modified Matlab script “MountainCarCost.m” (in text but not screen shot).
Remark: You should copy and paste “bga.m”, “cga.m”, “esp1p1.m” and “pso.m” and their associated files (e.g., gadecode.m) to the folder “CreatAnimation” for running the corresponding algorithm. “bga.m”, “cga.m”, “esp1p1.m” and “pso.m” are the main Matlab scripts for binary genetic algorithm, continuous genetic algorithm, (1+1) ES and particle swarm optimisation, respectively, which are all available in the folders under the corresponding lecture notes on KEATS.
Run Number
Binary Genetic Algorithm
Continuous Genetic Algo- rithm
(1+1) Evolu- tion Strategy
Particle Swarm Optimisation
1
2
3
4
5
6
7
8
9
10
Table 1: Statistical results.
Provide the control parameters for each algorithm, e.g., population size, Nkeep, mu- tation rate, methods of crossover and mutation, etc. (30 Marks)
Q6. Show the best solution (action sequence) from the results obtained in Table 1, i.e., in the form “a Sequence = [1, 0, −1, −1, · · · , 0, 1, 0];” and highlight its cost in Table
4
1. If more than one “best solution”, pick one among them. Verify this solution by generating a maintain car animation (“(MountainCar.avi)”) and upload it to KEATS.
To generate “(MountainCar.avi)”, the files in the folder “CreatAnimation” shown in Fig. 2 are used. Follow the following steps:
1. Point the working folder in Matlab to “CreatAnimation”.
2. Open the file “New GenerateData.m”.
3. Replace “123” in the first line “seed = 123;” with your student ID, i.e., “seed = s1s2s3s4s5s6s7;”.
4. Replace “zeros(1,100)” in the second line “a Sequence = zeros(1,100);” with the best solution you obatined above. For example, the second line will become “a Sequence = [1, 0, −1, −1, · · · , 0, 1, 0];”, which should contain 100 actions.
5. Save the changes and press the “Run” button at the the top of Matlab Editor interface.
6. It may take awhile to run the Matlab script. When it is done, it will generate two files, i.e., “(MountainCar.avi)” and “(Pos.mat)” (velocity and position data for generating the animation). Check the time stamp to make sure that these are the updated files if you have re-run the Matlab script.
7. Open the “(MountainCar.avi)” and make sure that it is viewable. Upload “MountainCar.avi” to KEATS.
(10 Marks)
Marking: The learning outcomes of this assignment are that student understands the working principle of various biologically inspired methods; develops problem-solving skills to formulate an optimisation problem by gathering information from an application; ap- plies the biologically inspired methods to deal with an optimisation problem. The as- sessment will look into the description, explanation, knowledge, problem-solving skills, understanding of the topics and application of the biologically inspired methods. When solving the problem, show/explain/describe clearly the steps and concepts with reference to the equations/theory/algorithms (stated in the lecture slides). When making com- ments, provide statements with support from the results obtained.
Purposes of Assignment: This assignment is designed in a way that you deal with a practical problem. It gives some ideas what kind of problems can be solved by biologically inspired methods. During the process of understanding the problem, it allows you to consider in-depth the information needed be used for optimisation problem formulation. Furthermore, it allows you to develop the problem solve skills by applying various types of biologically inspired methods to find the solution and know the limitations of each method.
5