[AIM] Evolutionary Algorithms

Day 4

Outline

  • Evolutionary Algorithms
  • Genetic Algorithms
  • Basic Components of Generic GAs
    • Representation
    • Initialisation
    • Fitness evaluation
    • Mate Selection
    • Crossover
    • Mutation
    • Replacement
    • Termination criteria

Evolutionary Algorithms

  • GA simulated natural evolution of individual structures at the genetic level using the idea of survival of the fittest via processes of selection, mutation, and reproduction(recombination)
  • An individual(chromosome) represents a candidate solution for the problem at hand
  • A collection of individuals currently “alive”, called population is evolved from one generation to another depending on the fitness of individuals in a given environment
  • Last generation will contain the final solution

EAs –Features

  • Avoid converging to local optima
  • Use exploration of the search space and exploitation of promising areas
    • Reproduction focuses attention on high fitness individuals, thus exploiting (exploitation) the available fitness information
    • Recombination and mutation perturb those individuals, providing general heuristics for exploration. Through recombination operators, reach better solutions by combining already found good solutions
  • Be independent of initial starting points
  • Conduct search in parallel over the search space
  • May be used together with other approaches

Genetic Algorithms

Generic Genetic Algorithm


Basic Components of GAs

  • A genetic representation (encoding) for candidate solutions to the problem at hand
  • An initialisation scheme to generate the first population of candidate solutions
  • A fitness function that plays the role of the environment, rating the solutions in terms of their fitness
  • A scheme for selecting mates (parents) for recombination
  • Crossover(recombination)
  • Mutation
  • Replacement strategy to select the surviving individuals for the next generation
  • Termination criteria

Representation

  • Each individual contains one chromosome
  • Each individual is evaluated and has an associated fitness value
  • Chromosomes contain a fixed number of genes: chromosome length
  • Traditionally binary encoding is used for each gene: Allele value {0.1}
  • A population contains a fixed number of individuals: population size
  • Each iteration is referred as generation
Population -> Individuals(Chromosome) -> Genes(Encoding in allele value)

Initialisation

Random initialisation: population size number of individuals are created randomly.

Fitness calculation

Fitness value indicates how fit the individual is to survive and reproduce under the current conditions and how much the current solution meets the requirements of the objective function

Generic GA - reproduction

Reproduction consists of
  • selecting individuals: a fitness proportionate selection method used => roulette wheel selection, tournament selection, rank selection, etc.
  • copying selected individuals into a mating pool (each individual may be selected more than once)
  • pairing individuals in pool for mating: mating pool consists of population size number of elements

Tournament Selection

This method involves running a number of “tournaments” among randomly chosen individuals (of tour size) selecting the one with best fitness at the end


Roulette wheel selection

There is a wheel, and the better the individual is, the bigger probability it will be chosen.
While candidate solutions with a higher fitness will be less likely to be eliminated, there is still a chance that they may be.

From the graph above, there is a formula for max or min problem.
For example, for a population like this, we can calculate the probability of each individual.

Then, we form a mating pool.. 4 random numbers will be thrown in (0, 1] to select 4 mates. If the random number is between 0 - 0.32, it will chose the second one (because its probability is 0.32)

Recombination/Crossover

  • Selected pairs/mates(parents) are recombined to form new individuals (children/offspring) - exchange of genetic material
  • crossover is applied with a crossover probability which in general is chosen close to 1.0

One point crossover

Generate a random number in [0, 1), if it is smaller than a crossover probability then
- select a random crossover site in [1, chromosome length]
- split individuals at the selected site
- exchange segments between pairs to form two new individuals

There are also other form of crossover:

Mutation

  • Loop through all the alleles of all the individuals one by one, and if that allele is selected for mutation with a given probability pm, you can either change it by a small amount or replace it with a new value
  • Mutation provides diversity and allows GA to investigate different regions of the search space(escaping)
  • Mutation rate is typically chosen to be very small. Choosing pm as 1/chromosome length implies on average a single gene will be mutated for an individual

Replacement Strategy

  • There are variety of strategies for replacing the old population by the new offspring population to form the next generation
  • (Trans-)Generational GA: N individuals produce aN offspring. So we need to choose N from (N+ aN). e.g.aN replace worst aN of N, sort (N+ aN) and choose N best(elitism)
  • Steady-state GA: Two offspring replace two individuals from the old generation. e.g. two offspring replace parents, or worst two of the population(elitism), or best two of parents and offspring replace parents or worst two of the population

Termination criteria

possible termination criteria:
  • A predefined maximum number of generations is exceeded
  • A goal is reached, for example
    • Expected fitness is achieved
    • Population converges
  • Best fitness does not change for a while
  • A condition is satisfied depending on a combination of above
What is convergence?
Gene convergence: a location on a chromosome is converged when 95% of the individuals have the same gene value for that location
Population convergence: a population is converged when all the genes have converged
Phenotypic convergence: average fitness of the population approaches to the best individual in the population

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文