3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Would you see this link? Is it what you looking for? $\endgroup$ – A.Omidi Nov 8 '20 at 16:34
  • $\begingroup$ In the following link handling equality constraint in GA has been discussed: researchgate.net/post/… $\endgroup$ – Oguz Toragay Nov 8 '20 at 16:44
  • $\begingroup$ Hello, @stevGates. Welcome to OR Stack Exchange. Is it really the problem you have to solve? Are all your variables continuous? Is there only one constraint to satisfy? If so, then check our answer on a similar problem: or.stackexchange.com/questions/4248/… $\endgroup$ – LocalSolver Nov 9 '20 at 22:32
3
$\begingroup$

The random key variant [1] 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:C\rightarrow 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 $c\in 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.

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer is a new knowledge to me. I wish if you could have elaborated a bit more on this. $\endgroup$ – your_boy_gorja Nov 12 '20 at 3:46
  • 2
    $\begingroup$ Done, I hope that helps :) $\endgroup$ – Geoffrey De Smet Nov 12 '20 at 8:00
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.