New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Introduction to Scientific Modeling

by: Trent Dare

Introduction to Scientific Modeling CS 365

Marketplace > University of New Mexico > ComputerScienence > CS 365 > Introduction to Scientific Modeling
Trent Dare
GPA 3.76

Stephanie Forrest

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Stephanie Forrest
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 57 page Class Notes was uploaded by Trent Dare on Wednesday September 23, 2015. The Class Notes belongs to CS 365 at University of New Mexico taught by Stephanie Forrest in Fall. Since its upload, it has received 9 views. For similar materials see /class/212188/cs-365-university-of-new-mexico in ComputerScienence at University of New Mexico.


Reviews for Introduction to Scientific Modeling


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
Introduction to Scientific Modeling CS 365 Fall Semester 2007 Genetic Algorithms Stephanie Forrest FEC 355E httpcsunmed uforrestcasclass06html forrestcsunmedu 5052777104 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 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 III 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 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 872 878 1993 J Koza Genetic Programming MIT Press 1992 The University of New Mexico Multiparameter Function Optimization FX y yX2 X4 Decimal Binary 0 000 001 010 011 100 101 110 111 The University of New Mexico l001 101BaseZ i 15 FOO1101 F15 5 1214 4 Base 10 NGChthA Multiparameter Function Optimization FX y yX2 X4 Decimal Binary Gray code o 000 000 39 39 1 001 001 Degrayl j 1 i 1 Eli str12ng Gray coded 2 010 W ase 3 011 010 1 1 4 1 5 Base 10 5 101 m 6 110 101 7 111 100 FOO1111 F15 5 1214 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 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 per bit The University of New Mexico Selection Methods Fitnessproportionate used in theoretical studies Expected value of individual feXpU Implement as roulette wheel f ED l CED D313 Rankbased SKIP Intended to prevent premature convergence slow down evolution Each individual ranked according to fitness Expected value depends on rank Min Max are constants f exp i Min Max Mm I Hi lt 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 lterate 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 min mean Require f afb favg favg Described in Goldberg 1989 Sigma Based on mean and standard deviation f 39 f f CO with cutoffs for extreme values 0 is typically 15 or 20 Exponen ak f kf Normalizes difference between 10 and 15 and 10000 and 10005 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 quot39 XX 3XY yy 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 xsin 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 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 xf 39 Dquot O 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 F Ill lt The University of New Mexico Schema Theorem Holland 1975 Let s be a schema in population at time 1 Nsz be the number of instances of s at time 1 Question What is the expected Nsz 1 Assume Fitnessproportionate selection Expected number of offspringx Em 17t Ignoring crossover and mutation A t Nst1 uS xNst F 0 Note If c then Nst c NsO 171 Crossover and mutation handled as loss terms NSt 1 2 x NSt1 pc DS1 Pm0s m 1 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 I III 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 1 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 tmpiies that crossover ts centrat 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 Permutation Problems and Special Operators Problem Find an optimal ordering for a sequence of Nitems 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 3223 Solutions Other representations Other operators Penalize illegal solutions through fitness function 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 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 364125 V New Individual Adjacent Keys 2234 11 36 156 156 24 2334 The University of New Mexico Using Genetic Algorithms to Model Natural and Artificial Systems Modeling social systems Evolution as a model of imitation Prisoner s Dilemma Economies stock market Cognitive systems Induction and learning Classifier Systems Genetic evolution Natural ecological systems Echo Immune systems Somatic evolution in CancerSim Ecosystem modeling Artificial life models In each of these systems adaptation is central What can we learn from modeling with genetic algorithms n m m The University of New Mexico Using Complex Systems Approaches to Social Modeling Societies and political systems Sugarscape models related to Cellular Automata George Gummerman s agentbased simulation of Anasazi settlements Economies Stock market models Econophysics approaches to understanding financial markets Game theory nonzero sum games Ant colony models social insects The University of New Mexico Evolution of Cooperation Axerod 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 I III 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 ln a Norms game I III 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 326 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 I III lt The University of New Mexico Results for Fixed En v 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 detecting on first move and then apologizing when necessary The University of New Mexico Results in Evolving Environment From Axerod 1997 400 350 Mean Score 300 250 1 l l I I l l l t A l I l l l l 1 I I I l I 1 1 k 1 1 I l l 1 I l l l I l 1 I I I l l l I l l Generations W In Figure 11 Prisoner s Dllemma 1n an Evolvmg Env1ronment lt e University of New Mexico Cognitive Modeling using Classifier Systems Induction 1985 Focus on problems with the following characteristics Perpetually novel streams of data noise fluctuations drift Continuous realtime requirements for actions complete rationality is infeasible lmplicitly defined goals such as survival making money winning a game Intermittent payoffs that give no direct information about individual actions Claim Many control problems have this form including cognitive systems Classifier systems are a learning system that Creates new categories based on observed regularities in the environment Continuously updates its model of the environment Can allocate credit among its components The University of New Mexico What is a Classifier System Abstract parallel architecture Forwardchaining rule system Ecology of program instructions Learning algorithms Credit assignment bucket brigade Rule discovery genetic algorithm Theory of model construction Homomorphic view of modeling Qmorphisms I III lt The University of New Mexico Classifier System A rchitecture Rule Discovery Credit Assignment messages Message Rule Set List mes sa es g gt Envrronment Bucket Brigade Genetic Algorithm Rules are of the form 1 0000 1111 OOOO101O 1 0 Pass through Don t care Defined values 01 Multiple conditions negativ ans Ill Ill The University of New Mexico Bucket Brigade How to assign credit to individual rules Each classifier C has a strength SCt Overall usefulness of rule Basis of competition between rules Bids BCt Based on past usefulness strength Relevance to current situation specificity HC BCt b X 90 X SCt Each rule acts like a middle man in an economy Producers and consumers of messages I III lt Direct payoff to last classifier in chain The University of New Mexico Bucket Brigade can t Winning classifiers Place their messages on the message list Pay out to suppliers 0 SCt 1 80 T BCt 80 T1 SC t a x BCt where a 1 Num Of Classifiers Probability matching vs optimizing Variants Partial matching Taxation Exponentials and coefficients Etc The University of New Mexico Ecological Modeling with Echo Echo is an abstract model of ecological behavior Large number of interacting agents Interactions among agents Trade Combat Mating Agents are distributed over a geography of sites 2 d array Each site has renewable resources letters Agents can migrate between sites Evolution Echo adds geography resources and interactions to GA s Echo adds evolution to resourcebased ecological models Echo lacks metabolism The University of New Mexico An Echo Agent Reservoir abda CdC b Conditions Tags abbac cod aab bba C Cddbb Trading Resource IEI Uptake Mask n Genome abbac cod aab bba c cddbbl al 1011 Conditions T Uptake Tags Trading Resource The University of New Mexico Agent Interactions Agent 1 Agent 2 Mating Mating Ta 39 9 aa Cb Mating Mating Condition Condition Cb aa Agent 1 is attracted to agents with a mating tag of CB agent 2 is attracted to agents with a mating tag of AA n I III lt The University of New Mexico The Echo Cycle Pairs of agents are selected to interact Combat Trade Mating Agents pick resources up from the environment Sites charge maintenance Agents die probabilisitically Sites produce resources Agents who have not acquired any resources migrate Agents replicate asexually if able The University of New Mexico The Ecology of Echo Stability of interactions among variants eg flyantcatepillar What happens when more resources are added to the system Relative species abundance trajectories duration distributions Cataclysmic events eg meteors Species formation Isolation effects Flows of resources Transition from singlecell to muticeuar organization The University of New Mexico What can we hope to learn from models like Echo Patterns of behavior Flow of resources Cooperation among agents Arms races Communities Critical regions of parameter space Interactions between local situations and global effects Effects of exogenous and endogenous changes Build intuitions about important dependencies and interactions Identify commonalities among naturally occurring complex adaptive systems The University of New Mexico Sorted Order Representation 010111001101011 O 1 0 Bit String 2 Key Values 3 1 5 4 2 Rotated Layout 1 5 4 2 3 Start at position 2 The Unlvers1ty of New Mexico Sorted Order Representation 010111001101011 3 4 5 010 2 fazaz Bit String Key Values PosMon Rotated Layout Start at position 2 The Unlvers1ty of New Mexico


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.