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.