1
$\begingroup$

I'm studying about genetic algorithm. I'm studying about different crossover operations used for binary chromosomes. These methods usually don't use any intelligence (1-point crossover, uniform crossover, etc.).

I found methods like Fitness-based Crossover and Boltzmann Crossover, which use fitness value so that the child will be created from better parents with a better probability.

So I wanted to know if there is any other similar method which uses fitness or any other way for intelligent crossover for binary chromosomes?

$\endgroup$
1
$\begingroup$

It's not obvious what you mean by "intelligent crossover".

However, it is common to use fitness-based selection of parents: individuals in the current population who have higher fitness are assigned a higher probability of being selected to mate and produce offspring. This will increase the likelihood that "good" combinations of genes in members of the current population will be passed along to the next generation, and that independent "good" combinations will be combined in some members of the next generation.

The "best" crossover operator depends dramatically on the structure of the problem being solved, and on the mapping of gene "vectors" to the salient features of a solution.

Edit #1: In some cases it is important to increase diversity in order to avoid convergence to a local optimum. In that case, an "intelligent" GA might for example select a first parent for its high fitness, and a second parent at random. In "Generator", a GA I sold for a while about 25 years ago, mate selection worked that way, and it was often very effective. Generator also replaced any duplicate individuals in the population with entirely random individuals. I have also structured genetic algorithms specifically to evolve multiple separate populations of individuals, with minimum gene flow between the populations, in order to evolve multiple solutions corresponding to "regional" fitness optima.

Edit #2: In genetic algorithms it is not common to directly seek the best combination of genes from both parents. The assumption is that higher-fitness parents are more likely to produce even higher-fitness offspring than lower-fitness parents. Sometimes there is a local search (hill climbing) operation where the offspring of two parents is mutated in various ways and the best of the mutants is put in the next generation.

And, sometimes a crossover operation involves producing a larger number of offspring than the parent generation, followed by culling low-fitness individuals to keep the population size constant. This is vaguely analogous to a local search via mutation, but uses random crossover instead of random mutation for its search.

$\endgroup$
  • $\begingroup$ From "intelligent", I mean a good combination of genes of the child. Yes, I mentioned fitness-based approach, but I was looking for other ways. $\endgroup$ – Pablo Jan 15 at 5:21
  • $\begingroup$ Please see my edit. $\endgroup$ – S. McGrew Jan 15 at 5:42
  • $\begingroup$ thanks. So after choosing a parent with high fitness and a random parent, how we are supposed to apply crossover operator on them? I mean how we can find the best combination of both of these parents (other than "fitness based crossover" and "Boltzmann crossover")? $\endgroup$ – Pablo Jan 15 at 5:48
0
$\begingroup$

The idea behind it

I'll do an analogy: while classical GAs look like how humanity reproduced until now, "intelligent crossover" is more looking like designer babies. You first would need to identify which genes are responsible for certain behaviors and then you can bring them on to the new generation.

Said this, you will understand why there aren't so many algorithms around: it is a very case-tailored approach. Possibly each problem requires a different method and certainly will increase considerably the complexity of the crossover algorithms.


How to make your own

If you want to create one of these algorithms, you might want to add a step to your GA cycle: Evaluation, Identification, Selection, Crossover, Mutation, Replacement.

On the Identification step, you can run a probabilistic search on your population to discover which genes might be responsible for higher fitness results. Then you can:

  • proceed normally: Select two parents based on their fitness and perform crossover giving more importance to the "good" genes. This is the "safest" way.

  • fuse Selection and Crossover: use the data retrieved during the Identification step to create good individuals directly from the population pool. This system is dangerous as it might reduce the population diversity at alarming rates, leading to stagnation. This is how the Fitness-based Crossover are generally built [paper]

$\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.