Genetic Programming
August 28, 2014
IBA GroupPavel CharnyshArtificial intelligence, intelligent self-learning machines, systems that can advise on how to do work better, and robotics – all of this has always been like magic to me. When I studied at the university, I was carried away by these topics. It is even more fascinating to use knowledge from one field for another and thus solve the tasks that seemed unsolvable.What do you think about the interaction of artificial intelligence and the theory of evolution, one of the most interesting open issues in biology? As I worked with algorithms and not hardware, I kept wondering, how we can teach a computer to be intelligent. I did research on the topic within an internal project at IBA. This article gives an overview of Genetic Programming and my speculations on how to use it in software development.As Wiki says, ‘Genetic Programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. Essentially GP is a set of instructions and a fitness function to measure how well a computer has performed a task. It is a specialization of genetic algorithms (GA) where each individual is a computer program. It is also a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program’s ability to perform a given computational task’.In my view, GP is a way to find a solution using atomic user-defined blocks.The following are the main principles of GP:1. Initially, we are given past performance data to build the most suitable program for reproducing the same principles of data structure in the future. We assume that the initial data were produced by a kind of a black box. We have historical input and output data to reproduce this system with the same rules and principles for future use.2. All programs are members of a population. It means that we get not the only solution, but a set of solutions and can choose the most suitable one.3. Changes in a population are made using an iterative method. At each iteration, the programs that are most fit for crossover and replenishment of the population are selected.4. A fitness function is used to determine, if a program is fit for the purpose. It is a user-defined metric that numerically presents the ability of a program to solve the defined task (to fit the mapping of the input and output parameters for a given data set).5. The fittest individuals of a population are selected to develop the population just the way evolution selects species.6. Changes that can be implemented in the surviving members are similar to biological evolution. A member can be mutated or crossed with another member of the population.7. A stop condition is defined for a fitness function, when one can stop GP and pick up a solution.To grow up a population, a programmer must define primitive blocks which will form an individual. These are terminals, including constants and variables, and primitive expressions such as +, -, *, /, cos, sin, if-else, foreach, and other predicates. Any program can be presented as a tree built up of these blocks. This way, any individual of a population can be presented.


