# How to handle an equality constraint in metaheuristic algorithms (like GA, PSO)?

Operations Research Asked by stevGates on January 11, 2021

Metaheuristic algorithms are generally used to find the optimal solution to unconstrained optimization problems. I would like to maximize $$x_1+3x_2-x_3ge0$$ while respecting the equality constraint $$x_1+x_2=5$$. How can I do by using a metaheuristic method?

The random key variant  of genetic algorithms was developed, I believe, to solve sequencing (permutation) problems, but it can be adapted to at least some other types of constrained problems. Let $$C$$ be the set of possible chromosomes and $$X$$ the set of feasible solutions to the original problem. You provide a surjection $$d:Crightarrow X$$ that decodes chromosomes to feasible solutions. So if $$f()$$ is the original objective function (expressed in terms of the original variables in the model) and $$cin C$$ is some chromosome, the fitness of $$c$$ is given by $$f(d(c))$$. Function $$d$$ does not need to be injective -- it's OK if multiple chromosomes map to the same feasible solution -- but must be surjective (every feasible solution is represented by at least one chromosome). Importantly, every possible chromosome must map to a feasible solution.

So, for instance, you could define a chromosome to be a vector of two reals, decoded by $$d(c) = (c_1, 5-c_1, c_2)$$ with fitness $$f(d(c))=c_1 + 3(5-c_1) - c_2=15 -2c_1 - c_2$$. Since you indicated the original objective function is nonnegative, I presume you have some bounds on the components of $$x$$. You would need to find the equivalent bounds for the genes $$c_1$$ and $$c_2$$ and then impose them as the domains of the genes.

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

Correct answer by prubin on January 11, 2021

You can create moves (neighborhoods) that don't impact the equality constraint.

For example in investment portfolio I added this custom move in OptaPlanner (java, open source) that uses Local Search configuration (Late Acceptance probably).

Elaboration:

In that example we need to decide how which percentage of our budget to invest in which assets (such as stocks). In the end, we need to invest 100% of our budget (total=100%). Now presume that in Local Search at some point we have 0% in asset A, 50% in asset B, 30% in asset C and 20% in asset D. A typical change move will add/remove a percentage for an asset, without balancing it out somewhere, so it break the "total=100%" hard constraint. Instead, we replaced all the out-of-the-box move selectors (=neighborhoods) with a set that never breaks the "total=100%" constraint. That InvestmentQuantityTransferMove takes a a part of percentage assigned to one asset and assigns it to another. For example, take 5% from B and assign it to A, so it results in 5% in asset A, 45% in asset B, 30% in asset C and 20% in asset D.

Answered by Geoffrey De Smet on January 11, 2021

One way in which you can handle constraints in evolutionary optimization is by adding penalty functions to you original objective function (assuming a minimization problem at hand). This penalty function can be defined in several ways and its goal is to quantify the amount of constraint violation.

However, implementing it sometimes is not as easy as it seems. The key problem comes with deciding the weight of penalty function you want to augment your original objective function with. This is in some sense a hyperparameter that you have to tune. An untuned amount of penalty can result in skewed objective function landscape with sharp constraint boundaries. Essentially you have to take care that original objective function and the penalty functions for the constrains are along approximately similar scales.

Answered by your_boy_gorja on January 11, 2021

## Related Questions

### How to optimize a utility function that contains step function?

1  Asked on January 5, 2022

### How to display the range of coefficients in docplex log?

1  Asked on January 1, 2022 by ehsank

### Scenario based approach to value-at-risk optimization using mixed-integer programming

1  Asked on January 1, 2022

### Multiple Knapsacks with splitting

1  Asked on December 20, 2021 by cesar-canassa

### How to balance the workload of teachers in OR-Tools (maximization of the minimum)

1  Asked on December 18, 2021 by neverletgo

### How to linearize a quadratic constraint to add it then via a callback function

2  Asked on December 9, 2021 by farouk-hammami

### Decision variable transformation in Gurobi

2  Asked on December 5, 2021

### Possibility of indexing decision variables with 2 indices using a set of tuples in Pyomo

3  Asked on November 24, 2021

### View of Constraints and Decision Variables in Pyomo

1  Asked on November 17, 2021

### CPLEX Python API Manual with References

1  Asked on November 4, 2021

### Are Python and Julia used for optimization in industry?

15  Asked on August 19, 2021

### How to improve the quality of code in OR?

3  Asked on August 19, 2021

### How would you characterize “optimization data?”

4  Asked on August 19, 2021 by marco-lbbecke

### Local optimum of dual of non-linear program

2  Asked on August 19, 2021

### Combinatorial Optimization using AMPL

2  Asked on August 19, 2021 by user3831

### Parallel nonlinear solvers

3  Asked on August 19, 2021 by josh-allen

### Tips on How to Review Operations Research Literature Effectively?

2  Asked on August 19, 2021 by ehsan

### Polynomially solvable cases of zero-one programming

1  Asked on August 19, 2021

### Error evalution for linear fits

1  Asked on August 19, 2021 by jane