담금질 기법: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 r2.6.4) (로봇이 바꿈: da:Simuleret udglødning |
편집 요약 없음 |
||
5번째 줄:
SA 알고리즘은 해를 반복해 개선함으로써, 현재의 해 근방에 있는 해를 임의로 찾는데, 그때에 주어진 함수의 값과 전역 인자 ''T'' (온도를 의미한다)가 영향을 준다. 그리고 앞에서 기술한 물리 과정과 비슷한 원리로. ''T''(온도)의 값은 서서히 작아진다. 따라서, 처음에는 ''T''가 크기 때문에 해가 크게 변화하지만, ''T''가 0에 가까워짐에 따라 변화가 줄어든다. 처음은 간단하게 비탈을 올라갈 수 있으므로, [[등산법]]으로 문제가 되는 [[지역 최적점]]에 빠졌을 때의 대책을 생각할 필요가 없다.
== 유사코드
아래
* P는 P=nk=5*100=500 이 되고 Step 이 500 이
* 담금질 기법의 원문을 자주 보거나 번역판을 보면 온도라는 말과 Frozen 즉 냉각이라는 말이 자주
begin<br />
Get an initial solution S; // s ← s0; e ← E(s) 초기값을
Get an initial temperature T>0; // 초기 온도값을 설정함, 예) T=1000<br />
while not yet "frozen" do // 최적의 경우를 찾을 때 까지 즉 온도가 완전히 내려 갈때 까지 프로그램을
<code><br />
for 1<= i <= P do // P=nk 즉 Step의 사이즈가 되고 k는 주어진 종류를 n은 우리가 결정하게
Pick a random neighbor S' of S; // 임의로 선택한 숄류션 S' 과 기존의 숄류션 S를
∆ <- cost(S')-cost(S); // 기존의 솔류션과 새로운 숄류션을 가격의 차 즉 최적화의 값의 차를 만듭니다.
// ∆ <- area(S')-area(S), 돌을 예를 들면 면적이 크기가 효율성의 차이
/* downhill move */
if ∆ <= 0 then S <- S' // S'의 값이 작으면 즉 차지하는 면적이 작고, 더 효율적으로 배치 되었으면,
// 이것이 현재까지의 최적화가 되고 이것을 온도가 내려간다. Downhill로
/* uphill move */
if ∆ > 0 then S <- S' // S'의 값이 크면 즉 차지하는 면적이 크고, 더 비 효율적으로 배치 되었으면, 이것을 온도가 올라간다.
// uphill로
</code><br />
T <-rT; // 한가지 경우의 수를 처리 했었므로 한 단계 줄어 들게 되면 다음 반복을
return S // 프로그램이 마무리 되면 우리가 찾는 최적화의 답을 리턴하고, 정확히 최적화의 답을 찾았으면 이것을 Global Optimization 즉 모든 경우의 수중에서 가장 최적화된
end<br />
* 여기서 원래의 SA(Generic Simulated Annealing Algorithm)은 여러가지 찾는 속도나 사용하는 메모리의 경우에 대하여 문제점이
▲* 여기서 원래의 SA(Generic Simulated Annealing Algorithm)은 여러가지 찾는 속도나 사용하는 메모리의 경우에 대하여 문제점이 있습니다. 그래서 여러 박사 과정의 분들이 새로운 기법을 추가하여 더욱 발전되 기법을 찾아 내었습니다. 하지만 이 아이디어 자체는 모든 분야에 대하여 적용이 가능합니다. 임의의 경우의 수가 많은 경우 정해진 조건에서 대용량의 최적화를 찾을 때 유용하게 사용이 됩니다.
[[분류:최적화 알고리즘]]
|