Parameter optimization with genetic algorithms

Hey there,

I have a question concerning GA. I want to optimize several parameter at once by using a function handle. One example is the optimization for a set-up of 2 variables. Each vector consists of 10 possible values so an exhaustive search would comprise 100 trials. Instead of the exhaustive search I want to use GA which for example only needs 20 trials to find the optimal set-up. The optimization function has to be a classification function whose error value should be minimized. How can I implement the 2 variables into the function?

Thanks a lot in advance

Danyo

[Matt J]

How do you conclude that GA would only require 20 trials?

[Daniel]

I don't conclude it but I would set the maximum to 20 e.g.

[Matthew Eicholtz]

I'm not sure I understand the question. Are you asking how to do a GA on two variables?

[Daniel]

I just want to implement the GA to optimize the fitness function (classification task) which needs to optimize two variables, C and Sigma for the RBF-SVM.

[Matt J]

Your question isn't specific enough for us to know what to advise you other than "do what the GA documentation says". Have you done

 >> doc ga

What are you looking for beyond what's written there?

Answer 1

[Matt J]

This page gives an example of ga optimization over integer variables

http://www.mathworks.com/help/gads/mixed-integer-optimization.html

The example with Rastrigin's Function is a 2 variable problem and shows you how to make one of the variables integer-variable, though of course you could make them both integers if you wished.

[Daniel]

Hey Matt,

yes I know it is not very specific. I explain it a little bit more in detail. I have read all the explanations about Rastrigin's function, but It does not help me. The aim of the procceding is to get the best classification result of a SVM. Therefore two parameters, C and Sigma for the SVM have to be optimizied. Sigma is part of the following kernel function:

kval = exp(-(1/(2*sigma^2))*(repmat(sqrt(sum(u.^2,2).^2),1,size(v,1))...
    -2*(u*v')+repmat(sqrt(sum(v.^2,2)'.^2),size(u,1),1)));

This together with the parameter C influence the performance of the SVM. Since usually there is poor apriori knowledge about the task, a Gridsearch is often performed e.g. C=[1:10:100] and Sigma =[10:10:100]. After that one can refine the intervalls and go further. This however takes a lot of time. Therefore I want to use the GA, but I don't know how to write such a fitness function. The general proceeding can be examined under the following link, first result:

http://www.google.de/#output=search&sclient=psy-ab&q=svm+parameter+genetic+algorithm&oq=svm+parameter+genetic+algorithm&gs_l=hp.3..33i21l2.1155.8165.0.8344.33.27.1.5.5.2.636.6344.0j12j9j3j1j1.26.0...0.0.0..1c.1.17.psy-ab.OtM9l0h1mtE&pbx=1&bav=on.2,or.r_qf.&bvm=bv.48572450,d.bGE&fp=20cdf1fec94ce463&biw=1280&bih=675

The real Problem is that I have no clue about the fitnessfunction: I thought it could work like this:

    function dy = fitness(Sigma_Vector, C_Vector)

    global target_binary ;
    global Features ;

    SVMStruct = svmtrain(target_binary , Features , 'Kernel_function', 'rbf','RBF_Sigma', sigma, 'boxconstraint', C_Vector, 'Method', 'LS');
    Group_train = svmclassify(SVMStruct, Features ) ;
    cp_train=classperf(target_binary ,Group_train);
    dy = 1 - cp_train.CorrectRate ;

end

Sigma_Vector represents the 10 possible values for sigma and C_VEctor the 10 values for C. Instead of the Gridseach I hope that GA finds the proper set-up faster. Furthermore I don't know how the meta function should be. I thougth something like this:

 [x fval] = ga(@fitness, 2, Sigma_Vector, C_Vector)

I know it is completely wrong but maybe this helps that you know what I am talking about. Thanks a lot in advance for your help.

Daniel

[Matt J]

Daniel, If Sigma and C are the unknowns, then the fitness function must be computed in terms of them and you must combine them into one vector. If it's convenient for you, you can unpack them into separate variables inside the workspace of the fitness function

     function dy = fitness(Unknowns)

       Sigma=Unknowns(1);
       C=Unknowns(2);

      ......

     end

You must use constraint arguments and IntCon to specify the range of values sigma and C can assume. For example, if both are integers from 0 to 10, you would do,

    lb=[0;0];
    ub=[10;10];
    IntCon=[1;1];

    [x fval] = ga(@fitness, 2,[],[],[],[],lb,ub,[],IntCon);

[Daniel]

Hey thanks a lot, even if I don't really understand why one has to proceed like this. So taking you exmaple with 10 integer values from 1 to 10 for each, C and Sigma I have the following codes:

if true
  lb=[0; 0];
ub=[10; 10];
IntCon=[1; 1];
Vector=[1:1:10; 1:1:10] ;
[x fval] = ga(@fitness, 2,[],[],[],[],lb,ub,[],IntCon);

end

and for the fitness function

if true
  function dy = fitness(Vector)
C_Vector=Vector(11:20);
Sigma_Vector=Vector(1:10);
SVMStruct = svmtrain(Merkmale_MA, KLASSE_1, 'Kernel_function', 'rbf','RBF_Sigma', Sigma_Vector, 'boxconstraint', C_Vector, 'Method', 'LS');
Group_train = svmclassify(SVMStruct, Features_train_window) ;
cp_train=classperf(Klasse_train_window,Group_train);
dy = 1 - cp_train.CorrectRate ;

end

But I get an error:

" ??? Error using ==> ga at 257 Tenth input argument must be a valid structure created with GAOPTIMSET. "

What is wrong?

[Matt J]

No, your fitness function is still wrong. You should have 2 unknowns (sigma and C) not 20. Also, I had IntCon wrong. It should be

IntCon=[1,2]

[Daniel]

Yes, I have changed it: I use "Vector" for the two unknown variables but I still get the same error. I do it as follows:

if true
 lb=[0; 0];
ub=[10; 10];
IntCon=[1, 2];
Vector=[1,2]' ;
[x fval] = ga(@fitness, 2,[],[],[],[],lb,ub,[],IntCon);
end

and for GA:

if true
  function dy = fitness(Vector)
Sigma_Vector=Vector(1);
C_Vector=Vector(2);
SVMStruct = svmtrain(Merkmale_MA, KLASSE_1, 'Kernel_function', 'rbf','RBF_Sigma', Sigma_Vector, 'boxconstraint', C_Vector, 'Method', 'LS');
Group_train = svmclassify(SVMStruct, Features_train_window) ;
cp_train=classperf(Klasse_train_window,Group_train);
dy = 1 - cp_train.CorrectRate ;
end

But how does the input of the variable "Vector" for the fitness function have to be? I mean the range for C and Sigma is managed with lb and ub...

Thanks for your help

[Matt J]

You mean you're still getting "Tenth input argument must be a valid structure created with GAOPTIMSET..."? Is it possible you have an older version of MATLAB?

[Daniel]

from 2008

[Matt J]

You'll have to run "doc ga" and see if the IntCon input argument is supported in R2008. It looks like it might not be supported and you will have to upgrade if you want integer programming capability.

[Sean de Wolski]

I think it was introduced in 11b era.

[Daniel]

Isn't there any possibility to deliver the possible values for C and sigma to the fitness function so that GA can optimize them?

[Matt J]

I don't really understand why sigma is discrete. In your expression for the kernel, it looks like sigma is the variance of a Gaussian pmf. So why not allow the optimizer to vary it continuously? And could you do the same with C? If you explain a bit more about the meaning of C,we can analyze whether discrete optimization is really needed and whether the whole thing might be doable via fminunc/fmincon.

[Daniel]

Really good point Matt, of course neither of them does have to be discrete. Actually it is the complete opposite. I just choose it so that the Gridsearch does not take too long. Continuously is even better. To make it easier and not too computationally expensive I would give a certain range for both e.g. [1;10] which is meaningful. But even that is not necessary... How would I have to set up the fitness and the GA function?

[Matt J]

The setup would be the same as we've been discussing, except that you would omit the IntCon argument. I'm beginning to wonder, though, whether GA is really the appropriate tool here, as opposed to FMINCON. One reason for staying with GA is that it's not obvious whether your objective function is smooth or not. I guess it also depends on whether there are lots of local minima to avoid.

[Daniel]

There are a lot of local minima where the algorithm can stuck in. Therefore GA is a good choice. I have changed it your way and now there is another error:

if true
  lb=[0; 0];
ub=[10; 10];
[x fval] = ga(@fitness, 2,[],[],[],[],lb,ub,[]);
end

and

if true
 function dy = fitness(Vector)
Sigma_Vector=Vector(1);
C_Vector=Vector(2);
SVMStruct = svmtrain(Merkmale_MA, KLASSE_1, 'Kernel_function', 'rbf','RBF_Sigma', Sigma_Vector, 'boxconstraint', C_Vector, 'Method', 'LS');
Group_train = svmclassify(SVMStruct, Features_train_window) ;
cp_train=classperf(Klasse_train_window,Group_train);
dy = 1 - cp_train.CorrectRate ;
end

and the following error occurs:

??? Error using ==> makeState at 50

GA cannot continue because user supplied fitness function failed with the following error:

Error using ==> svmtrain at 186 Group must be a vector.

Error in ==> galincon at 18 state = makeState(GenomeLength,FitnessFcn,Iterate,output.problemtype,options);

Error in ==> ga at 289 [x,fval,exitFlag,output,population,scores] = galincon(FitnessFcn,nvars, ...

Apparently there is something wrong with the command "svmtrain"

[Matt J]

svmtrain at 186 Group must be a vector.

The error originates in svmtrain, apparently because KLASSE_1 is expected to be a vector, but isn't.

[Daniel]

It is a binary target variable with the same length as the input features of Merkmale_MA... Without GA it works, so there should not be an error..

[Matt J]

svmtrain isn't receiving the input that you think it is receiving. Use DBSTOP to trap the error and to investigate what values are being fed to svmtrain when the error occurs.

[Daniel]

I trapped it, it was because of the "global". I have fixed it but now Matlab complains that Merkmale_MA and KLASSE_1 are unkown in the fitness function cause there are not input variables to the function...

??? Error using ==> makeState at 50 GA cannot continue because user supplied fitness function failed with the following error: Input argument "Merkmale_MA" is undefined.

[Matt J]

Daniel Commented:

I figured it out. And I have changed the set-up to: options=gaoptimset('Vectorized', 'off') ; [x fval] = ga(@fitness, 2,[],[],[],[],lb,ub,[],options);

Bur Matt, this take forever, and the range for C and Sigma is not even large yet. Is there a way to speed it up? like discrete values as input for C and Sigma so that GA does only have to combine to find the best solution for the SVM?

Many thanks, I know it must sound really stupid, but I am really new to GA especially in MATLAB

[Matt J]

If your fitness function is expensive, then the process will inevitably be slow....

You could try an exhaustive search on a coarse grid sigma=C=1:5:20. From the results of that, you could then do a finer grid optimization with tighter bounds. Or you could do a continuous domain optimization with GA within the tighter bounds.