hu.birot.OTKit.performance
Class RandomWalks

java.lang.Object
  hu.birot.OTKit.performance.RandomWalks

public class RandomWalks
extends java.lang.Object

This class contains static methods performing different types of random walks. In "randomWalk" a random neighbor is picked in each iteration, whereas in "gradientWalk" the best (the first/random?) neighbor is picked.

Each random walk requires a starting point (initial candidate), a neighborhood structure (being part of the information encoded in a candidate set), a target function (hierarchy/harmony function), rules of moving and a looping schedule (cooling schedule; defining the length of the random walk, and possibly other parameters of the random walk, such as the temperature).

By setting the static variable verbose to true, you can follow the path of the random walker in detail.

Field Summary

static boolean

verbose A static parameter saying whether you want each step printed on the standard error.

Constructor Summary

RandomWalks()

Method Summary

static Temperature	gradientWalk(Candidate w_init, Topology candidate_set, Hierarchy h, RulesOfMoving rom, CoolingSchedule cooling_schedule) This static method returns a candidate, the output of a gradient walk.
static Temperature	gradientWalkrnd(Candidate w_init, Topology candidate_set, Hierarchy h, RulesOfMoving rom, CoolingSchedule cooling_schedule) Same as method Candidate gradientWalk, the only difference being that if the present position of the random walk has more neighboring positions that are equally the best, then a random one of the best neighbors is chosen (and not, arbitrarily, the first one).
static Temperature	randomWalk(Candidate w_init, Topology candidate_set, Hierarchy h, RulesOfMoving rom, CoolingSchedule cooling_schedule) This static method returns a candidate, the output of a random walk.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

verbose

public static boolean verbose

A static parameter saying whether you want each step printed on the standard error. If true, in each iteration the position of the random walker and the temperature is printed to the standard error. By default, this parameter is false.

Constructor Detail

RandomWalks

public RandomWalks()

Method Detail

randomWalk

public static Temperature randomWalk(Candidate w_init,
                                     Topology candidate_set,
                                     Hierarchy h,
                                     RulesOfMoving rom,
                                     CoolingSchedule cooling_schedule)

This static method returns a candidate, the output of a random walk.

In fact, its output is a Temperature object, the temperature at the end of the simulation. Additionally, its field .output contains the output candidate (the final position of the random walk). Further fields of this final temperature can also be useful: for instance, field iterations contain the number of iterations performed in total, and field unmoved contains the number of iterations during which the random walker did not moved at the end of the simulation.

This walk starts from initial candidate w_init. A loop goes through a number of iterations, as defined by the cooling_schedule. The latter does not only determine the number of iterations, but also changes the "temperature", a variable that describes the state of the algorithm. In each iteration, a neighbor candidate c1 of the present position of the random walk (candidate c) is chosen. Neighborhood is defined by the neighborhood relation (topology) within candidate_set. Specifically in random walk, c1 is a random candidate among the candidates neighbor to c, with the weights of the neighborhood structure taken into consideration. Finally, the rules of moving rom determine whether the random walker should move from c to c1.

Field h.type must be specified: either "ot" or "hg" (case insensitive), depending on the type of grammar you employ.

Parameters:

w_init - : Initial candidate.

candidate_set - : A candidate set whose neighborhood relation determines the topology for the random walk.

h - : The hierarchy (the harmony function) defining the target function.

rom - : The rules of moving determining whether the random walker should move to a neighboring position, in function of the two positions' value at h (and possibly also of the state of the walk, i.e., the temperature).

cooling_schedule - : The cooling schedule defining the number of iterations, as well as the "temperature" in each iteration.

Returns:

The final temperature of the algorithm. Its field output contains the final position reached by the random walk. Other fields contain further information: field iterations returns the number of iterations performed during the entire random walk, while field unmoved returns the number of iterations at the end of the walk during which the random walker has not moved.

gradientWalkrnd

public static Temperature gradientWalkrnd(Candidate w_init,
                                          Topology candidate_set,
                                          Hierarchy h,
                                          RulesOfMoving rom,
                                          CoolingSchedule cooling_schedule)

Same as method Candidate gradientWalk, the only difference being that if the present position of the random walk has more neighboring positions that are equally the best, then a random one of the best neighbors is chosen (and not, arbitrarily, the first one).

See Also:

gradientWalk(hu.birot.OTKit.otBuildingBlocks.Candidate, hu.birot.OTKit.otBuildingBlocks.Topology, hu.birot.OTKit.otBuildingBlocks.Hierarchy, hu.birot.OTKit.performance.RulesOfMoving, hu.birot.OTKit.performance.CoolingSchedule)

gradientWalk

public static Temperature gradientWalk(Candidate w_init,
                                       Topology candidate_set,
                                       Hierarchy h,
                                       RulesOfMoving rom,
                                       CoolingSchedule cooling_schedule)

This static method returns a candidate, the output of a gradient walk.

In fact, its output is a Temperature object, the temperature at the end of the simulation. Additionally, its field .output contains the output candidate (the final position of the random walk). Further fields of this final temperature can also be useful: for instance, field iterations contain the number of iterations performed in total, and field unmoved contains the number of iterations during which the random walker did not moved at the end of the simulation.

This walk starts from initial candidate w_init. A loop goes through a number of iterations, as defined by the cooling_schedule. The latter not only determines the number of iterations, but also changes the "temperature", a variable that describes the state of the algorithm. In each iteration, a neighbor candidate c1 of the present position of the random walk (candidate c) is chosen. Neighborhood is defined by the neighborhood relation (topology) within candidate_set. Specifically in gradient walk, c1 is the best candidate among the candidates neighbor to c, with respect to hierarchy (harmony function) h. If the most harmonic subset of the neighbors of c contains more than one candidate, then the first one is chosen (whereas in method gradientWalkrnd, a random one is chosen). Finally, the rules of moving rom determine whether the random walker should move from c to c1.

Field h.type must be specified: either "ot" or "hg" (case insensitive), depending on the type of grammar you employ.

Parameters:

w_init - : Initial candidate.

candidate_set - : A candidate set whose neighborhood relation determines the topology for the random walk.

h - : The hierarchy (the harmony function) defining the target function.

rom - : The rules of moving determining whether the random walker should move to a neighboring position, in function of the two positions' value at h (and possibly also of the state of the walk, i.e., the temperature).

cooling_schedule - : The cooling schedule defining the number of iterations, as well as the "temperature" in each iteration.

Returns:

The final temperature of the algorithm. Its field output contains the final position reached by the gradient walk. Other fields contain further information: field iterations returns the number of iterations performed during the entire gradient walk, while field unmoved returns the number of iterations at the end of the walk during which the gradient walker has not moved.