Psyops Concepts: Program Space

A Program Space is Really Messed Up

After having conceived the notion of search space, it may be quite useful to understand what is a program space. If you are familiar with genetic programming (GP), you may have heard about the term program space or the phrase that the search space in GP is composed of all the possible computer programs. So what is program space? Let us try to extrapolate about program space through our imagination a little bit.

Program space is also a search space. The search space in numerical optimization may be a real-valued hyper-plane. Obviously it depends on whether the coefficients you are trying to tune assume real values. In the case of integer programming, for instance, the search space is an integer-valued hyper-plane. As discussed elsewhere, the search space in GP corresponds to all the possible computer programs that might be the candidate solutions to a problem.

However, it not possible to make a mental picture of the program space in one's mind. The mere reason is that human mind can not visualize beyond three dimensions. However, we can try to understand the program space by listing the same reasons due to which it cannot be visualized.

GP normally utilizes a quality of computer programs that they can be represented by their syntax tree. This makes a lot of things easier for GP practitioners. For instance, it makes implementation, adaptation, execution and manipulation of GP programs easier if they are represented as syntax trees.

GP also normally restricts the size of a computer program to 17. One can have a program represented as an n-ary tree in GP. This means that the various branches of the tree can have either one, two or three leaves (or children). A branch normally does not have more than three leaves, however, there is no restriction. Moreover, a tree in GP may have many nodes either representing a coefficient, a function, an operand or a system variable.

But why do we care about all of this information? The reason is that knowing all of this we may get an idea that how much flexibility is allowed to GP in developing a tree that represents a computer program or a mathematical model. Let us call this as degree of freedom of some sort. What this tells us that a tree in GP is not restricted to acquiring a form that may be captured with a few number of parameters. We have the depth, the variables, the various functions and their various arities and coefficients that can assume random values. Moreover, all of the building blocks of a tree are again not expected to occupy a certain fixed position, they may occupy different positions.

All of these factors literally obfuscate the problem of visualizing a GP tree. In simple words it may be said that all of these factors and various combinations of these factors alone require different planes for themselves for developing concrete mathematical notions of program space. In other words, a program space is increasingly hyper-planar to the extent that it cannot be visualized easily. However, discussing it somehow is beneficial in the sense that we can get an idea that how difficult it actually is to conceive a GP program space. Undoubtedly, appreciating this difficulty fully in itself is synonymous to achieving a great milestone.