Genetic Algorithm: Selection

In every generation, a selection agent comes to play which sifts out the fit chromosomes from the unfit chromosomes. The selection agent “kills off” a user specified percentage of organisms in the population.However, it is under the discretion of the selection agent in determining which chromosomes to kill. As mentioned earlier, fitness is defined by having the lowest weight in the circumstances put forth by the TSP. However selection may not necessarily be only off of that. This can be seen when comparing the two most prevalent types of selection operators:

  1. Percentage Cut Off Selection – In this form of selection every organism in a certain user defined percentage survives year over year. For example, in a population of 10 chromosomes and the cutoff being 30%, the percentage cut off selection operator will return a population consisting of the top three paths every time the fully populated (with 10 chromosomes) population is passed in.
  2. Inversely Linear Roulette Selection – Each individual is giving the probability Pi of being selected. Pi is linearly proportional to the fitness of the organism. The probability of each organism being selected decreases with higher weight making weight inversely proportional to the probability of being selected. The algorithm to determine probability for any certain organism can be seen in the equation below in which fi represents the fitness function of for the organism i. This method allows for the maintenance of a higher genetic diversity in the fact that the top chromosome doesn’t necessarily have a 100% chance of survival year over year and the most expensive or most unfit chromosome doesn’t necessarily have a 100% chance of death year over year. This opens the door to new crossovers that may lead to better paths and a further reach in the sample space.

    Fitness Proportional Selection
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s