(* :Title: Informed search algorithms *)
(* :Authors: Raza Ahmed and Brian L. Evans *)
(*
:Summary:
*)
(* :Context: HeuristicSearch`InformedSearch` *)
(* :PackageVersion: $Revision: 1.21 $ *)
(*
:Copyright: Copyright 1996 by Regents of the University of California
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.
*)
(* :History: *)
(* :Keywords: *)
(*
:Source:
*)
(* :Warning: *)
(* :Mathematica Version: 2.0 *)
(* :Limitation: *)
(*
:Discussion:
*)
(* :Functions: *)
(* B E G I N P A C K A G E *)
BeginPackage[ "HeuristicSearch`InformedSearch`",
{ "HeuristicSearch`GeneralSearch`" } ];
(* U S A G E I N F O R M A T I O N *)
CoolingScheduleFunction::usage =
"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::usage =
"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::usage =
"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.";
(* E N D U S A G E I N F O R M A T I O N *)
Begin[ "`Private`" ]
(*
HillClimbing
Algorithm to find the local maxima using the hill climbing strategy
*)
HillClimbing[problem_, options___] :=
Module[ {current = problem, currentnode = 0, evaluationfunction, listofrules,
localmax = True, maxtime, next = problem, nextnode = 0,
oplist, successorfunction, successors, time = 0},
oplist = Join[{options}, Options[ HillClimbing ] ];
{evaluationfunction, listofrules, maxtime, successorfunction} =
{EvaluationFunction, TransformationRules,
MaxIterations, SuccessorFunction} /. oplist;
nextnode = evaluationfunction[next];
While [ localmax && time < maxtime && successorfunction[current, listofrules] =!= {},
current = next;
currentnode = nextnode;
successors = successorfunction[current, listofrules];
next = SmallestInList[successors, evaluationfunction];
nextnode = evaluationfunction[next];
If [nextnode >= currentnode, localmax = False];
time++ ];
current ]
Options[ HillClimbing ] =
{ EvaluationFunction -> LeafCount,
MaxIterations :> $IterationLimit,
SuccessorFunction -> RuleBasedSuccessorFunction,
TransformationRules -> {} };
(*
SimulatedAnnealing
This function takes a problem and the schedule which is the mapping
from time to "temperature". The local variables used in the
algorithm include "current" and "next" which are the nodes. The other
local variable is the "temperature" which is the temperature
controlling the probability of downward steps.
*)
SimulatedAnnealing[problem_, options___] :=
Module[ {current, currentcost, deltaE, evaluationfunction, listofrules,
maxtime, next, nextcost, oplist, randomvar, schedule,
successorfunction, successors, temperature, time},
oplist = Join[{options}, Options[SimulatedAnnealing]];
{schedule, evaluationfunction, maxtime, listofrules,
successorfunction} =
{CoolingScheduleFunction, EvaluationFunction,
MaxIterations, TransformationRules,
SuccessorFunction} /. oplist;
If [ schedule == Automatic, schedule = coolingSchedule ];
current = problem;
currentcost = evaluationfunction[current];
For[ time = 1, time <= maxtime, time++,
temperature = N[ schedule[time] ];
If [ temperature == 0 || successorfunction[current, listofrules] === {} ,
time = maxtime,
successors = successorfunction[current, listofrules];
next = successors[[Random[Integer,
{1, Length[successors]}]]];
nextcost = evaluationfunction[next];
deltaE = nextcost - currentcost;
If [ deltaE > 0,
current = next;
currentcost = nextcost,
randomvar = Exp[deltaE/(temperature-deltaE+1)];
If [ Random[Real, {0, 1}] < N[randomvar],
current = next;
currentcost = nextcost ] ] ] ];
current ]
Options[ SimulatedAnnealing ] =
{ CoolingScheduleFunction -> Automatic,
EvaluationFunction -> LeafCount,
MaxIterations :> $IterationLimit,
SuccessorFunction -> RuleBasedSuccessorFunction,
TransformationRules -> {} };
(* this is a simple cooling schedule which tries to cool the system slowly *)
coolingSchedule[time_] := (1/time);
Protect[ CoolingScheduleFunction, HillClimbing, SimulatedAnnealing ];
End[];
EndPackage[];