๐ Ant Algorithms - ๊ฐ๋ฏธ ์๊ณ ๋ฆฌ๋ฌ
7, 8์ฐจ์
๐ซ Ant Algorithms - ๊ฐ๋ฏธ ์๊ณ ๋ฆฌ๋ฌ
Ant Algorithm - ๊ฐ๋ฏธ ์๊ณ ๋ฆฌ๋ฌ
๊ฐ๋ฏธ์ Stigmergy
- ๊ฐ๋ฏธ๋ค์ ์ํต๋ฐฉ๋ฒ(๋์/ํ๋ก๋ชฌ์ ์ด์ฉํ)
โ ๊ฐ๋ฏธ๋ ๊ฐ๋ ๊ธธ๋ง๋ค ํ๋ก๋ชฌ์ ๋ฟ๋ฆผ (Like ํจ์ ค๊ณผ ๊ทธ๋ ํ
)
โ ๊ฐ๋ฏธ๋ ํ๋ก๋ชฌ์ด ๋ง์ ์ชฝ์ ๋ฐ๋ผ๊ฐ
โ ์ ๋ต์ธ์ง๋ ๋ชจ๋ฅด์ง๋ง ์ต์ ๊ฒฝ๋ก์ ๊ฐ๊น์ธ์๋ก (์งง์ ์๋ก) ๋ ๋ง์ด ์๋ค๊ฐ๋ค ํ ์ ์์
โ ์ต์ข
์ ์ผ๋ก ๊ฐ์ฅ ๋ง์ ๊ฐ๋ฏธ๋ค์ด ๋ค๋๋ ๊ฒฝ๋ก = ์ต์ ๊ฒฝ๋ก
Nest, Food, Obstacle
๊ฐ๋ฏธ๋ Network์ ๋ฐ๋ผ ์ด๋, ๋์๊ฐ ๊ฐํ ์ชฝ์ผ๋ก ์ด๋
์ปดํจํฐ ๊ฐ๋ฏธ๋ ๋์๋ฅผ ์์ผ๋ก ๋งก์
(๊ฐ์ ์๋ฃ์ ์๋ ์์ ์ค๋ฅ๊ฐ ๋ง์)
์ต์ ์ ๊ธธ์ ์ฐพ์๋ด๋
๋ณํ์๋ ๊ธ๋ฐฉ ์ ์ํ๋
Traveling Salesman Problem - TSP
= ํด๋ฐํด ํจํด, ๋ชจ๋ ์ ์ ์ ์ค๋ณต์์ด ํ ๋ฒ์ฉ๋ง ๋ฐฉ๋ฌธ
๊ฐ๋ฏธ ๊ตฐ์ง ์ต์ ํ ACO - ์ฐธ๊ณ
@ U ์ค๊ฐ๊ณ ์ฌ ์ถ์ :
์ธ๊ณต ๊ฐ๋ฏธ ์ง๋จ์ ์๊ฐ ๋ณํ์ ๋ฐ๋ฅธ Behavior-ํํ๋ฅผ ๋ํ๋ธ ๊ทธ๋ฆผ 3์ฅ
๊ฐ๊ฐ ์ด๋ค ์๋ฆฌ์ ์ํด ์ด๋ค ์ผ์ด ์ผ์ด๋๊ณ ์๋์ง (๊ทธ๋ฆผ ์ฌ์ด์ฌ์ด ์ผ์ด๋ ์ผ)
โ (Stigmergy)-ํ๋ก๋ชฌ์ ๋จ๊ธฐ๋ฉด์ ์๋ก ์ํต ~
โ ํ๋ก๋ชฌ์ ์ํด ์๋ชป๋ ๊ฒฝ๋ก๋ฅผ ๋ง๋ค๊ธฐ๋ ํ์ง๋ง, ํ๋ก๋ชฌ์ ์ํด ๊ฒฐ๊ตญ ์ต์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์๋ธ๋ค
โ ์ด๋ค ์กฐ๊ฑด์์๋ ์ต์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์๋ธ๋ค
(๊ฐ๋ฏธ ์๊ณ ๋ฆฌ๋ฌ)-์ด ์๋ฆฌ๋ฅผ ์ด๋ป๊ฒ ์์ฉํ ์ ์๋์ง
โ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ~
๐ซ ์
ฯ - ์ด๋งค๊ฐ๋ณ์, (์ผ๋จ) ๋ฌด์ํด๋ ๋๋
ฮฑ - ํ๋ก๋ชฌ ์ง์, ฮฒ - ๊ฑฐ๋ฆฌ ์ง์
โ ์ด๋ค ๊ฑธ ๋ ์ค์ฌ์ ์ผ๋ก ์๊ฐํ๋๋์ ๋ฐ๋ผ ์กฐ์
ํ๊ฒ ๊ฒฝ์ฐ์ ๊ฐ / ํ์ฌ ์์น์์ ๊ฐ ์ ์๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์ ๊ฐ ํฉ
ฯ(r, u) - r, u ์ฌ์ด ํ๋ก๋ชฌ ์
ฮท(r, u) - r, u ์ฌ์ด ๊ฑฐ๋ฆฌ
๋ง์ฝ ํ๋ก๋ชฌ ์์ด ๋๊ฐ๋ค๋ฉด, ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ์ชฝ์ผ๋ก
(๋๋ฌธ์ ๊ฑฐ๋ฆฌ๋ ์ญ์ ๋ชจ์)