{"entities":{"Q2784999":{"pageid":2795737,"ns":120,"title":"Item:Q2784999","lastrevid":42011278,"modified":"2025-05-22T10:18:07Z","type":"item","id":"Q2784999","labels":{"en":{"language":"en","value":"Optimization by stochastic methods."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1733212"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784999$235F56BC-E2C6-4416-8357-149FB5551E6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c9b7e9e5c9144c0c29bd6a92775d6344864d8040","datavalue":{"value":"1052.65057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784999$5595B908-089B-4E1E-9040-36785FEA9B8C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d6f630a8f9062cc7a61bf0b0d4072e8f242af2b3","datavalue":{"value":{"time":"+2001-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2784999$2A711F53-56F9-4ECF-9216-F70D373ECE21","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784999$05457FEC-E9E9-4120-A62F-F0511B528E59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784999$2DEAA492-C86C-40F6-804A-36E43ED56F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63aec181f5f25f527f4a50518ef030353abadcda","datavalue":{"value":"65C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784999$58F65525-5156-436D-8A1B-AA8440242A24","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8cb3e17e1ad70c7a92d30de6929af929c2f2ae77","datavalue":{"value":"1733212","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2784999$180D540A-6ED8-4DFF-AB47-A656E1AB2E44","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27024bc3112e6fbf1cca0a9a4aacb8e7e4a77e0","datavalue":{"value":"optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$19BE19DA-8D6B-4F55-BE95-3496B9E9FC9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a436fb5c6cfb50cd61ade11ffc71abe5c6c372ca","datavalue":{"value":"Markov chain analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$7527FEA2-BEB5-47AD-91C8-1B124B0ED5C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32fb5f5a2e257719b0e7ccf5f4882f6f6dea3d43","datavalue":{"value":"renewal theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$65FB82E4-46A9-4FF3-8E02-30A6CBE01FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"605eaf52a7d40b4ca440dd997a658542e33d5665","datavalue":{"value":"simulated annealing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$3D8DB998-73D9-44F7-A656-32C32B35C575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1586b1403da743d9fc2d533df2d60166e4702011","datavalue":{"value":"restarted algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$41FCDC90-59BD-4BA0-BDCA-40DFAF392544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cc0ad3c55443a29a29bf0e9227bbcaa54e90e68","datavalue":{"value":"evolutionary computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$1733851F-CBF3-4FDE-8217-EE01766710D0","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784999$BB49AB97-1455-4EC2-99FE-D7576E4DC83D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"146122627016c06d67fe509e27eb67db30f58e9b","datavalue":{"value":{"entity-type":"item","numeric-id":3457251,"id":"Q3457251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4eda2fde0ac6f323792caeec84154e3ed0575f9","datavalue":{"value":{"amount":"+0.8304348","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$39EC2BB9-52A1-4E9A-9CCA-9C391E259E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5915b5b2096eec1637796816b29c947627f5d385","datavalue":{"value":{"entity-type":"item","numeric-id":1200634,"id":"Q1200634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14b8052aa3c60b6fa0f39415d79ea63e322bdd59","datavalue":{"value":{"amount":"+0.8245438","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$3C685AB2-FE81-4C43-A30F-0A28F5155DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4e5ba6cf0c28b1f1198dab645e360a60e9daef3","datavalue":{"value":{"entity-type":"item","numeric-id":3792250,"id":"Q3792250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b586db50a2e9fbf1ca0379e03c0bf90ad3a76314","datavalue":{"value":{"amount":"+0.8231154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$0BB33526-485D-41DF-B795-2AF38061B50D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1f8f4b9b028068a52adb01ae0af02aaf64ccb11","datavalue":{"value":{"entity-type":"item","numeric-id":3694984,"id":"Q3694984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa5a9bfffbe704d1723d394194a264f9ba9fee97","datavalue":{"value":{"amount":"+0.8203441","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$F7940954-0819-47DA-B1E5-3B933DBE2AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e9990394bad5d1309bdc1653a086e34d18fa3aa","datavalue":{"value":{"entity-type":"item","numeric-id":1342098,"id":"Q1342098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c6b68f406af86eeeb78963b760121dd2d8f11ec","datavalue":{"value":{"amount":"+0.81794226","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$FAA11921-F692-4155-8DEB-14A58FF1BD66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96cfe5416428e18729559d2897d1a4c4e9b0abd3","datavalue":{"value":{"entity-type":"item","numeric-id":3412975,"id":"Q3412975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abac43f47704c6dc3a4c01b5e3aad92042e53d61","datavalue":{"value":{"amount":"+0.81483173","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$D0DBB572-0F40-4870-96C3-CAA26EA60701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e3a47d129abec72a2d00d1bb23f0a31f2cd50cf","datavalue":{"value":{"entity-type":"item","numeric-id":1176572,"id":"Q1176572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d19b4e4f8a63fa05d0b65fa612b3f6dd332f5713","datavalue":{"value":{"amount":"+0.8109123","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$1E84536F-B1B5-415C-8B35-1389565D00E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0901c595f32d7e2344a1c372adc2a164b386d3e","datavalue":{"value":{"entity-type":"item","numeric-id":4371596,"id":"Q4371596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fe6fe5a51eae4ef3d9ea7ccf62cb3ca8648b1a4","datavalue":{"value":{"amount":"+0.8041265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$8E192999-13B0-40EF-83A8-2BEECDEE9055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ba529e5181ee3d97d5ea9875e782d553856bdb4","datavalue":{"value":{"entity-type":"item","numeric-id":1571313,"id":"Q1571313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5325a0df7f2e8c148a17ca1ab599bc944223dc37","datavalue":{"value":{"amount":"+0.80078256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2784999$10B1E72D-0E4B-4E56-8A43-00CFEDC58032","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"982ce386644b44e2443777dc3ab2dfc9345b497a","datavalue":{"value":{"entity-type":"item","numeric-id":356043,"id":"Q356043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784999$2207BA11-B112-4A40-9ED7-ED3A93293F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"038c11d21f502a663b93834bf9d2adc3188d61a0","datavalue":{"value":{"entity-type":"item","numeric-id":1165197,"id":"Q1165197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784999$B5A9D21F-B5EE-49C1-9203-F4546ACEFC30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"132289e9174af4cd25aacfcf8dc59005b71025a6","datavalue":{"value":{"entity-type":"item","numeric-id":1972853,"id":"Q1972853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2784999$615C7B89-D5F2-498F-A603-8F630586CF32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"babf2baa0c6950b3cfe1966f7847626a156565ba","datavalue":{"value":{"text":"Optimization by stochastic methods.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2784999$69009F90-239F-4FC5-8F7C-9DFD59916992","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a45e3cdfab72dfe1d74ab2ab3ec2ffb81a546cb6","datavalue":{"value":"This interesting survey is about searching for the extremal values of an objective \\(f\\), defined on a domain \\(\\Omega\\), a large finite set, and equally important, for where these values occur. The methods used for the problem can be analyzed as finite Markov chains or as renewal processes. Continuous functions on a subset of Euclidean space can be analyzed in this framework as well, i.g. if they satisfy to Lipschitz condition. By an optimal value a globally optimal one is meant. For example, \\(f_*\\), \\(x_*\\) are the minimal value and the minimizer if \\(f(x_*)=f_*\\) and \\(f_* \\leq f(x)\\), \\(x \\in \\Omega\\). It's worth noting that \\(f\\) is always deterministic even though all considered methods could be applied to probabilistic objectives. The traveling salesman problem and the permanent problem are used to illustrate the effectiveness of methods. In the latter the permanent of 0/1 matrices is maximized, e.g. 14:40 permanent problem is to maximize the permanent of \\(14\\times 14\\) matrix with 40 arrangements of 1's and 156 arrangements of 0's.NEWLINENEWLINEAt the beginning of the survey some deterministic methods, e.g. covering methods, branch and bound, iterative improvement and trajectory/tunneling methods are discussed for comparison and suitable references are given. The survey of stochastic methods includes Markov chain and renewal theory consideration, simulated annealing, restarted algorithms and evolutionary computations.NEWLINENEWLINEIn the Markov chain analysis the explicit estimations of the expected hitting time to the goal subset \\(G \\subset \\Omega\\) and of some related probabilities are given. The superlinear speedup of parallel search according to \\textit{R. Azencott (ed.)} [Simulated annealing. Parallelization techniques. Chichester: John Wiley (1992; Zbl 0746.00020)] and \\textit{R.~Shonkwiler} and \\textit{E. Van Vleck} [J. Complexity 10, No.1, 64--95 (1994; Zbl 0798.90124)] is discussed. Restarted algorithms, especially effective for multi-modal problems, are considered in a framework of both Markov chain and renewal theories (see, e.g. \\textit{F. Schoen} [J. Global Optim. 1, 207--228 (1991; Zbl 0752.90071)]).NEWLINENEWLINEIn the Simulated Annealing (SA) the energy dependent on function \\(f\\) is assigned to each state of the chain. Transition probabilities depend on the difference of energies and the ``temperature'' \\(T\\) of the system. The idea of SA is that the system tends to the state with the minimal energy as \\(T_n \\to 0\\) according to some cooling schedule where \\(T_n\\) is the temperature on the \\(n\\)-th iteration of SA. The estimations of the effectiveness of cooling schedules are given according to \\textit{B. Hajek} [Math. Oper. Res. 13, No.2, 311--329 (1988; Zbl 0652.65050)] and \\textit{O. Catoni} [Ann. Probab. 20, No.3, 1109--1146 (1992; Zbl 0755.60021)].NEWLINENEWLINERestarted algorithms allow to reduce essentially the expected time for the goal searching, e.g. an example is discussed that an infinite expected time can be reduced to finite value by restarting. Numerous references are given. The estimations of effectiveness of restarted algorithms are represented according to \\textit{F. Mendivil, R. Shonkwiler} and \\textit{C. Spruill} [Restarted search algorithms with simulated annealing, preprint (1999)] and numerical comparisons of algorithms are considered.NEWLINENEWLINEEvolutionary computations include genetic algorithms and evolutionary strategies (see, e.g. \\textit{J. Holland} [Adaptation in Natural and Artificial Systems (Univ. of Michigan Press, Ann Arbor, MI) (1975; Zbl 0317.68006)] and \\textit{T. B\u00e4ck, F. Hoffmeister} and \\textit{H.-P. Schwefel} [A survey of evolution strategies, Proc. of the Fourth Internat. Conference of Genetic Algorithms (Morgan Kaufman, San Mateo, CA) (1991)]). A clear introduction to principles and special features of algorithms is given. Constrained optimization problem is considered in this section as well, e.g. on the base of penalty approach.NEWLINENEWLINEFor the entire collection see [Zbl 0979.00017].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2784999$211E7D62-5235-4CFB-872D-6F4C1F5F746D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2784999","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2784999"}}}}}