Artificial Intelligence
Links
Optimization
Files
Hill Climbing
-
h( board ) = # of pairs of attacking queens
-
solution... h = 0
-
-
index = column
-
value = row
-
-
board = range( N )
-
shuffle( board )
-
-
then... only check diagonals
-
generate all nbrs... swap any pair
-
-
calculate h( nbr )
-
find min h ...repeat
-
-
does not always succeed
-
-
run 100 trials... success rate
-
run 100 trials... average # of steps
-
-
variations... sideways moves... limit
-
variations... first choice... random nbr
-
-
2015 pdf
Genetic Algorithm
-
variations... weighting... random nbr
-
variations... beam search... k = 4 , 6
-
-
chromosome... parameters... board
-
population... size = O( 2 * N )
-
-
fitness function... h ...or -h find max
-
weaker boards perish before mating
-
-
two parents... two children... crossover
-
then... IMPORTANT... random mutation
-
-
population size... constant over time
-
calculate h... check rows and diagonals
-
-
How many generations to converge on a solution?
-
Does the gene pool stagnate? Parental matching?
Back to AI
3 Sept 2015