2
$\begingroup$

I'm working on a genetic algorithm with a constraint on the sum of the alleles, e.g. if we use regular binary coding and a chromosome is 5-bits long I'd like to constrain it so that the sum of the bits has to be 3 or less (011100 is valid but 011110 is not). Moreover, the fitness function is such that invalid chromosomes cannot be evaluated.

Any ideas on how this problem could be approached?

I've started looking into the direction of messy GAs (since those can be over-specified) but I'm not sure if there's anything there.

$\endgroup$
1
$\begingroup$

There are multiple ways to handle 'illegal' individuals, each one with pros and cons:

  • Abortive methods: The individuals that violate constraints are eliminated as soon as discovered (i.e. after crossover or mutation) and new individuals are generated in order to keep the population stable. This usually implies a slower creation of new generations, as some individuals are discarded.

  • Contraceptive methods: The crossover and mutation are written in such a way to make it impossible for a newly generated individual to violate any constraints. This way to act is usually more efficient, as no individuals are discarded, but it might not be possible.

  • Penalization function: The fitness function gives a huge penalization to the individuals that violate constraints (usually proportionally to the constraints it violates). In this way they usually do not get to reproduce and their genes are eventually lost. You'd go this way if illegal individuals are very rare and there is no possibility for them to take over the full population (causing the algorithm to fail).

By experience, try to act on the crossover algorithm first (contraceptive way), it is the best way to exclude constraints violations. If this is not possible, pick one of the other two methods, depending on how often the illegal individuals are generated (not so often -> penalization, very ofter -> abortive) and on how easy it is to penalize individuals that violate constraints (easy -> penalization, not easy -> abortive).


A contraceptive way to handle your example is writing the crossover as following:

bool[] crossover(bool[] p1, bool[] p2)
{
    // classical binary crossover
    bool[] child = p2.copy()
    child[rndSection] = p1[rndSection]

    // contraceptive part
    while (CountTrue(child) > 3) child[RandomIndexOfTrue(child) = false

    return child
}

But this is a fairly complex problem and each scenario has its own specifications.

| improve this answer | |
$\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.