Application of Simulated Annealing to the Fragment Allocation Problem
Contents:
1) The simulated annealing algorithm
2) Description of allocation problem
3) Application of simulated annealing
i) Annealing parameters
ii) Determining states
iii) Cost function
iv) Complexity estimate
4) Results
5) Future work
1) Simulated Annealing algorithm
Simulated annealing is a methodology used to approximate the
solution of an NP problem. By selectively choosing state configurations
(approximate solutions) and evaluating them against a user-defined cost
function, a near optimal solution to the problem can be obtained.
Many NP problems, including the fragment allocation problem, are
optimization problems where each possible solution is a possible state of
the system and whose value must be measured against certain criteria to
determine its value.
The simulated annealing algorithm is a method of testing the
solution space of a given problem with rules on deciding which solutions
to keep and which to discard. As the algorithm progresses it eliminates
certain possible solution search paths, thus reducing the intractable
problem to approximately solvable in finite time. Like other
approximation algorithms, there is no guarantee that the solution is
optimal or even near optimal, but application of simulated annealing in
various fields have shown it to be very accurate.
The algorithm only decides when to keep an approximate solution
and is unaware of how this solution was reached nor how its cost is
evaluated. Given a random solution to the problem and a previous
solution to the problem:
i) The new solution is kept if it is less costly that the old one.
ii)The new solution may be kept based on an exponentially
decaying probability (temperature) whose value decreases as more
solutions are tested.
The first solution acceptance criteria performs the optimization by
continually choosing the best solution. The second criteria allows the
algorithm to work on a temporarily worse solution which may allow it to
reach a better solution in the future. This is especially needed at the
start of the algorithm where continually selecting the best solution may
only lead to a local minima whereas by accepting a more costly solution
initially allows the algorithm the ability to search an alternate search
path for a possibly better solution.
The problem can be visualized as choosing the best state in terms
of cost among all the possible states (solutions) to the problem. In
the state diagram, certain states are reachable only by search paths
through other states. If these search paths happen to contain a state
whose cost is higher than the best cost found so far, they would not be
searched in a greedy algorithm which continually chooses the best
solution. The second acceptance condition allows this state to be
visited and the other states, which may be minimal, which follow it on the
search path. Obviously, since the number of states is infinite, not all
search paths are searched, especially ones with higher cost, but the
strength of the algorithm is that it doesn't rule these out in advance, in
case they do happen to contain an optimal solution.
The simulated annealing algorithm is general as its
application to a given problem is entirely dependent on decisions made
"outside" the algorithm. Noticeably absent from the algorithm
description is a cost function and a method for determining random
solutions, as these are problem dependent. The seperation of simulated
annealing from any particular instance of a problem is the reason for its
wide-ranging applicability.
2) Description of Fragment Allocation Problem
Given a set of fragments produced by fragmentation of an
objectbase, allocate them across distributed sites to minimize network
transmission time and cost. As these are fragments of objects and not
simply files, there are relationships between the fragments, due to their
encompassing objects' behaviour, which force fragments to be allocated
physically to reflect the way they are accessed logically.
A site usage vector and interfragment reference vector are associated
with each fragment. They represent its usage at all sites and by all
other fragments respectively. These two factors, under the constraint of
site capacities, determine the optimal allocation of the fragments.
Transmission time/cost is assumed directly proportional to
fragment size, and the network is considered fully connected so that
transmission time between any two sites is constant and independent of
the underlying network protocol.
3) Simulated Annealing algorithm as applied to allocation problem
i) Simulated Annealing parameters
These parameters are specific to the simulated annealing
algorithm and are commonly present in any solution that uses it. The
actual values are problem specific.
temperature - T - controls the probability of accepting a more
costly random solution (exp(-chg/K*T) - where chg
is the change in cost of the two states
(>0 for worse solution)
- T decays exponentially as the algorithm proceeds
decay_rate - D - when T decays it does so by the formula:
T= T * D
max_successes - S - number of states accepted as the current best
before T is decreased
max_failures - F - number of failures (states rejected) before
T is decreased
max_losing_temps - L - number of consecutive temperatures where the
temperature was decreased because we reached
max_failures
- algorithm terminates if max_losing_temps is
reached
acceptance_const - K - a value which controls how likely a worse
solution will be accepted by the algorithm
The values of S and F control the number of solutions tested in
the solution space for a given temperature. Obviously, higher values
should theoretically yield a better approximation as more solutions are
tested. Testing has revealed that S=10,000 and F=50,000 are acceptable
values.
ii) Determining States
A major component of the algorithm is the ability to quickly
choose random solutions. The annealing algorithm may begin with an
initially random solution or a proposed optimal solution run by another
algorithm or the annealing algorithm itself. The former is refered to as
simulated sintering as the initial "solution" is not random.
A random move has two forms:
a) Move a random fragment to another random site.
b) Exchange two random fragments of approximately the same size.
Several attempts are made to make a move of the first type as
mvoing one fragment at a time allows for greater precision in determining
the cost of that fragment's current allocation. The second random move
type is needed when site usage nears capacity forcing fragments to move
by exchanging places in the respective sites. (swap space is assumed)
The performance of random move degenerates rapidly as percentage usage at
all sites increases beyond 95%.
Since many proposed solutions are rejected by the algorithm, it
must be able to undo moves quickly. Although state copying is possible,
it quickly becomes unfeasible as the memory allocation and variable
maintenance becomes the bottleneck of the algorithm. To avoid this, all
moves are done and undone using a form of logging. Instead of actually
performing the move, a proposed random move is created, recorded, and
passed to the cost function for evaluation which can be done using only
the log. This is significant improvement over the previous need for two
entire state evaluations to determine if the new state is an
improvement, as the simulated annealing algorithm is only interested in
the change of cost between the two states and not the absolute values of
the cost. The move can be quickly undone using the log eliminating the
need for storage of two states. If only a few fragments are moved in one
move, the complexity of the whole process is reduced from O(N^2) to O(N)
where N is the number of fragments being allocated.
iii) Cost Function
The cost of a proposed solution is the sum over all fragments the
cost of that particular fragment's allocation. The cost of a fragment's
allocation depends on the sum of all non-local references at other sites
or by other fragments at non-local sites. The formulas are presented below.
Let
NF = number of fragments
NS = number of sites
cost of one fragment =
C = ( (1/NF)*(sum over NF [non-local interfragment ref.]) +
(sum over NS [non-local sites ref.]) ) * fragment_size
cost of solution = (sum over NF [C for that fragment] )
For each proposed solution, only the determination of the cost
before and after for every fragment moved is needed. This is O(NF). The
evaluation of the cost function (O(NF)) and random move (O(1)) must be
performed for every proposed solution, so there optimization has been a
critical part of the overall design.
iv) Complexity Estimate
Let C be some constant representing the number of times the
temperature is decreased. C >=1 and its exact value is dependent on the
number of solutions tried at each temperature. Current estimates have 1<= C <=10. Then the complexity of the algorithm is:
O( max(F,S)*L*C*NF) = O(NF)
Storage needed is: O(NF^2)
4) Results:
a) C is related to S and L.
b) S=10,000 and L=50,000 are near optimal annealing parameters.
c) Algorithm tests on parameters of 5 sites and 2000 fragments resulted
in a 30% improvements over an initial random allocation. Running time is
about 20 minutes and memory usage was 15 MB.
d) Somewhat surprisingly, execution time does not depend directly on S
and L due to their interaction with C. When S and L are decreased, C
increases as does the solution cost indicating that higher values of S
and L are preferable.
e) Significant portion of execution time is spent on creating initial
random state and storing the result.
f) Reapplying the algorithm to the result of a previous execution results
in no improvement if S and L were sufficiently large in the first trial.
g) Determination of the acceptance constant, K, is nontrivial. Some
sources suggested taking a random sampling of the solution space and
taking the average as K. I have found that this yields too high of an
acceptance rate, so besides taking the average I divide by a constant
factor.
5) Future work:
The solution cost versus temperature is recorded as the algorithm
progresses thus making a graphical representation an interesting tool on
demonstrating how the annealing algorithm actually works. Comparison of
the simulated annealing approach with other proposed algorithms is
planned, including execution of the algorithm on proposed solutions by
other algorithms to determine if any improvement can be achieved.
Determination of the acceptance constant K must be done to more
precision. The current values of K tried cause the simulated annealing
algorithm to return a slight poorer result ( < 1%) than a pure greedy
algorithm. Sources claim that simulated annealing should consistently
beat the greedy algorithm, so obviously some tinkering of constants must
be done.