17_Genetic Programming

1 . Genetic Algorithm and Genetic Programming 

2 . A large class of stochastic algorithms that simulate nature 1. Have some kind of Various data structures can be used to describe the genotype: mutation, random change 1. Strings of characters. of a part of the 2. Binary vectors description. 3. Arbitrary vectors of numbers. 4. Matrices 2. Have some kind of 5. Trees, crossover, taking partial 6. Directed Acyclic Graphs. 7. Graphs. information from parents. 8. Images. 3. Have some mechanism of selecting parents. 4. Can have some additional mechanisms, deterministic or probabilistic 

3 .Crossovers in Nature • Two parental chromosomes exchange part of their genetic information to create new hybrid combinations (recombinant). • No loss of genes, but an exchange of genes between two previous chromosomes. • No new genes created, created preexisting old ones mixed together. 

4 .What are evolutionary algorithms and Genetic Algorithm (GA)? ROBOTICS Machine learning Genetic Algorithms evolutionary GP Artificial EP GA Intelligence ES Genetic Artificial Evolutionary Evolutionary programming Intelligence Strategies Programming 

5 . Genetic Algorithms 

6 . Genetic Algorithms • 1. Randomly initialize a population of chromosomes. • 2. While the terminating criteria have not been satisfied: – a. Evaluate the fitness of each chromosome: • i. Construct the phenotype (e.g. simulated robot) corresponding to the encoded genotype (chromosome). • ii. Evaluate the phenotype (e.g. measure the simulated robot’s walking abilities), in order to determine its fitness. – b. Remove chromosomes with low fitness. – c. Generate new chromosomes, using certain selection schemes and genetic operators. chromosome Gene or allele Moving Gene to different allele 

7 . Genetic Algorithms 1. Fitness function (quality function) 2. Selection scheme 3. Genetic operators 1. Crossover 2. Mutation 4. Create bitstrings 5. Evaluate bitstrings (genotype) 6. Transform bitstrings to robot behaviors (phenotype) Genetic Programming (GP) use trees instead of strings. 

8 .Crossover and mutation. 

9 . Agenda • What is Genetic Programming? • Background/History. • Why Genetic Programming? • How Genetic Principles are Applied. • Examples of Genetic Programs. • Future of Genetic Programming. 

10 . Genetic • Most widely used Algorithms • Robust • uses 2 separate spaces – search space - coded solution (genotype) – solution space - actual solutions (phenotypes) Genotypes must be mapped to phenotypes before the quality or fitness of each solution can be evaluated 

11 .Evolutionary Strategies 

12 .Evolutionary Strategies (ES) • Like GP nNo distinction between search and solution space • Individuals are represented as real-valued vectors. • Simple ES – one parent and one child – Child solution generated by randomly mutating the problem parameters of the parent. • Susceptible to stagnation at local optima 

13 . Evolutionary Strategies (cont’d) • Slow to converge to optimal solution • More advanced ES – have pools of parents and children • Unlike GA and GP, ES have these properties: – ES Separates parent individuals from child individuals – ES Selects its parent solutions deterministically 

14 .Evolutionary Programming 

15 .Evolutionary Programming • Resembles ES, developed independently • Early versions of EP applied to the evolution of transition table of finite state machines • One population of solutions, reproduction is by mutation only • Like ES operates on the decision variable of the problem directly (ie Genotype = Phenotype) Phenotype • Tournament selection of parents – better fitness more likely a parent – children generated until population doubled in size – everyone evaluated and the half of population with lowest fitness deleted. 

16 . General Architecture of Evolutionary Algorithms 

17 . Genetic Programming 

18 .Genetic Programming Please review about Behavioral systems, Genetic Algorithms and Genetic • John Koza, 1992 Programming from the book. Chapters 20, 21, 22, 23. • Evolve program instead of bitstring • Lisp program structure is best suited – Genetic operators can do simple replacements of sub-trees – All generated programs can be treated as legal (no syntax errors) 

19 . Genetic Programming • Specialized form of GA • Manipulates a very specific type of solution using modified genetic operators • Original application was to design computer programs • Now applied in alternative areas eg. Analog Circuits • Does not make distinction between search and solution space. • Solution represented in very specific hierarchical manner. 

20 .Background/History • By John R. Koza, Stanford University. • 1992, Genetic Programming Treatise - “Genetic Programming. On the Programming of Computers by Means of Natural Selection.” - Origin of GP. • Combining the idea of machine learning and evolved tree structures. 

21 . 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. • Again, Artificial Intelligence. 

22 . What Constitutes a Genetic Program? • Starts with "What needs to be done" • Agent figures out "How to do it" • Produces a computer program - “Breeding Programs” • Fitness Test • Code reuse • Architecture Design - Hierarchies • Produce results that are competitive with human produced results 

23 .How are Genetic Principles Applied? • “Breeding” computer programs. • Crossovers. • Mutations. • Fitness testing. 

24 . Computer Programs as Trees • Infix/Postfix • (2 + a)*(4 - num) * + - 2 a 4 num 

25 . “Breeding” Computer Programs • Start off with a large “pool” of random computer programs. • Need a way of coming up with the best solution to the problem using the programs in the “pool” • Based on the definition of the problem and criteria specified in the fitness test, mutations and crossovers are used to come up with new programs which will solve the problem. 

26 . The Fitness Test 

27 .The Fitness Test • Identifying the way of evaluating how good a given computer program is at solving the problem at hand. • How good can a program cope with its environment. • Can be measured in many ways, i.e. error, distance, time, etc… 

28 .Fitness Test Criteria • Time complexity a good criteria. – i.e. n2 vs. n logn. – “How long to find the solution?” • Accuracy - Values of variables. – “How good is the solution?” • Combinations of criteria may also be tested. 

29 .Mutations