Main Menu    Japanese
Related Links
Contact information:

Email: ibalabwww@ibalab, iba@ibalab
ibalab=iba.k.u-tokyo.ac.jp


Telephone Numbers:
7H1:+81-4-7136-3873
7H4:+81-4-7136-3874
7E4:+81-4-7136-3875
Description of Selection Methods of Parents for Recombination

Suppose the fitness of N individuals in a population are: f1,f2,f3,..., fN.

In roulette wheel selection, the probability of an individual being selected is 

Pi=fi/(f1+f2+...+fN).

Then a parent is selected by going through the following steps: 

a. Generate a random value r 
   between 0 and 1.
b. Set sum=0;
c. for i=1 to N do
    begin
       sum=sum+Pi;
       if (sum>=r)
	    return i;
    end

In linear rank based selection, each individual is assigned a rank based on its fitness. Assuming that the best individual in a population ranks the first, the probability of selecting an individual is calculated as follows: 

Pi=(nmax-(nmax-nmin)(i-1)/(N-1))/N
where 
nmax+nmin=2 and
nmax>=nmin >=0.
The recommended value for nmax=1.1. Then a parent is selcted by applying the steps described before.

In Boltzmann tournament selection with tournament size m, m different individuals are selected and the winner of the tournament is selcted as a parent. The probability of an individual x wining over y is: 

P(x,y)=1/(1+exp((fy-fx)/T))
where T is the temperature and 
fy<fx.

Frequently Asked Questions about Genetic Algorithm / Evolutionary Algorithm
Q1. Where are Genetic Algorithms widely used?

Answer: GAs are applied for those problems which either can not be formulated in exact and accurate mathematical forms and may contain noisy data or take much computational time or impossible to solve for traditional computational systems.


Q2. What are the parameters of a GA?

Answer. The parameters of a typical GA are: population size, offspring size, maximum number of generation to run, crossover probability and mutation probability.


Q3. Is it guaranteed that a GA always returns optimal solution(s)?

Answer. No. GAs are nondeterministic in nature and it is not guaranteed that a GA will return the same solution or optimal solution in each run.


Q4. What are the other disadvantages of GAs?

Answer. GAs have weak theoretical basis, require many parameters tuning for good performance and sometimes are computationally expensive and thus are slow.

 

Source Books:

  1. T Back, DB Fogel and T. Michalewicz, "Evolutionary Computation 1; Basic Algorithms and Operators", Institute of Physics Publishing, 2000.
  2. Xin Yao,"Evolutionary Computation; Theory and Applications", World Scientific,1999.

Genetic Algorithm (GA)

Genetic Algorithms (GAs), first proposed and analyzed by John Holland in 1975, are optimization techniques based on natural evolution and adaptation. In a GA, a population of  candidate solutions is always maintained. Candidate solutions are sometimes named as Individuals, Chromosomes, etc. Each Individual is an encoded representation of variables of the problems at hand. Each component (variable) in an Individual is termed as Gene.

The sequences of a GA are initial population generation, selection of population for reproduction, creation of new population by using recombination and mutation, evaluation of new population, replacement of old population by new generation. The skeleton of a GA may be as follows:

1.t=0;
  Generate initial population P(t) at random;
2.Evaluate each individual in P(t);
3.While termination condition not satisfied do
  begin
    t=t+1;
    Select some parents S(t) from P(t-1);
    Generate offspring Q(t) by applying
    crossover and mutation on S(t);
    Evaluate offspring Q(t);
    Combine old population and new 
    offspring to generate P(t);
  end;

In many problems, the initial population is generated randomly, crossover and mutation are performed probabilistically; so GAs are somehow stochastic.

Many issues arise in design of a Genetic Algorithm. First of all how to encode the problem, i.e. how to transfer phenotype to genotype and vice versa. Some problems can be solved using binary encoding while some by order encoding (for example, Traveling Salesman Problem (TSP)). Fitness is calculated according to the objective function. For TSP,  fitness can be negative of distance of a tour or inverse of distance; so the lower distance, the better fitness. Next comes selection strategy--how to select parents for recombination. Whatever may be the selection method, the better chromosome will have better chance to be selected. Roulette wheel selection, tournament selection and rank-based selection are common selection methods.

Crossover operator is crucial for the success of a GA and it is also problem dependent. If the encoding is binary, the crossover is easier to implement. Consider two parents: A=010101101101 and B=111010 000111. To apply one-point crossover on these parents, first we have to fix the crossover point; usually this is determined randomly. Suppose the crossover point is between position 6 and 7. Performing one point crossover two offspring are produced as C and D. This is illustrated below:

Parents: A:010101101101
         B:111010000111
Offspring:C:010101000111
          D:111010101101
Crossover is applied in the hope the new offspring will be better than its parents. Crossover is applied with higher probability. One point, two points and uniform crossover are widely used. Partially matched crossover (PMX), order crossover, cycle crossover, edge recombination crossover and edge assembly crossover are commonly used crossing techniques for combinatorial optimization like TSP.  A practical approach of PMX can be found in details in the implementation of TSP by GA.

Mutation is a genetic operator that is used to alter one or more genes in an individual. This operator is used to prevent GAs from stagnating at local optima. For example, if C of the above example is mutated at position 3 (bit is inverted), the new mutated offspring would be: 

C:011101000111

Replacement strategy determines which offspring will replace which old individuals. Elitism, steady state replacement and CHC selection are widely used for this purpose. In CHC strategy, if the original population size is N, N offspring are generated, they are combined to get 2N individuals which are then sorted and the best N individuals are accepted for next generation.