Genetic Programming

Table of Contents:

Genetic Programming (Wolfgang et al., 2009; Pytela, 2012) is an extension of GAs. Although inspired by biological evolution, GP is a machine learning technique used to derive the optimal solution on the basis of fitness score. It aims to achieve automatic programming by using natural selection principles and operations that are biologically inspired, namely crossover and mutation (as used in GA). Being a domain independent method, in order to derive solutions to specific problems it genetically breeds a population of computer programs.

Both GA and GP are special optimization methods of EAs. Both approaches start with initialization of some random population (input variables set in the case of G A (Zhang and Cheng, 2009) or a tree with operator and variables in the case of GP). The population

FIGURE 14.7

Genetic programming—basic representation.

initialized is then evaluated based on a fitness function (function to be optimized) and selection is made for the fittest individual (those with the solution nearest to the required solution). The individuals selected are then paired up for crossover. There is a chance of mutation occurring within any member of the population with a certain probabilistic value. The above operations are based on Darwin's theory of survival of fittest whereby if the population is evaluated at any given time on a fitness test—for example, climatic conditions or level in food chain—the one that survives this fitness test will reproduce to produce a new generation. The new generation is again evaluated on the same or a different fitness test and the process continues until all the individuals in the population are fit. The population set which does not lead to a fit offspring moves towards extinction with the passage of time. There is also a probability of mutation, for example, the organism modifies its parts to adapt to given circumstances; however, since it is a chance modification, mutation may not always lead to a fit individual.

Like biological organisms that are made up of cells consisting of a nucleus enclosing the genetic material "genes" in a unit called a "Chromosome," our problem also involves chromosomes, which are input variables in the problem represented in the form of a parse tree. Input variables can be represented as nodes of terminals and operators where each node corresponds to a biological nucleotide. The sub tree of the main parse tree having a tendency to alter the objective is called a gene and a collection of genes is called a chromosome. The total sum of the entire chromosome represents the genotype of the system and its actual interpretation corresponds to is its phenotype, which is the solution it actually leads to.

In GP, the genes are the elementary elements of an individual which are grouped together to form code. A separate platform is of a similar construction to a tree. Genes are of two kinds, namely utilities and stations. In sapling language, nodes with branches are called functions, whereas nodes without branches are called terminals (leaves). An example of an equation is 7(x + 9), where the functions are + and *, whereas 7, x and 9 are the terminals. Selection or creation of genes within a GP system is decided by the user. It is an important decision as poor selection may result in an insignificant solution (Figure 14.7).

14.5.1 Genetic Programming Algorithm

Step 1. The initial population is created based on random choice from the available primitives. Step 2. Repeating loop.

Step 3. Each individual program is executed and checked for its fitness.

Step 4. On the basis of fitness probability, one or two programs are selected.

Step 5. Genetic operations with specific probability are applied to create new programs. Step 6. Until condition (an acceptable solution/stop criteria have been reached).

Step 7. The best solution so far is returned.

14.5.2 Basic Terminology Used in Genetic Programming
1. Terminal set—This mainly consists of the program’s external inputs as independent variables and constants.
2. Operator set—This mainly consists of arithmetic functions like add, multiply, subtract, divide and related branching operators.
3. Fitness function—The fitness function specifies what needs to be done. It is a numeric value attached to each individual population. It is a primary method to check the appropriateness of the solution.
4. Control parameter [m]—Specification of the control parameter is an administrative task to control the entire run process. The major control parameters are:

a. Inhabitants scope—This is a significant restriction as it affects the solution to a large extent. As a rule, we can say that "the higher the complexity of a problem, the greater the population size required".

b. Supreme number of compeers—Time is an important factor in evolutionary processes, thus a higher number of generations may result in higher probability of reaching an optimal solution. On the contrary, no guaranteed solution can be reached even if the generations evolve further.

c. Probability of crossover and reproduction.

14.5.3 Advantages of Genetic Programming over Genetic Algorithms

The following are the criteria which prove that GP is better than GAs:

1. Chromosomal Representation: GAs follow a string of characters, which is generally a binary string representing its chromosome, while GP uses a tree to do the same. For example, 0101010110 may be a chromosome structure for GAs, while a tree such as that shown in Figure 14.7 may be an example of a chromosome in GP. It is very noticeable that trees are really easy to parse as each node has a meaning and algorithms can be applied easily to manipulate trees, while it is difficult to mark the start and end of the string if multiple chromosomes are represented together.
2. Chromosome Length: GAs deal with fixed length chromosomes in contrast to the variable length in GP. The fixed length representation makes it really difficult to apply their structure dynamically. Moreover, variability in chromosomal length increases the application domain and removes the coding restrictions.
3. Domain Syntax: Generally the domain specific symbols are encoded to a binary string or any other character string in GAs, which is not the case with GP. This leads to a reduction in time required for encoding and decoding domain input variables in GP.
4. Executables: Since GAs have an intermediate encoding format, executables which can be fed directly to the interpreter are very rarely found except in a few situations where input variables are actually binary. On the other hand, when we talk about GP, the nodes in the tree structure have a defined meaning as they are either a terminal or an operator, and an interpreter is available for tree manipulation, so it is easy to have executables of GP code.
5. Basic Domain: GA is a search optimization process, while GP is an extension of GA which not only provides a search functions but also helps in the generation of new programs. These programs may be actual programs where blocks of code are terminals while conditional, branching or looping statements act as operators. When dealing with mathematical expressions, the operators are actual mathematical operators, while the terminals are functions or constants. This makes GP applicable to a wide range of domains.

Particle Swarm Optimization (PSO)

PSO is a swarm intelligence based procedure (Lhotska, 2008) inspired by the social behavior of birds flocking. PSO shares many similarities with GAs and GP, specifically random initialization of the population and updating generations when searching for an optimal solution. In comparison with GAs and GP, PSO does not use evolutionary operators, namely mutation and crossover. Potential solutions in PSO are called subdivisions which aim to explore the search space by imitating the optimal particles. Unlike GAs, implementation of PSO is easier because few parameters require adjustment.

PSO works by simulating the flocking behavior of birds. In simple terms, imagine a scenario where the aim is for a group of birds (swarm) to search for food in a given area.

Constraints:

1. All birds are hungry and simultaneously searching for food.
2. The area has only one piece of food.
3. The location of the food is not known to any bird.

Problem: Finding the best strategy to discover the food.

Solution: Imitating the bird who is nearest to the food and evaluating the distance from the food in an iterative manner.

The behavior of the birds mentioned in the scenario, where the tasks are multiple but the resources are limited, is simulated in the computation domain and the algorithm is called PSO. By learning from the above scenario, diverse real-time problems are solved using PSO where in a given search space each solitary resolution is referred to as a "bird" (particle). A fitness value is assigned to each particle according to the value derived on the basis of the fitness function to be optimized. The particles are directed for movement (flying) by their velocity (inertia). The direction of overall movement can change whenever a particle's best movement is better than the overall swarm's best. The entire operation makes the movement disordered and maximizes the probability of closeness to global minima of the cost function.

The algorithm begins with initialization involving the with collection of random particles (solutions) and updating generations to search for optima. Each iteration results in updating the following "best" values:

1. Fitness (best solution) achieved so far by particle is referred to as p_best (personal best).
2. Fitness (best solution) evaluated by PSO among particles in the population is referred to as g_bcst (global best).
3. Best value achieved by a particle in its topological neighborhood is referred to as l_best(local best).

Once the two best values, namely p_best and g_bes„ have been evaluated, the velocity and position of the particle are simplified through the following two equations:

where

p_v refers to particle velocity If refers to learning factor

randQ represents the random number between 0 and 1

The first equation updates velocity for each particle, whereas the second equation identifies the location of each particle. In the algorithm the information is shared with others using g_best and l_best only, which makes it a one-way statistical distribution instrument, whereas in GAs chromosomes share all information with each other. Thus the statistical distribution instruments are different in GA and PSO.

PSO offers one more advantage over GA, namely assigning real numbers as particles rather than genetic operators or binary encoding.

The pseudo code of the PSO is shown in Figure 14.8.

FIGURE 14.8

The pseudo code of the PSO.

Comparison: Genetic Algorithm, Genetic Programming and Particle Swarm Optimization

The above discussion can be better understood with the summary of the advantages and disadvantages of each algorithm given in Table 14.1 below. The tabulated summary of the EAs and Swarm Intelligence (SI) based algorithms will help in understanding their applicability in specific problems of optimization.

TABLE 14.1

Comparison of GA, GP and PSO

Algorithm	Advantages	Disadvantages
Genetic Algorithm (GA)	• Easy to implement with faster and efficient solutions. • Parallel execution, which addresses the problem of local maxima efficiently. • Requirement for information on derivatives is nil. • Provides better solutions rather than just one single solution. • With the help of size of population, decoding time and number of generations, we can predict solution time. • Complex computational problems can be easily solved with simple operators. • Works well with multi-objective problems, and single as well as discrete functions.	• No standard method to derive fitness function; it totally depends on the user. • Approximation of control parameters such as size of population and crossover rate is difficult. • No single termination criterion is defined. • Scalability issues when the number of variables is high results in larger chromosomes and thus time consumption is also high. • Tire quality of the solution cannot be guaranteed.
Genetic Programming (GP)	• Output is a program which can be expressed as a mathematical expression which makes it easy to understand. • Tree based representation gives it an edge over GA. • There is flexibility'’ of fitness function (designed on the basis of the problem specified). • Efficient results can be derived when the problem space is not clearly understood. • There is no fixed length of solution (depends on hardware limits).	• It has a high computational cost due to the fitness evaluation of each individual after every generation. • It requires a large dataset to derive an optimal solution. • It does not guarantee an exact solution.
Particle Swarm Optimization (PSO)	• Implementation is easy in terms of coding compared to GA and GP. • PSO implementation is easier with the requirement for few parameters for adjustment. • It provides efficient solutions with a shorter calculation time. • It does not work on evolution operators like mutation and crossover.	• It does not have a strong mathematical foundation for analysis. • Tire continuous nature of PSO makes it unsuitable for discrete problems. • Compared with classical approaches, it has slow convergence.

Conclusion

This chapter presents bio inspired algorithms, namely EAs and swarm intelligence based algorithms, as efficient optimization solutions. All EAs, namely GA and GP, share some common features, such as population based algorithms based on best survival criteria; iterative evolution for a best solution; great complexity in fitness function fixation; and natural selection operators—mutation and crossover—with differences in chromosome representation and length. On the other hand, swarm intelligence based algorithms, namely PSO, aim to explore the search space by intimating the optimal particles (swarm). PSO is comparatively easy to implement with fewer parameters and does not involve evolution operators like crossover and mutation. Lastly, the chapter presents a tabulated summary of the bio inspired algorithms with their respective advantages and limitations so that their applicability can be understood.

References

Alba, E. and Tomassini, M., 2002. Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput., 6(5), 443-462.

Coello, С. A. C. and Lamont, G. B., 2004. Applications of Multi-Objective Evolutionary Algorithms (Vol. 1). World Scientific, Singapore.

Dasgupta, D. and Michalewicz, Z. (Eds.), 2013. Evolutionary Algorithms in Engineering Applications. Springer Science & Business Media, Berlin.

Goldberg, D. E. and Holland, J. H., 1988. Genetic algorithms and machine learning, Mach. Learn., 3(2/3), 95-99, https://doi.Org/10.1023/A:1022602019183.

Kachitvichyanukul, V., 2012. Comparison of three evolutionary algorithms: GA, PSO, and DE, Ind. Eng. Manag. Syst., 11(3), 215-223.

Krink, T. and Lovbjerg, M., 2002. Improving particle swarm optimization by hybridization of stochastic search heuristics and self-organized criticality, University of Aarhus, Aarhus.

Lobo, F. J., Lima, С. E, and Michalewicz, Z. (Eds.), 2007. Parameter Setting in Evolutionary Algorithms (Vol. 54). Springer Science & Business Media, Berlin.

Lovbjerg, M.: Improving particle swarm optimization by hybridization of stochastic search heuristics and self-organized criticality. Master's thesis, Department of Computer Science, University of Aarhus (2002)

Macas, M., Lhotska, L. 2008. Social Impact and Optimization. International Journal of Computational Intelligence Research 4(2), 129-136

Nowak, A., Szamrej, J., and Latan, B., 1990. From private attitude to public opinion: A dynamic theory of social impact, Psychol. Rev, 97(3), 362-376.

Pytela, J., 2012. Implementation and Testing of Social Optimization Algorithms, Czech Technical University, Prague.

Ursem, R. K., 2002, September. Diversity-guided evolutionary algorithms. In International Conference on Parallel Problem Solving from Nature (pp. 462-471). Springer, Berlin, Heidelberg.

Wolfgang, J., Peter, N., Robert, E. K., and Frank, D. F., 2009. Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann Publishers/ Dpunkt-Verlag, San Francisco, CA/Heidelberg.

Zhang, Y. and Cheng, H., 2009. Improved genetic programming algorithm applied to symbolic regression and software reliability modeling, Software Eng. Appl. 2(5), 354—360.