๐ Genetic Algorithms - ์ ์ ์๊ณ ๋ฆฌ๋ฌ
N์ฐจ์
@ ์ฉ๋ถ์ฉ์ค
@ ๋ฃจ์นด LUCA
@ En~ : ~์ด ๋๊ฒ ํ๋ค
@ Takes Place : ๋ฐ์ํ๋ค
@ ์ ์ ์ ์๊ณ ๋ฆฌ๋ฌ (X, ์๋ชป๋ ํํ)
@ ๋ต์ ์ฐพ์์ผ ํ๋๋ฐ, ๋ต์ ๋ชจ๋ฆ
@ ๋ ์ข์ ์ํ๋ค์ ์์ด์ ๋ต์ ์ฐพ๊ฒ ๋ค๋ ๊ฒ
๐ซ Genetic Algorithms - ์ ์ ์๊ณ ๋ฆฌ๋ฌ
๊ณ์ฐ ๋ฌธ์ ํด๊ฒฐ์ ์ฐ๋
Simulated Evolution ๋ชจ์ ์งํ, ์งํ ํ๋ด
๋ฅผ ์์๋ณธ๋ค
์ ์ ์๊ณ ๋ฆฌ๋ฌ์ ํ์ ์๊ณ ๋ฆฌ๋ฌ
์ด๋ค
์ฃผ์ด์ง ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด
Encoded ์ํธํ๋ Candidate ํ๋ณด Solutions ์ Population ๋ชจ์ง๋จ
์์ ๋์ํ๋ ์๊ณ ๋ฆฌ๋ฌ์ด๋ค
๊ฐ๋จํ ์๊ณ ๋ฆฌ๋ฌ์
Sequence of Instructions ๋ช
๋ น์ด ์ด์ ์งํ์ํค๋ ์งํ์ ์ธ ๊ณ์ฐ์ ํตํด
์ ์ ์๊ณ ๋ฆฌ๋ฌ์ Use๋ฅผ Illustrate ๋ณด์ฌ์ค๋ค
โ Stack Machine
๐ซ Biological Inspiration
Phenomenon ํ์ of Natural Evolution๋ฅผ ํ๋ด๋ด๋
Optimization ์ต์ ํ ์๊ณ ๋ฆฌ๋ฌ์ด๋ค
์์ฐ ์งํ์ ์์ด์,
Species ์ข
์, ๋ณต์กํ ํ๊ฒฝ/์น์ดํ ๊ฒฝ์ ์์์ ์์กดํ๊ธฐ ์ํด
์ ์ํ๋ ๋ฐฉ๋ฒ์ Search ํ์ํ๋ค
ํ์, Chromosomes(์ผ์์ฒด, DNA)์์ ์ผ์ด๋๋ ๋ณํ์ ๊ทธ ํจ๊ณผ๋
์์กด๊ณผ Reproduction ์ฌ์์ฐ์ ๋ํ Graded ์ ์
๋ก ๋งค๊ฒจ์ง๋ค
Natural Selection ์์ฐ ์ ํ
~
๐ซ Genetic Algorithm High-Level Flow
@ U ์ค๊ฐ๊ณ ์ฌ ์ถ์ : 8-Queen ๋ฌธ์ ์ ์ ์ ์๊ณ ๋ฆฌ๋ฌ์ ์ ์ฉํ๋ ๊ณผ์
- Initialization
- ๋ฌธ์ ์ ์
- ์ธ์ฝ๋ฉ (์ปดํจํฐ๊ฐ ์ฒ๋ฆฌํ ์ ์๋ ํํ๋ก, ์๋ฃ๊ตฌ์กฐ ์ง์ ์๊ตฌ)
- ์ ํฉ๋ ํจ์ ๋์์ธ
- Evaluation
- ์ ํฉ๋ ๊ณ์ฐ (์ ํฉ๋ ํจ์ ์ฌ์ฉ)
- Selection
- ์ ํ ์ฐ์ฐ
- Recombination
- Generic Operation ์ ์ ์ฐ์ฐ
- Crossover ๊ต์ฐจ
- Mutation ๋์ฐ๋ณ์ด
- Generic Operation ์ ์ ์ฐ์ฐ
Initialization - ๋ฌธ์ ์ ์, ์ธ์ฝ๋ฉ, ์ ํฉ๋ ํจ์ ๋์์ธ
โ ์ฌ๋์ด ๊ด์ฌํ๋ ๋จ๊ณ
Evaluation - ์ ํฉ๋ ํ๊ฐ(๊ณ์ฐ) ๋จ๊ณ
โ .E. PPT ๋ผ๋ฉด ๋ง ์ฒ๋ 7, 10, 9, 5
Selection - ์ ํ ์ฐ์ฐ ๋จ๊ณ
โ ๋ชจ๋ ๋ง ์ฒ๋๋ฅผ ๋ํ๊ณ , ๊ทธ ๋น์จ์ ์ํ์ ํ์, (๋คํธ ๊ฒ์์ฒ๋ผ) ๋๋ค์ผ๋ก ์ ํ
โ ๋น์จ์ด ๋ฎ์ ์์๋ ๊ฝค ๋์ ํ๋ฅ ๋ก ์ ํ๋ ์ ์์ = ์์ฐ์ ํ
โ ์ข์ ๊ฒ๋ง ์ ํํ์ง ์์
Recombination - Genetic Operation ์ ์ ์ฐ์ฐ ๋จ๊ณ
โ Crossover ๊ต์ฐจ, Mutation ๋์ฐ๋ณ์ด
Crossover - ๊ต์ฐจ, ๋ถ๋ถ ๊ต์ฒด : ๋ถ๋ชจ ์ ์ ์ ์์ด๋ฏ
Mutation - ๋์ฐ๋ณ์ด : ์์ฃผ ๋๋ฌผ๊ฒ, ๋ถ๋ชจ์๊ฒ ์๋ ์ฑ์ง์ ์ฃผ๊ธฐ ์ํด
โ (๊ต์ฒด๋ณด๋ค ๋๋น ์ง ํ๋ฅ ์ด ๋์, ๊ต์ฒด๋ณด๋ค ๋น์จ์ ์ ๊ฒ)
@ ๋๋ถ๋ถ ๋๋น ์ง๋ ๊ฒฝ์ฐ๊ฐ ๋ง์๋ฐ,
@ ๊ณตํ์ (์ํ์ )์ธ ๋ฌธ์ ์ ๊ฒฝ์ฐ, ๋ชจ์ง๋จ์ ํ๊ท ์ ์๋ ๋์์ง
๐ซ In Example
MSG, ๊ณ๋, ํ, ๊น
๋ผ๋ฉด์ ์ฌ๋ฃ ๋ค์ด๊ฐ๋ ๊ฒฝ์ฐ์ ์
@ ์ค์ ๋ก๋ ์ฌ๋ฃ ์ข
๋ฅ๊ฐ ๋ง๊ฒ ์ฃ
โ 2^4 - 1 = 15
โ (์๋ฌด๊ฒ๋ ์๋ฃ๋ ๊ฒฝ์ฐ ์ ์ธ, 0000)
1 = 0001, 2 = 0010, 3 = 0011, โฆ
๋ ์ํผ Like DNA
๋ ์ํผ ๋ฒํธ๋ฅผ ํตํด ์ด๋ค ์ฌ๋ฃ๊ฐ ๋ค์ด๊ฐ์๋ ์ง ์ ์ ์์ (10์ง์ โ 2์ง์)
Initialization
โ ๋ฐ์ดํฐ๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ๋ง์ ํ๊ฐํ ์ ์๋ ํจ์ (์ ํฉ๋ ํจ์)
โ ๋ชจ์ง๋จ ๋ง๋ค๊ธฐ : ์์์ ๋ชจ์ง๋จ ์์ ์ (์ด๋งค๊ฐ๋ณ์)
Evaluation ์ ํฉ๋ ํ๊ฐ : ์ ํฉ๋ ํจ์ ๊ณ์ฐ ~
Selection ์ ํ ์ฐ์ฐ : ๋์ ๋ง๋~
Recombination - Genetic Operation ์ ์ ์ฐ์ฐ
โ ๊ต์ฐจ : ์ผ๋ฐ์ ์ผ๋ก ๋ชจ๋ ๊ต์ฐจ X, (70%? - ์ด๋งค๊ฐ๋ณ์)
โ ๋์ฐ๋ณ์ด : ์ผ์์ฒด ๋จ์๊ฐ ์๋๋ผ ์ ์ ์ ๋จ์๋ก, ์์ฃผ ๋๋ฌผ๊ฒ
๐ซ Sample Problem - Stack Machine
@ U ์ค๊ฐ๊ณ ์ฌ ์ถ์ : Stack Machine, ์ฃผ์ด์ง ๋ช ๋ น์ด์ ์คํ์ ๋ณด๊ณ , ์ต์ข ์ ์ผ๋ก ํ๋ก๊ทธ๋จ์ด ์ด๋ค ๋ฌธ์ ๋ฅผ ํธ๋์ง
์ซ์๊ฐ ์๋๋ผ ๊ธฐํธ๋ฅผ ๋ค๋ฃจ๋ ๋ฌธ์ ๋ฅผ ์ต์ ํํ๋ ๋ฌธ์ ๋ฅผ ๋ค๋ค๋ณด์
โ ๋ช
๋ น์ด๋ค์ ์ด
์คํ ๋จธ์ (in VM)
Zero-Address
- 0 DUP : A โ A A, Duplicate
- 1 SWAP : A B โ B A
- 2 MUL : 2 3 โ 6, Multiply
- 3 ADD : 2 3 โ 5
- 4 OVER : A B โ B A B, ์์์ ๋ ๋ฒ์งธ์ ์๋ ์์ DUP
- 5 NOP : No-Operation, Filler
Solution Encoding
๋ฌธ์ ์ ์๋ฃจ์
์ ์ธ์ฝ๋ฉ (๋ฌธ์ ์์ฒด๊ฐ ์๋๋ผ)
โ ๋ช
๋ น์ด (0 ~ 5)๋ฅผ ์ฐ์๋ ๋ฐ์ดํธ ๋ฌธ์์ด๋ก ํํ
Fitness Evaluation - ์ ํฉ๋ ํ๊ฐ
โ ์์์ ์คํ, ํ๋ก๊ทธ๋จ์ด Endํ๊ฑฐ๋ (Solve?), END ๋ช
๋ น์ ๋๋ฌํ ๋๊น์ง
โ ๊ทธ ๋ค์ ์ ํฉ๋ ๊ณ์ฐ (ํ์ฌ ์คํ ์ํ์ ๋ชฉ์ ํจ์ ๊ฒฐ๊ณผ ์ฐจ์ด)
Recombination - ์ฌ์์ฐ
โ Crossover ์ฐ์ฐ์, ํน์ ์ง์ ์์ ๋ถ๋ชจ์ ๊ผฌ๋ฆฌ๋ฅผ SWAP
โ Mutation ๋์ฐ๋ณ์ด, ๋ช
๋ น ๋๋ค ์ฌํ ๋น
I.E.
x^8 โ DUP MUL DUP MUL DUP MUL
DUP : x โ x x
MUL : โ x^2
DUP : โ x^2 x^2
MUL : โ x^4
DUP : โ x^4 x^4
MUL : โ x^8