MATLAB Answers

what is the maximum population size handled by GA ? What are your advices for large MINLP problems?

5 views (last 30 days)
parag patil
parag patil on 16 Apr 2021
Commented: parag patil on 16 Apr 2021
I am trying to solve a MINLP problem using genetic algorithm.
My number of decision variables are 168.
  • 96 of these decision variables are binary [0 1]
  • Remaining 72 variables can take the integer values of [1 2 3].
The problem is accurately formulated and there is no doubt about it.
Following are my doubts:
  1. What is the appropriate population size to be used ? I am trying : 2*168 , 3*168 and 4*168. But the size seems to be large. Since all the decision variables are integers, what do you suggest about the population size ?
  2. For different initial guesses, I get different different optimized solutions. I am using 20,50 and 60 % of the population size as initial population matrix. Of-course, I know that we cannot guarantee global optimum with GA; but still what can you suggest to get global optimum ? Trying multiple times and getting lowest fval doesnt sound good to me.
  3. The mutants are taken as 10% of total population. Can you suggest an appropriate size of it ?
Finally, when initial population matrix is not defined at all, I do not get the linear constraints (inequality) satisfied. But with some initial population size, I get ( but i think the optimum values are local and not global.
  1. Other than genetic algorithm, are there other optimizers for such problems ? (I do not like to think surrogate-optimization)
  2. Are there other toolboxes (apart from global optimization toolbox), which are free but can be use to handle large MINLP?
Thanks

Accepted Answer

Alan Weiss
Alan Weiss on 16 Apr 2021
General MINLP with over 100 variables are not solvable globally. How can I make this blanket statement? For a general MINLP with 100 binary variables, to guarantee a global minimum you would need to evaluate the objective on all
2^100
ans = 1.2677e+30
points, which takes entirely too long even if you could evaluate 10^10 points per second. ga uses heuristics to attempt to find a global minimum, but has no guarantees, and as I just showed, no algorithm is guaranteed to find the global minimum of a general MINLP with over 100 variables.
So what can you do? Well, it depends on whether your objective function has any nice properties. For example, if your objective function is convex, you might be able to use the technique in Mixed-Integer Quadratic Programming Portfolio Optimization: Problem-Based. The idea there is to approximate the problem by a MILP and iteratively refine it. Not so straightforward in general.
Or perhaps your objective function is close to linear. In that case, try solving it using intlinprog. Then, if necessary, refine the constraints or objective and try again.
But in general, no matter what you try you are not going to be able to guarantee that you found the global minimum.
If you must use ga, try using a large population, parallel evaluation, and maybe use intlinprog to help generate feasible initial points using random objective function vectors and the problem's linear constraints and bounds.
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
  4 Comments
parag patil
parag patil on 16 Apr 2021
Steven, you should look into literature.
People have solved many such large MINLP problems with large number of variables.
For instance a recent paper in Computers and Chemical Engineering shows to solve a MINLP problem with following:
  • Cont. vars : 7800
  • Binary vars : 480
  • Equality constraints: 4320
  • Inequality constraints: 38164
Here is the LINK of the paper : Paper
By the way, they have solved it and the Earth is there.. Moon is here too

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!