COSC 3402 Artificial Intelligence

<<< Situation Calculus

Genetic Algorithms

Space of possible solutions:
P = [..............]
Fitness function:
f: P -----> R+

f(a) < f(b) : b is "better" than a

maxa:P(f(a)) = 66

Threshold value c:
If a:P is such that f(a) >= c, then a is acceptable.

Ex. Sorting algorithm for arrays of size 100.
    Given a test set of arrays to be sorted
        and a sorting algorithm b, f(b) = the average 
        number of array locations in right order.
    If c = 100 then f(b) = 100 /* sorts all numbers */

General G.A.

• Given
  • P₀ - initial population
  • f - fitness function
  • c - treshold

            P [population of solution] <-----+
                        |                    |
                        |                    |
                        V      [application of genetic operation to P]
                       / \                   |
              ,_______/   \__________________|
              |   YES \   / NO
              |        \_/    
              V
          Return x

Questions

1. How to represent elements of a population?
2. What are the genetic operations?

Example:
(1) Behaviour of a game character
a1                  a2                          a4
p1,p2,...,p100      p1,p2,...,p100              p1,p2,...,p100
1  0      1         1  1      1                 0  0      1

Our character's "genetic code" (or representation) is a string of 0's and 1's.

Genetic Operations:

A. Random mutation
[010..|x| ... ]  (Randomly Selected)
 --α--   --β--
to:
[ α | 1-x | β ]

B. Cross Over

[  x1  |  y1  ]    [  x2  |  y2  ]
to:
[  x1  |  y2  ]    [  x2  |  y1  ]

(Chunks of same size must be replaced.)

A G.A. selects a set of elements from P_i and sends them directly to P_i+1, then selects another set (parents), finds the offspring using genetic operations and sends the offspringto P_i+1

The selection of x depends on the value of f(x). E.g. the elements with large values of f(x) have high probability of being selected.
pr(x) = f(x)/c

Genetic Algorithm

INPUT:  P(0) - initial population
        f - fitness function
        c - treshold

OUTPUT: x such that f(x) >= c

METHOD:
    Step 0: P(i) = P(0)
            Evaulate all the elements of P(i) using f
            
    WHILE termination = false
        A. select parents from P(i) based on fitness
        B. generate Offspring from parents usings genetic operations
        C. generate a subset L of Pi based on fitness
        D. P(i+1) = Offspring U L
        E. Evaluate all the elements of P(i+1) using f.
            If there is a x in P(i) such that f(x) >= c
                Then return x
            Else
                i = i + 1

Example: Given a set, S of say, 1000 clauses, 
find a truth-value assignment h that makes all 
these clauses true (if possible).

C1,C2,...,C1000   ,   p1,...,p100

(Only one genetic operation - random mutation)

h1   1, 0, ..., 0
h2   0, 1, ..., 1
       ...
h500 1, 1, ..., 1

f(h) = the n number of caluses true under h.
c = 1000