A Vector Based Genetic Algorithm

Paul Juell
Radha Balakrishnan
North Dakota State University

the presenter
http://www.cs.ndsu.nodak.edu/~juell

ABSTRACT

Traditional GA Crossover

Genetic Algorithm (GA) search
- Problem - find the highest point (based on a metric m=f(p1,p2,...pn)
- simple hill climbing may have problems (because of complexity of space)
- suggestion - simulate survival of the fittest (with a population of search points and simulated genetic crossover)
Crossover Operator

Limitations of Traditional Crossover

addresses the foothills problem (but can be slow)
part of the slowness comes from changing limited part of chromosome

The Vector Crossover

Testing

Results

Conclusion

Figure 1: The crossover operations

parents
       /---crossover point
       |
1 1 1 1|1 0 0 0
       |
0 1 0 1|0 1 0 1
       |

children

       |
0 1 0 1|1 0 0 0
       |
1 1 1 1|0 1 0 1
       |

Figure 2: Effects of Crossover

Starting position
    |
    |
    |                   o point 1
    |
    |
    |
    |
    |    o
    |    point 2
    |____________________________

Crossover could have no effect
    |
    |
    |                   o point 1
    |
    |
    |
    |
    |    o
    |    point 2
    |____________________________

Crossover could interchagne coorendents
    |
    |    new point 1
    |    o       <_____ o point 1
    |
    |    ^
    |    |
    |    |
    |    o             o new point 2
    |    point 2
    |____________________________

One of the dimenstions can change
    |
    |    new point 2
    |    o         <--- o point 1
    |
    |    o              o new point 1
    |    ^
    |    |
    |    o
    |    point 2
    |____________________________

Figrue 3: The Vector Crossover

    |                         o new point 1
    |                      .
    |                   o point 1
    |                .
    |            . o new point 2
    |        .
    |    
    |    o
    |    point 2
    |____________________________