Smart Systems Lecture 6: Genetic Programming
48 Questions
3 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 is the primary purpose of Genetic Programming (GP)?

  • To analyze genetic sequences
  • To create complex user-defined programs
  • To automatically solve problems without predefined solutions (correct)
  • To require specific algorithms from the user

    • LISP is chosen as the main programming language for Genetic Programming because it allows programs to be manipulated as data.

    True

    What is the role of 'survival of the fittest' in Genetic Programming?

    To find solutions by selecting and breeding the most effective programs.

    In LISP, the mathematical expression for addition is represented in _____ notation.

    <p>prefix</p> Signup and view all the answers

    Match the genetic programming components with their descriptions:

    <p>Generate Population of Random Programs = Step where initial solutions are created Run Programs and Evaluate Their Quality = Step for assessing how effective a program is Breed Fitter Programs = Step for combining the best solutions Solution = Final output of the genetic programming process</p> Signup and view all the answers

    Which of the following expressions demonstrates prefix notation?

    <ul> <li>2 1</li> </ul> Signup and view all the answers

    The prefix notation in LISP includes parentheses to denote order of operations.

    <p>False</p> Signup and view all the answers

    What type of problems can Genetic Programming solve?

    <p>A wide range of problems, including complex algorithm design.</p> Signup and view all the answers

    What does an expression tree primarily represent?

    <p>A visual representation of numerical expressions</p> Signup and view all the answers

    Genetic algorithms cannot evolve expression trees to fit data.

    <p>False</p> Signup and view all the answers

    What are the two types of nodes in an expression tree?

    <p>Terminals and functions</p> Signup and view all the answers

    The prefix notation of the tree represented as + 1 2 (IF (> TIME 10) 3 4) is an example of __________.

    <p>expression tree</p> Signup and view all the answers

    Match the following trees with their operations:

    <p>Expression Tree 1 = + 1 2 Expression Tree 2 = * 2 (+ 1 2) Expression Tree 3 = * 9 (+ (- 2 1) 4)</p> Signup and view all the answers

    Which of the following is considered a primitive set?

    <p>Functions and terminals</p> Signup and view all the answers

    In an expression tree, depth refers to the longest path from the root to a leaf node.

    <p>True</p> Signup and view all the answers

    What fitness function is used for in genetic algorithms?

    <p>To evaluate how close the expression is to the data and answers.</p> Signup and view all the answers

    Which method generates trees with the same shape and size?

    <p>Full Method</p> Signup and view all the answers

    The Grow Method generates trees with fixed depth.

    <p>False</p> Signup and view all the answers

    What kind of structures do the terminal set include?

    <p>Variables and Constant Values</p> Signup and view all the answers

    The __________ method combines both the full and grow methods.

    <p>Ramped Half-and-Half</p> Signup and view all the answers

    Match the following tree generation methods with their characteristics:

    <p>Full Method = Same shape and size Grow Method = Variable size Ramped Half-and-Half = Combination of full and grow methods</p> Signup and view all the answers

    Which of the following nodes appears in Tree 1 of the Grow Method?

    <p>1</p> Signup and view all the answers

    In the Full Method, nodes at levels less than maximum depth are chosen from both function and terminal sets.

    <p>False</p> Signup and view all the answers

    What are 0-arity functions mentioned in the terminal set?

    <p>rand, go_left</p> Signup and view all the answers

    What does the grow initialization method do?

    <p>Creates a tree with a maximum depth.</p> Signup and view all the answers

    In tournament selection, the best individual from a set of randomly selected individuals is chosen to be the parent.

    <p>True</p> Signup and view all the answers

    What is one disadvantage of tournament selection?

    <p>It reduces diversity in the next generation.</p> Signup and view all the answers

    In fitness-proportionate selection, individuals are selected based on their ______ values.

    <p>fitness</p> Signup and view all the answers

    What is the purpose of subtree crossover?

    <p>To create offspring by replacing part of one parent's tree with another's.</p> Signup and view all the answers

    Match the following concepts with their descriptions:

    <p>Crossover = Combining parts of two parent trees Mutation = Randomly altering parts of a tree Reproduction = Copying an elite individual to the next generation Fitness-Proportionate Selection = Choosing individuals based on fitness values</p> Signup and view all the answers

    In the grow method, all branches must reach the maximum depth before being terminal.

    <p>False</p> Signup and view all the answers

    Name one type of selection strategy used in breeding the next generation.

    <p>Tournament selection or Fitness-Proportionate selection</p> Signup and view all the answers

    What does the process of subtree mutation involve?

    <p>Replacing a mutation point with a randomly generated tree</p> Signup and view all the answers

    Point mutation replaces a randomly selected node with another primitive of a different arity.

    <p>False</p> Signup and view all the answers

    What is the purpose of the fitness function in genetic programming?

    <p>To measure how well a program solves a given problem</p> Signup and view all the answers

    The operation (y+1) * (x/2) corresponds to which offspring tree?

    <p>Tree 2</p> Signup and view all the answers

    Match the type of mutation with its description:

    <p>Subtree Mutation = Replacing a mutation point with a new tree Point Mutation = Replacing a node with a primitive of the same arity Both Mutations = Used in genetic programming for tree modification Fitness Function = Measures program performance in solving problems</p> Signup and view all the answers

    Which of the following is a feature of depth-first search order in genetic programming?

    <p>Evaluating the left subtree before the right subtree</p> Signup and view all the answers

    The correct encoding of a problem through fitness functions is crucial for the success of genetic programming.

    <p>True</p> Signup and view all the answers

    What does the primitive set for genetic programming define?

    <p>The search space of programs</p> Signup and view all the answers

    What is one way to measure fitness in Genetic Programming?

    <p>The amount of error between output and desired output</p> Signup and view all the answers

    Genetic Programming is effective when the interrelationships among relevant variables are well understood.

    <p>False</p> Signup and view all the answers

    What is one disadvantage of GP trees during the genetic programming process?

    <p>They can grow sparse and unbalanced.</p> Signup and view all the answers

    Genetic programming can be used in stock market prediction, advanced mathematics, and _____ applications.

    <p>military</p> Signup and view all the answers

    Which of the following is NOT a preparatory step in setting up Genetic Programming?

    <p>Choosing a programming language</p> Signup and view all the answers

    Match the following components of Genetic Programming with their descriptions:

    <p>Terminal Set = Basic inputs to the program Function Set = Operations that can be performed Fitness Measure = Criteria to evaluate solutions Parameters = Settings that control the evolutionary process</p> Signup and view all the answers

    The fitness measure in Genetic Programming only considers the time required to reach a target state.

    <p>False</p> Signup and view all the answers

    Name one condition under which Genetic Programming is particularly useful.

    <p>When the search domain is huge and solutions are sparsely distributed.</p> Signup and view all the answers

    Study Notes

    Smart Systems and Computational Intelligence

    • Lecture 6 of the Smart Systems and Computational Intelligence course
    • Topics covered include Genetic Programming (GP).

    What is Genetic Programming?

    • Genetic Programming (GP) is a technique in Evolutionary Computation (EC)
    • GP automatically solves problems without needing the user to specify the form or structure of the solution
    • GP is a systematic and domain-independent method for computers to solve problems automatically, starting from a high-level statement of the problem
    • GP saves time by automating the design of complex algorithms, leading to optimal solutions

    How is Genetic Programming?

    • GP uses a control flow based on the principle of "survival of the fittest" to find solutions
    • The process involves generating a population of random programs
    • Evaluating the quality of these programs
    • Breeding fitter programs from the best programs

    Genetic Programming

    • Genetic programming manipulates programs using genetic operators
    • LISP is used as the main language for genetic programming manipulation due to the ease of manipulating programs as data and executing them as programs
    • GP uses prefix notation in languages like LISP, instead of standard mathematical notation

    Genetic Programming- Example

    • Examples of prefix notation include:

      • +2 1
      • *+2 1 2
      • +*-2 1 4 9

    • Expression trees can easily be built from these prefix notation strings

    • For example: the prefix string "+ 1 2 would be translated to an expression tree with + as the root node and 1 and 2 as child nodes

    Genetic Programming

    • Expression evaluation is easier with GP
    • Genetic algorithms can evolve an expression tree to generate a close fit to given data
    • The process involves "splicing" and "grafting" trees, evaluating the results, and using a "fitness function" to evaluate how close the expression is to the answer

    Algorithm

    • Randomly create an initial population of programs from available primitives
    • Repeat the following steps until an acceptable solution is found or a stopping condition is met:
    • Execute each program and evaluate its fitness
    • Select one or two programs from the population based on probabilities related to their fitness, to participate in genetic operations
    • Create new programs by applying genetic operations (with specified probabilities)

    Tree Structure

    • Programs are represented by tree structures
    • The programs use a prefix notation

    Basics

    • Terminal: Variables and constants (e.g., x, y, 3) that form the leaves of the tree
    • Function: Arithmetic operations (+, *, max) that are internal nodes in the tree
    • Primitive Set: The combination of functions and terminals

    Terminal Set

    • Variables: (e.g., x, y)
    • Constant values: (e.g., 3, 0.45)
    • 0-arity functions: (e.g., rand, go_left)

    Initialisation of Population

    • Full Method: internal nodes from function sets until the maximum depth is reached; then selects a node from the terminal set until all branches end at the same level
    • Grow Method: Picks nodes from the primitive set up until maximum depth is attained
    • Ramped Half-and-Half Method: A combination of Full and Grow methods; constructing half of the population using the full method and the other half using the grow method. Maximum depth of the tree not fixed

    The Grow Method

    • Trees have variable sizes.
    • Node labels at levels below the maximum depth are selected from both function and terminal sets
    • Node labels at the maximum depth are selected from the terminal set

    The Full Method

    • All trees have the same shape and size.
    • Node labels from the function set only are selected for levels below the maximum depth
    • Node labels from the terminal set are selected at the maximum depth

    Ramped Half-and-Half

    • Produces trees of various shapes and sizes using a mix of the full and grow methods.
    • Creates varying populations using both techniques to generate diverse solutions.

    Initialization of Population (Full Method)

    • Shows examples of creating a full tree of depth 2.
    • Demonstrates the process of selecting terminal nodes in the full method

    Initialization of Population (Grow Method)

    • Shows examples of how trees grow differently because random nodes are selected from the primitive set
    • Shows how at points the left branch of a node is shut down, before the maximum depth of the tree has been reached

    Selection Strategies

    • Tournament Selection: Chooses the best individual from a randomly selected set of individuals to be a parent.
    • Advantage: Rescales fitness within the population
    • Disadvantage: Small fitness differences get exaggerated in subsequent generations

    Selection Strategies

    • Fitness-Proportionate Selection: Select individuals based on their fitness values. Weights are determined by a proportional fitness function.

    Breeding Next Generation

    • Crossover, mutation, and reproduction are used to generate offspring from parents
    • Subtree Crossover: Replaces a subtree from one parent with a subtree from another parent
    • Reproduction creates a copy of a superior individual (an elite individual) to the subsequent generation

    Mutation

    • Subtree Mutation: Replaces a point in the program with a newly generated tree.
    • Point Mutation: Randomly selects a node and replaces it with a different primitive of the same arity.

    Fitness Function

    • Evaluates the quality of the computer program in solving the given problem.
    • Proper coding of fitness functions is vital for successful GP performance.
    • The fitness function runs the program on appropriate data and checks its performance relative to the correct answer by using an error parameter

    Fitness Function

    • Fitness can be measured in different ways. These include:
    • Comparing generated output to desired output
    • Calculating the time needed to reach a desired state/target
    • Measuring how accurately the program can classify objects
    • Checking how efficiently the program succeeds at a particular task

    Five Preparatory Steps to Set Up GP

    • Determining the set of terminals (T).
    • Determining the set of functions (F).
    • Determining the fitness measures needed.
    • Determining the GP parameters to use.
    • Determining the termination criteria to end the process

    Areas Where GP Will Do Well

    • Useful when interrelationships between variables are poorly understood.
    • Useful when solution size and shape are difficult or expensive to determine
    • Useful when search space is large and solutions are scattered.
    • Useful when simulators can effectively check potential solutions, but direct solution discovery is difficult.

    Genetic Programming

    • GA limitations in a wide search space where an infinite numerical and equation possibilities exist
    • GP tree struggle to grow effectively sometimes and thus creating an unbalanced sparse population. This may negatively affect results.

    Studying That Suits You

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

    Quiz Team

    Related Documents

    Smart Systems Lec 6 PDF

    Description

    This quiz tests your knowledge on Genetic Programming, a crucial topic in the Smart Systems and Computational Intelligence course. Explore the principles behind GP, its applications in problem-solving, and how it automates the design of algorithms through the evolutionary computation paradigm.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser