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.
In a typical implementation of the GD, the algorithm starts with a poor approximation,S, of the optimum solution. A numerical value called thebadness is computed based onS and it measures how undesirable the initial approximation is. The higher the value ofbadness the more undesirable is the approximate solution. Another numerical value called thetolerance is calculated based on a number of factors, often including the initial badness.
A new approximate solution S', called a neighbour ofS, is calculated based onS. The badness of S', b', is computed and compared with the tolerance. If b' is better than tolerance, then the algorithm is recursively restarted withS : = S', andtolerance :=decay(tolerance) wheredecay is a function that lowers the tolerance (representing a rise in water levels). If b' is worse than tolerance, a different neighbour S* ofS is chosen and the process repeated. If all the neighbours ofS produce approximate solutions beyondtolerance, then the algorithm is terminated andS is put forward as the best approximate solution obtained.
Gunter Dueck: "New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel", Technical report, IBM Germany, Heidelberg Scientific Center, 1990.
Gunter Dueck: "New Optimization Heuristics The Great Deluge Algorithm and the Record-to-Record Travel", Journal of Computational Physics, Volume 104, Issue 1, p. 86-92, 1993
