26 views (last 30 days)

Show older comments

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:

- 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 ?
- 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.
- 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.

- Other than genetic algorithm, are there other optimizers for such problems ? (I do not like to think surrogate-optimization)
- Are there other toolboxes (apart from global optimization toolbox), which are free but can be use to handle large MINLP?

Thanks

Alan Weiss
on 16 Apr 2021 at 17:56

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

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

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

Start Hunting!