시뮬레이션 어닐링이란 무엇입니까?

시뮬레이션 어닐링은 문제에 대한 최적의 솔루션은 아니지만 최적의 솔루션을 찾을 수있는 컴퓨터 기술입니다. 그것은 소둔의 야금 과정을 모방하기 때문에 그렇게 명명되었습니다. 금속에서 어닐링은 금속을 가열 한 다음 천천히 냉각하여 정제하는 과정입니다. 컴퓨터 프로그램은 남아있는 모든 것이 최고 또는 거의 최상의 솔루션이 될 때까지 솔루션 공간을 "정제"합니다.

시뮬레이션 된 어닐링 프로그램의 사용자가 지정해야하는 두 가지 중요한 요소가 있습니다 : 시작 온도 또는 탐색 할 수있는 더 나쁜 솔루션의 백분율; 냉각 속도는 백분율이 감소하는 속도입니다. 낮은 시작 온도는 종종 결과가 최적에서 멀어지면서 종료됩니다. 매우 높은 온도에서 시작하면 검색에 필요한 시간보다 훨씬 많은 시간이 소요될 수 있습니다. 마찬가지로 냉각 속도가 너무 높으면 결과가 나 빠지고 냉각 속도가 매우 낮 으면 프로그램이 매우 오랫동안 실행됩니다.

시뮬레이션 된 어닐링 프로그램의 "고온"상태는 이미 발견 된 솔루션보다 더 많은 솔루션을 포함하여 광범위한 솔루션을 볼 수있는 설정입니다. 컴퓨터는 현재 솔루션보다 더 나쁜 많은 솔루션을 검토하여 최고보다 실질적으로 더 나쁜 로컬 최소값을 유지하지 않아도됩니다. 예를 들어 언덕이나 산 꼭대기에서 출발하여 기지에 도달하는 것을 상상할 수 있습니다. 길을 따라 갈매기 나 틈이있을 수 있습니다. 컴퓨터가 밖으로 나올만큼 충분히 오르막길을 벗어날 수 없다면, 컴퓨터가 바닥에 가까이 있지 않아도 컴퓨터가 멈추게됩니다.

프로그램이 얼마나 멀리 갈 수 있는지는 프로그램이 조사 할 수있는 더 나쁜 해결책의 비율에 의해 결정됩니다. 시간이 지남에 따라 점진적으로 더 나은 솔루션이 발견되고 틈새의 위험이 줄어 컴퓨터가 탐색 할 수있는 더 나쁜 솔루션의 비율이 줄어 듭니다. 이 비율을 줄이면 "냉각"이라고합니다. 온도가 0이 될 필요가없는 미리 설정된 비율에 도달하면 검색이 종료됩니다.

시뮬레이션 어닐링 또는 기타 인공 지능 검색 기술을 사용하는 이유는 최적에 가까운 솔루션을 찾는 데 필요한 시간을 관리 가능한 양으로 줄이기 때문입니다. 많은 문제의 경우, 가능한 모든 솔루션에 대해 가능한 각 솔루션을 테스트하는 철저한 검색에는 몇 개월 또는 몇 년이 걸릴 수 있습니다. 모의 어닐링에 대한 가장 널리 알려진 대안은 유전자 알고리즘입니다. 다른 인기있는 인공 지능 검색 알고리즘에는 개미 식민지 최적화, 입자 떼 최적화, 가장 가까운 이웃 및 베이지안 분류 기가 포함됩니다.