1
$\begingroup$

I have chromosomes with floating point representation with values between 0 and 1. For example-

Let p1=[0.1,0.2,0.3 and p2=[0.5,0.6,0.7] be two parents. Both comply with the set of constraints. However, the children produced by 1 point crossover, we get c1=[0.1, 0.6, 0.7] and c2=[0.5, 0.2, 0.3] out of which 1 or both may not comply with the given constraints.

A similar scenario can also occur with small perturbation of values due to mutation strategy. Correct me if I am wrong in the belief that such kind of scenarios might arise irrespective of the strategy employed for crossover and mutation. What are the options to handle such kind of cases?

Edit- In my case, the major constraint is- $$ p1[1]*p1[2] - k*p1[0] \geq 0 $$ for any chromosome $p1$. For the example above we can take $k=0.3$ which renders c2 infeasible.

$\endgroup$
1
$\begingroup$

You have two broad categories of options, prevention and repair.

Prevention means defining a crossover and mutation operator that try to be more intelligent about respecting the constraints. Suppose you have an encoding where each individual is a list of integers, and the constraint is that there can't be duplicates. You might define a crossover operator that did something like the following. For each position in the offspring, choose randomly from one parent such that, if possible, you choose a value that hasn't already appeared in the offspring. If both parents have values at that position that are already used in the offspring, choose a random value.

That operator would avoid violating the constraint in the first place, while attempting as much as possible to have the offspring inherit information from the parents.

Another option is to just let the operator violate constraints and then deal with the ramifications afterward. You don't go into details about what your constraints actually are, just that c1=[0.1, 0.6, 0.7] violates them. Let's say the constraint is that the third position should not be more than 4x greater than the first one. OK, so then let's take this offspring and adjust either the first or third item. Maybe we make the new individual into c1=[0.2, 0.6, 0.7].

Often, you want some element of randomness in either option so that you don't strongly bias the production of new search points. In my example, don't always make the first element larger. Sometimes, make the third element smaller or produce some random combination of both to repair the constraint violation.

Finally, both options typically strongly benefit from domain knowledge. Design an operator that understands your problem and tries to intelligently solve the problem.

$\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.