Create Presentation
Download Presentation

Download Presentation
## CSCE833 Machine Learning

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**CSCE833 Machine Learning**Lecture 11 Evolutionary Algorithms Dr. Jianjun Humleg.cse.sc.edu/edu/csce833 University of South Carolina Department of Computer Science and Engineering**Objectives**• Understand ideas and components of Genetic Algorithms (GA) • Able to formulate and solve problems using GA (global optimization problem) • Understand basic ideas of Genetic Programming • Able to do symbolic regression using GP using GP software package**Easy-to-use GA/GP packages**• Matlab GA package • Open Beagle (C++): GA, GP, ES • http://gaul.sourceforge.net/ • ECJ: Java EA package: GA, GP, ES, etc • Python, Perl, etc**Genetic Algorithms:A Tutorial**“Genetic Algorithms are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might not otherwise find in a lifetime.” - Salvatore Mangano Computer Design, May 1995**The Genetic Algorithm**• Directed search algorithms based on the mechanics of biological evolution • Developed by John Holland, University of Michigan (1970’s) • To understand the adaptive processes of natural systems • To design artificial systems software that retains the robustness of natural systems**The Genetic Algorithm (cont.)**• Provide efficient, effective techniques for optimization and machine learning applications • Widely-used today in business, scientific and engineering circles**Components of a GA**A problem to solve, and ... • Encoding technique (gene, chromosome) • Initialization procedure (creation) • Evaluation function (environment) • Selection of parents (reproduction) • Genetic operators (mutation, recombination) • Parameter settings (practice and art) x=(0.1,0.21, 0.32)**Simple Genetic Algorithm**{ initialize population; evaluate population; while TerminationCriteriaNotSatisfied { select parents for reproduction; perform recombination and mutation; evaluate population; } }**Population**population Chromosomes could be: • Bit strings (0101 ... 1100) • Real numbers (43.2 -33.1 ... 0.0 89.2) • Permutations of element (E11 E3 E7 ... E1 E15) • Lists of rules (R1 R2 R3 ... R22 R23) • Program elements (genetic programming) • ... any data structure ...**Reproduction**children reproduction parents Tournament Selection population Parents are selected at random with selection chances biased in relation to chromosome evaluations.**PROBABILISTIC SELECTION BASED ON FITNESS**• Better individuals are preferred • Best is not always picked • Worst is not necessarily excluded • Nothing is guaranteed • Mixture of greedy exploitation and adventurous exploration • Similarities to simulated annealing (SA)**Chromosome Modification**• Modifications are stochastically triggered • Operator types are: • Mutation • Crossover (recombination) children modification modified children**Mutation: Local Modification**Before: (1 0 1 1 0 1 1 0) After: (0 1 1 0 0 1 1 0) Before: (1.38 -69.4 326.44 0.1) After: (1.38 -67.5 326.44 0.1) • Causes movement in the search space(local or global) • Restores lost information to the population**Crossover: Recombination*** P1 (0 1 1 0 1 0 0 0) (0 1 0 0 1 0 0 0) C1 P2 (1 1 0 1 1 0 1 0) (1 1 1 1 1 0 1 0) C2 Crossover is a critical feature of genetic algorithms: • It greatly accelerates search early in evolution of a population • It leads to effective combination of schemata (subsolutions on different chromosomes)**Evaluation**• The evaluator decodes a chromosome and assigns it a fitness measure • The evaluator is the only link between a classical GA and the problem it is solving modified children evaluated children evaluation**Deletion**population • Generational GA:entire populations replaced with each iteration • Steady-state GA:a few members replaced each generation discarded members discard**An Abstract Example**Distribution of Individuals in Generation 0 Distribution of Individuals in Generation N**A Simple Example**The Traveling Salesman Problem: Find a tour of a given set of cities so that • each city is visited only once • the total distance traveled is minimized**Representation**Representation is an ordered list of city numbers known as an order-based GA. 1) London 3) Dunedin 5) Beijing 7) Tokyo 2) Venice 4) Singapore 6) Phoenix 8) Victoria CityList1(3 5 7 2 1 6 4 8) CityList2(2 5 7 6 8 1 3 4)**Crossover**Crossover combines inversion and recombination: * * Parent1 (3 5 7 2 1 6 4 8) Parent2 (2 5 7 6 8 1 3 4) Child (5 8 7 2 1 6 3 4) This operator is called the Order1 crossover.**Mutation**Mutation involves reordering of the list: ** Before: (5 8 7 2 1 6 3 4) After: (5 8 6 2 1 7 3 4)**Issues for GA Practitioners**• Choosing basic implementation issues: • representation • population size, mutation rate, ... • selection, deletion policies • crossover, mutation operators • Termination Criteria • Performance, scalability • Solution is only as good as the evaluation function (often hardest part)**Benefits of Genetic Algorithms**• Concept is easy to understand • Modular, separate from application • Supports multi-objective optimization • Good for “noisy” environments • Always an answer; answer gets better with time • Inherently parallel; easily distributed**Benefits of Genetic Algorithms (cont.)**• Many ways to speed up and improve a GA-based application as knowledge about problem domain is gained • Easy to exploit previous or alternate solutions • Flexible building blocks for hybrid applications • Substantial history and range of use**When to Use a GA**• Alternate solutions are too slow or overly complicated • Need an exploratory tool to examine new approaches • Problem is similar to one that has already been successfully solved by using a GA • Want to hybridize with an existing solution • Benefits of the GA technology meet key problem requirements**THE CHALLENGE**"How can computers learn to solve problems without being explicitly programmed? In other words, how can computers be made to do what is needed to be done, without being told exactly how to do it?" Attributed to Arthur Samuel (1959)**CRITERION FOR SUCCESS**"The aim [is] ... to get machines to exhibit behavior, which if done by humans, would be assumed to involve the use of intelligence.“ Arthur Samuel (1983)**Decision trees**If-then production rules Horn clauses Neural nets Bayesian networks Frames Propositional logic Binary decision diagrams Formal grammars Coefficients for polynomials Reinforcement learning tables Conceptual clusters Classifier systems REPRESENTATIONS**GENETIC PROGRAMMING (GP)**• GP applies the approach of the genetic algorithm to the space of possible computer programs • Computer programs are the lingua franca for expressing the solutions to a wide variety of problems • A wide variety of seemingly different problems from many different fields can be reformulated as a search for a computer program to solve the problem.**GP MAIN POINTS**• Genetic programming now routinely delivers high-return human-competitive machine intelligence. • Genetic programming is an automated invention machine. • Genetic programming has delivered a progression of qualitatively more substantial results in synchrony with five approximately order-of-magnitude increases in the expenditure of computer time.**PROGRESSION OF QUALITATIVELY MORE SUBSTANTIAL RESULTS**PRODUCED BY GP • Toy problems • Human-competitive non-patent results • 20th-century patented inventions • 21st-century patented inventions • Patentable new inventions**A COMPUTER PROGRAM IN C**int foo (int time) { int temp1, temp2; if (time > 10) temp1 = 3; else temp1 = 4; temp2 = temp1 + 1 + 2; return (temp2); }**PROGRAM TREE**(+ 1 2 (IF (> TIME 10) 3 4))**CREATING RANDOM PROGRAMS**• Available functions F = {+, -, *, %, IFLTE} • Available terminals T = {X, Y, Random-Constants} • The random programs are: • Of different sizes and shapes • Syntactically valid • Executable**GP GENETIC OPERATIONS**• Reproduction • Mutation • Crossover (sexual recombination) • Architecture-altering operations