Revision 10 as of 2017-05-11 16:46:24

Clear message

Factory for pattern collections

combo

combo(max_states=1000000)

Genetic Algorithm Patterns

The following paper describes the automated creation of pattern databases with a genetic algorithm. Pattern collections are initially created with a bin-packing algorithm. The genetic algorithm is used to optimize the pattern collections with an objective function that estimates the mean heuristic value of the the pattern collections. Pattern collections with higher mean heuristic estimates are more likely selected for the next generation.

genetic(pdb_max_size=50000, num_collections=5, num_episodes=30, mutation_probability=0.01, disjoint=false, random_seed=-1)

Note: This pattern generation method uses the zero/one pattern database heuristic.

Implementation Notes

The standard genetic algorithm procedure as described in the paper is implemented in Fast Downward. The implementation is close to the paper.

  1. Initialization
    In Fast Downward bin-packing with the next-fit strategy is used. A bin corresponds to a pattern which contains variables up to pdb_max_size. With this method each variable occurs exactly in one pattern of a collection. There are num_collections collections created.

  2. Mutation
    With probability mutation_probability a bit is flipped meaning that either a variable is added to a pattern or deleted from a pattern.

  3. Recombination
    Recombination isn't implemented in Fast Downward. In the paper recombination is described but not used.

  4. Evaluation
    For each pattern collection the mean heuristic value is computed. For a single pattern database the mean heuristic value is the sum of all pattern database entries divided through the number of entries. Entries with infinite heuristic values are ignored in this calculation. The sum of these individual mean heuristic values yield the mean heuristic value of the collection.

  5. Selection
    The higher the mean heuristic value of a pattern collection is, the more likely this pattern collection should be selected for the next generation. Therefore the mean heuristic values are normalized and converted into probabilities and Roulette Wheel Selection is used.

Language features supported:

hillclimbing

hillclimbing(pdb_max_size=2000000, collection_max_size=20000000, num_samples=1000, min_improvement=10, max_time=infinity, random_seed=-1)

manual

manual(patterns)

Systematically generated patterns

Generates all (interesting) patterns with up to pattern_max_size variables. For details, see

systematic(pattern_max_size=1, only_interesting_patterns=true)