Why is ga optimization ridiculously slow to solve a problem ?

If you consider the following code, you can see that I have only one integer variable with [10 16] interval.

Therefore, in my mind, ga should look up for the minimal value by trying to set the variable with 10 11 12 13 14 15 16 only.

The function take roughly a few second to run when I am doing it manually. Then why is this optimization so long? Any guess what i am doing wrong?

Answer 1

[Stephen23]

"Therefore, in my mind, ga should look up for the minimal value by trying to set the variable with 10 11 12 13 14 15 16 only."

Nope. That is not how the ga algorithm works.

"Any guess what i am doing wrong?"

You are using the wrong tool for the task.

A global solver like ga does not work by simply defining a list of all possible values and trying each of them in turn. All global optimization routines have overhead because they have to set up whatever variables (e.g. sample populations, etc) depending on the algorithm and options selected, and then they run the algorithm until some conditions are met. The fitness function will be called many times during this process, because that is how global optimizers work. For example the conditions for ga include the population size, which according to the ga documentation for one variable and a mixed integer problem will be 40... so your (apparently slow) function gets called for each of those 40 population members on each step of the algorithm, and will be quite few steps until the conditions are met such that the solver stops. Just because your particular domain only has seven possible values does not mean that this sample population is reduced, or that the other conditions magically disappear: there is no shortcut, no special case where the ga algorithm will decide to use some other different algorithm (e.g. the one that you apparently want to use "try each one and see which is best"). You decided to use a ga algorithm, which involves creating a large population and calling the function for each population member while changing the population values. That is what the ga algorithm does.

If you want to want to find a global maximum then read about the different algorithms, and see how they work, keeping in mind that there is no "perfect" optimizer because different ones work well in different situations:

https://www.mathworks.com/help/gads/choose-a-solver.html

If you want a simple "try each value" algorithm, then why not just use a for loop anyway? Using any optimization tools for this seems like a waste of time.

[John D'Errico]

+1. Using GA here is like using a Mack truck to carry a pea to Boston. You are using an overly sophisticated tool to solve a trivial problem.

That sophisticated tool does not know that the problem is trivial to solve using a loop. It only knows how it is designed to solve a given class of problem. So it spends a lot of effort doing the best job it can. You told it to do this job, so it will do what you it was designed to do.

That you picked the wrong tool to solve the problem? You can use a hammer to drive in a screw. But the screw will be the worse for the wear, all bent and bunged up. And the task will take far longer and more effort than needed. A simple screwdriver would have been a far better choice to drive the screw. So understanding the tools available is important, because it helps you to choose a realistic and proper tool for the task at hand.

[Pierre Lonfat]

Thank you very much both of you. I actually have more than one variable. I just tested it out with one variable to see if ga was still overly slow.

I actually have 3 variables. What I did then is to calculate a matrix of all possible combinations, do a huge for loop, retain the combination that match min value. Not very glorious, also time consuming, but better than nothing :) !

[Stephen23]

@Pierre Lonfat: has the function been written with vectorized code?

[Pierre Lonfat]

I am not sure to understand you question since I don't have a high level on Matlab. The value of the variable will have an influence of how many data (number of lines) the code will use to compute, i.e. mean and rolling averages. The actual size of vector are indeed going to change in function of the variable choice. Is it what you mean ?

[John D'Errico]

Vectorization is a good possibility. Or it may be possible to use a partial vectorization. So eliminate some of the loops using vectors or arrays.

Very often, slow code is an indication that there are bottlenecks that can be eliminated. Have you looked at using the profile tool to see if there are places the code could be improved?

Also, remember that GA does not assure you that it will find the global optimum. So if the search space is very large, or if the function is a bit lumpy, there is only some probability that it will succeed.

[Pierre Lonfat]

Thank you John. Indeed, my code can be improved, I just discovered that rolling average formula exist on Matlab. I am actually doing a lot of unnecessary loops... But with my actual level, I have better confidence using them because in my mind, they are more representative of what the code is doing ;)

[Stephen23]

@Pierre Lonfat: keep in mind that with MATLAB:

• numeric operations and functions often work very efficiently on whole arrays of data without requiring any loops (this is what vectorized code takes advantage of), and
• inbuilt operations and functions are usually quite optimized for speed: they are often written using C, or call highly optimized linear algebra libraries.

Both of these mean that using whole arrays with inbuilt functions is a good starting point for writing efficient code, that can be tailored later as required. It is also a good rule of thumb to not write code twice: if MATLAB already has a function that does what you want, then use it: it will be well tested by many users, well documented, and most likely more efficient.

You might like to read these:

https://www.mathworks.com/matlabcentral/answers/228557-experts-of-matlab-how-did-you-learn-any-advice-for-beginner-intermediate-users

https://www.mathworks.com/help/matlab/matlab_prog/vectorization.html

https://www.mathworks.com/help/matlab/performance-and-memory.html

Keep in mind that the solution to slow code (e.g. your question) is not to throw another even slower operation at it (e.g. using ga), but to understand why that code is slow, and fix it at the source. The more you read about and practice writing efficient MATLAB code, then easier this will be for you.

[Pierre Lonfat]

Thank you very much Stephen for your detailed answers ! I am starting to work now on improving my code efficiency. As I am a beginner, it is not straight forward to me to write vectorized code with cell variables. If you are willing to help me again, I just asked a question right there because I couldn't find any detailed example: https://ch.mathworks.com/matlabcentral/answers/388205-if-function-with-cellfun-i-e-vectorized-code-instead-of-ridiculously-slow-loop

Thanks again !