Transcript Beautiful Thinking

Introduction to Artificial Intelligence
for Bradley University – CS 521
Anthony (Tony) J. Grichnik
Visiting Scientist to Bradley University
Caterpillar Inc.
Outline

Introduction:
The Clans of Artificial Intelligence (AI)

Logical – Be the Expert

Statistical – Would you like to play a game?

Biological – Solutions…naturally

The Future – Hybrids and more
Copyright 2006, Tony Grichnik ~ All Rights Reserved
What if we played MasterMind
on a larger scale…


Like, what if there were a LOT more digits?
…and what if we could reuse digits?
Enter Code ==> 2 5 6 8 1 3 2 2 8 9 4 3 8 6 3 2 9 0 2 6 7 1 8 1 4 5 6 2 9 0 2 5 6 8 3
Enter Guess ==> 2 2 3 9 5 6 7 9 2 3 5 6 7 9 0 1 2 3 4 5 6 7 0 9 2 3 6 7 3 1 8 8 4 6 1
??? Digits Correct


How long would it take for your algorithm to solve it?
We need something faster…a LOT faster….
Copyright 2006, Tony Grichnik ~ All Rights Reserved
How do Genetic Algorithms work?

A Genetic Algorithm (GA) works on three simple steps…
Genes – used to encode individual variables
x1x2 x3
Allele
Chromosome – Encoding of all variables
Populate

Mutation target
Select
Reproduce
Mutate
To make a GA go, you need to know the variables and a
goal function, or measure of whether one solution is better or
worse than another.
Copyright 2006, Tony Grichnik ~ All Rights Reserved
Your Assignment

We’re going to play MasterMind like last time, but with a
twist.






62 integer values (which would be the same as the symbols:
0 to 9, plus A to Z, plus a to z). We will represent them with
the integers 1 through 62.
Each integer can be reused multiple times at multiple
positions.
30 positions in the vector.
All other original rules apply.
Same grading scheme applies.
How many “brute force” permutations are there?


62! – or…
31,469,973,260,387,937,525,653,122,354,951,000,000,000,0
00,000,000,000,000,000,000,000,000,000,000,000,000,000,0
00 – give or take a few.
Copyright 2006, Tony Grichnik ~ All Rights Reserved
So what if we used a GA to help us?

What would be the variables?

What would be the goal function?

How much faster would it be? Or at what
point would the GA outperform the
stochastic approach?
Copyright 2006, Tony Grichnik ~ All Rights Reserved