Article
Full entry |
PDF
(1.8 MB)
Feedback
PDF
(1.8 MB)
Feedback
Keywords:
combinatorial optimization; Monte Carlo algorithm; suboptimal solutions; large combinatorial complexity; circular wheel balance optimization
combinatorial optimization; Monte Carlo algorithm; suboptimal solutions; large combinatorial complexity; circular wheel balance optimization
Summary:
The author investigates a Monte Carlo algorithm for finding suboptimal solutions for a wide clase of complicated optimization problems characterized by a large combinatorial complexity. This algorithm was applied to one specific problem: circular wheel balance optimization. The slow increase of the effort along with the increasing size of the problems and the generality of the method promise that the thermodynamically motivated optimization will become a very universal and effective optimization method.
References:
[1] V. Černý: A Therrnodynamical Approach to The Travelling Salesman Problem: An Efficient Simulation Algorithm. Report, Institute of Physics and Biophysics, Comenius University, Bratislava, 1982, to be published in Journal of Optimization Theory and Applications.
[2] S. Kirkpatrick S. D. Gelatt M. J. Vecchi: Optimization by Simulated Annealing:. Science, 220(1983), 671-680. MR 0702485
[3] C. Kittel: Thermal Physics. J. Wiley and Sons, New York, 1969.
[4] N. Metropolis A. Rosenbluth M. Rosenbluth A. Teller, E. Teller: Equation of state Calculations by Fast Computing Machines. J. Chem. Phys., 21 (1953), 1087-1092. DOI 10.1063/1.1699114
[5] R. E. Burkard, F. Rendl: A TherrnodynamicalIy Motivated Simulation Procedure for Combinatorial Optimization Problems. Report 83-12, Institut für Mathematik, Technische University, Graz, 1983.
[6] V. Černý: Multiprocessor System as a Statistical Ensemble: a Way Towards General-purpose Parallel Processing and MIND Computers?. Report, Institut of Physics and Biophysics, Comenius University, Bratislava, 1983.
[7] S. Lin, B. W. Kernighan: An Effective Heuristic Algorithm for The Travelling Salesman Problem. Opns. Res., 21 (1973), 498-516. DOI 10.1287/opre.21.2.498 | MR 0359742
[8] A. Croes: A Method for Solving Travelling Salesman Problems. Opns. Res., 5 (1958), 791-812. DOI 10.1287/opre.6.6.791
Search
Partner of
