๐ Simulated Annealing - ๋ชจ์ ๋ด๊ธ์ง
3, 4์ฐจ์
@ ๊ฐ์์ค ์ด๋์ง ๋๋ฌด ํท๊ฐ๋ ค~
๐ซ Simulated Annealing - ๋ชจ์ ๋ด๊ธ์ง
Simulated Annealing - ๋ชจ์/์ ์ฌ ๋ด๊ธ์ง
์ต์ ํ โ ๊ฒ์ โ ๋ชจ์ ๋ด๊ธ์ง
๋ด๊ธ์ง :
๊ธ์์ ๊ฐ์ดํ๊ณ ๊ธ๋์์ผ ๊ฒฝ๋๋ฅผ ๋ํ๋ ์์
๊ณ ์ฒด โ ์ก์ฒด โ ๊ธฐ์ฒด
๊ณ ์ฒด โ ์ก์ฒด โ ๊ธฐ์ฒด
์์ โ ๋ถ์์ (๋ณํ ๊ฐ๋ฅํ)
0 - ์ง๊ธ๋ณด๋ค ๋ ๋์ ์ํ ์๊ตฌ
1 - ์ง๊ธ ๊ทธ๋๋ก๊ฐ ์๋๋ผ, ๋ณํ๊ฐ ์์ด์ผ
โ ๋ณํ๊ฐ ์ผ์ด๋๊ธฐ ์ฌ์ด ์ํ๋ก
2 - ๊ณ์ํด์ ๋ณํ๋ง ํ๋ฉด ์๋จ
โ ๋ค์ ์์ ํ ์ํ๋ก
๐ซ ๊ณผ์
์์์ ์กฐ๊ฑด/๊ฐ์ค์น ๊ณ์ฐ, ๊ฒฐ๊ณผ A
์์์ ๋ณํ, ์๋ก์ด ๊ฒฐ๊ณผ B
์ด์ ๊ฒฐ๊ณผ A ์ ์๋ก์ด ๊ฒฐ๊ณผ B ๋น๊ต
Loopํ์ฌ ๋ต์ ์ฐพ๋ ๊ฒ
์ง๊ธ๋ณด๋ค ์ข์ ์ํฉ๋ง
์ฐพ์
โ Greedy Algorithm - ๋งน๋ชฉ์ ์๊ณ ๋ฆฌ๋ฌ
โ Hill Climbing Algorithm
์ง๊ธ ์ํ๊ฐ ์ ๋ง ๊ฐ์ฅ ์ข์ ์ํ์ธ๊ฐ?
Local Max, Global Max
ํ์ฌ ์์น์์ ํ ๋ฐ์๊ตญ ์ฉ ์ฎ๊ฒจ์ ๋ ๋์ ๊ณณ์ผ๋ก ์ด๋
โ Hill Climbing Algorithm
๋ฌธ์
โ ํ๋ฉด์ด๋ Local M์ ๋ง๋๋ค๋ฉด?
โ ๊ณผ์ ํฉ
โ ์ฌ๋ฌ ๊ตฐ๋ฐ์์ ์์ํ๋ฉด ๋ ๊น?
์ ์ผ
์ข์ ๊ณณ์ ๊ฐ๊ธฐ์ํด์๋
์ข์ ๊ณณ๋ง ์ฐพ์ง ๋ง๊ณ , ์์ฌ์ ๋ฒ๋ฆฌ๊ณ ์๋๋ก ๋ด๋ ค๊ฐ์ผ ํ๋ค
โ ์ ์ฐฉ์ ๋ชปํจ
์ธ์ ์ ์ฐฉ ?
โ ์๊ฐ์ด ์ง๋ ์๋ก ์กฐ๊ฑด์ ๊น๋ค๋กญ๊ฒ
Sample Problem - N-Queen
์ด๊ธฐ soln๋ฅผ ๋์ถฉ ๋ง๋ค์ด๋๊ณ , soln๋ฅผ ํ๊ฐ
๋ต(์ต์ ์)์ ๋ชจ๋ฅด๋๊น ๋๊ฐ ์ด๋์ ๋ ์ข๋ค
ํต์ฌ ๋ ๊ฐ์ง
- ์ง๊ธ๋ณด๋ค ๋ ์ข์ง ์์ ์๋ฃจ์ ์ ์ฐพ์ ๊ฒฝ์ฐ์๋ ์ด์ ๊ฒ์ ๋ฒ๋ฆฌ๊ณ ๋์ ๊ฒ์ ๋ฐ์๋ค์ผ ์ ์๋ค๋ ๊ฒ
- ๋์ ๊ฒ์ ๋ฐ์ ๋ ์ฌ์ฌ๋ฅผ ํ๋๋ฐ ์ฌ์ฌ๊ธฐ์ค์ ์ฒ์์๋ ๋ฃจ์ฆํ๊ฒ(๋ง์ด ๋๋น ๋ OK), ์ ์ ๊น๋ค๋กญ๊ฒ(ํ์ ํ๋ฐ๋ถ์์๋ ํ์ฉ X)
๊ธฐ์ฒด/์ก์ฒด/๊ณ ์ฒด ์๋ณํ์์๋,
๊ทธ๊ฑธ ๋น์ ์ ์ผ๋ก ์ด์ผ๊ธฐ ํ ์ ์๋
Loss (์ฑ
์์๋ Energy)
ํ์ฌ ์ํฉ์ด ์ข์๊ฐ? ์ ๋ํ ๊ธฐ์ค
์ผ๋ง๋ ๋์๊ฐ (ํด์๋ก ๋์ ๊ฒ, ์๋์ง๊ฐ ๋์ ์๋ก ๋ณํ๊ฐ ๋ง์)
Loss๊ฐ ๋ฎ์์ผ ์ข์ ๊ฒ
๊ต์ฒด ํ๋ฅ (0 ~ 1) :
โ ๊ทธ๋ํ์์ Y์ถ
โ 1์ด๋ฉด ๋ฌด์กฐ๊ฑด ๋ฐ๊พธ๊ฒ ๋ค๋ ๊ฒ
Delta Energy - ํ๊ฐ ๊ฒฐ๊ณผ = ์๋์ง E
I.E. 0~20, N-Queen ๊ฒน์น๋ ๊ฒฝ๋ก ์
๊ต์ฒด ํ๋ฅ , ํ๊ฐ ๊ฒฐ๊ณผ ๊ทธ๋ํ์ ๋ํด,
โ ํ๊ฐ ๊ฒฐ๊ณผ๊ฐ ์์ ์๋ก ๊ต์ฒด ํ๋ฅ ์ด ํฌ๋ค
โ ํ๊ฐ ๊ฒฐ๊ณผ๊ฐ ์ต๋๊น์ง ๊ฐ๋๋ผ๋ ๊ต์ฒด ํ๋ฅ ์ด ์กด์ฌํ๊ธด ํ๋๋ฐ ์๋ค
โ ๋ ๋์ ์๋ก ๋ ๋ง์ ๊ธฐํ๋ฅผ
Temperature ์จ๋ (์์)
โ ์จ๋๊ฐ ๋๋ค = ์์ ๋จ๊ณ
โ ์จ๋๊ฐ ๋ฎ๋ค = ๋ ๋จ๊ณ
์์ฐ์์๋
โ ์จ๋๊ฐ ๋๋ค = ๋ฌด์ง์ํ๋ค (Like ๊ณ ์ฒด-์ก์ฒด-๊ธฐ์ฒด)
โ ์จ๋๋ฅผ ๋ฎ์ถ ์๋ก ์์ ์ ์ธ ์ํ๊ฐ ๋๋ค
ํ๊ฐ ๊ฒฐ๊ณผ๊ฐ ์ต๋๋๋ผ๋, ์จ๋๊ฐ ๋์ผ๋ฉด (์ฆ ์์ ๋จ๊ณ๋ฉด)
๊ต์ฒด ํ๋ฅ ์ด ๋๋ค
๊ฐ์ ์จ๋์์๋ (๋ค์๋งํด ์จ๋ ์๊ด์์ด๋)
ํ๊ณผ ๊ฒฐ๊ณผ๊ฐ ๋ฎ์์๋ก ๊ต์ฒด ํ๋ฅ ์ด ๋๋ค
@ U ์ค๊ฐ๊ณ ์ฌ ์ถ์ : ๋ ๊ฐ์ง (์กฐ๊ฑด, ์)์ ๊ฐ์ง๊ณ ๋ชจ์๋ด๊ธ์ง์ ์ค๋ช ํ์์ค. (๊ฐ๊ฐ ์จ๋ 50, 2 ~)
์์ฌ์์ด ์๊ณ ๋ฆฌ๋ฌ๊ณผ ๊ทธ ๋ฌธ์ ์
โ ์ข์ ์ํ๋ง ์ฐพ์, ๋ก์ปฌ Max์ ๋จธ๋ฌด๋ฅผ ์ ์๋ค
๋ฐ๋ฉด ๋ชจ์ ๋ด๊ธ์ง
โ ํต์ฌ์ ์จ๋(๋ถ์์ ์์น)๋ผ๋ ๊ฐ๋
์ ๋์
ํด์,
โ ํ์ ์ด๊ธฐ์๋ ํ์ฌ ์ํ๋ณด๋ค ๋ง์ด ๋์ ์ํ์ฌ๋ ์ฑํํ๋ ํ๋ฅ ์ ๋๊ฒ ์ค์ ํ๊ณ ,
โ ์๊ฐ์ด ์ง๋ ์๋ก ํ์ฌ ์ํ๋ณด๋ค ๋ง์ด ์ข์ ์ํ์ฌ๋ ์ฑํํ๋ ํ๋ฅ ์ ๋ฎ๊ฒ
โ (๋ถ์์ ํ ์จ๋ ์์ ์ํค๊ธฐ, ์ด๊ธฐ ๋๊ฒ ์ค์ ๋ ์จ๋๋ฅผ ์ ์ฐจ ๋ฎ์ถ๊ธฐ)