期刊名称：International Journal of Advanced Research In Computer Science and Software Engineering
印刷版ISSN：2277-6451
电子版ISSN：2277-128X
出版年度：2013
卷号：3
期号：6
出版社：S.S. Mishra
摘要：Simulated annealing is a method of finding optimal values numerically. It chooses a new point, and (for optimization) all uphill points are accepted while some downhill points are accepted depending on probabilistic criteria. For certain problems, simulated annealing may be more efficient than exhaustive enumeration ¡ª provided that the goal is to find an acceptably good solution in a fixed amount of time, rather than the best possible solution. Simulated Annealing is a local search method based on local optimization. In this method each trial solution in the solution space has a cost, and the objective is to find a feasible solution of least cost. The method is iterative. In each cycle we try to move from the current trial solution S to a neighboring point S' in the solution space in an effort to find a better trial solution. Let us assume that the problem is a minimization problem. If cost(S') < cost(S), S' becomes the new trial solution; the move from S to S' is then called a downhill move. If cost(S') > cost(S), S' becomes the new trial solution with probability p = exp (-¦¤/temp), where temp is a parameter known as the temperature and ¦¤ = cost(S') - cost(S); S is retained as the trial solution with probability (1-p). Thus S' can become the new trial solution even when its cost is higher than the cost of the current trial solution S; this kind of move from S to S' is called an uphill move. This deliberate choice of an inferior trial solution with a non-zero probability helps to ensure that the procedure does not get trapped in a local minimum. By slowly reducing the temperature, the probability p is reduced in the course of the iteration as better trial solutions are found. Bin packing problem [1], [2] solves the packing of objects of different volumes into a finite number of bins of capacity V in a way that minimizes the number of bins used. The approximation algorithm is applied on Multiple Bin Packing Problem in such a way that the algorithm produces the minimum number of bin used as a result.
关键词：One bin packing; multiple bin packing; simulated annealing; best fit problem; first fit decreasing; meta- ;heuristics; constraints (parameters).
