How to set up an optimization problem to minimize the sum of squared residuals using the Genetic Algorithm?

Hello, my name is Victor Assis and I am a student from Brazil. I have been working hard on a problem that I could not quite get myself, and I need your help. This is the deal:

I have to fit an equation to a data set. But my equation does have linear and nonlinear parameters. My idea is to simply use OLS, with a slightly difference: I am gonna anchor the value of my linear parameters on the value of the nonlinears. To do this I just set up the OLS classical problem, and computed the partial derivatives of the linear parameters. Once I got those, I am using this as a constraint (but I just substituted it for the values in the sum of the squared residuals).

the problem that i am facing is that I don't seem to understand how to set up this problem in Matlab. When I am trying to set up an objective function I don't understand how to define what is parameters and what is the dataset that i am gonna use.

I don't know if i made myself clear, but i will print the equation i am trying to fit to my dataset here just in case:

y= A + B*(tc-t)^(z)+C*(tc-t)^(z)*cos(w*log(tc-t)+phi)

Linear parameters that will be anchored : A,B, C Parameters estimated by the Genetic algorithm : tc,z,w,phi Dataset used: y,t (both are column vectors Nx1

I appreciate your help. Thank you very much.

Answer 1

[Star Strider]

To parameterise your function to be used in MATLAB regression functions, you need to write your function as:

% b(1) = tc,   b(2) = z,   b(3) = w,   b(4) = phi
yfit = @(b,t,A,B,C) A + B.*(b(1)-t).^b(2) + (C.*(b(1)-t).^b(2)).*cos(b(3).*log(b(1)-t)+b(4));

or, if you put A, B, and C inside the function rather than calling them as arguments, the function becomes:

yfit = @(b,t) A + B.*(b(1)-t).^b(2) + (C.*(b(1)-t).^b(2)).*cos(b(3).*log(b(1)-t)+b(4));

The nonlinear regression functions ( nlinfit, lsqcurvefit ) will compute the Jacobian for you. If you use a genetic algorithm, you will not need the Jacobian because it does not use it.

See the documentation for various functions for details in using them. You may have to experiment with different choices of initial parameter estimates in order for your regression to converge.

[Victor Assis]

Thank you Star Strider, it was very helpful. I have been reading the documentation but it does not seem clear to me what to do further. My skills on matlab are very limited.

I understood what you said, but if I don't know how to proceed because: - I need to set up a objective function that is the sum of the squared residuals using y and yfit, but should i do it in the matrix form? - I have to impose constraint over A,B,C which is

    % code
 A
 B = (X'X)^(-1)X'Y, 
 C

in which X is a matrix N (number of individuals) by 3

1 (tc-t1)^(z) (tc-t1)^(z)*cos(w*log(tc-t1)+phi) 
1 (tc-t2)^(z) (tc-t2)^(z)*cos(w*log(tc-t2)+phi)
1 (tc-t3)^(z) (tc-t3)^(z)*cos(w*log(tc-t3)+phi)
.    .             .
.    .             .
.    .             .
1 (tc-tn)^(z) (tc-tn)^(z)*cos(w*log(tc-tn)+phi)

and y is a N by 1

y1
y2
y3
y4
y5
y6
.
.
.
yN

I don't know how to write this constraint so it would work in the genetic algorithm. When I try to set up I need to assume values for the parameters tc,z,w,phi otherwise the matrix constraint won't work.

[Star Strider]

First, instead of:

 B = (X'X)^(-1)X'Y;

state this as:

B = X\Y;

However, this is a linear regression. Your function is by definition nonlinear (it is ‘nonlinear in the parameters’), so the linear regression will not identify your parameters-of-interest.

Second, I will assume here that you have a vector of time values, t, as your independent variable, and an equal-size vector of data, y. Your function returns an equal-size vector of estimates, yfit. Your sum-of-squares objective function is then:

SS = sum((y-yfit(b,t).^2);

using the second yfit function I posted in my original Answer, so you would use SS as your objective function to fminsearch. See Curve Fitting via Optimization for all the necessary details.

[Victor Assis]

Thank you again Star Strider, I much appreciate all your attention. If I could just ask one more question, because I quite do not understand how to state the constraint, when the same parameters that are gonna be changed by the algorithm composes it, so the software could fully understand it.

I attached here a part of a paper that is like a guide to my work. This part illustrates the optimization problem that I am facing, because I feel I have not been clear enough.

I got how to create the objective function, but the slaving of my linear variables on the nonlinear ones that is the deal. I know i cannot use a simple OLS because it won't identify the nonlinear parameters, so I chose to use the genetic algorithm because the problem is full of local minima that can be a trap for other optimization process, except the ga.

thank you for your help!

[Star Strider]

I would have to read the entire paper to know what you are doing. You will have to upload the PDF of the paper. (Use the ‘paperclip’ icon above the window for your original Question. It is easier to find if you put it there.)

In order for those equations to work, you first need to know the values of tc, omega, beta, and phi. Then, as stated, it becomes a simple linear regression problem, and:

b = X\y;

will give you the values of A, B, and C. (Equation 25 in the paper is the classical derivation of a linear least-squares parameter estimation problem. MATLAB implements the more efficient and accurate solution, b=X\y, that I suggest instead. What the paper says is correct, but MATLAB has a better solution for it.)

If however you already know the values for A, B, and C and need to estimate tc, omega, beta, and phi, (or if you know none of the 7 parameters), then it becomes a nonlinear regression problem.

[Victor Assis]

Thank you very much Star Rider, I could not be more grateful. I have already uploaded the paper.

The problem is that I don't know any of the 7 parameters and in order to estimate only four (tc, omega, beta and phi) I write the remaining A,B,C as a function of (tc, omega, beta and phi). And this yields what will be my constraint for the algorithm.

[Star Strider]

This is going to be a very difficult problem to solve using least squares, because as the paper notes, there are myriad local minima for the function to get trapped in.

I suggest you use a genetic algorithm instead. The MATLAB Optimization Toolbox can do this, or if you don’t have it, there are some very good genetic algorithm routines written in MATLAB that are available for free on the Internet. They are also very easy to write, but can be slightly difficult to ‘tune’ (optimising the mutation and crossover rates, for instance). Be sure that you save the fittest individual from each generation! An early ‘fittest’ individual may be the best for the entire run. The least squares objective function, SS, that I wrote for the nonlinear least squares problem a few comments earlier (or its inverse, depending on how your genetic algorithm is written), will also work as a ‘fitness function’ for your genetic algorithm.

When you get the best-fit individual at the end of the genetic algorithm run, you can then fine-tune it with a nonlinear least squares regression, using the parameters estimated by the genetic algorithm as the starting estimates for the regression.

You might also look through the MATLAB documentation and the File Exchange to see if there are Toolboxes or contributed functions that might apply to your problem.

[Victor Assis]

I do hace the Global optimization kit for the Matlab, I am trying to use it for the Genetic algorithm.

If I use the SS function as the objective one, together with the second yfit function that you wrote on your previous comments, how am I gonna slave the A,B,C parameters on the estimated values of b (the vector of nonlinear parameters.

thank you again Star Strider, you are actually saving my life.

[Star Strider]

Good point!

% b(1) = tc,   b(2) = z,   b(3) = w,   b(4) = phi,   b(5) = A,   b(6) = B,   b(7) = C
yfit = @(b,t) b(5) + b(6).*(b(1)-t).^b(2) + (b(7).*(b(1)-t).^b(2)).*cos(b(3).*log(b(1)-t)+b(4));

That should work. The SS function doesn’t change.

My pleasure! I’m glad I could help.

Answer 2

[Victor Assis]

Thank you very much Star Strider, if there is anything you might need help in the future I will be glad to return the favor!

[Star Strider]

My pleasure!

Considering that you appear to be an Economist, I just might!

[Victor Assis]

It would be my pleasure