Отличный алгоритм потопа

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

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

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

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

См. также

• Автор: Гюнтер Дуек

Ссылки

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