2

I'm developing a heuristic based on U-NSGA-III and GA for continuous variables with a crossover operator from this article: https://www.researchgate.net/publication/331451524_CAM-ADX_A_New_Genetic_Algorithm_with_Increased_Intensification_and_Diversification_for_Design_Optimization_Problems_with_Real_Variables.

My model has binary and continuous variables, being the continuous variables dependent on the binary ones, so I divided my problem into two: 1 solves the problem with the binary type, and for each solution of the problem 1, there's another problem that defines the continuous variables.

Using this technique, my algorithm is slower than a B&B Algorithm, so I want to know, this kind of division is always a bad option or I could be doing something wrong other than that?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Josa Ferreira
  • 338
  • 1
  • 9
  • 1
    You can try to solve the continuous subproblem with an exact solver while retaining the GA for the combinatorial part. Even that might not be beneficial, depending on your problem. From my experience, metaheuristics perform bad on continuous problems compared to exact solvers, because solvers are so advanced nowadays and can exploit gradient information much better than metaheuristics. Also, related. – ktnr Nov 02 '20 at 15:39
  • 1
    Your partition of variables into integer master problem and continuous subproblem is the basis of Benders decomposition. Added that tag. – RobPratt Nov 02 '20 at 16:09

2 Answers2

5

There is a type of GA called a "random key" GA [1] that was originally designed for scheduling problems, with an eye toward dealing with constraints inherent in those problems. I've had some luck using it on other types of problems. The gist of the approach is that you establish a chromosome (in your case, a vector with some positions designated binary and the rest continuous between specified bounds) and then provide a function that "decodes" chromosomes into solutions. The critical part is that every chromosome must decode to a feasible solution. (It's okay if multiple chromosomes decode to the same solution.) Also important: every feasible solution, or at least every good feasible solution, is represented by some chromosome. Everything else about GAs (fitness, crossover, mutation, elitism, ...) is unchanged. If you can make your problem fit that paradigm, you can solve it with a single GA rather than having to "nest" two different GA models.

[1] Bean, J. C. Genetic Algorithms and Random Keys for Sequencing and Optimization ORSA Journal on Computing, 1994, 6, 154-160

prubin
  • 39,078
  • 3
  • 37
  • 104
3

Your problem is what we call at LocalSolver a mixed-variable problem. It involves discrete decisions and continuous decisions that cannot be expressed from the discrete ones. Once the discrete decisions are fixed, you have to decide the continuous ones, that may have to satisfy some (linear or nonlinear) constraints and that may appear in the objectives of your model as well. This is the typical structure of problems like the unit commitment problem or the inventory routing problem.

When the discrete part of the model is not heavily combinatorial and the continuous part can be linearly approximate, the model may be frontally solved by MILP solvers. When you don't get quality solutions in short running times like this, then you have several ways to proceed.

  1. You can use MILP solvers through decomposition approaches like Benders decomposition, as Rob mentioned in his comment above. Benders decomposition is quite sophisticated. There are many ways to heuristically decompose the problem, then solving each part with MILP solvers. For example, solve first the discrete part of the model by approximating roughly the continuous part; then, having values for the discrete variables, solve the continuous part (exactly or heuristically).

  2. You can use "mixed-variable" local search approaches like the ones described in this paper for a real-life, large-scale unit commitment problem or this paper for a real-life, large-scale inventory routing problem. The main idea of the approach is simple but the practical implementation can be hard. Starting from a solution (feasible or infeasible), you perform a "mixed-variable" local search at each iteration. It consists of moving discrete decisions (as classically done in local/neighborhood search methods or evolutionary methods) and then of repairing the continuous part by exact or heuristic continuous methods (for example, by using incremental greedy algorithms which is complex to implement but makes the overall approach converging very fast in practice, or by using basically LP/NLP algorithms which is easier but slower). Here you can also use evolutionary methods as the one described in the paper you mentioned in the question to repair the continuous part of the solution.

LocalSolver has under its hood some of the approaches described above.

Hexaly
  • 2,976
  • 1
  • 11
  • 17