대홍수 알고리즘

GD(Great Delugge algorithm)는 최적화 문제에 적용되는 일반적인 알고리즘이다.그것은 여러 면에서 힐 클라이밍 및 시뮬레이션 어닐링 알고리즘과 유사하다.

엄청난 홍수 속에서 언덕을 오르는 사람은 수위가 올라갈수록 올라갈 길을 찾고자 하는 바람으로 발이 젖지 않는 어떤 방향으로든 움직이려 할 것이라는 비유에서 유래한 이름이다.

GD의 일반적인 구현에서 알고리즘은 최적 용액의 낮은 근사치 S로 시작한다.Badness라는 수치 값은 S를 기반으로 계산되며 초기 근사치가 얼마나 바람직하지 않은지를 측정한다.나쁜 점의 값이 높을수록 대략적인 해결책이 바람직하지 않다.공차라고 불리는 또 다른 수치 값은 종종 초기 불량성을 포함한 여러 요인에 기초하여 계산된다.

S의 이웃이라고 불리는 새로운 근사 용액 S'는 S에 근거하여 계산된다.S' , b' 의 불량성을 계산하여 허용오차와 비교한다.b'가 공차보다 나은 경우, 알고리즘은 S : = S' 와 공차 := 붕괴(tollance)로 재귀적으로 재시작된다. 여기서 붕괴는 공차를 낮추는 기능이다(수위 상승을 나타낸다).b'가 허용오차보다 심할 경우 S의 다른 인접 S*를 선택하고 과정을 반복한다.만약 S의 이웃들이 모두 허용오차를 넘어 근사치 해결책을 내놓는다면, 알고리즘은 종료되고 S는 얻어진 최선의 근사치 해결책으로 제시된다.

참고 항목

• 데:군터 라섹

참조

• Gunter Liltck: "새로운 최적화 경험치:"대홍수 알고리즘과 기록-기록 여행", 기술 보고서, IBM 독일 하이델베르크 과학 센터, 1990.
• Gunter Lilteck: "새로운 최적화 경험해석학 위대한 홍수 알고리즘과 기록-기록 이동", 제104권, 제1권, 페이지 86-92, 1993