The week's pick
Random Articles
Reseach Article
Generic Algorithm Implementation of Approximation Algorithm using Simulated Annealing (SA)
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 81 - Number 3 |
| Year of Publication: 2013 |
| Authors: Diptam Dutta |
10.5120/13992-2014
|
Diptam Dutta . Generic Algorithm Implementation of Approximation Algorithm using Simulated Annealing (SA). International Journal of Computer Applications. 81, 3 ( November 2013), 17-24. DOI=10.5120/13992-2014
Abstract
This paper describes a complementary mechanism that attempts to learn the structure of the search space over multiple runs of SA on a given problem[29] (Best fit Problem & First Fit Decreasing). Specifically, we introduce a mechanism that attempts to predict how (UN) promising a SA runs is likely to be, based on probability distributions that are "learned" over multiple runs. The distributions, which are built at different checkpoints, each corresponding to a different value of the temperature ('temperature' is a variable which decrements its value at each step-as SA has a great relation with physics, the variable is termed in this manner) parameter used in the procedure, approximate the cost reductions that one can expect if the SA run is continued below these temperatures. 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.
References
- Assmann, S. and D. Johnson, D. Kleitman, J. Leung, On a dual version of the one-dimensional bin packing problem, J. Algorithms 5 (1984) 502-525.
- Baker, B. , A new proof for the first-fit decreasing bin-packing algorithm, J. Algorithms 6 (1985) 49-70.
- Baker, B. and E. Coffman, Jr. , A tight asymptotic bound for next-fit-decreasing bin packing, SIAM J. Alg. Disc. Math. , 2 (1981) 147-152.
- Bentley, J. and D. Johnson, F. Leighton, C. McGeoch, L. McGeoch, Some unexpected expected behavior results for bin packing. , in Proceedings of the 16th Annual ACM Sym. on Theory of Computing, 1984, p. 279-288.
- Brucker, P. , Scheduling Algorithms, Springer-Verlag, New York, 1995.
- Coffman, Jr. , and G. Galambos, S. Martello, and D. Vigo, Bin Packing Appoximation Algorithms: Combinatorial Analysis, in Handbook of Combinatorial Optimization, D. Du and P. Pardalos, (eds. ), Kluwer, Amsterdam, 1998.
- Coffman, Jr. , and M. Garey, D. Johnson, Dynamic bin packing, SIAM J. Comput. , 12 (1983) 227-258.
- Coffman, Jr. , and M. Garey, D. Johnson, Approximation Algorithms for Bin-Packing,: An updated survey, in Algorithm Design for Computer Systems Design, G. Ausiello, M. Lucertini, and P. Serafini, (eds. ), Springer-Verlag, New York, 1984, 49-106.
- Conway, R. and W. Maxwell, L. Miller, Theory of Scheduling, Addison-Wesley, Reading, 1967.
- Courcoubetis, C. and R. Weber, Necessary and sufficient conditions for the stability of a bin
- packing system, J. Appl. Prob. , 23 (1986) 989-999.
- Csirik, J. , The parametric behavior of the first-fit decreasing bin packing algorithm, J. Algorithms 15 (1993) 1-28.
- Csirik, J. and J. Frenk, G. Galambos, A. RinnooyKan, Probabilistic analysis of algorithms for dual bin packing problems, J. Algorithms 12 (1991) 189-203.
- Csirik, J. and D. Johnson, Bounded space on-line bin packing; best is better than first, In Proceedings, Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, p. 309-319.
- Fernandez del la Vega, W. and G. Lueker, Bin packing can be solved in 1 + ? in linear time, Combinatorica 1 (1981) 34-355.
- Flexzar, k. and K. Hindi, New heuristics for one-dimensional bin packing, Computers and Operations Research 29 (1902) 821-839.
- Floyd, S. and R. Karp, FFD bin packing for item sizes with distribution on [0, 1/2], Algorithmica, 6 (1991) 222-240.
- French, S. , Sequencing and Scheduling, Wiley, New York, 1982.
- Garey, M. and R. Graham, D. Johnson, A. Yao, Resource constrained scheduling as generalized bin packing, J. Combinatorial Theory Ser. A, 21 (1976) 257-298.
- Garey, M. , and D. Johnson, Approximation algorithms for bin packing problems-A survey, in Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini, (eds. ). , Springer-Verlag, New York, 1981, p. 147-172.
- Garey, M. and D. Johnson, A 71/60 theorem for bin packing, J. of Complexity, 1 (1985) 65-106.
- Graham, R. , Bounds for certain multiprocessing anomalies, Bell System Tech. J. , 45 (1966) 1563-1581.
- Graham, R. , Bounds on multiprocessing anomalies, SIAM J. Applied Math. , 17 (1969) 263-269.
- Graham, R. , Combinatorial Scheduling, in Mathematics Today, L. Steen, (Ed. ), Springer-Verlag, New York, 1978, p. 183-211.
- Hofri, M. , Probabilistic Analysis of Algorithms, Springer-Verlag, New York, 1987
- Johnson, D. , Near-Optimal Bin Packing Algorithms, Doctoral Thesis, MIT, Cambridge, 1973.
- Average-Case Analyses of First Fit and Random Fit Bin Packing, Susanne Albers, Michael Mitzenmacher,
- Dósa G. , Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013
- D. Dutta, S. K. Jha, Seikh B. Ahmad, D. K. Pal, Implementation of Approximations Algorithms with Simulated Annealing (SA), IJARCSSE,2013
Index Terms
Keywords