Video summary

Lec 14 Genetic Programming

Main summary

Key takeaways

Educational

Genetic Programming

Genetic programming (GP) is an extension of genetic algorithms that evolves computer programs to solve a task. Instead of evolving fixed-length strings, GP typically evolves program structures represented as trees.

The approach was proposed by John Koza, whose work describes the method and a range of its applications.

GP begins with a population of randomly generated programs. Each program is evaluated against a set of tasks or examples, and selection and genetic operators produce new programs. Over successive generations, the process tends to favor programs that perform better.

Programs are assembled from:

  • Functions, such as arithmetic, mathematical, logical, or domain-specific operations.
  • Terminals, such as constants, variables, numbers, Boolean values, vectors, or other data types.

The function and terminal sets must be appropriate to the problem so that the resulting expressions form valid programs. In Lisp-style representation, program trees can be written as S-expressions.

Main Components of a GP System

  1. A set of program structures to evolve.
  2. Initial structures appropriate to the problem domain.
  3. A domain-dependent fitness measure for evaluating programs.
  4. Genetic operators that transform programs.
  5. A representation or description of individuals in each generation.
  6. Termination conditions that determine when to stop.

Fitness and Evolution

Fitness measures how well a program performs across a collection of fitness cases. One possible measure is the error between a program’s output and the expected output across those cases. Fitness can also account for program size, favoring smaller, more parsimonious programs when they achieve similar results.

Selection methods can be the same as those used in genetic algorithms, such as roulette-wheel or deterministic selection. The process continues until a program meets the desired performance threshold or a set number of generations has been reached. The best-performing program is then selected, potentially favoring a shorter program among similarly fit candidates.

Genetic Operators on Program Trees

  • Crossover: Select a subtree in each of two parent programs and exchange the subtrees to create offspring. The root can also be selected as a crossover point.
  • Mutation: Change a node in a program. For example, a terminal can be replaced with another terminal, or with a function and the required child nodes.
  • Permutation-like operation: Swap terminals or functions within a program, provided the resulting program remains valid.

Example: Kepler’s Third Law

The example seeks a program relating a planet’s orbital period (P) to its distance (A) from the Sun. Kepler’s law is given as

[ P^2 = C A^3 ]

In the normalized example, the target relationship is represented as

[ P = \sqrt{A \times A \times A}. ]

The terminal set contains (A), and the function set includes addition, subtraction, multiplication, division, square, and square root.

Candidate programs are tested against planetary data. A program is counted as correct for a case if its output falls within 20% of the expected value. Fitness is the number of correct cases among the six examples. A program that succeeds on all six meets the stated termination criterion; otherwise, the population can continue evolving.

GP can also be applied to other tasks, such as deriving relationships in electrical systems. The lecture points interested learners toward Koza’s book for further applications and implementation details.

Speakers and Sources

  • Speaker: An unnamed lecturer presenting an NPTEL course session on artificial intelligence.
  • Source mentioned: John Koza, cited as the proposer of genetic programming and the author of books on the topic.
  • Example concept: Kepler’s third law of planetary motion.

Rate this summary

Your feedback will help improve summaries.

Improve this summary

Reprocess with a stronger model when the summary feels incomplete or inaccurate.

Pro

Translate summary in another language

Pro

Ask questions to this video

Chat for follow-up questions, clarifications, and source-backed answers.

Coming soon

Share this summary

Original video