Heuristic Search Packages 0.1 for Mathematica
Raza Ahmed and Brian L. Evans
Dept. of EECS, University of California, Berkeley, CA 94720-1770
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
1.0 Introduction
This package defines breadth-first, depth-first, hill climbing, and
simulated annealing search techniques in the Mathematica programming
language. These search techniques apply a list of transformation rules
to minimize the cost of an expression. The user gives the list of
rearrangement rules, the expression to be optimized, and the function
to compute cost. When LeafCount is used as the cost function, for
example, the search techniques will simplify the expression.
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.
2.0 System Requirements
The heuristic search packages are written in the Mathematica programming
language and require Mathematica 2.0 or higher. They come with an
examples notebook that requires Mathematica 2.2 to read.
3.0 Installation
The heuristic search packages consist of the following files:
GeneralSearch.m
InformedSearch.m
Master.m
PolySearchFunctions.m
UninformedSearch.m
They must be placed in a directory called HeuristicSearch, which must
appear on Mathematica's path. Evaluate $Path to see the current value
of Mathematica's path. You can add to Mathematica's path by using
AppendTo[ $Path, new-path ]
where new-path might be "/users/me/mathematca" on Unix machine,
"users:me:mathematica" on a Macintosh, or "c:\\users\\me\\mathematica"
on a PC.
4.0 New Mathematica Commands
The heuristic search packages define the following Mathematica commands
and options:
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.
5.0 Examples
This section presents examples of using the new heuristic search functions.
Initialize the heuristic search packages in the conventional manner:
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.
6.0 References
[Eva95] B. L. Evans, S. X. Gu, A. Kalavade, and E. A. Lee, "Symbolic
Computation in System Simulation and Design," Invited Paper, Proc. of SPIE
Int. Sym. on Advanced Signal Processing Algorithms, Architectures, and
Implementations, July 9-16, 1995, San Diego, CA, pp. 396-407.
http://ptolemy.eecs.berkeley.edu/papers/spie95symcomp/
[Wol91] Stephen Wolfram, Mathematica: A System for Doing Mathematics by
Computer, Addison-Wesley, ISBN 0-201-51502-4, 1991.
7.0 Copyright
The heuristic search packages are covered by the standard freely distributable
U.C. Berkeley copyright shown below.
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.
8.0 Acknowledgements
The development of the heuristic search packages was supported by
the Ptolemy project.
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:
Mathematica: http://www.wolfram.com/, comp.soft-sys.math.mathematica
Ptolemy: http://ptolemy.eecs.berkeley.edu/, comp.soft-sys.ptolemy