I need to maximize an objective function using genetic algorithm but the toolbox fails to do so. Can you help ?

My objective function contains 93 integer variables including 16 binary variables. I have used fx = - Fmax to maximize it but unfortunately, the result I get is positive. That is, the value of Fmax comes out to be negative whereas solving the same code in LINGO gives me an accurate result. Also, when I try to input the Initial population as the one I got from LINGO optimization, it produces the exact same result as LINGO. I am confused here. How is it possible that when GA starts on its own, it goes to the negative side of the function even though it is undergoing maximization. I have tried changing the following parameters to see any improvements but none solved the issue.

1. Migration - 'both side' instead of 'forward'

2. setting lower bound of variables as zero.

3. changing the creation function to feasible population or constraint dependent

It is getting very hard to find the cause of this randomness.

Answer 1

[Alan Weiss]

Is your problem inherently nonlinear? If you can express your objective and constraints as linear functions, then you would doubtless have much better results by using intlinprog.

But if you must use ga, then perhaps these guidelines will help.

1. Read the documentation on integer ga. For example, you cannot set a creation function; as documented, ga overrides your setting.
2. Read the documentation on options. In particular there is no benefit in setting any migration options.
3. It is very difficult for ga to solve an integer problem with about a hundred variables. To have a chance, take a large population size ( PopulationSize option), perhaps 1e4 or 1e5. ga will run slowly, and there are no guarantees that you will get a good solution.
4. To have the best chance of getting a good solution, give ga a wide variety of initial feasible points. It can be hard to come up with feasible points, but that is the best thing that you can do. See Population Diversity, which unfortunately is not geared toward integer problems.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Parikshit Agrawal]

1. Yes, my objective function and constraints are linear and I have expressed constraints in the form of matrices A and b.

2. I have also already read the documentation and hence, I incorporated the equality constraints as described (with +ve and -ve signs).

3. My primary purpose of the optimization is to see the results from ga integer optimization.

I want to ask a very general but important question. Is it this hard or time-absorbing to solve a 93 variable MILP with GA or my case an exception? Because I have seen some research papers which have solved integer model via GA but I don't know if they faced the same issue or not and if they did, what correctional measures must they would have taken to produce sound and correct results!

In my case, one time ga results in -ve value and infeasibilities while other times it results in some large value which is out of bounds. I compared ga results with the B & B algorithm I applied using other software and the results only match if I input the initial population as the one got from the other software. I am not able to reason this behavior out. Thanks for your help in advance.

[Alan Weiss]

Our built-in integer ga implementation is not particularly fast or robust in high dimensions. The workaround for equality constraints in particular is not robust, as documented. And, like all genetic algorithm solvers, the algorithm's behavior is stochastic, so you are never guaranteed to get a good result.

Use intlinprog for integer-constrained problems with linear constraints and linear objective. Using ga on such a problem is not recommended. If you want to investigate algorithmic behavior, feel free, but don't be surprised when non-recommended approaches give poor results.

Alan Weiss

MATLAB mathematical toolbox documentation