Abstract. For this article let us discuss the implementation of the Room Assignment Problem with the Simulated Annealing technique. Later on a parallel implementation with MPI is implemented.
1. Introducing the problem
Using the simulated annealing as proved to be a great general-purpose technique for solving problems by reusing the concept of annealing (cooling) in solids and their thermal equilibrium. The number of iterations in a problem like room assignment (that is on focus for this paper) is extremely high, hence the use of this technique that may not result in an optimal solution, instead it returns an optimal or near-optimal solution.
In this article some experiments are made for the room assignment problem without and with simulated annealing, and running each one of these cost minimization algorithms in a sequential and parallel environment. However, we won't study the parallelization process (and optimizations) of the algorithm itself, instead we will run the algorithm in separate processors therefore getting many solutions for the same problem - the idea is to eventually get the lowest cost that a given processor returns. With this I mean that the main goal is to distribute the work done by the algorithm through several working units (using MPI).
2. Objectives
2.1. Simulated Annealing
Simulated annealing is an iterative process that goes through the current solution and generates a random change. If that newer and random change has a lower cost, the change is accepted. This acceptance decision is based upon, obviously, the lower cost, and a temperature argument existing in the algorithm that decreases as we run through the iterations - it is this temperature that controls the acceptance rate in the solution.
2.2. Room Assignment problem
The room assignment problem is a combinatorial optimization problem. The problem is enunciated this way: lets consider that an even number (N) of students need to share rooms in a college dorm (so there are N/2 rooms available); each student fills in an inquiry where they classify their disliking regarding other possible room-mates (the dislikes matrix); the objective is to find a room distribution with the lowest possible cost.
Note: To guarantee the correctness of the algorithm, we consider that the optimal solution is reachable (within the provided input). Inserting the optimal solution consists in putting a series of minimal cost values (0) in a way that exists at least one combination of students in the system that returns a cost 0.
3. Cost minimizing without Simulated Annealing (SA)
We will study how to generate a minimized cost function not considering parallelism and simulated annealing – however this algorithm will be directed to further integrate the SA algorithm. The program basically generates an N-sized matrix with random values between 0 and 10 that represents the dislikes between the students. Then an initial random distribution of students is applied to the rooms not paying attention to the dislike-costs such student combination brings. So now that we have a dislikes matrix and the first room assignment we can start paying attention to minimize cost function. We start by fetching two different students (student1 and student2) that do not share a room and getting their room-mates (student3 and student4; student1 and student3 share a room; student2 and student4 share another room).
Do{
student1 = getRandomStudent()
student2 = getRandomStudent()
} Repeat While(student1 and student2 are in the same room);
student3 = getRoomMateOf(student1)
student4 = getRoomMateOf(student2)
Now that we reached the point that we have a possible new combination we need to check if the cost associated with the students switching rooms is better, for instance, switching student3 with student4. We will store this cost difference in a delta argument. So we will basically calculate the difference cost of the initial combination with the new possible combination.
delta = (Dislikes[st1][st4]+Dislikes[st2][st3]) – (Dislikes[st1][st3]+Dislikes[st2][st4])
If delta0 it means that the new combination has a lower cost and if the students swap rooms we get a lower overall cost in the entire distribution – if so the students are swapped. By repeating this same procedure, due to the fact that we always try to reach random students to check the swap-rooms cost, the program will fetch lower cost combinations and finally when a maximum number of iterations (Max_Iter) is reached we will probably have a low-cost combination. An important detail is that when a swap is performed this iteration counter is set to its initial value in order to get a viable final cost. This detail states that we will only reach the maximum number of iterations, when we spend Max_Iter iterations without finding any improvement in the distribution. The final algorithm with Max_Iter implemented is given below.
Do{
Do{
student1 = getRandomStudent
student2 = getRandomStudent
}Repeat While(student1 and student2 are in the same room);
student3 = getRoomMateOf( student1 )
student4 = getRoomMateOf( student2 )
delta = (Dislikes[st1][st4]+Dislikes[st2][st3]) – (Dislikes[st1][st3]+Dislikes[st2][st4])
if( delta < 0 ){
swapStudents( student1, student2 )
itetator = 0;
} else {
iterator = iterator + 1
}
}Repeat While(Max_Iter not reached)
4. Cost minimizing with Simulated Annealing (SA)
The minimization algorithm with simulated annealing is exactly the same as the one before, but introducing a simple temperature parameter T that decreases as the program runs through the iterations. This T is first initialized with 1 and decreases with T=0.999*T, however we can experiment on several initial values of T. In this paper we also experiment on T0=10 (being T0 the first value of T when the system begins).
T=1
iterator=1
Do{
Do{
student1 = getRandomStudent
student2 = getRandomStudent
}Repeat While(student1 and student2 are in the same room);
student3 = getRoomMateOf( student1 )
student4 = getRoomMateOf( student2 )
delta = (Dislikes[st1][st4]+Dislikes[st2][st3]) – (Dislikes[st1][st3]+Dislikes[st2][st4])
random_prob = getRandomProbability
if( delta < 0 OR exp(-delta/T) >= random_prob ){
swapStudents( student1, student2 )
iterator = 0;
}else
iterator = iterator + 1
T=0.999*T
}Repeat While(Max_Iter not reached)
5. Results for cost minimizing with SA
The results presented were made for N (number of students) varying from 20 to 100. We also experiment on the parameter T0=1 and T0=10 (Sorry for the image quality!).
As we can see there are significant improvements on the minimized cost with SA, although they are only visible as we increase N. The minimized costs for N are not visible because for this experiment the minimized cost is 0. We conclude from this graph that just by inserting the simmulated annealing techinque we can find costs that reach out to the minimum, this is a very good improvement in minimization quality.
For another trial experiment for SA we set the T parameter to 10. Increasing the initial temperature parameter (T0) will cause the algorithm to take longer but we can expect better results.
We can see that for T0=10 we have more costs that reach down to 0. This is fue to the fact that by increasing T we are increasing the number of tests done per iteration.
6. Cost minimizing introducing parallelism
We will insert parallelism in our previous implementations with MPI (Message Passing Interface). The objective is to run our sequential implementations as many times as possible in different processors so we can reach a better solution. However there is an importante detail to take in consideration: the initial dislikes matrix and room distribution must be the same for every processor that runs the cost minimization functions. Based on this consideration the main processor (the one that the program considers to have a rank 0) must send the dislikes matrix and the vectors with the initial room distribution to every other processor. We can do so with the broadcast primitive in MPI called Bcast(...). The main pseudo-code where we insert the MPI primitives is shown bellow.
MPI_Init(...)
MPI_Comm_rank(... ,rank)
if(rank == 0){
initializeMatrix(Dislikes)
createFirstDistribution(rooms)
// processor 0 sends the Dislikes matrix and rooms distribution to all other processors
MPI_Bcast (Dislikes, ...)
MPI_Bcast (rooms, ...)
}else{
// other processors will receive Dislikes and rooms
MPI_Bcast (Dislikes, ...)
MPI_Bcast (rooms, ...)
}
min_cost = minimizeCost(Dislikes,rooms)
MPI_Finalize()
If the processor that runs this code is the one with rank 0 it will broadcast the mentioned values to all other processors, if not it means that the code will be run in any other processor and it will receive these values. All processors (including rank 0) will run the cost minimization function.
7. Results for cost minimization with simulated annealing with MPI
Running our algorithms in the cluster taking advantage of a multi-core architecture shows obvious enhancements. These experiments were run on the cluster reserving them to 4 nodes totaling 32 cores, so in the end of the execution we have 32 different results for each N in which only the smallest was chosen to include in the previous graph. From the graph we extract that there aren't much differences between using T0=1 and T0=10, still for T0=10 the quality of the results is better since the minimized cost appears slightly more often than for T0=1. We can check a rare case of generating the initial distribution without worrying about any minimized cost at N=28.
The quality of the solutions reached for both algorithms (with and without SA) are better when run in this parallel environment because we can then choose the minimal cost returned by the various processors.
8. Conclusions
In conclusion we see that using the simulated annealing technique is a major improvement when it comes to minimizing costs. It works better if a bigger N since the difference between the minimized results are more noticable.
Thanks for reading.
9. References
[1] Wikipedia on Simulated Annealing - http://en.wikipedia.org/wiki/Simulated_annealing
[2] MPI C examples - http://people.sc.fsu.edu/~burkardt/c_src/mpi/mpi.html
[3] Message Passing Interface (MPI) - https://computing.llnl.gov/tutorials/mpi/
[4] Michael J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill 2003.
Sem comentários:
Enviar um comentário