Beyond Conventional Search

Hill Climbing

Beyond Conventional Search - Hill Climbing.png#invert

Follow the slope to converge towards the local maxima. This is defined by a function (like a Heuristic Function).

Simulated Annealing

Idea: escape local maxima by allowing some "bad" moves.
But gradually decrease their size and frequency

Idea: keep states instead of ; choose top of all their successors.
Problem: quite often, all states end up on same local hill.

Close analogy to natural selection!

Genetic Algorithms

All methods of evolutionary computation simulate natural evolution by creating a population of individuals, evaluating their fitness, generating a new population through genetic operations, and repeating this process a number of times.

Steps To GA

  • Step. Represent the problem / variable domain as a chromosome of a fixed length.
    • Choose the size of a chromosome population
    • The crossover probability
    • And mutation probability
  • Step. Define a fitness function to measure the performance (or fitness) of an individual chromosome in the problem domain. This function is used to determine the best solutions to "mate"
  • Step. Randomly generate an initial population of chromosomes of size .
  • Step. Calculate the fitness of each individual chromosome.
  • Step. Select a pair of chromosomes for mating using the fitness function
  • Step. Create a pair of offspring chromosomes by applying the genetic operators - crossover and mutation.
  • Step. Place the created offspring chromosomes into the new population
  • Step. Repeat step 5 until the size of the new chromosome population reaches the size of the initial population .
  • Step. Replace the initial (parent) chromosome population with the new (offspring) population. (Or make them compete for fitness)
  • Step. Go to Step 4 and repeat

Components of a GA

  • Encoding technique (gene, chromosome)
  • Initialization procedure (creation)
  • Evaluation function (environment)
  • Selection of parents (reproduction)
  • Genetic operators (mutation, recombination)
  • Parameter settings (practice and art)

Chromosomes

A chromosome represents a solution in some way. These could be:

  • Bit strings
  • Real numbers
  • Permutations of elements
  • Lists of rules
  • Program elements
  • any data structure

GA Operators

Crossover (Recombination)

The crossover operator combines the information from two "parents" without changing the data itself.

Mutation

Mutation represents a change in the gene (unlike a crossover). The role of this is to provide a guarantee that the search algorithm is not trapped on a local optimum. This value is usually kept very low, usually between 0.001 and 0.01.

Evaluation

This decodes a chromosome and assigns it a fitness. This is the only relationship between the GA and the problem it is solving.

Deletion

Removes a chromosome from the population.

Generations

GA represents an iterative process. Each iteration is called a generation. A typical number of generations for a simple GA can range from 50 to over 500. The entire set of generations is called a run.

Because GAs use a stochastic search method, the fitness of a population may remain stable for a
number of generations before a superior chromosome appears.

TSP as Genetic Algorithm

Representing TSP as an Encoding

We will represent each solution as an ordered list of city indicies. This is known as an order-based GA.

Beyond Conventional Search - GA TSP Let.png#invert

These lists can be crossed over, or cities can be switched.

Keep track of changes from parent to child
Determine whether that change was detrimental or supplemental (did the fitness go up or down)

If it was supplemental then duplicate it and cross it with another supplemental chromosome.
If it was detrimental then replace it with the most supplemental chromosome that happened in the last generation.

In other words rather than crossing based on total fitness, cross based on the change in fitness.

The base case for this (since you have to start with some change) would be that sufficiently neutral changes are always mutated.

A mutation would be applied to each supplemental duplicate chromosome and each detrimental chromosome. This mutation would either change a single city to a random other city, or swap two of it's own cities.

So:

  1. The mutation either randomly changes the city, or swaps two existing cities.
  2. Force all paths to start on the same point.
  3. If the fitness of a chromosome does not sufficiently change between generations, then mutate it.
  4. If the fitness goes up then swap it's changes with another chromosome who's fitness also went up.
  5. If the fitness went down then replace it's changes with a chromosome who's fitness went up and mutate it.