Thursday, March 25, 2010

Simulated annealing approach to pagination problem

Currently i am involved in my the final year project which is for the ANCL (The Associated Newspapers of Ceylon Ltd.) . The main research area of that project is to give a solution to the pagination problem. We have four member in our team. My main contribution to the project is implementing the simulated annealing algorithm.
Here is my approach to do it.

My algorithm
This is a simplified version of the simulated annealing approach to the pagination problem. At first we place one large advertisement for each page in a section. This is for the regulations we have to follow in our implementation.(Largest advertisement should be in the bottom right corner in odd page ,bottom left corner in the even page).

Based on previous step result initial solution can be generated by placing the remaining ads.
when we placing the ads to the dummy we use three steps.
  1. width and height fit ad
  2. width or height fit ad
  3. random ad which reduces the energy
After creating the initial solutions we remove some random ads and the ads near to the empty spaces to a new array ads we place these ads according to the given three steps. Then we calculate the energy of the newly created solution and if it is less than what we have for the previous one we take it as the current solution.

No comments:

Post a Comment