How should I choose the FunctionTolerance of genetic algorithm optimisation?

I am optimising MRI experiment settings in order to get optimal precision of tissue property measurements using my data.

To optimise the settings (i.e. a vector of numbers) I am using the MATLAB genetic algorithm function (ga()). I want to compare the final result of different optimisation experiments, that have different parameter upper bounds but I do not know how to choose the FunctionTolerance.

My current implementation takes several days. I would like to increase FunctionTolerance so that it does not take as long, yet still allows me to make reliable comparisons of the final results of the two different optimisation experiments. In other words, I do not want to stop the optimisation too early. I want to stop it when it gets close to its best results, but not wait for a long time for it to refine the result.

My cost function is based on the measurement precision. Firstly the cost function simulates data (signal time courses) for the given MRI experiment settings, using a Monte Carlo approach with 1000 different noise seeds. Fitting is performed on these 1000 time course. This gives a distribution of 1000 measurement errors. My cost function value is the measurement efficiency = true value / ( (measurement error standard deviation)*sqrt( length of simulated MRI experiment) ). The tissue property, the measurement errors and the length of the simulated MRI experiment are all in units of seconds

Is there a general rule for choosing FunctionTolerance or does it depend on what is being optimised?

Answer 1

[Alan Weiss]

I recently answered a customer support problem that sounded like yours. (Maybe it was you? The support was anonymous from my end.) Here is what I said, slightly edited:

You are looking to get more efficiency from ga by stopping early. This can be effective for some problems, but it would probably be even more effective to use a different solver.

I suggest that you consult the following documentation: Implementation Notes (In particular, “However, no solver employs an algorithm that can certify a solution as global.”) Choosing Between Solvers for Nonsmooth Problems (In particular, “ga has little supporting theory and is often less efficient than patternsearch or particleswarm.” and in the following table note that there is “No convergence proof” for ga.)

In summary, you cannot have confidence in the results of ga, either for obtaining a local solution or a global solution.

If your problem is smooth (I cannot tell from your description), then you are likely to get better results using an Optimization Toolbox solver such as fmincon. At least that solver is likely to return a local solution.

If your problem is not smooth, then patternsearch is the recommended solver (see Table for Choosing a Solver). And patternsearch is likely to give a local solution at least.

There is some documentation on obtaining solutions faster or with higher confidence, not tied to any particular solver, though some are useful only for smooth problems. See Improving Results.

Sorry not to have a more positive response.

Alan Weiss

MATLAB mathematical toolbox documentation

[funkmunk]

Thanks a lot for the detailed reply. I hadn't submitted a customer support problem but I had posted this question on the stackoverflow site.

I think my problem is non-smooth, but I'm not sure I understand the definition. I do not have an analytical description of it, since the time courses in my cost function are generated by a series of matrix rotations. I suppose the problem may still be smooth, even if I can't differentiate it analytically.

It seems that patternsearch is worth trying. Is it roughly correct that stotastic methods (such as GA or particleswarm) may find a better (i.e. 'more optimal') result than patternsearch, but that patternsearch is more reliable since it has 'proven convergence to local optimum' (as written in Solver Characteristics ) ?