Genetic programming

An overview of what genetic algorithm and genetic programming is in Artificial Intelligence.

1. GENETIC PROGRAMMING

2. Genetic Algorithm : A genetic algorithm (or GA ) is a search technique used in computing to find true or approximate solutions to optimization and search problems . The Techniques are inspired by natural evolution such as inheritance, mutation, selection and crossover. Gas are implemented by having arrays of bits or characters to represent the chromosomes.

3. Flowchart :

4. Steps for GAs : Choose initial population. Evaluate the fitness of each individual in the population. Repeat until termination. Select best ranking individuals to reproduce. Breed new generation through crossover and/or mutation and give birth to offspring. Evaluate the individual fitnesses of the offspring. Replace work ranked part of the population with offspring.

5. Genetic Programming : Genetic programming(GPs) is a evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user defined tasks. Is specialization of genetic algorithms where the individuals are the computer programs. GPs automatically solves problems without requiring the user to know or specify the form of structure of the solution.

6. Basic control flow of GPs : Generate population of random program. Run Program and evaluate their quality. Solutions Breed fitter programs.

7. Working of GPs : Uses Darwinian Principle of natural selection (Survival of the fittest). Old Chinese says “Animated gift is one mega World.” Can automatically create in a single run a general solution to a problem in the form of graphical structures.

8. Representation: Expressed as Syntax trees rather than lines of code . Variables and constants are the leaves of the trees, which are called Terminals, while the arithmetic operations are called Functions . The Root node acts as a glue.

9. For example : max( x+x , x+3*y) max + + X X X * Y 3

10. Genetic Operators : The main operators used in genetic programming are: Reproduction Crossover Mutation

11. Reproduction: Reproduction of the two parent chromosomes is done based on their fitness. Probability distribution of fitter one is higher. Thus it ensures that only the fittest of the available solutions mate to form offsprings .

12. Crossover: Simply switching one of it’s nodes with anther node from another individual in the population. Replacing the node means replacing the whole branch. Steps: Choose two strings , Pick point on strings. Swap segments , create two new strings.

13. Gives two new children: 0100010 and 01111111010

14. Mutation: It affects an individual in the population. It can replace whole node in selected individual , or it can replace just the node information. Like for small region of DNA. Example: a model with 6-bit gene coding an integer: 101101 101111 (45) (47)

15. One more example:

16. Steps For GPs : Create an initial population. Execute each program in the population & ascertain its fitness. Select the programs with highest probability of fitness to participate in genetic operations. Create new programs by applying genetic operators which are: 1) Reproduction. 2 ) Crossover . 3) Mutation. After the termination criteria is satisfied the single best program in population produced is the solution.

17. Why Genetic programming : It saves time by freeing the human from having to design complex algorithms. Not only designing the algorithms but creating ones that give optimal solutions.

18. Applications: “Black art problems” such as automated synthesis of analog electrical circuits, controllers, antennas etc. “Programming the unprogrammable ” involves creation of computer programs for unconventional computing devices. Commercially useful new inventions(CUNI) involves the use of genetic programming as automated “invention machine” for creating new inventions.

19. Any Questions ..???