Stochastic algorithms in discrete optimization with noisy values for the function

• Autorzy: Wieczorkowski Robert

Identyfikatory

DOI

10.14708/ma.v24i38.1839

Warianty tytułu

PL

Algorytmy stochastyczne w optymalizacji dyskretnej przy zaburzonych wartościach funkcji

• Języki publikacji: PL

Abstrakty

EN

The paper deals with stochastic methods for searching approximately global minimum of function defined on discrete set. A measure of quality of solution is defined to compare different algorithms. Simple Monte Carlo method is analysed as main algorithm for which formulas dealing with the measure of quality are derived(two cases: exact values and noisy values of function). This Monte Carlo method is used as a base in simulation experiments for comparing other stochastic algorithms. The second part of the paper analyses asymptotic properties of the generalised simulated annealing algorithms. Theory of Markov chains is used in modelling this class of algorithms. Theorems about convergence of the records of algorithms to set of optima with probability one are presented in the case of function having random noisy values. The paper also reviews known results in the field of simulated annealing type algorithms for function with randomly perturbated values.

Słowa kluczowe

EN

stochastic programming; mathematical programming; integer programming

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Matematyka Stosowana : matematyka dla społeczeństwa
• Rocznik: 1995
• Tom: Nr 38
• Strony: 119--153
• Opis fizyczny: Bibliogr. 27 poz., tab.

Twórcy

autor

Wieczorkowski Robert

• Instytut Matematyki Politechniki Warszawskiej, Plac Politechniki 1, 00-661 Warszawa

Bibliografia

• [1] [ANI87a] Anily, S., A. Federgruen, Simulated Annealing Methods With General Acceptance Probabilities, J. Appl. Prob. 24 (1987) 657-667.
• [2] [ANI87b] Anily, S., A. Federgruen, Ergodicity in Parametric Nonstationary Markov Chains: An Application To Simulated Annealing Methods, Operat. Res., Vol. 35, No. 6 (1987) 867-874.
• [3] [BON84] Bonomi, E., J. L. Lutton, The N-city Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm, SIAM Review 26 (1984) 551-568.
• [4] [CER85] Cerny, V., Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simidation Algorithm, J. Opt. Theory Appl., 45 (1985) 41-51.
• [5] [DUE90] Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing, Journal of Computational Physics 90 (1990) 161-175.
• [6] [FEL66] Feller, W., An introduction to probability theory and its applications, Vol. 1., Wiley, (1966).
• [7] [GEL89] Gelfand, S. B., Mitter, S. K., Simulated Annealing with Noisy or Imprecise Energy Measurements, J. Opt. Th. Appl., Vol. 62, No. l (1989), 49-62.
• [8] [GR084] Grotschel, M., Polyedrische Kombinatorik und Schnittebenenvenfahren (in German), Preprint No. 38, Universitat Augsburg (1984).
• [9] [HAR65] Harlamov, B. P., Ob odnom algoritmie stochasticzeskowo poiska maksimuma w determinowannom polie, Trudy Matem. Inst. im. Stieklova, LXXIX (1965).
• [10] [HAS70] Hastings, W., Monte Carlo Sampling Methods Using Markov Chains and Their Applications, Biometrika 57 (1970) 97-109.
• [11] [IOS80] Iosifescu, M., Finite Markov Processes and Their Applications, (1980), Wiley, (wyd. polskie: Iosifescu, M., Skończone procesy Markowa i ich zastosowania, PWN, Warszawa 1988).
• [12] [JMM88] American Journal of Mathematical and Management Sciences, vol. 8, NOS. 3 & 4 (1988).
• [13] [KIR82] Kirkpatrick, S., C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, IBM Research Report RC 9355 (1982).
• [14] [KIR83] Kirkpatrick, S., C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, 220 (1983) 671-680.
• [15] [KOR89] Koronacki, J., Aproksymacja stochastyczna: metody optymalizacji tu warunkach losowych, WNT, Warszawa 1989.
• [16] [LAA87] Laarhoven, P. J. M., E. H. Aarts, Simulated Annealing: Theory and Applications, Reidel (1987).
• [17] [LUN86] Lundy, M., A. Mees, Convergence of the Annealing Algorithm, Math. Programing 34 (1986) 111-124.
• [18] [MET53] Metropolis, N., A. Rosenblnth, M. Rosenbluth, A. Teller, E. Teller, Equation of State Calculations by Fast Computing Machines, J. Chem. Phys. 21 (1953) 1087-1092.
• [19] [SYS93] Sysło, M., Deo, N., Kowalik, J. S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal, PWN, Warszawa (1993).
• [20] [TSI89] Tsitsiklis, J., Markov Chains with Rare Transitions and Simulated Annealing, Math. of Oper. Res., Vol. 14 (1989), 70-90.
• [21] [VOL82] Volgenant, T., Jonker, R., A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, Europ. J. Operat. Res. 9 (1982), 83-89.
• [22] [ZAM90] Zaman, A., Marsaglia, G., Toward a universal random number generator, St. & Prob. Letters, 8, 35-39, (1990).
• [23] [ZIE65] Zieliński, R., On the Monte-Carlo Evaluation of the Exstremal Value of a Function, Algorytmy II, 4 (1965), 7-13.
• [24] [ZIE79] Zieliński, R., Generatory liczb losowych, WNT, Warszawa. (1979).
• [25] [ZIE80] Zieliński, R., Global Stochastic Approximation: a Review of Results and Some Open Problems, in: Numerical Techniques for Stochastic Systems, (1980), Amsterdam, North Holland.
• [26] [ZIE92] Zieliński, R., Records of Simulated Annealing, in: Model-Oriented Data. Analysis, Physica-Verlag (1993).
• [27] [ZIN86] Zieliński, R., Neumann, P., Stochastyczne metody poszukiwania minimum funkcji, WNT, Warszawa (1986).