AIMA - CH 4 - Search in Complex Environments Flashcards
When is crossover most beneficial in genetic algorithms
Genetic algorithms are similar to stochastic beam search, but with the addition of crossover operation.
Crossover is advantageous when blocks of an agent’s DNA perform are useful as a set, or perform useful functions. From the book, in the 8 queens problem, there may be a set of three queens in the first three columns that don’t attack each other. This could be a useful block to combine with other useful blocks to find a solution.
If blocks do not have any purpose, that is they are not useful as sets, then it can be shown mathematically, that crossover doesn’t have any advantage.
What is a schema in the context of genetic algorithms?
A schema is a substring in which some of the positions of an agent DNA are left unspecified.
For example, with the 8 queen problem, a schema of 246*****, describes all 8-queen states where the first three queens are in rows 2,4,6. Strings that match the schema, for instance 24613578, are called instances of the schema.
It can be shown that if the average fitness of the instances of a schema are above the mean, then the number of instances of the schema will grow over time.
When do genetic algorithms work best?
GA work best when schemas correspond to meaningful components of a solution. If schemas, or blocks, aren’t particularly important, then genetic algorithms don’t have much advantage.
==> Careful planning and engineering of the problem representation are necessary to successfully use genetic algorithms.
What are empirical gradients?
Empirical gradients are methods that measure the changge in the value of an objective function between two nearby points - it is basically a steepest-ascent hill climbing in a discretized state space.
