CODEWITHSUNDEEP
genetic-algorithm
gskema
gskema

Reputation: 3221

What is the correct way to execute selection procedure in a genetic algorithm?

I am working on a genetic algorithm for symmetric TSP in VB.NET. I want to know what is the correct way go execute selection procedure. There seems to be at least two different possibilities:

1)

-create a "reproduction pool" of size R by using SELECTION(pop) function
-do offspring creation cycle
-randomly (uniformly) select two parents from that pool for each offspring 
 that needs to be created in each iteration

2)

-do offspring creation cycle
-use modified SELECTION(pop) function that will return two different parents from pop
-perform crossover to produce a child

Bonus question: After selecting two parents it is possible to produce two different offsprings (if the crossover operator is mot commutative): CROSS(p1, p2) and CROSS(p2, p1). Should I insert both offsprings immediately or produce them one by one ? Will this make a difference?

Currently I am producing them one by one because I think it will give more variance in the population.

Upvotes: 0

Views: 147

Answers (2)

Andreas
Andreas

Reputation: 6465

In genetic algorithms you don't use a separate reproduction pool, but sample from the population (|N| until you have 2*|N| parents out of which you create |N| children). If your reproduction pool R is of size 2*|N| and you sample randomly out of that pool it's essentially the same behavior, but you need more random numbers and it's more expensive to compute (depending on your RNG). Note, that there is no need to care about getting two different parents. A parent mated by itself will produce a child that is the same as the parent (if the crossover is idempotent). It's similar to using crossover probability. Also the check if two parents are different may be quite expensive if you compare them structurally. You could also compare them by fitness, but often you can have very different solutions of the same quality.

Regarding your second question: I would say that it doesn't matter much. I would choose to return only one child for simplicity reasons: A method that takes two solutions and returns one solution is easier to deal with than one that returns an array of solutions. I would say that returning both is only interesting in those cases where you can create two distinct solutions. This is the case of binary or real-valued encoding. With permutations however you cannot guarantee this property and some genetic information will be lost in the crossover anyway.

Upvotes: 1

Rommel Dias
Rommel Dias

Reputation: 63

It depends on the codification.

You can consider the two fittest individuals of the current population.

Or you can use roulette whell selection (Google it) to associate each individual with a reproduction rate, this is the usual way.

Upvotes: 1

Related Questions