Алгоритм Великого потопа - Great Deluge algorithm

В Алгоритм Великого потопа (GD) - общий алгоритм, применяемый к оптимизация проблемы. Он во многом похож на скалолазание и имитация отжига алгоритмы.

Название происходит от аналогии с тем, что во время сильного наводнения человек, поднимающийся на холм, будет пытаться двигаться в любом направлении, чтобы не намочить ноги, в надежде найти путь вверх по мере повышения уровня воды.

В типичной реализации GD алгоритм начинается с плохой аппроксимации, S, оптимального решения. Числовое значение, называемое зло вычисляется на основе S и он измеряет, насколько нежелательно начальное приближение. Чем выше значение зло тем более нежелательным является приблизительное решение. Другое числовое значение, называемое толерантность рассчитывается на основе ряда факторов, часто включая исходную непригодность.

Новое приближенное решение S ' , назвал соседом S, рассчитывается на основе S. Плохое S ' , б ' , вычисляется и сравнивается с допуском. Если б ' лучше, чем допуск, то алгоритм рекурсивно перезапускается с S : = S ' , и толерантность := распад (терпимость) куда разлагаться - это функция, которая снижает допуск (представляя подъем уровня воды). Если б ' хуже терпимости, другой сосед S * из S выбирается, и процесс повторяется. Если все соседи S производить приблизительные решения сверх толерантность, то алгоритм завершается и S предлагается как наилучшее приближенное полученное решение.

Смотрите также

• de: Гюнтер Дук

Рекомендации

• Гюнтер Дук: «Новая эвристика оптимизации: алгоритм Великого потопа и переход от записи к записи», Технический отчет, IBM Германия, Научный центр Гейдельберга, 1990.
• Гюнтер Дук: «Новая эвристика оптимизации - алгоритм Великого потопа и переход от записи к записи», Журнал вычислительной физики, том 104, выпуск 1, с. 86-92, 1993