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

Artificial Intelligence

by: Dr. Humberto Beier

Artificial Intelligence 22C 145

Marketplace > University of Iowa > ComputerScienence > 22C 145 > Artificial Intelligence
Dr. Humberto Beier
GPA 3.87

Hantao Zhang

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

Hantao Zhang
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 16 page Class Notes was uploaded by Dr. Humberto Beier on Friday October 23, 2015. The Class Notes belongs to 22C 145 at University of Iowa taught by Hantao Zhang in Fall. Since its upload, it has received 26 views. For similar materials see /class/228040/22c-145-university-of-iowa in ComputerScienence at University of Iowa.


Reviews for Artificial Intelligence


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: 10/23/15
Genetic Algorithms 22c 145 Chapter 43 What is Evolutionary Computation An abstraction from the theory of biological evolution that is used to create optimization procedures or methodologies usually implemented on computers that are used to solve problems The Argument Evolution has optimized biological processes therefore Adoption of the evolutionary paradigm to computation and other problems can help us find optimal solutions I Evolutionary Computing Genetic Algorithms invented by John Holland University of Michigan in the 1960 s Evolution Strategies invented by Ingo Rechenberg Technical University Berlin in the 1960 s Started out as individual developments but converged in the later years Si Natural Selection Limited number of resources Competition results in struggle for existence Success depends on fitness tness ofan individual how welladapted an individual is to their environment This is determined by their genes blueprint for their physical and other characteristics Successful individuals are able to reproduce and pass on their genes SH When changes occur Previously fit welladapted individuals will no longer be bestsuited for their environment Some members of the population will have genes that confer different characteristics than the norm Some of these characteristics can make them more fit in the changing environment Genetic Change in Individuals Mutation in gene may be the to various sources eg UV ra s chemicals etc r 1001001 01001001001001 Aner Mulauon Location ofMulalion 1001000001001001001001 Genetic Change in Individuals Recombination Crossove occurs during reproduction sections of genetic material exchanged between two chromosomes l Recom 39nation Crossover cnrnmnsum Ernxsinnnver 3 have mm es WW edu xnmwmiassm The Nature of Computational Problems Require search through many possibilities to nd a solution eg search through seE of rules for one set that best predlcE the ups and downs ofthe financial markes Search space mo big search won39t return within our lifetims Require algorithm to be adaptive or to construct original solution eg interfaces that must adapt to idiosyncrasies of different users Why Evolution Proves to be a Good Model for Solving these Types of Problems Evolution is a method of searching for an almost optimal solution Possibilities W all individuals Best solution 77 the most t or wellsadapted individual Evolution is a parallel process Test39ng and changing of numerous species and individuals ccur at the same time or in parallel Evolution can be seen as a method that designs new original solutions to a changing environ ment The Metaphor EVOLUTION PROBLEM SOLVING Individual Candidate Solution Fitness 4 Quality Environment Problem 5 Genetic Algorithms Closely follows a biological approach to problem solving A simulated population of randomly selected individuals is generated then allowed to evolve Encoding the Problem Example Looking for a new site which is closest to several nearby cities Express the problem in terms of a bit string 2 1001010101011100 where the rst 8 bits ofthe string represent the Xcoordinate and the second 8 bits represent the Ycoordinate SH Basic Genetic Algorithm Step 1 Generate a random population of n chromosomes Step 2 Assign a tness value to each individual Step 3 Repeat until n children have been produced Choose 2 parents based on tness proportional selection Apply genetic operators to copies of the parents Produce new chromosomes Fitness Function For each individual in the population evaluate its relative fitness Fora problem with m parameters the fitness can be plotted in an m1 dimensional space I Sample Search Space A randomly generated population of individuals will be randomly distributed throughout the search space image from http lvnmna informatih uni erlangen dellacoblEvolvicalJavalllultiModalSearchrats ll ilSurlace gil I Genetic Operators Crossover Mtation Production of New I Chromosomes 2 parents give rise in 2 children g Generations As each new generation of 1 individuals is generated they replace their pare t generation To achieve the desired resulls typically 500 to 5000 generations are require The Evolutionary Cycle Selection I y pmms Rcco 39nation Population Mu men I Replacement Offspring 5 Ultimate Goal Each subsequent generation will evolve toward the global maximum After sufficient generations a near optimal solution will be present in the population of chromosomes Dynamic Evolution Genetic algorithms can adapt to a dynamically changing search space Seek out the moving maximum via a parasitic fitness function as the chromosomes adapt to the search space so does the tness function SH Basic Evolution Strategy 1 Generate some random individuals 2 Select the p best individuals based on some selection algorithm tness function 3 Use these p individuals to generate cchildren 4 Go to step 2 until the desired result is achieved ie little difference between generations g Encoding Individuals are encoded as vectors of real numbers object parameters 0p 01 02 03 0m The strategy parameters control the mutation of the object parameters 5p 51 52 53 Sm These two parameters constitute the individual s chromosome Fitness Functions Need a method for determining if one solution is more optimal than another Mathematical formula Main difference from genetic algorithms is that only the most fit individuals are allowed to reproduce elitist selection SH Forming the Next Generation Number of individuals selected to be parents 2 too many lots of persistent bad traits too few stagnant gene pool Total number of children produced c limited by computer resources more children 3 faster evolution El Mutation Needed to add new genes to the pool optimal solution cannot be reached ifa necessary gene is not present bad genes filtered out by evolution Random changes to the chromosome object parameter mutation strategy parameter mutation changes the step size used in object parameter mutation Discrete Recombination Similar to crossover of genetic algorithms Equal probability of receiving each parameter from each parent 8 12 31 5 2 5 23 14 2 12 31 14 SH Intermediate Recombination Often used to adapt the strategy parameters Each child parameter is the mean value of the corresponding parent parameters 8 12 31 52 5 23 14 5 85 27 95 Example Find the max value I of fx1 x100 i Population real vectors of length 100 Mutation randomly replace a value in a vector Combination Take the average of two vectors Evolution Process p parents produce cchildren in each generation Four types of processes pc p parents produce cchildren using mutation only no recombination The fittest p children become the parents for the next generation Parents are not part of the next generation c2 p prc is the above with recombination g Forming the Next Generation Similar operators as genetic algorithms mutation is the most important operator to uphold the principal of strong causality recombination needs to be used in cases where each child has multiple parents The parents can be included in the next generation smoother tness curve pc p parents produce cchildren using mutation only no recombination The fittest p individuals parents or children become the parents of the next generation prc is the above with recombination Tuning a GA Typical for a small problem Other concerns population diversity ranking policies removal policies role of random bias 39 Domains of Application Numerical Combinatorial Optimization System Modeling and Identi cation Planning and Contro Engineering Design Data Mining Machine Learning Arti cial Life 39W global local M L If 3quot 1 Local Beam Search A generalization of Hillclimbing Start with p candidates Keep the best p neighbors of these p candidates in the next round g Stochastic Beam Search Similar to Local Beam Search Randomly choose p neighbors in the next round Keep better neighbors Keep worse neighbors with a probability I GA vs Local Beam Search The starting part is the same GA uses both mutation and combination for next ge ations LBS uses all the neighbors similar to mutation Both keep best candidates for next d GAv Stochastic Beam Search The starting part is the same GA uses both mutation and combination for next generations SBS picks random neighbors very much like mutation GA keeps best candidates for next round 535 may keeps worse candidates for next round GA suitable for Rugged Terrain More of a challenge to optimize eas to get stuck in many local maxi ma mutation and crossover rates g Drawbacks of GA Difficult to find an encoding for a problem Difficult to define a valid fitness function May not return the global maximum Why use a GA requires little insight into the problem the problem has a very large solution space the problem is nonconvex does not require derivatives objective function need not be smooth variables do not need to be scaled fitness function can be noisy eg process data when the goal is a goodsolution When NOT to use a GA if gobaoptimality is required if problem IhSthtcan signi cantl im act algorithm erformance simplify problem representation if the problem is highly constrained if the problem is smooth and convex use a gradientbased optimizer if the search space is very small use enumeration El Taxonomy


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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

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!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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.