E-mail: ble@eecs.berkeley.edu, Web: http://ptolemy.eecs.berkeley.edu/~ble
6/24/96
-- Table of Contents --
1.0 Introduction 5.0 Examples 2.0 System Requirements 6.0 References 3.0 Installation 7.0 Copyright 4.0 New Tcl Commands 8.0 Acknowledgements
Breadth-first and depth-first searches will always find the optimal answer but requires memory that is exponential in the number of transformation rules in the worst case. Hill climbing and simulated annealing only require a constant amount of memory, but they are not guaranteed to find the optimal answer. Simulated annealing can be modified to find the optimal answer in exponential time with constant memory.
We provide a notebook that gives examples of using these search techniques to minimize the cost of evaluating polynomials. Hill climbing outperforms breadth-first and depth-first searching in execution time and memory usage to find the same optimal answer. Hill climbing runs faster than simulated annealing because the optimization steps fit a steepest decent approach.
AppendTo[ $Path, new-path ]where new-path might be "/users/me/mathematica" on Unix machine, "users:me:mathematica" on a Macintosh, or "c:\\users\\me\\mathematica" on a PC.
The Heuristic Search Packages are available from MathSource and the Ptolemy FTP site.
GeneralSearch.m
CostReductionFactor is an option for the BreadthFirstSearch and DepthFirstSearch routines. A setting of 2 will attempt to reduce the cost by a factor of 2.
EvaluationFunction is option for the search routines. It specifies a function that returns the cost of an expression.
GoalFunction[problem, parameter, evalfun] is a function which accepts the problem as one of the arguments and the parameter by which the cost has to be reduced. If the function is used under one of the uninformed search algorithms, then the parameter should be supplied as the optional argument. For the usage within the uninformed algorithm, see the usage of the uninformed search algorithm to be used.
GoalTest[state, goal, evalfun] is used by the uninformed search algorithm. It takes the state on which the goal test is supposed to be applied and the goal which is set by calling the GoalFunction before testing for the goal state.
RuleBasedSuccessorFunction[expr, rules] is the default function for the package to generate the successors of the expression expr by applying the transformation rules to every subexpression of expr.
SuccessorFunction is an option that specifies a function to generate a list of possible new states from an existing state. The function must take two arguments: an expression and a list of rules. In the search functions, it applies a set of transformation rules to various parts of the expression to generate a list of equivalent expressions.
SmallestInList[list, evalfun] returns the element in the list with the lowest cost returned by evalfun.
TransformationRules is an option for the various search routines. It should be set to a list of rules such as {a -> b, c[d_] :> d^2}.
InformedSearch.m
CoolingScheduleFunction is an option whose value is a function that maps time into temperature. Time is positive and temperature is nonnegative. A common cooling function is 1/time. For SimulatedAnnealing, the cooling function should cool slowly for best results.
HillClimbing[expr, options] applies hill climbing to minimize the cost of the expression expr. The EvaluationFunction option specifies a function to return the cost of an expression. The value of the TransformationRules option indicates the rules to apply to the expression. By default, no rules are applied. The SuccessorFunction option specifies a function to apply the rules to obtain a list of alternate expressions (new states). The default successor function applies the rules at each level of the expression. The duration of the search can be controlled by the MaxIterations option.
SimulatedAnnealing[expr, options] applies simulated annealing to minimize the cost of the expression expr. The EvaluationFunction option specifies a function to return the cost of an expression. The value of the TransformationRules option indicates the rules to apply to the expression. By default, no rules are applied. The SuccessorFunction option specifies a function to apply the rules to obtain a list of alternate expressions. The default successor function applies the rules at each level of the expression. The duration of the search can be controlled by the MaxIterations and CoolingScheduleFunction options. The default CoolingScheduleFunction returns 1/t for argument t.
PolySearchFunctions.m
PolynomialComponentCost function is used to specify the cost of addition and multiplication encountered in the polynomial.
PolynomialEvaluationCost[polynomial] computes the total implementation cost to evaluate the polynomial.
PolynomialSuccessorFunction[problem, listofrules] uses the rule1list to generate the rule1list to generate subpolynomials which are then factored by the polyfactor. This list of the factored subpolynomials are then appended to the rest of the terms of the polynomial to generate the successor states to be used by the search algorithms.
UninformedSearch.m
BreadthFirstSearch[problem] returns a state satisfying the goal criteria after going down the search tree through the successor states top to bottom.
DepthFirstSearch[problem] returns a state satisfying the goal criteria after going down the search tree through the successor states bottom to top.
In[2]:= Needs[ "HeuristicSearch`Master`" ]In the following example, we will apply a series of rearrangements to a polynomial to obtain the most efficient form to compute it, given that addition costs 1 unit and multiplication costs 5 units. We will use a generic sixth-order polynomial:
In[3]:= poly = A x + B x^2 + C x^3 + D x^4 + E x^5 + F x^6
2 3 4 5 6
Out[3]= A x + B x + C x + D x + E x + F x
We can apply hill climbing to find the optimal form for implementation:
In[4]:= {timing, optpoly} =
Timing[HillClimbing[poly, EvaluationFunction -> PolynomialEvaluationCost,
SuccessorFunction -> PolynomialSuccessorFunction]]
Out[4]= {1.41667 Second, x (A + x (B + x (C + x (D + x (E + F x)))))}
In[6]:= optcost = PolynomialEvaluationCost[optpoly]
Out[6]= 35
In[7]:= initcost = PolynomialEvaluationCost[poly]
Out[7]= 110
In[8]:= FactorReductionInCost = N[initcost/optcost]
Out[8]= 3.14286
We have reduced the implementation cost by a factor greater than 3.
Copyright (c) 1996 The Regents of the University of California. All rights reserved.
Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
The Ptolemy project is supported by the Advanced Research Projects Agency and the U.S. Air Force (under the RASSP program, contract F33615-93-C-1317), Semiconductor Research Corporation (project 95-DC-324), National Science Foundation (MIP-9201605), the State of California MICRO program, and the following companies: Cadence, Dolby Laboratories, Hitachi, Lucky/Goldstar, Mentor Graphics, Mitsubishi, Motorola, NEC, NORTEL (formerly Bell Northern Research), Pacific Bell, Philips, and Rockwell.
For more information, visit the following Web sites and news groups: