Experiments with simulated annealing

ABSTRACT

The performance of simulated annealing is compared to that of other Monte Carlo methods for optimization. Our experiments show that these other methods often perform better than simulated annealing.

REFERENCES

• COHO83a: J. Cohoon and S. Sahni, Heuristics for the board permutation problem, lProceedings 1983 iC CAD Conference, Sept 1983.
• COHO83b: James Cohoon , Sartaj Sahni, Heuristics for the Circuit Realization Problem, Proceedings of the 20th conference on Design automation, p.560-566, June 27-29, 1983, Miami Beach, Florida, United States
• GEMA83: D. Geman and S. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.
• GOLD84: B. Golden and C. Skiscim, Using simulated annealing ;o solve routing and location problems, University of Maryland, College of Business Administration, Technical Report, Jan. 1984.
• GOTO77: S. Goto, I. Cederbaum, and B.S. Ting, "Suboptimal Solution of the Backboard Ordering with Channel Capacity Constraint", IEEE Trans. Circuita and Systems, Nov. 1977, pp. 645-552.
• GREE84: J. Greene and K. Supowit, Simulated annealing without rejected moves, Proceedings ICCD, Oct. 1984, pp 65,8-663.
• JEPS83: D. Jepsen and C. Gelatt Jr., Macro placement by Monte Carlo annealing, Proceedings 1983 IC CAD Conference, Sept 1983, pp. 495-498.
• KANG83: Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
• KIRK83: S. Kirkpatrick, C. Gelatt, Jr., and M. Vecchi, Optimization by simulated annealing, Science, Vol 220, No 4598, May 1983, pp. 671-680.
• LIN73: S. Lin and B. Kernighan, An effective heuristic for the traveling salesman problem, Operations Research, Vol 21, pp. 498-516, 1973.
• LUND83: M. Lundy and A. Mees, Convergence of the annealing algorithm, University of Cambridge, 1983.
• METR53: N. Metropolis, A. Rosenbluth, A. Teller, and E. Teller, Equation of state calculations by fast computing machines, Jr. Chem. Phys., Vol 21, p. 1087, 1953.
• NAHA84: S. Nahar ,S. Sahni and E. Shragowitz ,Exper,- meats with simulated annealing, University of Minnesota,Minneapolis,~fechnical report ~ 84- 36,1984.
• RAGH84: R. Raghavan and S. Sahni, The complexity of single row routing, IEEE Trans. On Circuits and Systema, Vol GAS-31, No 5, May 1984, pp. 462-471.
• ROME84a: F. Romeo, A. Vincentelli, and C. Seehen, Research on simulated annealing at Berkeley, Proceedings ICCD, Oct. 1984, pp 652..857.
• ROME84b: F. Romeo and A. VincenteIli, Probabilistic hill climbing algorithms: Properties and applications, University of Californ!a, Berkeley, UCB/ERL M84/34, 1984.
• STEW77: W. Stewart, A computation ally efficient heuristic for the travelling salesman problem, Proceedings of the 13th Annual Meeting of Southeastern TIMS, Myrtle Beach, S.C., pp 75-83, 1977.
• TING78: B. Ting and E. Kuh, An approach to the routing of multilayer printed circuit boards, Proc~ {EEE Syrup. On Circuits and ~tstems, pp. 902-911, 1978.
• WHIT84: S. White, Concepts of scale in simulated annealing, Proceedings ICCD, Oct 1984, pp 646-651.
• VECC83: M. Vecchi and S. Kirkpatrick, Global wiring by simulated annealing, IEj~E Trans. On Computer Aided Design, Vol CAD-2, No 4, Oct. 1983, pp 215-222.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
Monte Carlo method, heuistic, optimization, simulated annealing