๋น ๋ฅธ ์ฐ์ฐ์ ์ธ๋ฅ์ ์ด๋กญ๋ค
์๊ฐ๊ฐ ์์ฑํ ์ฅ์์์ ๋ด์ฐ๋ฆฌ๋ฅผ ์ฐพ๋๋ค. ๊ฐ์ฅ ๋ปํ ์ ๋ต์, ๊ฐ์๊ฑฐ๋ฆฌ์์ ํ์ธํ ์ ์๋ ์ค๋ฅด๋ง๊ธธ์ ์ฐพ๋ ๊ฒ์ด๋ค.(Hill Climbing ์ ๋ต์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค) ๋ง์ฝ ์ฃผ๋ณ์ ๋๋ฌ๋ดค์ ๋ ๋ชจ๋ ๊ธธ์ด ๋ด๋ฆฌ๋ง์ด๋ผ๋ฉด, ์ฐ๋ฆฌ๋ ๋ด์ฐ๋ฆฌ์ ๋๋ฌํ ๊ฒ์ด๋ค.
๊ทธ๋ฌ๋ ๋ด๊ฐ ์ฐพ์ ๊ทธ ๋ด์ฐ๋ฆฌ๊ฐ, ์ ์ฒด์์ ์ ์ผ ๋์ ๋ด์ฐ๋ฆฌ์ผ ํ๋ฅ ์ ๋ฎ๋ค. ์๊ฐ๊ฐ ๊ฑทํ๊ณ ๋ณด๋, ๋ด๊ฐ ์ค๋ฅธ ๋ด์ฐ๋ฆฌ๋ ์๋ฒ ๋ ์คํธ์ฐ ์ ๋ง์น ์๋ ์กฐ๊ทธ๋งํ ๋์ฐ์ผ ๋ฟ์ด์๋ค.
Hill Climbing์์์ Global Max์ Local Max
๊ณ์ฐํํ์ด๋ผ๋ ๋ถ์ผ๊ฐ ์๋ค. ์ปดํจํฐ๋ฅผ ํตํด ํํ๋ฐ์์ ๊ฐ์์ผ๋ก ์๋ฎฌ๋ ์ด์
ํ๋ ์ผ์ ๋งํ๋ค. ๋น์ธ๊ฑฐ๋ ์ํํ ํํ์คํ ๋ฑ๋ ์ปดํจํฐ์์์ ๊ฐ์์ผ๋ก ๋๋ฆด ์ ์๊ณ , ์ํ๋ ๊ฒฐ๊ณผ๊ฐ ๋์ค์ง ์์์ ๊ฒฝ์ฐ, ๋ณ์ธ๋ค์ ๋๋ฒ๊น
ํ๋ฏ ๋ค์ฌ๋ค๋ณผ ์ ์์ด์ ๋
ธ๋ฒจ ํํ ์๋ ๋ฐ์๋จ๋ค.
ํ ๋ฒ์ ๋ฏธ๊ตญ์์ ๋ถ์์ฉ ์๋ ๋ชจ๋ฅดํ(morphine)์ ์ฐพ์ผ๋ ค ํ๋ ์ผ์ด ์์๋ค. ์ด๋ ์๋ฎฌ๋ ์ด์
ํ ๋ถ์๊ฐ 300๋ง ๊ฐ์ง๊ฐ ๋์๊ณ ์ ์ธ๊ณ ํํ์๋ค์ด ๋ค ๋ฌ๋ผ๋ถ์ด๋ ์ด๋ฒ ์ธ๊ธฐ ์์ ๋๋ด์ง ๋ชปํ์ ๋ถ๋์ด์๋ค.
์ด๋, ๊ณ์ฐํํ์ ํตํด, ์ปดํจํฐ๋ฅผ ์ด์ฉํ ๋ถ์ ์คํ์ ์ํํ์ฌ 300๋ง ๊ฐ์ง์ ๋ถ์ ์ค ๊ฐ๋ฅ์ฑ ์๋ 23๊ฐ์ ๋ถ์๋ฅผ ์ถ๋ ธ๊ณ ๋ง์นจ๋ด โPZM21โ์ด๋ผ๋ ๋ฌผ์ง์ ๋ฐ๊ฒฌํ๋ค.
์ค์ PZM21์ ๋ถ์๊ตฌ์กฐ๋ ๋ชจ๋ฅดํ๊ณผ์ ๊ณตํต์ ์ด ๋ณ๋ก ์์๊ณ , ๋ง์ฝ ๊ณ์ฐํํ์ ๋์ ์์ด ์ฌ๋์ด ์ผ์ผ์ด ๋
ธ๊ฐ๋ค๋ฅผ ํด์, ๋ชจ๋ฅดํ์์๋ถํฐ ์ถ๋ฐํ์ฌ ๋ถ์๊ตฌ์กฐ๋ฅผ ์กฐ๊ธ์ฉ ๋ฐ๊ฟ๊ฐ๋ ์์ผ๋ก Hill Climbingํ๋ค๋ฉด, ๊ฒฐ์ฝ ์ฐพ์๋ผ ์ ์์์ ๋ฌผ์ง์ด์๋ค๋ ๊ฒ์ด๋ค.
์ฐ๋ฑ์ฑ์ด์ ์๊ฐ๋ฅผ ๊ฑทํ๊ฒํ์ฌ ๊ณง๋ฐ๋ก ์ฒญ๋ช
ํ ์๋ฒ ๋ ์คํธ๋ฅผ ๋ฐ๋ผ๋ณผ ์ ์๊ฒํ ๊ฒ์ ์ญ์ ์ปดํจํฐ์ ๋์ ๋๋ถ์ด๋ค. ์ด์ฏค ๋๋ฉด ์ฐ์ฐ ์๋๋ ๋น ๋ฅด๊ธฐ๋ง์ ์๋ฏธํ์ง ์๋๋ค.
์์ฌ๋ฅผ ์ค๊ฐ๋ ๊ธด๊ธํ ์งํ์ ๊ฑธ๋ฆฐ ํ์์ ๋ณ์ ํน์ ์ง๋๋ฐ 1๋
์ด ๊ฑธ๋ฆฐ๋ค๋ฉด, ํด๋น ๊ฒ์ฌ๋ ์คํํ ์ ์๋ ๋ฐฉ๋ฒ์ด ๋๋ค. ๊ทธ๋ฌ๋ ๊ธฐ์ ๋ ฅ์ด ๋ฐ์ ํ์ฌ ๊ฒ์ฌ ๊ธฐ๊ฐ์ด 1์ฃผ์ผ๋ก ์ค์ด๋ค์๋ค๋ฉด, ํด๋น ๊ฒ์ฌ๋ ํด๋ณผ ๋งํ ๊ฒ์ฌ๊ฐ ๋๋ค. ๋จ์ํ ๊ฒ์ฌ์ ์๋๊ฐ ๋นจ๋ผ์ก๋ค๊ฐ ์๋๋ผ, ๊ฒ์ฌ๊ฐ โ๊ฐ๋ฅํด์ก๋คโ์ ๋ฌธ์ ๋ผ๋ ๊ฒ์ด๋ค.
์ ๋ง๋ก ๋น ๋ฅธ ์ฐ์ฐ์ ์ธ๋ฅ์ ๋์์ด๋๋ค.ย
GPGPU๋ฅผ ๋ฐฐ์ฐ๊ณ ์ตํ๊ฐ ์๋ก, ๋์ ์์ ํ์ด ์ธ์์ ๋ณดํฌ์ด ๋ ์ ์๊ฒ ๋ค๋ ํฌ๋ง์ ๊ฐ๊ฒ ๋๋ค. ๋์ ๋ฐฐ์์ด ๋ณด๋ค ๋ง์ ์ฌ๋๋ค์ ํ๋ณตํ๊ฒ ํ์ผ๋ฉด ์ข๊ฒ ๋ค. ๊ทธ๋ฐ ์ฌ๋์ด ๋๊ณ ์ถ๋ค.ย