Smart Systems Lecture 6: Genetic Programming

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.

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.