Modification of simulated annealing method for solving combinatorial optimization problems

Boris S. Kiselyov; Nickolay Yu Kulakov; Andrei L. Mikaelian

doi:10.1117/12.983196

2 February 1993 Modification of simulated annealing method for solving combinatorial optimization problems

Boris S. Kiselyov, Nickolay Yu Kulakov, Andrei L. Mikaelian

Proceedings Volume 1773, Photonics for Computers, Neural Networks, and Memories; (1993) https://doi.org/10.1117/12.983196
Event: San Diego '92, 1992, San Diego, CA, United States

Abstract

Proposed is a modification of simulated annealing method to minimize the cost function in combinatorial optimization problems. The modification differs from the traditional method in that, first, a random fluctuation of the cost function feasible at the given effective temperature is evaluated, and then, a few random rearrangements of system elements are executed. Accepted are those rearrangements for which the real change in the cost function does not exceed this random fluctuation. As shown, the probability of finding an optimal or near-optimal solution is improved by increasing the number of rearrangements for one fluctuation, the annealing time being the same. The proposed method is more adapted to parallel computing devices.

Citation Download Citation

Boris S. Kiselyov, Nickolay Yu Kulakov, and Andrei L. Mikaelian "Modification of simulated annealing method for solving combinatorial optimization problems", Proc. SPIE 1773, Photonics for Computers, Neural Networks, and Memories, (2 February 1993); https://doi.org/10.1117/12.983196

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available