In this exercise a set of optimization problems will be studied with the help of MATLAB. The problems are stated as rather simple mathematical functions and they shall be solved using different optimization techniques in order to assess the pros and cons of different optimization methods. Throughout this exercise we assume that the derivatives of the functions are not known. Therefore, the gradient based methods need to use numerical approximations of the gradients. This is because that for real world engineering problems it is often hard to obtain analytical derivatives.
Give your answers directly in this document. When you are finished convert the file to pdf and upload it to your group folder on LISAM. Give your answers clearly so your peer group can understand them. Name the file logically, ex. Tmkt48_assignment1_group_XX.pdf.
Your student group will then be assigned the report of another group for assessment, and the other group will assess your report. Both groups should read the other groups report and then meet and discuss their reports. You are required to write down some comments on the report you are assessing and upload them to your folder in LISAM. The examiner will manage the division of assessment groups. There is also a seminar when you can meet and discuss your reports. A guide to peer-assessment can also be found at the course website. Please read the guide carefully.
How to get started
• Create a folder for this course e.g. named TMKT48 in your home catalogue (e.g. Z:\TMKT48)
• Copy the files for assignment1 to your home catalogue and unpack the files into the same folder.
• Start MATLAB
• In MATLAB, at the top of the window, set Current directory to the folder you extracted the files to (Z:\TMKT48\Complex)
• Start with the first task.
• There might be some hints after each problem. Therefore, read the whole problem statement including the hints before you try to solve the problem.
• For many of the problems you are requested to run 10 optimizations to get some statistics to analyse. It is therefore convenient to create a for-loop that does everything in one go.
• GOOD LUCK!
 
Problems to Optimize
Task 1. Investigate problems
• Investigate the problems that will be optimized using different algorithms in the following tasks in this assignment. The problems can be found in the file problems-to-optimize_assignment1.pdf.
• Fill in in the first two columns in the matrix in task 15.
• YOU DO NOT NEED TO OPEN MATLAB FOR THIS TASK
 
Task 2. Introduction to MATLAB
Now you can use MATLAB. Create a mathematical function that sums the values in the input vector. Then fill in the values in the table below:

x1 x2 sum
0 0
1 -2
2 3

Hints:
The creation of a function is done by creating an m-file.

Create a new m-file and fill it with a code similar to the one below:

A function is a file that returns a value given a vector of values. You run the file above by writing the following in the command window

x=[1 -2]

myAwesomeName(x)

This will tell MATLAB to call the file myAwesomeName with x as input. The two values (1 and -2) are set to the variables x1 and x2 on rows 2 and 3 respectively. x1 and x2 are then added together into a variable y on row 4.

Row 4 is the last row of the file and the file will not be evaluated further. Instead, the variable y will be returned from the function, and written in the command window of MATLAB.

 
fmincon
Task 3. Minimize the function Rosenbrooks banana or DeJong 2 with fmincon
Solve the function known as Rosenbrooks banana or DeJong2 using MATLABS’s built-in method fmincon (constrained optimization). Use a couple of different starting points, for example [-2 -2], [2 2], [0 2], [2 0] and [0 0].

Document your optimization runs in this table and then answer the questions below:
Starting point x* obtained f(x*) NoEvals NoIterations
[-2 -2]
[2 2]
[0 2]
[2 0]
[0 0]

Questions:
a) What is the optimal value and where is it located?
Answer:

b) Approximately how many function evaluations are needed?
Answer:

Hints:
Type ‘help’ and then the name of the method to get information on how it is used. These methods call number of function evaluations for function count, or something similar.
In order to get more detailed results out of the optimization call the function with left hand arguments, i.e.
[x,f,flag,output]=fmincon(‘dejong2’,[-2 -2])
The number of function evaluations can for example be f ound in output.funcCount

For fmincon you need to pass some empty matrices for the constraints if you want to use lower and upper bounds of the variables but not any other constraints. You also need to specify that you want to run its gradient-based algorithm
options=optimoptions(‘fmincon’,’algorithm’,’sqp’)

[x,f,flag,output]=fmincon(‘dejong2’,[start_point],[],[],[],[],[lower_bound],[upper_bound],[],options) 
Task 4. Minimize the function DeJong3 with fmincon
Solve Dejong3 using Matlabs built-in function fmincon. Use the starting points [2.5 2.5 2.5], [2.5 2 -2] and [2 -2 -2]. Summarize your result in a table as before.

Starting point x* obtained f(x*) NoEvals NoIterations
[2.5 2.5 2.5]
[2.5 2 -2]
[2 -2 -2]

Questions:
a) What results do you obtain from the different starting points and why?
Answer:
 
Task 5. Solve the Peaks function using fmincon.
Find the minimum of the peaks function by solving the following problem:

A function called peaks_opt.m has been provided that implements the function so that it could easily be used together with the optimization routines.

Starting point x* obtained f(x*) NoEvals NoIterations

Questions:
a) Solve the problem using fmincon. Run 9 optimization with different starting points evenly spread in the design space, e.g. [2,2], [1,1], [-2,2], [-1,1], [2,-2] , [1,-1], [-2,-2], [-1,-1], [0,0]. Present your results in a table as in task 3 and 4. Which results do you obtain and why?
Answer:
 
The Complex Method
Task 6. Solve DeJong2 using the complex method.
The function is coded in the file dejong2.m. Run 10 optimizations so you are sure that you have identified the optimum. Document your results in a table of the form below. See hints on the next page to see how you call the Complex algorithm

Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5
6
7
8
9
10

Questions:
a) Where is the optimum located, and what is the optimal value, i.e. x* and f(x*)
Answer:

b) Approximately how many iterations does it take to reach that point?
Answer:

c) Approximately how many function evaluations does it take to reach that point?
Answer:

d) Why are the number of iterations and function evaluations not the same?
Answer:

e) What is the approximate relation between number of iterations and function evaluations?
Answer:

f) In the output from the optimization:
What is the meaning of maximum and minimum function value?
What is the meaning of min(x) and max(x)?
Answer:

g) Investigate the progress of the optimization by plotting the evolution of the optimization variables and the objective function as functions of the number of iterations, for one of your optimization runs. (Paste the plots into this document.)
Answer:

h) Create a movie of the progress of the optimization. (You can look at it but not include it in your report)

Hints:
Make the directory where you have the complex files the current directory of MATLAB and open the file complexrf.m and dejong2.m in the editor. Both these files include functions that could be executed as any MATLAB function if they are in the current directory or in the MATLAB Path.
Type help complexrf in order to get help on how to use the complex method.
You can solve the problem and plot the progress of the optimization method with the following commands:
x_low =[-2.048 -2.048]; x_up=[2.048,2.048];
[x,f,xhist,fhist] = complexrf(‘dejong2’,x_low,x_up)
plot(xhist(:,1))
If you cut the text above and paste it into MATLAB, you may need to change the “ ’” signs around ‘dejong2’, as they might not be recognized by MATLAB.

The number of iterations and function evaluations can be found by extracting six entities from complexrf:
[x,f,xhist,fhist,flag,output] = complexrf(‘dejong2’,x_low,x_up)
The iterations and function evaluations can be found by writing output.iterations and output.funcCount.

To create the animation of the progress of the Complex method, use the m-file cmplx_mov.m. This problem merely has two design variables so it can easily be plotted. The call to cmplx_mov could look like this:
mov=cmplx_mov(xhist,4,1,2)
To play the movie type movie(mov).

 
Task 7. Solve DeJong3 using the complex method.
Use the Complex method to solve the problem “DeJong 3”. The function is implemented in the m-file dejong3.m.

The function floor rounds the variable xi to the nearest integer towards minus infinity. PLEASE note that there are 3 OPTIMIZATION variables for this problem.

Run 10 optimizations and document your result in a table as previously. Then answer the questions below.
Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5
6
7
8
9
10

Questions:
a) Which optimal solutions do you obtain?
Answers:

b) What is the optimal function value and what is the global optimal point/points, i.e. (x1, x2, x3) and f(x)?
Answers:

c) Turn off the randomization factor and the forgetting factor and run 10 more optimizations. How do these results differ from the ones previously obtained? Why is that so?
Answers:
Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5
6
7
8
9
10

Hints:
The default parameters of complexrf are 0.3.
To change the default parameters of complexrf call the method as:
complexrf(‘dejong3’,x_low,x_up, ‘rfak’,0, ‘gamma’,0)
 
Task 8. Solve the peaks function using the complex method.
Find the minimum of the peaks function:

A function called peaks_opt.m has been provided that implements the function so that it could easily be used together with the optimization routines.

Questions:
a) Solve the problem using the Complex method. Run 10 optimizations and summarize the results in a table.
Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5
6
7
8
9
10

b) Can you improve the results of the method by using more points in the complex? Run 10 optimizations with k= 8. Compare the results to the one from a) and write down your comments.
Opt nr. x* obtained f(x) NoEvals NoIterations 1 2 3 4 5 6 7 8 9 10 Answers: c) Investigate what happens when the randomization factor is turned off. Run 10 optimizations with k=4 and rfak = 0 and compare to the results from a). Opt nr. x obtained f(x*) NoEvals NoIterations
1
2
3
4
5
6
7
8
9
10
Answers:

Hints:
To change the default number of points in the complex (k=2*no opt variables) call the method as:
complexrf(‘peaks_opt’,x_low,x_up, ‘k’,6)

In order to change the randomization factor, call the method as:
complexrf(‘peaks_opt’,x_low,x_up, ‘rfak’,0)
 
Genetic Algorithms
Task 9. Solve Dejong2 using a real encoded Genetic Algorithm.
Use the MATLAB script GA_real_obj.m that implements a GA using the Geatbx for MATLAB. Start by studying the script and make sure that you recognize the basic principle of a GA. For this problem make sure that the GA toolbox is in the current directory or is added to the MATLAB path.
Run the optimization 10 times, summarize the results in a table, and answer the following questions.
Opt nr. x* obtained f(x*) NoEvals NoGenerations
1
2
3
4
5
6
7
8
9
10

Questions:
a) Where is the optimum located and what is the optimal value?
b) What is the formula for calculating the number of function evalautions from an optimization using a GA?
c) What does the final population look like? Plot the final population (Chrom) and paste it in the document together with your comments.
d) Track the evolution of the population by plotting the parameter values as well as the objective function value for the best individual.
e) Run the optimization with different number of individuals and for different number of generations. How do these changes affect the performance of the algorithm in terms of identifying the global optimum, convergence of the population, and the number of function evaluations needed?

Hints:
Make the directory where you have the GA files the current directory of MATLAB and open the file ga_real_obj.m in the editor. Rows 15-19 contain the parameters of the algorithm.

The algorithm can be called as:
[x_opt,y_opt,n_eval,BestInd,Best,Chrom]=ga_real_obj(‘dejong2’,x_low,x_up)

The final population could be studied by looking at or plotting the variable Chrom. Try both to write just Chrom at the Matlab prompt and also plot(Chrom(:,1),Chrom(:,2), ‘. ‘).
The best objective function value from each generation is stored in Best, and the parameter values for the best individual in BestInd. Try plot(Best) and plot(BestInd).
You can change the y-axis of the graph so that it has logarithmic scaling. This will make it easier to see the progress of the optimization. To do that click on the left most arrow on the figure toolbar (Edit plot), and then double click on the y-axis. Then select log scaling.
In the directory /geatbx/geadocuhti there is an extensive documentation of the toolbox, and also a good documentation about how genetic algorithms work in general. Read that to learn more about GA:s! 
Task 10. Solve Dejong2 again using a binary encoding Genetic Algorithm.
Use the script GA_bin.m that implements a binary encoded GA. Start by studying the script, and then run 10 optimizations.
Questions:
a) What optimum do you obtain?
b) What does the optimum point look like in the Genotype and in the Phenotype space? (Present the bits and the real numbers)
c) Change the precision in the encoding of the variables. In the first run you used 12 bits per variable. Try using 4, 8, 16 and 20. What difference does that make and why? Change the number of generations if needed.

Hints:
You can change the objective function on row 19 and the number of variables on row 21.
In order to go from the genotype to the phenotype space use the function bin2real(Chrom, FieldD).
FieldD is the field description that describes how the real number is decoded as a string of bits. For each variable FieldD contains: [the number of bits, lower bound, upper bound, 0 or 1 for bin or Gray encoding, 0 or 1 for scaling, 0 or 1 for inclusion or exclusion of lower bound, 0 or 1 for inclusion or exclusion of upper bound], see also bindecod.m.

Answers:
 
Task 11. Solve Dejong 3 using a Genetic Algorithm.
Questions:
a) State which method and parameter settings that you have used.
b) What results have you achieved? Present a table of 10 different runs.

Answers:
 
Task 12. Minimize the peaks function using a Genetic Algorithm.
A function called peaks_opt.m has been provided that implements the function so that it could easily be used together with the optimization routines.

Questions:
a) What results have you achieved? Present a table of 10 different runs.

Answer:
Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5

 
Particle Swarm Optimization
Task 13. Solve DeJong2 using Particle Swarm Optimization
MATLAB also has an inbuilt Particle Swarm Optimization (PSO) algorithm. Solve DeJong2 (Rosenbrock’s banana) using this optimization algorithm.

[X,FVAL,EXITFLAG,OUTPUT] = particleswarm (@functionName,NoOfVariables,LowerBounds,UpperBounds)

[x,f,flag,output]=particleswarm(@dejong2,2,[-2.048 -2.048],[2.048 2.048])

The number of iterations and function evaluations are included in the OUTPUT struct and can be called by OUTPUT.iterations and OUTPUT.funccount

The link below explains how MATLAB’s PSO algorithm works:
https://se.mathworks.com/help/gads/particle-swarm-optimization-algorithm.html?s_tid=gn_loc_drop

Questions:
a) What results have you achieved? Present a table of 10 different runs.

Answers:
Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5
 
Task 14. Solve the peaks function using PSO.
Find the minimum of the peaks function.

A function called peaks_opt.m has been provided that implements the function so that it could easily be used together with the optimization routines.

Questions:
a) What results have you achieved? Present a table of 10 different runs.

Answer:
Opt nr. x* obtained f(x*) NoEvals NoIterations
1
2
3
4
5
 
Performance
Task 15. Compile your results.
Fill in the matrix below using the data that you have compiled in previous tasks:

Problem Uni- or Multimodal? Nr of design variables Minimum function value, f(x). Optimal design variable values, x.
DeJong 2
DeJong 3
Peaks
 
Task 16. Calculate performance indices for DeJong2.
Calculate the performance indices for the four algorithms for DeJong2. You should have the results from the previous tasks, so you should not need to perform new optimizations.

a) Compare the algorithms by calculating the number of times the global optimum have been found, the number of times it fails completely (e.g. gets stuck on variable limits), and how many function evaluations it needs for each method. Present these results in a table of the form below:
b) What conclusions can you draw from the table in a)?

Hints:
The value that should go into the rightmost column of the table in a) can be calculated by calling the calcPerfInd.m file with the %Global optimum and Mean no evals numbers as arguments.
Example: Let’s say that 40% of the fmincon optimizations return the global optimum and that it requires 30 function evaluations. calcPerfInd.m should then be called as below:
calcPerfInd(0.4,30)

Answer:
Method % Global optimum % fail Mean no evals Performance Index
Complex
fmincon
GA
PSO

 
Task 17. Calculate performance indices for Peaks.
Calculate the performance indices for the four algorithms for Peaks

a) Compare the algorithms by calculating the number of times the global optimum have been found, the number of times a local optima has been found, the number of times it fails completely (e.g. gets stuck on variable limits), and how many function evaluations it needs for each method. Present these results in a table of the form below:
b) What conclusions can you draw from the table in a)?

Answer:
Method % Global optimum % local optimum % fail Mean no evals Performance Index
Complex
fmincon
GA
PSO

 
Task 18. Reflections
What are your reflections on the different methods after you have solved these problems?