시뮬레이티드 어닐링이 알고리즘은 넓은 탐색 공간에서 특정 명제에 대한 최적의 솔루션을 찾는 데 사용되는 일반적인 확률적 알고리즘입니다.

원칙

열역학 이론을 통계에 적용하여 탐색 공간의 각 지점을 공기 중의 분자로 상상해보세요. 분자의 에너지는 분자 자체의 운동 에너지이다. 그리고 탐색 공간의 각 점은 공기 분자와 마찬가지로 명제에 대한 점의 적합성 정도를 나타내는 "에너지"를 가지고 있습니다.

알고리즘은 검색 공간의 임의의 지점에서 시작합니다. 각 단계에서 "이웃"을 선택한 다음 현재 위치에서 "이웃"에 도달할 확률을 계산합니다.

기본 요소

상태 공간 및 상태 생성 함수

1. 검색 공간은 상태 공간이라고도 불리며, 인코딩된 실행 가능한 솔루션의 집합으로 구성됩니다.

2. 상태 생성 함수(이웃 함수)는 생성된 후보 솔루션이 가능한 한 전체 솔루션 공간에 분산되도록 해야 합니다. 일반적으로 후보 솔루션을 생성하는 방법과 후보 솔루션의 확률 분포라는 두 부분으로 구성됩니다.

3. 후보 솔루션은 일반적으로 특정 확률 밀도 함수에 따라 솔루션 공간을 무작위로 샘플링하여 얻습니다.

4. 확률 분포는 균일 분포, 정규 분포, 지수 분포 등이 될 수 있습니다. 

상태 전이 확률

1. 상태 전이 확률은 한 상태에서 다른 상태로 전이할 확률을 말합니다.

2. 일반적으로 알려진 바는 새로운 해결책을 현재 해결책으로 받아들일 확률입니다.

3. 현재 온도 매개변수 T와 관련이 있으며 온도가 낮아질수록 감소합니다.

4. 대도시 기준이 일반적으로 채택됩니다.

내부 루프 종료 기준

1. 목적 함수의 평균이 안정적인지 확인하세요.

2. 목표 값은 여러 단계에 걸쳐 조금씩 변경됩니다.

3. 일정한 단계에 따른 샘플링.

외부 루프 종료 기준

1. 종료 온도 임계값을 설정합니다.

2. 외부 루프 반복 횟수를 설정합니다.

3. 알고리즘이 찾는 최적값은 여러 단계 연속으로 변경되지 않습니다.

4. 시스템 엔트로피가 안정적인지 확인하세요.

주요 단계

새로운 상태 생성 함수 → 새로운 상태 수용 함수 → 샘플링 안정성 기준 → 냉각 함수 → 어닐링 종료 기준

시뮬레이티드 어닐링의 장점

시뮬레이티드 어닐링 알고리즘은 문제에 대한 대략적인 최적해를 빠르게 찾을 수 있습니다. 적절한 매개변수 설정의 전제 하에, 시뮬레이트된 어닐링 알고리즘은 높은 검색 효율성을 갖습니다.

관련 단어: 최적화 알고리즘