Simple Genetic Algorithm (SGA) Variants
10 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What type of crossover operator is used in the SGA approach?

  • Scattered crossover
  • Uniform crossover
  • 1-point crossover (correct)
  • 2-point crossover
  • What is the population size in the SGA approach?

  • 8
  • 4 (correct)
  • 16
  • 2
  • What type of mutation operator is used in the SGA approach?

  • Swap mutation
  • Deletion mutation
  • Insertion mutation
  • Bitwise mutation (correct)
  • What is the purpose of the selection mechanism in the SGA approach?

    <p>To select parents for crossover</p> Signup and view all the answers

    How are the individuals represented in the SGA approach?

    <p>Using a 5-bit binary encoding</p> Signup and view all the answers

    What is a shortcoming of the SGA approach?

    <p>The representation is too restrictive</p> Signup and view all the answers

    What type of selection mechanism is used in the SGA approach?

    <p>Roulette-Wheel Selection</p> Signup and view all the answers

    What is the survivor selection mechanism used in the SGA approach?

    <p>Generational Model</p> Signup and view all the answers

    What is the purpose of the initialization step in the SGA approach?

    <p>To generate the initial population</p> Signup and view all the answers

    What is a key difference between classical AI approaches and evolutionary approaches to the EIGHT-QUEENS problem?

    <p>Whether they are incremental or not</p> Signup and view all the answers

    Study Notes

    Simple Genetic Algorithm (SGA)

    • Representation: Bit-Strings
    • Recombination: 1-Point Crossover
    • Mutation: Bit-Flip
    • Parent Selection: Fitness Proportional - implemented by the Roulette-Wheel
    • Survivor Selection: Generational

    Reproduction Cycle of SGA

    • Select parents (with duplication) for the mating pool (size of mating pool = population size)
    • Shuffle the mating pool
    • Apply crossover for each consecutive pair with probability pc (and the children replace the parents immediately)
    • Apply mutation for each offspring (bit-flip with probability pm independently for each bit)
    • Replace the whole population with the resulting offspring

    Suitable Values for SGA Parameters

    • Mutation rates: between 1/l and 1/μ
    • Crossover probabilities: around 0.6 - 0.8
    • Population sizes: in the fifties or low hundreds

    Maximize x Problem

    • Simple problem: maximize x^2 over the integers in the range {0, 1, ...}
    • Can be solved using SGA

    Evolutionary Algorithm Variants

    • Genetic Programming
    • Evolutionary Strategy
    • Differential Evolution
    • Swarm-Intelligence based algorithms:
      • Ant Colony Optimisation
      • Particle Swarm Optimisation
      • Gravitational Search
      • etc.
    • Physics/Chemistry-based algorithms:
      • Simulated Annealing
      • etc.
    • Bio-Inspired algorithms:
      • Dolphin Echolocation
      • Flower Pollination Algorithm
      • etc.

    Genetic Algorithms (GAs)

    • Developed in the 1960s
    • Initially conceived by J.Holland as a means of studying adaptive behavior
    • Most widely known type of EAs
    • Widely used for teaching EAs and is the first EA many people encounter

    Shortcomings of SGA

    • Representation is too restrictive
    • Mutation & Crossover operators only applicable for bit-string & integer representations
    • Selection Mechanisms are sensitive for converging populations with close fitness values
    • The Generational Population Model can be improved with explicit survivor selection (for instance, elitism)

    EIGHT-QUEENS Problem

    • Can be solved using evolutionary approach
    • Classical AI approaches to this problem work in a constructive, or incremental, fashion
    • Evolutionary approach is drastically different because it is not incremental

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Description

    This quiz explores the technical summary of Simple Genetic Algorithm (SGA) variants, including representation, recombination, mutation, and selection methods. Learn about the traditional workflow and reproduction cycle of SGA.

    More Like This

    Use Quizgecko on...
    Browser
    Browser