Here is a term paper on ‘Genetic Programming’. Find paragraphs, long and short term papers on ‘Genetic Programming’ especially written for school and college students.
Term Paper # 1. Meaning of Genetic Programming:
One of the central challenges of AI science is to get a computer to do what needs to be done, without telling it how to do it. Genetic programming addresses this challenge by providing a method for automatically creating a working computer program from a high-level problem statement of the problem.
Genetic programming achieves this goal of automatic programming (also sometimes called program synthesis or program induction) by genetically breeding a population of computer programs using the principles of natural selection and biologically inspired operations.
The operations include reproduction, crossover (sexual recombination), mutation, and architecture-altering operation patterned after gene duplication and gene deletion in nature. The genetic algorithm learning methods are based on models of natural adaptation and evolution. These learning systems improve their performance through process which model population genetics and survival of the fittest.
ADVERTISEMENTS:
In the field of genetics, a population is subjected to an environment, which places demands on the members. The members, who adapt well, are selected for mating and reproduction. The offspring of these better performers inherit genetic traits from both their parents. Members of this second generation of offspring, which also adapt well, are then selected for mating and reproduction and the evolutionary cycle continues.
Poor performers die off without leaving the offspring. Good performers produce good offspring and they, in turn, perform well after some number of generations the resultant population will have adapted optimally or at least very well to the environment.
Term Paper # 2. Preparatory Steps Cycle of Genetic Algorithm:
The human user communicates the statement of the problem to the genetic programming system by performing certain well-defined preparatory steps.
The five major preparatory steps for the basic version of genetic programming require the human user to specify:
ADVERTISEMENTS:
1. The set of terminals (for example, the independent variables of the problem, zero-argument functions, and random constants) for each branch of the to-be- evolved program,
2. The set of primitive functions for each branch of the to-be-evolved program (for example, the arithmetic functions of addition, subtraction, multiplication and division as well as a conditional branching operator).
3. The fitness measure (for explicitly or implicitly measuring the fitness of individuals in the population).
4. Certain parameters for controlling the run (for example, population size), and
ADVERTISEMENTS:
5. The termination criterion and method for designating the result of the run (for example, maximum number of generations to be run).
Figure 12.26 shows the five major preparatory steps for the basic version of genetic programming. The preparatory steps (shown at the top of the figure) are the human-supplied input to the genetic programming system. The computer program is the output of the genetic programming system. (Fig. 12.26)
Term Paper # 3. Executional Steps of Genetic Programming:
The executional steps of genetic programming are as follows:
ADVERTISEMENTS:
1. Randomly create an initial population (generation 0) of individual computer programs composed of the available functions and terminals.
2. Iteratively perform the following sub-steps (called a generation) on the population until the termination criterion is satisfied:
(a) Execute each program in the population and ascertain its fitness (explicitly or implicitly) using the problem’s fitness measure.
(b) Select one or two individual program(s) from the population with a probability based on fitness (with reselection allowed) to participate in the genetic operations in (c).
ADVERTISEMENTS:
(c) Create new individual program(s) for the population by applying the following genetic operations with specified probabilities:
(i) Reproduction:
Copy the selected individual program to the new population.
(ii) Crossover:
Create new offspring program(s) for the new population by recombining randomly chosen parts from two selected programs.
(iii) Mutation:
Create one new offspring program for the new population by randomly mutating a randomly chosen part of one selected program.
3. After the termination criterion is satisfied, the single best program in the population produced during the run (the best-so-far individual) is harvested and designated as the result of the run. If the run is successful, the result may be a solution (or approximate solution) to the problem.
Term Paper # 4. Explanation of Genetic Algorithm:
Genetic algorithm system starts with a fixed size population (a set of randomly generated states called individuals) of data structures, which are used to perform some given tasks. After requiring the structures to execute the specified tasks some number of times, the structures are rated on their performance, and a new generation of data structures is then created. Mating the higher performing structures to produce offspring then creates the new generation.
These off-springs and their parents are then retained for the next generation while the poor performing structures are discarded. The process is repeated for a number of generations until the resultant population consists of only the highest performing structures. The basic cycle is illustrated in figure 12.27.
Term Paper # 5. Operators of Genetic Algorithm:
1. Reproduction or Selection:
The reproduction operation copies a single individual, probabilistically selected based on fitness, into the next generation of the population.
2. Crossover (Sexual Recombination Operation):
In the crossover, or sexual recombination operation, two parental programs are probabilistically selected from the population based on fitness. A crossover point is randomly chosen in the second parent. Then the upper halves of the two strings are exchanged to produce new string. Crossover is the predominant operation in genetic programming (and genetic algorithm work and is performed with a high probability (say, 85% to 90%).
3. Mutation Operation:
Mutation is used to ensure that all locations of the rule space are reachable. This ensures that the selection process does not get caught in a local minimum. Since crossover and inversion may not be able to produce some undiscovered structures, so mutation overcomes this by simply selecting a bit position or a point in a tree at random and changing it. This asexual mutation operation is typically performed sparingly (with a low probability of, say 1% during each generation of the run).
To understand Genetic Algorithm we would take example. We can start with a learning decision list-representation for the restaurant waiting problem. The fitness function here is the number of examples which an individual is consistent with.
The representation is little difficult: there are ten attributes in the problem but not all of them are binary. It turns out (analysis not given here) that we need 5 bits to represent each distinct attribute/value pair. We also need one bit for each test to say if the outcome is yes or no. Thus, if we want to represent a k-DL with a length of upto t tests, we need a representation with t (5k + I) bits. A practical example, to explain the procedure of genetic algorithm is the 8-queen problem.
This goal of 8-queens problem is to place eight queens on a chess board such that no queen attacks any other (A queen attacks any piece in the same row, column or diagonal) An 8-queen state must specify the positions of 8-queen, each in a column of 8-square and so requires 8 x (log2 8) = 24 bits.
Alternatively, the state could be represented as 8-digit, each in the range from 1 to 8 (the two encodes behave differently). We keep 8-digit string for our discussion for keeping the treatment simplified. In Fig. 12.29 (a) four 8-digit strings representing 8-queens states are shown and the generation of next generation states are explained in Fig. 12.28 (b)-(e).
In Fig. (b) each state is rated by the evaluation function or fitness function (in GA domain) which measures the fitness of an individual. It is a real number and should return higher values for better states. For the 8-queens problem solution fitness function is 28. For the four states considered here this function has the values 24, 23, 20 and 11 respectively.
There are many variations of genetic algorithm for reproduction and in the one considered here the probability of being chosen for reproducing is directly proportional to the fitness function, the percentages are shown next to the raw scores.
In Fig. 12.28 (c), a random choice of two pairs is selected for reproduction, in accordance with the probabilities in Fig. (b).
Depending upon the method of culling used here, all individuals below a given threshold are discarded. One individual is selected twice and one out of the four is not selected for pairing at all.
For each pair to be mated, a crossover point is randomly chosen from the positions in the string (crossover point is a number in that range N, say 10, meaning that one offspring will get genes 1 through 10, from the first parent and the rest from the second parent. The second offspring will get genes from 1 through 10 from the second parent and the rest from the first). Here, the crossover points are after the third digit in the first pair and after the fifth digit in the second pair.
Fig. (d) shows the off-springs generated from the pair of strings obeying the crossover points enumerated in (c). The 8-queens states involved in this representation step are shown in Fig. 12.29. The queen states correspond to first two parents in Fig. 12.29. (c) and the first offspring in Fig. 12.29 (d).
We may note that the crossover operation may produce an offspring which is far different from the two parents (strings), as is true here. It is often the case that the population is quite wild in the early steps of the search process and the smaller steps taken towards the end make the off-springs converge to near similarity.
In it is shown that each gene can be altered to a different value by random mutation with small independent probability. One digit was muted in the first, third and fourth offspring. In the present problem this corresponds to choosing queen at random and moving it to a random square in its column.
The algorithm given below is based on the steps a – e (Fig; 12.28)
Genetic Algorithm:
Genetic algorithm combines hill claiming with Beam search in which successor states are generated by combining two parent states, rather than by modifying a single state (as in the hill-climbing search). The analogy to natural selection is the same as in the Beam search except that in genetic algorithm we deal with sexual rather than asexual reproduction. Moreover, genetic algorithm uses a random exploration because we are making small genetic changes to the individuals and using the best resulting off-springs.
The searching resources need to be used optimally; time saved can be spent only on the most promising individuals and at the same time saving ‘moves’ from getting stuck on a local maximum (of simulated annealing). However, the exchange of information is in parallel search threads and because of this capability genetic algorithm has the growing potential for solving problems of enormous complexity.
The advantage of genetic algorithm comes primarily from the crossover operation, which should be executed very wisely otherwise it conveys no practical advantage specially when the initial genetic code is permuted randomly. Intuitively, the advantage of genetic algorithm comes from the ability of crossover to combine large blocks of letters which have evolved independently to perform useful functions, thus raising the level of granularity at which the search operates.
For example, it could be that putting the first three queens in positions 2, 4, 6 (where they do not attack each other) constitutes a useful block which can be combined with other blocks to prepare a solution.
The working of genetic algorithm makes use of the idea of schema, which is a substring in which some of the positions can be left unspecified. For example, the schema 246***** describes all 8-queens states in which the first three queens are in position 2, 4, 6 respectively. Strings which match the schema (such as 24613578) are called instances of the schema.
When the average fitness of the instances of a schema is above the mean then the number of the instances of the schema within the population will grow over time. Genetic algorithms work best when schemes correspond to meaningful components of a solution. For example, if the string is a representations of an antenna, there the schemes may represent components of the antenna, such as reflectors and deflectors.
Solutions to certain types of problems in areas of optimisation, product design and the monitoring of industrial systems are especially appropriate for genetic algorithms. Many business problems require optimisation because they deal with issues such as minimisation of costs, maximisation of profits, most efficient scheduling, and use of resources. If these situations are very dynamic and complex, involving hundreds of variables or hundreds of formulas, genetic algorithms are suitable for solving them because they can attack a solution from many directions simultaneously.
Commercial applications of genetic algorithms are emerging. Engineers at General Electric in USA used genetic algorithm to help them design jet turbine aircraft engines, a complex problem involving about 100 variables and 50 constraints equations. The engineers evaluate design changes on a workstation which runs a simulation of the engine in operation.
Because each design change requires a new simulation to test its effectiveness, the designers can spend-weeks on solutions which may or may not be optimal. Using an expert system reduced the time to produce a satisfactory design from several weeks to several days, but the solution could reach upto a point only. Further improvements required simultaneous changes in large numbers of variables.
At that point General Electric introduced a genetic algorithm which took the initial population of designs produced by the expert system and generated a design which contained three times the number of improvements over the best previous version in a period of only two days.
At present, it is not clear whether the appeal of the genetic algorithms arises from their performance or from their aesthetically pleasing origins in the theory of evolution. A lot of research is going on to identify the conditions under genetic algorithms perform well.