Artificial Intelligence Overview

Artificial Intelligence Overview

Genetic Algorithms and Their Applications John Paxton Montana State University August 14, 2003 Glacier National Park Natural Evolution more offspring are produced than can

survive the offspring are not all the same the offspring best suited to the environment are more likely to survive Genetic Algorithm 1. Generate a population of chromosomes of size N 2. Calculate the fitness of each chromosome 3. If the termination condition is satisfied,

stop. 4. Select a pair of chromosomes for mating 5. With the crossover probability, pc, produce two offspring via crossover. Genetic Algorithm 6. With the mutation probability, pm, randomly change the gene values in the two offspring. 7. Place the resulting chromosomes in the

new population. 8. If the population size is not yet N, go to step 4. 9. Replace the current population with the new population, go to step 2. Termination Condition Stop after a set number of generations. Stop after n generations have passed without significant improvement

Stop after a good enough solution has been produced Representation Maximize f(x) = 7x x2 where x is an integer in [0 .. 7]. Possible chromosomes: 000, 001, 010, 011, 100, 101, 110, 111 Initial Population

010 100 000 001

Fitness Function Chromosome Fitness (7x x2) 010 10 101

10 000 0 001 6

Selection Based on fitness of individuals Roulette Wheel selection is very common Fitness

Selection Probability 10 11/30 10 11/30

0 1/30 6 7/30 Crossover Operator

Old 010 101 (fitness 10) (fitness 10) New 011 100

(fitness 12) (fitness 12) Crossover Operator Crossover is a very effective search technique. It conducts a parallel search through the most promising building blocks. Building blocks with above average fitness

occur more frequently in the next generation! Crossover Operator Fitness Space Generation 1 Generation 2 Convergence

A nasty problem that must be overcome! Mutation Operator Old 011

New 001 Purpose: Genetic Diversity Mutation Operator Generation 1 Generation 2

Elitism Copy the n most fit chromosomes from the previous generation into the new one. Typically, n is 1. Custom Operators Traveling Salesperson Problem Chromosome 1: (1 2 3 4 5) Chromsome 2: (2 4 5 3 1)

Custom Crossover Chromosome 1: (1 2 4 5 3) Chromosome 2: (2 4 1 3 5) Many Decisions

Representation of Individuals Population Size Genetic Operators How to Use Operators Stopping Conditions Fitness Function

Genetic Programming Generation 1 (* (+ a a) (- a b) 2) (- 2 a) Generation 2 (* 2 (- a b) 2) (- (+ a a) a) Genetic Programming

Select terminals Select primitive functions Define the fitness function Decide on the parameters (crossover probability, etc.)

Decide the stopping condition Applications There are numerous applications of genetic algorithms. Artificial Life Framsticks is a three-dimensional life simulation project. Both the physical structure of creatures and their control

systems are evolved. Evolutionary algorithms are used with selection, crossover and mutation. Finite element methods are used for simulation. Both spontaneous and directed evolutions are possible. Biocomputing Biocomputing, or Bioinformatics, is the field of biology dedicated to the automatic

analysis of experimental data (mostly sequencing data). Several approaches to specific biocomputing problems have been described that involve the use of GA, GP and simulated annealing. There are three main domains to which GA have been applied in Bioinformatics: protein folding, RNA folding, sequence alignment. Cellular Automata

Nature abounds in systems involving the actions of simple, locally- interacting components, that give rise to coordinated global behavior. Evolvable Hardware The idea of evolving machines, whose

origins can be traced to the cybernetics movement of the 1940s and the 1950s, has recently resurged in the form of the nascent field of bio-inspired systems and evolvable hardware. Game Playing GAs can be used to evolve behaviors for playing games. Work in evolutionary game theory typically surrounds the evolution of

a population of players who meet randomly to play a game in which they each must adopt one of a limited number of moves. For example, poker. Job Shop Scheduling The Job-Shop Scheduling Problem (JSSP) is a very difficult NP- complete problem which, so far, seems best addressed by

sophisticated branch and bound search techniques. GA researchers, however, are continuing to make progress on it. Nonlinear Filtering New connections between genetic algorithms and Non Linear Filtering Theory have been established. GAs have already been successfully applied to a large class of non-linear filtering problems such as

radar / sonar / GPS signal processing. For example, the military uses GAs to identify radar signals. Timetabling This has been addressed quite successfully with GAs. A very common manifestation of this kind of problem is the timetabling of exams or classes in Universities, etc.

Other Applications Genetic Programming. Neural Networks. Jazz. Find good and bad riffs for jazz improvisation (Al Biles). Stock companies. Predict stock market. Oil pipeline throughput. Targets for GA Research

Using GAs as general problem solving tools Finding the perfect GA for a given class of problems Understanding the behavior of GAs Using GAs for teaching and learning Using GAs for increasing cooperation between disciplines Questions?

Recently Viewed Presentations

  • From Greeks to Geeks: a History and Explanation of Computer ...

    From Greeks to Geeks: a History and Explanation of Computer ...

    History of computer science Pre-dates modern computers by more than 2000 years! Digital computers make it more practical to compute. "Computer" was a job title for people around time of WWII Computers Electronic computers created because of need for them:...
  • Postwar America

    Postwar America

    THE POSTWAR BOOM Chapter 19
  • World War II Posters

    World War II Posters

    With the growth of the Internet, the flow of persuasive messages has been dramatically accelerated. For the first time ever, citizens around the world are participating in uncensored conversations about their future.
  • Working With 4-Year-Olds - ALEX

    Working With 4-Year-Olds - ALEX

    Try out a few different options to solve problems and perseverance is encouraged. Learn the simple skills associated with figuring out how to fix or work through any problem. Math Counting and number recognition. For example, children learn to count...
  • "A Rose for Emily" - Elgin Community College

    "A Rose for Emily" - Elgin Community College

    Passage of time - Emily's denial of it "A Rose for Emily" By William Faulkner PLOT Exposition: Initial equilibrium complication (Homer) Setting 3. Characterization (What are the characters like?
  • Introduction to economics

    Introduction to economics

    The idea that all resources are limited is known as… Scarcity! But people's needs/wants are . unlimited, therefore… People and economies must make
  • Anglo-Norman and Medieval Romance - WordPress.com

    Anglo-Norman and Medieval Romance - WordPress.com

    Romance: A fictional story in verse or prose that relates improbable adventures of idealized characters in some remote or enchanted setting; or, more generally, a tendency in fiction opposite to that of realism. Medieval romance is distinguished from epic by...
  • She was dressed in rich materials  satins, and

    She was dressed in rich materials satins, and

    What is the meaning of the image of 'a red balloon bursting? Does Miss Havisham have a fair view of men? What do you think of her view of being an unmarried woman? How far does the poem show Miss...