1
$\begingroup$

I knew that Reproduction and Crossover are the same things,

  1. Wikipedia
  2. Obitco.com
  3. TutorialsPoint

But, The following is the exercise given by my teacher,

Exercise 1 Genetic algorithm to solve pattern finding problem.

Your task is to design a simple genetic algorithm, with binary-coded chromosomes, in order to solve pattern finding problem in 16-bit strings.

The objective function is given by the following formula:

F(x) = NoS("010") + 2NoS("0110") + 3NoS("01110") + 4NoS("011110") + 5NoS("0111110") + 6NoS("01111110") + 7NoS("011111110") + 6NoS("0111111110") + 5NoS("01111111110") + 4NoS("011111111110") + 3NoS("0111111111110") + 2NoS("01111111111110") + NoS("011111111111110")

The algorithm should display each population on the screen in the form And should save the history of it’s operation (average fitness in each population) in the text file. At the end it should also display the best solution found.

You may use the following operators:

  1. Reproduction.
    You can use either one of the following reproduction types: Proportional, Ranking, Tournament. They are described more in detail below: ... ... ... ... ... ... ... ...

  2. Crossing over.
    In order to perform this operation the individuals must be grouped in pairs (randomly), and with certain probability pcross information from their chromosomes must be exchanged. There are many flavors of the crossing-over operator, but in our case (short, 16-bit chromosome), simple, one-point crossover will be enough. It can be performed by selecting a random number k from the range <1;15> and cutting the chromosomes of both individuals on that position. Each of the individuals copies bits belonging to the other to it’s own chromosome.

  3. Mutation
    This operator changes the value of each bit in the chromosome to the opposite one with a very small probability pm (usually about 10-3). If we denote chromosome as [b1, b2, ... , b16]; then after the mutation each bit can be described as: Where k Î {1,2, ...,16} flip(x) – result of a Bernoulli flip with a success probability x.

Here I see that by Reproduction and Crossover he means different things.

What is the catch?

$\endgroup$
1
$\begingroup$

The terminology of this exercise is not standard. What is referred to as 'Reproduction' in the exercise is usually referred to as 'Selection'.

The term 'Reproduction' does indeed seem conceptually closer to the notion of Crossover/Recombination (these two are the same thing), which is probably where your confusion has arisen.

See the excellent (and freely-downloadable) 'Essentials of Metaheuristics' for an introduction to the usual terminology for evolutionary algorithms.

$\endgroup$
0
$\begingroup$

In adaptive genetic simulation theory, commonly termed genetic algorithms, the simulation of sexual reproduction is a superset of crossover.

Simulated genetic evolution is typically as follows.

  • Initialize population — corresponding in biology to a stable population placed under a new stress
  • Replication — corresponding in biology to the creation of gametes across the population
  • Crossover and mutation — corresponding in biology to imperfect chromosome unwinding, separation, alignment, splicing, bonding, mirroring, and rewinding
  • Migration — corresponding in biology to geometric clustering of individuals and interchange between the clusters
  • Evaluation — corresponding in biology to genetic expression governing growth and life function
  • Elimination — corresponding in biology to reproductive termination of individuals in the population through injury or fatality
  • Test of convergence to decide whether to replicate again or exit, returning results

Reproduction includes both replication, crossover, and mutation, not just crossover. This fact is not always obvious because replication in procedural programming languages with operator overload and collections support is often little more than an assignment operator or method call. Also, crossover is sometimes thought of as including mutation, which is not technically correct in either biology or AI.

Both are stochastic, but crossover is an exchange of data between two sequences at random splicing locations, whereas mutation is the replacement of data with random data at random locations. Because of the general acceptance of symbiogenisis as a factor in speciation and biological adaptivity, there is a need for further research into a third stochastic factor of crossover or the addition of data from other species.


References

Genetic Algorithms as Function Optimizers, D. Bethka, 1978

An Overview of Standard and Parallel Genetic Algorithms, Abtin Hassani, Jonatan Treijs, 1975

Cognitive Systems Based on Adaptive Algorithms, 1978, John H. Holland, Judith S. Reitman

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy