4.7.1 Genetic Algorithms

A genetic algorithm [45] is a stochastic optimization algorithm, derived from the concepts of the biological theory of evolution. Genetic algorithms use the information from E _{T r}( w) only (without gradient information). They are capable of escaping from the traps of the local minimum and finding the global minimum. Genetic algorithms have the following steps.

• Step 1: Set up an initial population of w points, w ⁽ⁱ⁾, i = 1, 2, , K, where K is the size of the population.

• Step 2: Evaluate the fitness of each point. The fitness function is defined in such a way that points with lower (higher) values of E _{T r}( w) will have higher (lower) fitness. For example,

  (4.63)

  where a and ? are constants.

• Step 3: Choose lucky parents. A random selection process is adapted such that two w points with higher fitness values in the population are more likely to be selected. Let the selected points also called parents be w ^A and w ^B.

• Step 4:Generate an offspring from the parents as w ^(new) = function ( w ^A, w ^B ). This step is usually achieved by a crossover operation between w ^A and w ^B.

The generation of offspring is well-defined for discrete optimization problems where w is a binary vector. For...