메타휴리스틱을 이용한 최적화(Simulated Annealing)

소개

대학생과 대학원과정에서 최적화관련한 여러 강의가 있습니다. 본 리포트는 최적화에서 휴리스틱한 방법중 Simulated Annealing에 대한 세부 알고리즘과 프로그램 개발을 위해서 어떻게 해야 할지에 대해 상세하게 설명해놓은 자료입니다. 이 조사보고서를 참고하면 SA대해 프로그램 개발수준까지 할 수 있을 것으로 생각됩니다.

목차

1. 최적화란?
2. Simulated Annealing개념
2.1 SA 정의
2.2 SA 알고리즘 아이디어
3. Simulated Annealing 알고리즘
3.1 기본아이디어
3.2 온도개념의 역할
3.3 SA와 국소탐색방법의 차이
3.4 비개선해의 채택방법
4. SA Pseudo-Code
4.1 변수
4.2 함수설명
5. SA를 이용한 최적해 탐색과정
5.1 신규해 갱신여부 결정함수
5.2 최적해 탐색 과정
5.3 개선해 갱신여부 결정(dE가 0보다 큰 경우)
5.4 비개선해 갱신여부 결정(dE가 0보다 작은 경우)
5.5 최적화 문제에 근거한 dE함수의 정의
6. 상수K
7. 온도감소
8. SA의 활용분야
9. SA적용시 주의사항
10. SA개발
10.1 알고리즘 구상
10.2 탐색영역 선정
10.3 온도감소

본문내용

1. 최적화란?
최적화란 주어진 제약조건하에서 달성하고자 하는 목표를 이루기 위한 의사결정 문제를 모형으로 정형화하고 이에 대한 해를 구하기 위한 방법론으로 시스템의 최적화(최대의 이익, 최소의 비용, 고객서비스의 최대화, 최적의 선택)를 대상으로 하고 있다.
 구체적인 적용분야
- 제조 : 스케줄링 및 재고관리, 기계설비배치, 생산공정관리, 설계최적화 등
- 유통 : 유통망설계, 물류센터 위치선정, 운송노선결정, 수송계획 결정 등
- 통신 : 통신망설계, 통신망경로설정, 기지국 위치선정 등
- 공공 : 도시건설, 도로건설, 교통시스템 수립, 상하수도 네트웍 설계 등
 모델링 방법
- Exact Method : 수리계획법(Mathematical Programming)
- 발견적 기법(Heuristic)
- Meta-Heuristic : Genetic Algorithm, Simulated Annealing, Tabu Search
- 탐색기법(Search) : Constraint Programming

2. Simulated Annealing개념
2.1 SA 정의
SA란 Simulated Annealing을 말한다. 여기서 Simulated 는 `가상의, 흉내낸, 모의의` 이런 뜻이고 Annealing이란 ‘풀림’이란 뜻이다.

2.2 SA 알고리즘 아이디어
일반적으로 금속을 달군 뒤에, 냉각하게 될 경우 어떤 조건(온도, 기압)에서 금속을 냉각시키는지에 따라서 해당 금속의 성질은 상이하게 달라진다. 따라서 자기가 원하는 스타일의 금속을 얻기 위해서는, 담금질에서 냉각 스케쥴이 매우 중요하다.
담금질에서 금속온도가 높을 때에는 원소들이 활발하게 움직이기 때문에 원소들이 제자리를 찾기 쉬워진다. 그러나 온도가 낮을 때에는 원소들의 움직임이 안정되기 때문에 원소들이 움직임이 둔화되고 안정된 상태의 결정상태가 되기 때문에 원소들의 랜덤한 이동이 어렵게 된다. SA란, 이러한 것들을 컴퓨터를 통해 흉내내어, 조합최적화 문제의 최적해를 얻고자 하는 방법이다. 담금질 과정에서 원소들의 움직임을 보다 쉽게 설명하면, 아래와 같은 사례를 들 수 있다.

참고자료

· 메타휴리스틱(김여근, 윤복식, 이상복 공저)