Previous topic  Top  Next topic  Print this Topic
 

Hillclimbing Optimizer

 

The command opt_hillclimbing <queryID> optimizes the bodyordering using a hillclimbing algorithm. You can change the ordering manually.

Usage

opt_hillclimbing [file, filename], [rewrite], module, modulename, queryID

opt_hillclimbing isoptimizing

opt_hillclimbing kill

opt_hillclimbing status

Example:

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

 

command.cmd "opt_hillclimbing file, \"test.data\", rewrite, module, <http://www.ontoprise.de#testonto>, \"queryID"s\"

Options

file filename - file name for optimization data.
rewrite - rewrites the file with optimization data if it exists.
kill - stops the optimization. 
isoptimizing - checks whether the optimization is already running.
status - returns the best result of the running optimization.

for all rules r

 := max

 fomintime r all body permuations  p of r

         evaluate query

         if evaltime < mintime

                 mintime = evaltime

                 minpermutation = p

 set body permutation of r to minpermutation        

It is displayed as plain text in the file bodyordering.data. You can rename the file in OntoConfig.prp:

BodyOrderingDataFile = mybodyordering.data

Additional information on the hillclimbing algorithm

Hill climbing can be used to solve problems that have many solutions, some of which are better than others. It starts with a random (potentially poor) solution, and iteratively makes small changes to the solution, each time improving it a little. When the algorithm cannot see any improvement anymore, it terminates. Ideally, at that point the current solution is close to optimal, but it is not guaranteed that hill climbing will ever come close to the optimal solution

Limitations

Rule bodies should not have many literals! If you have e.g. 10 rule bodies you have to deal with 10 permutations. In this case it would be better to deactivate the unfolding.