algoritmo del gran diluvio

El algoritmo del Gran Diluvio ( GD ) es un algoritmo genérico aplicado a problemas de optimización . Es similar en muchos aspectos a los algoritmos de ascenso de colinas y recocido simulado .

El nombre proviene de la analogía de que, durante 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 forma 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 índice de indeseabilidad , basado en S , que mide cuán indeseable es la aproximación inicial. Cuanto mayor sea el valor de este índice, más indeseable será la solución aproximada. Se calcula otro valor numérico, denominado tolerancia , en función de diversos factores, entre los que suele incluirse el índice de indeseabilidad inicial.

Se calcula una nueva solución aproximada S' , denominada vecina de S , a partir de S. Se calcula la mala calidad de S' , b' , y se compara con la tolerancia. Si b' es mejor que la tolerancia, el algoritmo se reinicia recursivamente con S  := S' y tolerancia  := decaimiento(tolerancia) , donde decaimiento es una función que reduce la tolerancia (representando un aumento en los niveles de agua). Si b' es peor que la tolerancia, se elige una vecina diferente S* de S y se repite el proceso. Si todas las vecinas de S producen soluciones aproximadas que superan la tolerancia , el algoritmo finaliza y S se presenta como la mejor solución aproximada obtenida.

• de:Gunter Dueck

• Gunter Dueck: "Nuevas heurísticas de optimización: el algoritmo del gran diluvio y el viaje de registro a registro", Informe técnico, IBM Alemania, Centro Científico de Heidelberg, 1990.
• Gunter Dueck: "Nuevas heurísticas de optimización: El algoritmo del gran diluvio y el viaje de registro a registro", Journal of Computational Physics, volumen 104, número 1, págs. 86-92, 1993