Previous topic  Top  Next topic  Print this Topic
 

Genetic Optimizer

 

The genetic optimizer allows the optimization of specific queries. This optimizer is typically used before deploying ontologies on a production server. The order of the body literals can be changed/permutated and this might improve the inference speed dramatically. If you create all possible permutations, you may find the perfect result, but this would take an extremely long time. For 10 rules with 4 body literals you would have 104! possible solutions, for 100 rules with 8 body literals you would have 1008! possible solutions. The idea is, that you do not need the best result, but a result that is good enough. If you get one change that improves the query, it should be even better when combined with other positive changes. For optimizations in such high dimensional search spaces genetic algorithms are applicable. Thus the genetic optimizer optimizes the sequence of body literals in the rules using a genetic approach. In the initialization process a random population will be created. This population is a defined number of individuals with each representing exactly one permutation. These individuals together are called a generation, as it is the first one this one, is generation 0. Then the fitness of all individuals will be determined. For this, the permutations will be applied and the query will be executed. The smaller the evaluation time is, the better the fitness. The better the fitness of an individual is the better is its chance to contribute to the following creation of the individuals of the next generation. Their characteristics, the ordering of body literals, will be mixed and a new population will be created. New random changes may be made. The fittest individual survives unchanged. This continues until the wanted number of generations has been calculated.

Limits

As the continuum of all possible reordering is very big, you will need many individuals to test. For complex rule scenarios several thousand individuals should be created, so that it takes a lot of time to optimize a long-running query. Another problem may be the memory demand of the query evaluation. Some permutations will need much more memory than the average. If you already operate on the limits OntoBroker can handle with the available main memory, you might encounter out of memory" errors when using genetic optimizer.

NOTE: If you optimize a specific query with the genetic optimizer and you change the rules or the facts then you will need to execute the genetic optimizer again. If you only change the constants or the order of literals in a rule you do not need to optimize the query again.

Usage

Command

Description

opt_genetic <queryID>

Commands to send an optimized query to OntoBroker

opt_genetic status

The return value is a string. The status of the last complete generation will be returned.
At least one generation has to be evaluated before valid results can be delivered.

OntoBroker Return Values: The return value is a "string" without line separators. Use | as separation character.

opt_genetic kill

Stops a running optimization. It may take a short time, you can use the -isoptimizing command to see when it is done. The timeout window has to fit into the timeout of the socket connection, so that it may be too small for some cases.

opt_genetic isoptimizing

Returns if an optimization process is currently running or not.

OntoBroker Return Values: The return value is a "string".

Example:

opt_genetic file, "test.data", rewrite, timeout, 1000, module,"<http://www.NewOnto1.org/ontology>", "queryID"

Options

file filename - file name for optimisations data.
rewrite - rewrites the file with optimisations data if exists.
timeout value - optimisation timeout (ms).
kill - stops the optimisation.
isoptimizing - checks whether the optimization is already running.
status - returns the best result of the running optimization.