El algoritmo del Gran Diluvio ( GD ) es un algoritmo genérico que se aplica a problemas de optimización . Es similar en muchos aspectos a los algoritmos de escalada de colinas y recocido simulado .
El nombre proviene de la analogía de que en un gran diluvio una persona que sube una colina intentará moverse en cualquier dirección que no le moje los pies con la esperanza de encontrar una manera de subir a medida que sube el nivel del agua.
En una implementación típica del GD, el algoritmo comienza con una aproximación deficiente, S , de la solución óptima. Se calcula un valor numérico denominado maldad en función de S y mide lo indeseable que es la aproximación inicial. Cuanto mayor sea el valor de maldad, más indeseable será la solución aproximada. Otro valor numérico denominado tolerancia se calcula en función de una serie de factores, que a menudo incluyen la maldad inicial.
Se calcula una nueva solución aproximada S' , llamada vecino de S , en base a S . Se calcula la maldad de S' , b' , y se compara con la tolerancia. Si b' es mejor que la tolerancia, entonces el algoritmo se reinicia recursivamente con S : = S' , y tolerancia := decaimiento(tolerancia) donde decaimiento es una función que reduce la tolerancia (lo que representa un aumento en los niveles de agua). Si b' es peor que la tolerancia, se elige un vecino diferente S* de S y se repite el proceso. Si todos los vecinos de S producen soluciones aproximadas más allá de la tolerancia , entonces se termina el algoritmo y se propone S como la mejor solución aproximada obtenida.