2

Suppose we have to solve a global optimization problem in which we have to find values of 5 variables, all of which are integers. Assume we get following two parent chromosomes,

Parent 1: 6, 10, 3, 5, 12

Parent 2: 12, 10, 3, 8, 11

If we do cross-over after first 2 elements, we get following

Child 1: 6, 10, 3, 8, 11

Child 2: 12, 10, 3, 5, 12

Here we can clearly see the children are related to parents.

But when we encode as bit strings, then each chromosome is encoded as a single string of bits and we can, at random, choose any point for crossover. I do not see how this is any more beneficial than completely randomly picking any trial solutions.

I have a similar question with mutation. We randomly flip a bit. If the bit flipped has a small place value, then the change will be small. But if it has a big place value, the change will be big. How is it better than completely randomly changing a chromosome?

Improve this question
1
  • You're correct. Converting to a bit string is usually not helpful. Sometimes it's OK. Mostly not. Commented Dec 21, 2019 at 9:21

1 Answer 1

Reset to default
0

Binary encoding is still common mainly because first works about GA used that encoding.

Furthermore it's often space efficient: [6, 10, 3, 5, 12] represented as a sequence of integers would probably require 5 * 32 bits; for a bit string representation 5 * 4 bits are enough (assuming numbers in the [0;15] range).

Under this aspect the knapsack problem is the best case for the bit string representation (each bit says if the corresponding object is in the knapsack).

we can, at random, choose any point for crossover. I do not see how this is any more beneficial than completely randomly picking any trial solutions

In general choosing a crossover point in the middle of a digit introduces an essentially arbitrary mutation of that digit with a destructive (negative) effect.

There is a nice example about this effect in the Local Search Algorithms and Optimization Problems - Genetic Algorithms section of Artificial Intelligence - A modern approach (Russel, Norvig).

Take also a look at a similar question on Software Engineering.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.