CODEWITHSUNDEEP
genetic-algorithm
user2297037
user2297037

Reputation: 1217

Genetic Algorithm - Best crossover operator for a weights assignment

According to your experience, what is the best crossover operator for weights assignment problem. In particular, I am facing a constraint that force to be 1 the sum of the all weights. Currently, I am using the uniform crossover operator and then I divide all the parameters by the sum to get 1. The crossover works, but I am not sure that in this way I can save the good part of my solution and go to converge to a better solution. Do you have any suggestion? No problem, if I need to build a custom operator.

Upvotes: 2

Views: 341

Answers (1)

manlio
manlio

Reputation: 18972

If your initial population is made up of feasible individuals you could try a differential evolution-like approach.

The recombination operator needs three (random) vectors and adds the weighted difference between two population vectors to a third vector:

offspring = A + f (B - C)

You could try a fixed weighting factor f in the [0.6 ; 2.0] range or experimenting selecting f randomly for each generation or for each difference vector (a technique called dither, which should improve convergence behaviour significantly, especially for noisy objective functions).

This should work quite well since the offspring will automatically be feasible.

Special care should be taken to avoid premature convergence (e.g. some niching algorithm).

EDIT

With uniform crossover you are exploring the entire n-dimensional space, while the above recombination limits individuals to a subspace H (the hyperplane Σi wi = 1, where wi are the weights) of the original search space.

Reading the question I assumed that the sum-of-the-weights was the only constraint. Since there are other constraints, it's not true that the offspring is automatically feasible.

Anyway any feasible solution must be on H:

If A = (a1, a2, ... an), B = (b1, ... bn), C = (c1, ... cn) are feasible:

  • Σi ai = 1
  • Σi bi = 1
  • Σi ci = 1

so

Σi (ai + f (bi - ci)) = Σi ai + f (Σi bi - Σi ci) = 1 + f (1 - 1) = 1

The offspring is on the H hyperplane.

Now depending on the number / type of additional constraints you could modify the proposed recombination operator or try something based on a penalty function.

EDIT2

You could determine analytically the "valid" range of f, but probably something like this is enough:

f = random(0.6, 2.0);

double trial[] = {f, f/2, f/4, -f, -f/2, -f/4, 0};

i = 0;
do
{
  offspring = A +  trial[i] * (B - C);
  i = i + 1;
} while (unfeasible(offspring));

return offspring;

This is just a idea, I'm not sure how it works.

Upvotes: 2

Related Questions