Please enable JavaScript.

Coggle requires JavaScript to display documents.

Search techniques - Coggle Diagram

- - - - IRS-RS-Day1-Slide67
      - Will get stuck at local optimum since it doesn't look back
    - - Record a few previous moves in the Tabu List so that can't immediately return to previous points. But after few iterations, all is well again
  - - - Hill Climbing that sometimes accept random moves
        
        If improving next move, definitely take it
        
        Else, take it with some probability depending on temperature
        
        The higher the temperature, the more energy we have, we can move uphill escaping local minima
    - - Initial Population
        
        Evaluate fitness and choose parents based on fitness
        
        Crossover and mutate to get children
        
        Add parents + children the new population (return to 2)
        
        Terminate when criteria satisfied
        
        Generational GA, replace entire pop
        
        Steady State GA, just replace the worst
        
        How to choose
        
        Roulette Wheel (IRS-RS-Day3-Slide24)
        
        Rank (just rank by best to worst, then give the best highest fitness value)
        
        Linear or exponential (first is given 1, second is given s (=0.99) and third is s2 = (0.99 * 0.99) etc
        
        Tournament (IRS-RS-Day3-Slide28)
        
        How to crossover
        
        One point/multipoint (typically low constant value of 2)
        
        IRS-RS-Day3-Slide31
        
        Uniform cross over with a mask
        
        Crossover rate
        
        1.We have a probability of crossover.
        
        Now, we generate a random number between 0 - 1. If random no. < probability, select the given chromosome
        
        After selected two chromosomes, we generate a random integer number from 1 to m-1 (no. of bits of chromosome). This random number is crossover point
        
        After crossover, leave this chromosome aside.
        
        IRS-RS-Day3-Slide34
        
        How to mutate
        
        Have a probability of mutation
        
        For each bit in all the chromosomes of the population, get a random number in range of 0 - 1. If random number < prob of mutation, then mutate the bit.
        
        When to stop
        
        After fixed no. of generations
        
        When a chromosome with high enough fitness value
        
        After all the chromosome in a population is homogenous enough
        
        How to improve the GA solution
        
        Method for encoding solutions
        
        Method for selecting individuals
        
        Choices of genetic operators (crossover and/or mutate and/or selection)
        
        Parameter settings - population size, crossover probability, mutation probability
        
        When to use
        
        Cannot enumerate all possible solutions, and this is an optimisation problem
      - IRS-RS-Day3-Slide15
  - - - Distance travelled + straight line distance from current node till goal
      - IRS-RS-Day1_Slide76
  - - - A*, Hill Climbing
    - - Tabu Search, Simulated Annealing, GA
    - - Avoid repeated states
        
        Some can't avoid like route finding problems
        
        Trade off between space (store every past solution) and time (repeated visit same solution cos forgot)
        
        Can try to avoid by having closed and open list. closed list is by storing nodes that were previously expended
- - - - IRS-RS-Day1-Slide24
      - Applications,
        find things that only has on solution e.g., maze
    - - Examples like web crawlers
        (go to a webpage and get all the links, dunnid to go into the links), or find nearby places (like clinics etc)