시뮬레이티드 어닐링(SA) 개요

목차

1. SA의 개요
2. SA의 성능을 올리기 위한 전략들
3. SA의 적용

본문내용

1. SA의 개요
1.1 서론
시뮬레이티드 어닐링은 조합 최적화 문제의 한 해법으로 기존의 반복적 개선에 근거한 발견적 기법들이 국부 최소점에 빠져 버리는 단점을 개선한 범용의 최적화 기법으로, 그 원리는 반복적 개선법을 기본으로 하되 비용증가의 이동을 확률적으로 허용하는 것으로, 기본 아이디어는 고체 물리학에서 에너지 수준이 가장 낮은 상태인 조직 결정 구조를 얻기 위해 이용하는 금속의 열처리 공정 중 하나인 어닐링(풀림)을 조합적 최적화 문제에 모사하는 것이었다.
어닐링(풀림)은 금속을 액체 상태가 될 때까지 가열한 후 온도를 서서히 낮추어 가장 안정된 고체결정상태의 금속을 얻는 과정으로, 액체 상태에서는 분자들이 자유롭게 이동하다가 온도를 내림에 따라 점점 일정한 구조로 조직이 배열하게 되고, 온도를 급격히 내리면 가변적 안정상태의 비정질의 조직이 얻어지게 된다.

<중 략>

1.2 주요 요소
(1) 초기화(Initialize)
알고리즘에 시작하는데 필요한 초기해 X와 컨트롤 파라미터 T, 내부 루프의 반복수 L을 결정해 주어야 한다. T는 결정 상태를 얻기 위한 어닐링 과정에서의 온도와 같은 역할을 하는 컨트롤 파라미터인데 초기값이 충분히 높을 필요가 있다. 그러나 적절한 초기치를 설정하는 효과적인 방법이 아직까지 확립되어 있지 않다. L은 주어진 온도에서 평행상태에 이를 때까지 무작위적인 입자들의 이동을 계속하게 하는 어닐링 과정에 해당하는 내부 루프의 반복수이며, 적정한 값을 설정하는 규칙이 확립되어 있지 않다. 초기해 X는 적어도 이론적으로는 알고리즘의 성능에 별 영향을 주지 않는다.

(2) 인접해 생성(Perturb)
현재의 해에 변동을 주어 새로운 인접해를 만드는 과정으로, 구체적인 문제의 특성에 따라 다르게 정해지는데 매우 많은 반복이 계속되므로 되도록 단순한 과정으로 만드는 것이 좋다. 이 과정은 알고리즘의 성능에 직접적인 영향을 미치므로 문제의 구조에 따라 효율적인 생성 방법을 찾아내는 노력이 요구된다.

참고자료

· Gidas(1985), Mitra et al.(1986), Hajek(1988).
· Johnson(1989, 1991), Van Larhoven and Aarts(1987).
· Saab and Rao(1991).
· Anily and Federgruen(1987).
· 조형수(2001), 다목적 혼합모델 조립라인의 투입순서 결정 방법 연구:시뮬레이티드 어닐링 접근법, 박사학위 청구 논문, 동의대학교 대학원.
· Aarts and Korst(1989).
· Johnson et al.(1989).
· Huang et al.(1986).
· Lee and Yee(1989).
· Aarts and Van Larhoven(1987).
· Johnson et al.(1989).
· Kirkpatrick et al.(1983).
· 이승환, 손소영(2001), 시뮬레이티드 어닐링을 이용한 레이 아웃의 수율 향상 기법, 대한산업공학회 공동학술대회 논문집, 847-850.
· 황인혁 외(2010), 시뮬레이티드 어닐링을 활용한 조선 소조립 라인 소일정계획 최적화, 한국시뮬레이션학회, Vol. 19. No.1, 73-82.
· 김주년, 김보관(2007), 시뮬레이티드 어닐을 이용한 신뢰도 최적 소자배치 연구, 대한전자공학회, 44(5), 42-49.
· 김경희, 홍순흠(2009),시뮬레이티드 어닐링을 이용한 선로용량배분 최적화 문제, 한국철도학회 학술발표대회논문집, 109-117.