http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Great_deluge_algorithm 2026-05-15T04:18:11Z Revision history for this page on the wiki MediaWiki 1.43.1 http://debianws.lexgopc.com/wiki143/index.php?title=Great_deluge_algorithm&diff=3631939&oldid=prev 2022-10-24T03:59:45Z

<p><span class="autocomment">top</span></p> <p><b>New page</b></p><div>The &#039;&#039;&#039;Great deluge algorithm&#039;&#039;&#039; (&#039;&#039;&#039;GD&#039;&#039;&#039;) is a generic algorithm applied to [[Optimization (mathematics)|optimization]] problems. It is similar in many ways to the [[hill-climbing]] and [[simulated annealing]] algorithms.<br /> <br /> The name comes from the analogy that in a great deluge a person climbing a hill will try to move in any direction that does not get his/her feet wet in the hope of finding a way up as the water level rises.<br /> <br /> In a typical implementation of the GD, the algorithm starts with a poor approximation, &#039;&#039;S&#039;&#039;, of the optimum solution. A numerical value called the &#039;&#039;badness&#039;&#039; is computed based on &#039;&#039;S&#039;&#039; and it measures how undesirable the initial approximation is. The higher the value of &#039;&#039;badness&#039;&#039; the more undesirable is the approximate solution. Another numerical value called the &#039;&#039;tolerance&#039;&#039; is calculated based on a number of factors, often including the initial badness.<br /> <br /> A new approximate solution &#039;&#039; S&#039; &#039;&#039;, called a neighbour of &#039;&#039;S&#039;&#039;, is calculated based on &#039;&#039;S&#039;&#039;. The badness of &#039;&#039; S&#039; &#039;&#039;, &#039;&#039; b&#039; &#039;&#039;, is computed and compared with the tolerance. If &#039;&#039; b&#039; &#039;&#039; is better than tolerance, then the algorithm is recursively restarted with &#039;&#039;S&#039;&#039; : = &#039;&#039; S&#039; &#039;&#039;, and &#039;&#039;tolerance&#039;&#039; := &#039;&#039;decay(tolerance)&#039;&#039; where &#039;&#039;decay&#039;&#039; is a function that lowers the tolerance (representing a rise in water levels). If &#039;&#039; b&#039; &#039;&#039; is worse than tolerance, a different neighbour &#039;&#039; S* &#039;&#039; of &#039;&#039;S&#039;&#039; is chosen and the process repeated. If all the neighbours of &#039;&#039;S&#039;&#039; produce approximate solutions beyond &#039;&#039;tolerance&#039;&#039;, then the algorithm is terminated and &#039;&#039;S&#039;&#039; is put forward as the best approximate solution obtained.<br /> <br /> ==See also==<br /> * [[:de:Gunter Dueck|de:Gunter Dueck]]<br /> <br /> ==References==<br /> * Gunter Dueck: &quot;New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel&quot;, Technical report, IBM Germany, Heidelberg Scientific Center, 1990.<br /> * Gunter Dueck: &quot;New Optimization Heuristics The Great Deluge Algorithm and the Record-to-Record Travel&quot;, Journal of Computational Physics, Volume 104, Issue 1, p. 86-92, 1993<br /> <br /> [[Category:Optimization algorithms and methods]]<br /> <br /> <br /> {{Optimization algorithms}}</div>

imported>Tony1