3

I have two genes with different sizes and I want to produce offspring from them. The position of the chromosome doesn't make difference in the gene.

I want to know what is common to do in this situation

Gene1:

123456789

Gene2:

ABCDEFGHIJKL

I can use a single cross point in each

12345.6789
ABCD.EFGHIJKL

And with this I have 8 possible combinations

1. 12345ABCD
2. 12345EFGHIJKL
3. 6789ABCD
4. 6789EFGHIJKL
5. ABCD12345
6. ABCD6789
7. EFGHIJKL12345
8. EFGHIJKL6789

Is it okay to create all the 8 offsprings, or should I just make 1, if so, do I need to randomize the method or just pick one and stick with it?

davejagoda
  • 2,420
  • 1
  • 20
  • 27
f.rodrigues
  • 3,499
  • 6
  • 26
  • 62
  • What do your genes mean? Usually these are coefficients in a neural network, and for given NN topology you have a fixed number of these coefficients. – Archie Nov 18 '15 at 15:37
  • They don't mean much at this stage, is just to conceptualize what needs to be done. They will be fragment of videos in a future project. – f.rodrigues Nov 18 '15 at 15:44
  • Well in a genetic algorithm you have to 'evolve' the model by testing the population against a certain criteria, them pick the fittest and replace the rest of the population with x-crossed or random offspring. Given your genes set, how do you intend to use them in your model? – Archie Nov 18 '15 at 15:47
  • I ask for the users to rate the videos, with rates from 1~5, and keep displaying videos until I find convergence. In this example I could have 8 new videos from 2 old one. They would be quite repetitive, but in a population with more than 100, this would mean that the most liked will probably appear more often. – f.rodrigues Nov 18 '15 at 15:51
  • 1
    You can generate as many offspring siblings as you want. In your case you will test your population of videos on users and score them, if I understood correctly. Then you will keep some with high-scored ones (set threshold here) and replace all the rest with random and/or x-crossed from the high-scored ones. You can even replace the entire population is none of the videos reaches the acceptance threshold. – Archie Nov 18 '15 at 16:01
  • @Archie, That's what I was thinking, but I haven't found anything telling me otherwise. You might want to add this as an answer. – f.rodrigues Nov 23 '15 at 16:15

2 Answers2

2

Genetic algorithms are mocking biological processes where chromosomes crossover at one point and exchange their parts after the crossover point if we are talking about single point crossover.

Chromosome Crossover

As you can see in picture above parents exchange "tail" parts of the chromosome after the crossover point. Therefore you have only 2 offspring/children produced by crossover. That's how crossover occurs in nature, how biologists describe it.

If you refer to any literature dealing with topic of Genetic Algorithms they also state this convention that when using single point crossover parent chromosomes are split into head and tail denoted as H/T like that (see citation below):

   H    T
123456.789

   H    T
ABCDEF.GHI

Therefore offspring produced with this crossover will be:

123456GHI
ABCDEF789

Following this convention is much better than creating all possible combinations and then selecting random or fittest of the offspring as it is computationally more efficient. If you want to solve more complex problems you just simply increase size of the population to allow more diversity.

"Single point crossover: A single random cut is made, producing two head sections and two tail sections. The two tail sections are then swapped to produce two new individuals (chromosomes)".

Genetic Algorithms and Genetic Programming: Affenzeller, Michael Wagner, Stefan Winkler, Stephan, ISBN: 1584886293

Alternatively you can use multipoint crossover which follows similar convention where chromosomes are split into sections and parents exchange parts in a way that offspring chromosome is just alternation of parents chromosomes so if you have parents with chromosomes:

A1.A2.A3.A4
B1.B2.B3.B4
|
| this will produce offspring
|
A1 B2 A3 B4
and
B1 A2 B3 A4

This answer might help you as well: Crossover of chromosomes with different length

Community
  • 1
  • 1
MichaelDD
  • 766
  • 6
  • 14
  • Thanks for the input. That's how I would do if it both genes had the same number of chromosomes and the order of the genes mattered.In your example (a~i is 9 chromosomes long), so is 1~9. But in my case is different, each gene can have varying lengths of chromosomes, one might have 9 chromosomes (1~9 in my example) and the second have 12 (A~L). And since in my problem it doesn't matter if some part is tail or head, it doesn't matter the order which you 'glue' the two new parts, so you essentially have 8 possible combinations. – f.rodrigues Nov 23 '15 at 16:09
  • 1
    I believe length of the chromosomes doesn't matter even if you have chromosomes with different length you should still split them into H and T and swap the T. If was reading about it quite recently if I find reference I will post but that textbook was discussing exactly issue with different chromosome lengths and still when doing single point crossover you should swap tails. It will matter when you encode multiple values into one chromosome as randomly swapping parts of the chromosome may increase searching time. – MichaelDD Nov 23 '15 at 16:32
0

It seams you use Gene instead of Chromosome and vice versa. In this case and if different size of chromosome is okay, you can create all 8 offspring. But your population increases in each iteration and you should control this. For example keep 2 of the best offspring or 2 random offspring and replace their parents by.

Ahmad Sarabian
  • 144
  • 3
  • 13
  • The number population would always be the same, as it's a different part of the algorithm that deal of keeping track of how many genes we have in the population. My program does something like `while new_population < target_population: create_new_genes()` and in the end, since it could lead to overflowing (since I add 8 at a time), I do `while new_population > target_population: population.pop()` – f.rodrigues Nov 23 '15 at 16:13