ST Prog Analy &Mechanization
ST Prog Analy &Mechanization CS 591
Popular in Course
Popular in ComputerScienence
This 65 page Class Notes was uploaded by Trent Dare on Wednesday September 23, 2015. The Class Notes belongs to CS 591 at University of New Mexico taught by Stephanie Forrest in Fall. Since its upload, it has received 8 views. For similar materials see /class/212189/cs-591-university-of-new-mexico in ComputerScienence at University of New Mexico.
Reviews for ST Prog Analy &Mechanization
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/23/15
CS 591 Topics in Complex Adaptive Systems Spring Semester 2006 Genetic Algorithms Stephanie Forrest FEC 355E httpcsunmed uforrestcascass06html forrestcsunmedu 5052777104 H I l T lbu L IdhL39I mj39U If i13914 Maxim Genetic Algorithms Principles of natural selection applied to computation Variation Selection Inheritance Evolution in a computer Individuals genotypes stored in computer s memory Evaluation of individuals artificial selection Differential reproduction through copying and deletion Variation introduced by analogy with mutation and crossover Simple algorithm captures much of the richness seen in naturally evolving populations The University of New Mexico A Simple Genetic Algorithm Population at Tn Population at T M Mutation I 00111 11100 01100 11100 11100 11010 01010 Selection 01010 X Crossover 01 100 F00111 01 F11100 09 F01010 05 I quotI lt The University of New Mexico Example Performance Curve mean fitness max fitness 100 Q Q Q Q QQ Q Q Q Q Q D 0xb x q9q339wb w q quot 39quotab b999gtb b 939 Generation m In The University of New Mexico Multiparameter Function Optimization FX y yX2 X4 Decimal Binary Gray code o 000 000 O O 1 1 1 1 Bit string Gray coded 1 001 00quot Degrayl 2 010 011 001 101 BaseZ 3 011 m 1 1 4 1 5 Base 10 5 101 m 6 110 101 7 111 100 FOOO1111 F15 5 01214 4 The University of New Mexico Example Applications of Genetic Algorithms Engineering applications Multiparameter function optimization eg spectroscopic applications turbine engine design Sequencing problems eg circuit design factory scheduling TSP Machine and robot learning Complex data analysis Automatic programming eg genetic programming Modeling Rule discovery in cognitive systems Learning strategies for games Affinity maturation in immune systems Ecosystem modeling The University of New Mexico Genetic Programming Evolve populations of computer programs Typically use the language Lisp Select a set of primitive functions for each problem Represent program as a syntax tree Function approximation vs function optimization Crossover operator Exchange subtrees between individual program trees Schema Theorem Many applications Optimal control eg the pole balancing problem Circuit design Symbolic regression data fitting The University of New Mexico Genetic Programming Expression X2 3xy y2 U LISP XX 3XY yy I quotI lt The University of New Mexico Genetic Programming cont Consider evolving a program to compute cos 2x A humandesigned program 1 2sin2x In Lisp 1 2 sin sin x A genetic programming solution sin2x2 sin sin sin sin sin sin sin sin 1 Sin Sin 1 Junk DNA The University of New Mexico Where did these ideas originate Genetic algorithms Holland 1962 Original idea was to create an algorithm that captured the richness of natural adaptive systems Emphasized the adaptive properties of entire populations and the importance of recombination mechanisms such as crossover Application to function optimization introduced by DeJong 1975 Evolutionstrategie Rechenberg 1965 Emphasized the importance of selection and mutation as Mechanisms for solving difficult realvalued optimization problems Evolutionary programming Fogel et al 1966 Emphasis on evolving finite state machines Genetic programming Koza 1992 Evolutionary Computation I III lt The University of New Mexico References J H Holland Adaptation in Natural and Artificial Systems Univ of Michigan Press 1975 Second Edition published by MIT Press 1992 D E Goldberg Genetic Algorithms in Search Optimization and Machine Learning AddisonWesley 1989 M Mitchell An Introduction to Genetic Algorithms MIT Press 1996 S Forrest Genetic Algorithms Principles of natural selection applied to computation Science 261 872878 1993 J Koza Genetic Programming MIT Press 1992 The University of New Mexico How do Genetic Algorithms Work The Central Dogma of Genetic Algorithms Holland 1975 Schema processing Schema Theorem Implicit parallelism Building block hypothesis Karmed bandit analogy The University of New Mexico Genetic Algorithms and Search Highdimensional search spaces All binary strings of length All possible strategies for playing the game of chess All possible tours in the Travelling Salesman Problem Genetic algorithms use biased sampling to search highdimensional spaces Independent sampling Selection biases search towards highfitness regions Crossover combines partial solutions from different strings Partial solution formalized as schema I quotI lt The University of New Mexico Schemas Schemas capture important regularities in the search space 1 0 0 1 1 1 011 11 gtlltgtllt0gtlltgtlltgtllt 0 1 Implicit Parallelism 1 individual samples many schemas simultaneously Schema Theorem Reproduction and crossover guarantee exponentially increasing samples of the observed best schemas Order of a schema Os number of defined bits Defining length of a schema DS distance between outermosh I III lt The University of New Mexico Schema Theorem Holland 1975 Let s be a schema in population at time t Nst be the number of instances of s at time 1 Question What is the expected Nst 1 Assume Fitnessproportionate selection Expected number of offspringx Em 17t Ignoring crossover and mutation N SJ 1 x N S t Note If Mc then Nstc NsO 171 Crossover and mutation handled as loss terms NS9t 1 X NS9t1 90 pm OS m In The University of New Mexico Fitness Royal Road Schemas schema 1 schema 2 schema 3 100 120 140 16Q 180 200 220 240 260 280 300 0 20 40 60 80 Generatlon F quotI lt The University of New Mexico Study Question Given a population consisting of N individuals Each individual is L bits long How many sohemas are sampled by the population in one generation Hint Minimum value is 2L Maximum value is Nx2L The University of New Mexico Building Blocks Example Fitness I 391 L I I I I Genome 00 10 Interpret bit string as a binary decimal 1000 05 01000 025 l 2 05 l even intervals O S 05 0 odd intervals The University of New Mexico Questions When will genetic algorithms work well and when they will not Not appropriate for problems where it is important to find the exact global optimum GA domains are typically those about which we have little analytical knowledge complex noisy dynamic poorly specified etc Would like a mathematical characterization that is predictive What makes a problem hard for genetic algorithms Deception multimodality conflicting schema information noise What makes a problem easy for genetic algorithms What distinguishes genetic algorithms from other optimization methods such as hill climbing What does it mean for a genetic algorithm to perform well The University of New Mexico Building Blocks Hypothesis Holland 1975 1 GA initially detects biases in loworder schemas GA obtains good estimates of schema average fitness by sampling strings 2 Over time information from loworder schemas is combined through crossover and 3 GA detects biases in highorder schemas 4 Eventually converging on the most fit region of the space implies that crossover ls cehtral to the success of the GA Claim GA allocates samples to schemas in a near optimal way Karmed bandit argument The University of New Mexico The Twoarmed Bandit Originated in statistical decision theory and adaptive control Suppose a gambler is given Ncoins with which to play a slot machine with two arms A1 and A2 The arms have Mean payoff per trial rates m1 and m2 Variances s12 and s22 The payoff processes from the two arms are each stationary and independent of one another The gambler does not know these payoffs and can estimate them only by playing coins on the different arms The University of New Mexico Twoarmed Bandit cont Given that the player wants to maximize total payoff what strategy is best Online payoff maximize payoff during N trials vs Offline payoff determining which arm has the higher payoff rate Claim Optimal strategy is to exponentially increase the sampling rate of the observed best arm as more samples are collected Apply to schema sampling in GA 3L schemas in an Lbit search space can be viewed as 3L arms of a multi armed slot machine Observed payoff of a schema H is simply its observed fitness Claim The GA is a near optimal strategy for sampling schemas Maximizes online performance Fl Ill lt The University of New Mexico Most GA theory is not practical or predictive except in a general way Analysis methods Walsh polynomials and schema analysis Population genetics models Markov chains Signaltonoise analysis Statistical structure of fitness landscapes Statistical mechanics models PAC learning Common traps Infinite populations Analysis intractable except for short strings 16 or less Enumerate all possible populations Convergence proofs based on idea that any string can mutate into any other string Weak b0 u n ds The University of New Mexico Implementation Issues Implementation issues Permutation problems and special operators Example TSP Genetic programming Example Trigonometric functions Modeling applications Example Prisoner s Dilemma Example Classifier Systems Example Echo The University of New Mexico Implementation Issues Data structures Packed arrays of bits Byte arrays Vectors of real numbers Lists and trees Representation Feature lists Binary encodings gray codes Real numbers Permutations Trees Selection On next slide Scaling On next slide Crossover 1point 2point npoint Uniform Special operators Mutation Bit flips Creep Gaussian noise Elitism Parameters rough guidelines Bitstring length 32 10000 Population size 100 1000 Length of run 50 10000 Crossover rate 06 per pair Mutation rate 0005 n F quotI The University of New Mexico Selection Methods Fitnessproportionate used in theoretical studies Expected value of individual fexpg Rankbased f 6XpiMinMaxMin g f Implement as roulette wheel SKIP Intended to prevent premature convergence slow down evolution Each individual ranked according to fitness Expected value depends on rank Min Max are constants The University of New Mexico Selection Methods cont Tournament Computationally efficient Choose T 2 size of tournament 2 is a common value Pick subsets of size T from the population randomly with replacement Compare fitnesses within the subset and choose the winner either deterministically or stochastically Iterate Steady state Implicit eg Echo immune models etc Reproduction rate proportional to resources obtained The University of New Mexico Scaling Methods How to maintain a steady rate of evolution SKIP Linear Based on max min39 mean f39 afb such that favg favg Described in Goldberg 1989 Sigma Based on mean and standard deviation f 39 f f 60 with cutoffs for extreme values c is typically 15 or 20 Exponen ak f H Normalizes difference between 10 and 15 and 10000 and 10005 The University of New Mexico Permutation Problems and Special Operators Problem Find an optimal ordering for a sequence of N items Examples Traveling Salesman Problem TSP Bin packing problems Scheduling DNA fragment assembly Traveling Salesman Problem 1 3 4 2 6 5 2 2 3 The University of New Mexico Using Genetic Algorithms to Find Good Tours for TSP Natural representation Permutations in which each city is labeled by a unique integer bitstring 3 2 1 4 4 1 2 3 Problem Mutation and crossover do not produce legal tours 3 2 2 3 Solutions Other representations Other operators Penalize illegal solutions through fitness function F Ill lt The University of New Mexico Specialized Operators What information schemas should be preserved Absolute position in the sequence Relative ordering in the sequence precedence Adjacency relations How much randomness is introduced Order crossover Davis 1985 Partiallymapped crossover PMX Goldberg et al 1985 Cycle crossover Oliver et al 1987 Edgerecombination Try to preserve adjacencies in parents Favor adjacencies common to both parents When 12 fail make a random selection I quotI lt The University of New Mexico Edge Recombination Operator Algorithm 1 Select one parent at random and assign the first element in its permutation to be the first one in the child 2 Select the second element for the child as follows If there is an adjacency common to both parents then choose that If there is an unused adjacency available from one parent choose it If 1 and 2 fail then pick an adjacency randomly 3 Select the remaining elements in order by repeating step 2 The University of New Mexico Edge Recombination Example 362145 521364 Original Individuals Key CDO ILOON t V 364125 New Individual Adjacent Keys 2234 11 36 166 156 24 2334 The University of New Mexico Evolution of Cooperation Axelrod 1984 What is the Prisoner s Dilemma PlayerB Cooperate Defect Cooperate 33 05 PayerA Defect 50 11 Nonzero sum game Total number of points is not constant for each configuration What is the best move for Player 1 Player 2 F quotI lt The University of New Mexico Prisoner s Dilemma cont Iterated Prisoner s Dilemma Play game for an indeterminate number of steps Raises possibility of strategies based on the behavior of the other player What are the possible strategies RANDOM Always cooperate always defect TitForTat Model other player and try to maximize against that model etc The University of New Mexico Evolution of Cooperation 1980 Two tournaments Each strategy entry encoded as a computer program Round robin everyone plays everyone TitForTat TFT won both times 198285 Learning algorithms Can TFT evolve in a competitive environment How could a TFT strategy evolve in nature Is there a better strategy How do strategies develop Use genetic algorithm to study these questions In environment of tournament In a changing environment coevolution In a 3person game In an nperson game na Norms game Fl Ill lt The University of New Mexico Prisoner s Dilemma Using Genetic Algorithm Population consists of individual strategies 1 strategy per chromosome Each chromosome is a 64 70 bit string Each bit specifies the strategy s next move cooperate or defect for one particular history of 3 moves Encoding Need to remember each player s move for 3 time steps gt 6 pieces of information At each point either player could cooperate or defect binary decision 226 64 possible histories Value of bit at a given position tells strategy what to do 0 coop 1 defect in the context of that history Additional 6 bits encodes assumption about previous interactions before the start of the game The University of New Mexico Prisoner s Dilemma Encoding cont Let A be the sum formed by Counting the other s defection as 2 Counting my own detection as 1 And giving weights of 16 to the most recent moves 4 to the move two time steps in the past and 1 to the move three time steps in the past Eg History of mutual cooperation for 3 time steps gt O History of mutual defection for 3 times steps gt 63 What history should we assume for first 3 moves Mutual cooperation Genetically determined need 6 more bits The University of New Mexico Prisoner s Dilemma Using GA Fitness Function Environment of tournament Select 8 strategies from 16O tournament entries that predict performance and play each candidate strategy against those 8 representatives Coevolutionary environment Strategies play against other strategies in the population The University of New Mexico Results for Fixed Env From a random start the GA evolved populations whose median member was just as successful as TFT Most of the evolved strategies resemble TFT In some rules strategies were discovered that did significantly better than TFT in tournament env Discriminates between different opponents based only on its behavior Adjusts its own behavior to exploit an exploitable opponent Does this without getting into too much trouble with other opponents Achieved this by defecting on first move and then apologizing when necessary The University of New Mexico Mean Score Figure 11 Prisoner s Dilemma in an Evolving Environment 400 350 W 300 250 n 200 Results in Evolving Environment From Axelrod 1997 O 5 10 15 20 5 30 35 4o 45 50 i Generations I quotI lt 6 University of New Mexico Sorted Order Representation 010111001101011010 BitString l l l l l 2 7 1 5 3 2 KeyValues Rotated Layout 1 5 4 2 3 Start at position 2 The UnlverSIty of New Mexico Sorted Order Representation 010111001101011010 BitString l l l 2 7 1 5 3 2 Key Values 1 2 3 4 5 Position y 3 1 5 4 2 Rotated Layout 1 5 4 2 3 Start at position 2 The UnlverSIty of New Mexico CS 591 Topics in Complex Adaptive Systems Spring Semester 2006 Measures of Complexity Stephanie Forrest FEC 355E httpcsunmed uforrestcascass06html forrestcsunmedu 5052777104 H I l T lbu L IdhL39I mj39U If i13914 Maxim What are Complex Adaptive Systems Collections of agents Molecules cells animals planets stars economic agents Agents interact locally with one another and with their environment No central controller Interactions are nontrivial Ie nonlinear Chemical reactions cellular interactions mating buysell decisions Unanticipated properties often result from the interactions Immune system responses flocks of animals settlement patterns earthquakes speculative bubbles and crashes Agents adapt their behavior to other agents and environmental constraints Imitation adaptation learning System behavior evolves over time Rules change unfolding of complex behavior The University of New Mexico Example Complex Adaptive Systems Natural ecosystems Economies Social systems Immune systems The Internet and other computer systems The University of New Mexico Caveat Some people believe that there is no general science of complex systems It s becoming apparent that a theory of complexity in some sense of a great and transforming body of knowledge that applies to a whole range of cases may be untenable Sir Robert May 2001 I III lt The University of New Mexico Understanding Nature and Society Through Computation Using information processing methods to learn more about natural systems Cognitive science Biological models eg vaccine design ecological models Lattice gas models in physics Prisoner s dilemma in social systems Contrast with computational science Modeling nature as a mechanical device vs modeling nature as an information system Eg computational biologygenomics and protein folding The University of New Mexico Computers are complex systems Even though we build them we don t necessarily understand how they work Complexity is overwhelming design strategies based on functional decomposition reductionism Contextfree languages Objectoriented programming Conventional parallel and concurrent programming models Need new methods for engineering nonlinear computations Neural networks Genetic algorithms Simulated annealing Emergent computation The University of New Mexico Characteristics of Complex Systems What makes a system complex Nonlinear interactions among components Multiscale phenomena Evolution of underlying components and environments How to measure a system s complexity ls complexity inherent in the system or in our understandin of it By its unpredictability By how difficult it is to describe Length of most concise description No single model adequate to describe systemthe more models that are required the more complex the system Lee Segel By measuring how long before it halts if ever By how long until it repeats itself Entropy Multiple levels of organization Number of interdependencies I quotI lt The University of New Mexico Representative Measures of Complexity Computational complexity Cook How long a program runs or how much memory it uses Asymptotic Language complexity Classes of languages that can be computed recognized by different kinds of abstract machines Decidability computability Logical depth Bennett Informationtheoretic approaches Algorithmic Complexity Solomonoff Komogorov and Chaitin Length of the shortest program that can produce the phenomenon Kolmogorov complexity Mutual information many authors Thermodynamic depth Lloyd and Pagels Effective complexity GellMann and Lloyd n F II The University of New Mexico Computational Complexity Introduced by Steve Cook 1970 Asymptotic running time andor memory consumption of an algorithm Worstcase versus averagecase Important computational complexity classes NP Can be verified in polynomial time Opn on a nondeterministic Turing Machine NC polylogarithmic timeOlogk n using polynomial number of processors P polynomial time using a single processor f n is Ogn iff E1ltC 739ngtkfnS c39gn Ck are constant and n is the size length of the input Polynomial time algorithms P are Opn for some polynomial function p Drawbacks Says nothing about transient behaviors Many interesting systems never reach asymptopia The categorization is very coarsein the real word constants w r The University of New Mexico Computational Complexity Classes from Papadimitriou 1994 i 39 l1quotiquot 1quot quotr 39 39 7 EH 1le I39I quot39 1 x a i a I 39 quot39 x H39 a a J 5 I 7539 Iquot 5 quot 39 5 llquot FIT5quot h 1 3 1 quot I quot3 I 39 r I F l l I ii i If i i J ll i 39II II 7392 39 I II 1 If I E I II quot1quot 39 1 I a Er I Ii lji39 39 i I II p A F I a 39 39 39 I F 39 F I i I E39I I quotI I LII I I I 39 IL I a I i 39 I 39 39r i I I 139 quotH5 939 l 2 gt 39 1 39 5 39l I I I r i I I 7 l I I i I bl 39I I I i I 39 I r I I 39 I i l i Irl II I III Eli I II I V I I II I II Ii li Ih i i if 7 71 E I la a 3939 39 F quotI lt The University of New Mexico Algorithmic Complexity AC also known as KolmogorovChaitin complexity The KolomogorovChaifin complexity KX is the length in bits of the smallest program that when run on a Universal Turing Machine outputs prints xand then halts Example What is KX where Xis the first 10 even natural numbers Where Xis the first 5 million even natural numbers Possible representations 02 4 6 8 10 12 14 16 18 2n 2 for j 0 j lt n j printf odn j 2 How many bits Alternative 1 On log n Alternative 2 KX Olog n Two problems Calculation of KX depends on the machine we have available eg what if we have a machine with an instruction print the first 10 even natural nu rs In general it is an uncomputable problem to determine KX for ar quotI The University of New Mexico Algorithmic Complexity cont AC formalizes what it means for a set of numbers to be compressible and incompressible Data that are redundant can be more easily described and have lower AC Data that have no clear pattern and no easy algorithmic description have high AC What about random numbers If a string is random then it possesses no regularities KX Printx The shortest program to produce Xis to input to the computer a copy of X and say print this Implication The more random a system the greater its AC AC is related to entropy The entropy rate 11 of a symbolic sequence measures the unpredictability in bits per symbol of the sequence The entropy rate is also known as the entropy density or the metric density The average growth rate of KX is equal to the entropy rate h For a sequence of n random variables how does the entropy om sequence grow with n lt The University of New Mexico Measures of Complexity that Capture Properties Distinct from Randomness Algorithmic Structural Complexity Complexity Randomness hp Randomness hit Measures of randomness do not capture pattern structure correlation or organization Mutual information Wolfram s CA classification The edge of chaos n W Ill The University of New Mexico Logical Depth Bennett 19861990 The Logical depth of X is the run time of the shortest program that will cause a UTM to produce xand then halt Logical depth is not a measure of randomness it is small both for trivially ordered and random strings Drawbacks Uncomputable Loses the ability to distinguish between systems that can be described by computational models less powerful than Turing Machines eg finitestate machines The University of New Mexico Turing Machines Cnntml Unit lFll Nll39ITE E HTR L STATES 5mm Ii 5mm 1 Imam Sitlam 4 Sitmite 5 Tape lilnlAlT a ll Jlulllullll Eeri39EQH nsd F quotI lt The University of New Mexico Detour into Information Theory Shannon Entropy H to measure basic information capacity For a random variable X with a probability mass function px the entropy of X is defined as 1M f pltxgtlog2pltxgt Entropy is measured in bits H measures the average uncertainty in the random variable Example 1 Consider a random variable with uniform distribution over 32 outcomes To identify an outcome we need a label that takes on 32 different values eg 5bit strings 32 32 HX 2 pilogpi ilog3i2 log32 5 bits i 32 The University of New Mexico What is a Random Variable A function defined on a sample space Should be called random function Independent variable is a point in a sample space eg the outcome of an experiment A function of outcomes rather than a single given outcome Probability distribution of the random variable X PX x1 fxj j 12 Example Toss 3 fair coins Let X denote the number of heads appearing X is a random variable taking on one of the values 01 23 PXO 18 PX1 38 PX2 38 PX3 18 The University of New Mexico Detour into Information Theory cont Example 2 A horse race with 8 horses competing The probabilities of 8 horses are 1 1 1 1 1 1 1 1 E Z E E a a a a Calculate the entropy H of the horse race 1 1 1 1 1 1 1 1 1 1 HX 2log2 4log4 8log8 16log16 46410g64 2b1ts Suppose that we wish to send a short message to another person indicating which horse won the race Could send the index of the winning horse 3 bits Alternatively could use the following set of labels O10110111011110011110111111011111 Average description length is 2 bits instead of 3 The University of New Mexico Detour into Information Theory cont More generally the entropy of a random variable is a lower bound on the average number of bits required to represent the random variable The uncertainty complexity of a random variable can be extended to define the descriptive complexity of a single string Eg Kolmogorov or algorithmic complexity is the length of the shortest computer program that prints out the string Entropy is the uncertainty of a single random variable Conditional entropy is the entropy of a random variable given another random variable The University of New Mexico Mutual Information Measures the amount of information that one random variable contains about another random variable Mutual information is a measure of reduction of uncertainty due to another random variable That is mutual information measures the dependence between two random variables It is symmetric in X and Y and is always nonnegative Recall Entropy of a random variable X is HX Conditional entropy of a random variable X given another random variable Y HX Y The mutual information of two random variables X and Yis 1936 y pxpy The University of New Mexico 1X Y we HX I Y 2 pxylog Summary of Complexity Measures Computational complexity How many resources does it take to compute a function The languagemachine hierarchy How complex a machine is needed to compute a function Informationtheoretic methods Entropy Algorithmic complexity Mutual information Logical depth Runtime of the shortest program that generates the phenomena and halts Asymptotic behavior of dynamical systems Fixed points limit cycles chaos Wolfram s CA classification Langton s lambda parameter n W Ill The University of New Mexico Suggested References Computational Complexity by Papadimitriou AddisonWesley 1994 Elements of Information Theory by Cover and Thomas Wiley 1991 I quotI lt The University of New Mexico
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'