유전 알고리즘으로 진화하기
중학교 자유학기제
유전 알고리즘
STEAM
진화란 무엇일까요 ?
학습 목표
유전 알고리즘의 원리를 이해하고 ,
이를 응용하여 사람의 모습을 구현해 봅시다 .
STEAM
생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적의 값을 찾아내는 검색 방법
유전 알고리즘
STEAM
숫자카드 놀이하기
{1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3 개를 골라서 20 으로 만들어라 .
각 숫자 카드는 유전자로 가정한다 . 세 개의 카드를 뽑아 그 합을 구한 뒤 20 이 되는지 확인한다 .
●
●●
●
●●
●●
●●
●●
●●●
●●
●●●
●
●
●
●●
●●●
●●
●
●
●
●●
●
●●
●●●
●●●
●●●
STEAM
숫자카드 놀이하기
1 단계 [ 무작위 생성하기 ] : 숫자 세 개를 뽑아 4 개의 조합을 만들고 , 각각의 적합도를 구하세요 .
만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 각각 카드를 뽑았다고 하자 . 각각의 적합도를 구하 면 , { 11, 3, 6, 5 } 이 되며 , 이 값이 높을수록 20 에서 멀기 때문에 해로서 부적당하다는 것을 의 미하며 , 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다 .
●
●●
●
●●
●
●
●
1+5+3=9 20-9=11 적합도 : 11
●●●
●●
●●●
●●●
●●●
●●●
8+0+9=17 20-17=3 적합도 : 3
<
STEAM
숫자카드 놀이하기
2 단계 [ 선택하기 ] : 다음 세대를 만들기 위해 , 위에서 만든 세대의 개체 중 적합도가 높은 2 개의 유전자를 선택하세 요 .
이때 선택은 적합도가 높은 3 과 5 의 값 즉 , (8,0,9) 와 (3,7,5) 를 선택하고 나머지를 제거한다 .
(1,5,3) (8,0,9) (9,9,8)
(3,7,5)
STEAM
숫자카드 놀이하기
3 단계 [ 교배하기 ] : 교배위치를 무작위로 선택하고 , 숫자를 교환하여 적합도 값을 구하세요 .
선택된 2 개의 유전자의 유전체는 두 번째 자리를 서로 교환해서 새로운 세대가 형성된다 . 예로
(8,0,9), (3,7,5) 가 선택되었고 다음 세대의 개체는 (8,7,9), (3,0,5) 가 되며 , 각각의 적합도는 4, 12 가 된다 .
STEAM
4 단계 [ 돌연변이 만들기 ] : 자손 개체의 세 번째 자리에 무작위의 숫자를 넣어 적합도를 확인하세요 .
자손 개체 (8 ,7, 9). (3, 0, 5) 에서 세 번째 유전체 9 와 5 를 각각 무작위수로 뽑아 (8 ,7, 3). (3, 0, 9) 라는 돌연변이를 생성한다 .
●●●
●●
●●●
●
●
●
●●
●●●
●●
●
●
●
●●●
●●●
●●●
숫자카드 놀이하기
STEAM
1 단계 [ 무작위 생성하기 ] : 숫자 세 개를 뽑아 4 개의 조합을 만들고 , 각각의 적합도를 구하세요 .
2 단계 [ 선택하기 ] : 다음 세대를 만들기 위해 , 위에서 만든 세대의 개체 중 적합도가 높은 2 개의 유전자를 선택하세 요 .
3 단계 [ 교배하기 ] : 교배위치를 무작위로 선택하고 , 숫자를 교환하여 적합도 값을 구하세요 .
[ 돌연변이 만들기 ] : 선택한 개체 중 하나를 선택하여 무작위의 숫자를 넣어 적합도를 확인하세요 .
[2~3
단계 반복하기 ] : 선택하기과 교배하기 과정을 2 번 반복하세요 .숫자카드 놀이하기
STEAM
이러한 과정을 반복하면 어떻게 될 것이라고 생각하나요 ?
숫자카드 놀이하기
STEAM
유전 알고리즘의 적용
https://www.youtube.com/watch?v=Yr_nRnqeDp0&t=11 2s
‘ 유전 알고리즘으로 그네 타는 법을 학습시켰다‘
아래 사이트를 클릭하여 영상을 확인해보세요 .
STEAM
사람 모형 만들기
왼쪽과 같은 신체 부위를 가진 사람을 만들자 .
STEAM
사람 구현하기
1 단계 [ 무작위 생성하기 ]
- 5 명이 각각의 뽑기 상자에서 원 모양 , 직사각형 모양의 색종이 조각 12 개를 뽑는다 . - 뽑는 순서대로 위에서 아래로 , 왼쪽에서 오른쪽으로 각 신체 부위에 도형을 배치한다 .
STEAM
사람 구현하기
2 단계 [ 선택하기 ( 적자생존 )]
- 해당 신체 부위의 도형이 완성하고자 하는 도형과 일치하면 그 값을 1 씩 누적하여 적합도를 계산한다 . 신체 부위가 12 개이므로 12 가 되면 사람이 완성된다 .
- 5 명 중 만들고자 하는 사람의 모습과 가장 적합도가 높은 개체 2 개만 남기고 나머지 3 개의 개체 조각들 은
다시 상자 속에 넣는다 .
개체모양
적합도
6 4 8 2 5
선택 탈락 선택 탈락 탈락
STEAM
사람 구현하기
3 단계 [ 교배하기 ]
- 선택된 개체를 만든 사람을 제외한 나머지 사람 중 2 명은 선택된 개체의 상체를 교환한 형태의 자손을 만든다 .
STEAM
4 단계 [ 돌연변이 만들기 ]
- 나머지 한 사람은 4 개의 개체 중 무작위 ( 주사위 사용 ) 로 한 개체를 고른다 .
- 선택된 개체의 신체 부위 중 하나를 무작위 ( 주사위 2 개 사용 ) 로 골라 다른 모양으로 바꾼다 . - 적합도가 12 가 될 때까지 위의 과정을 반복한다 .
사람 구현하기
STEAM
① Travelling Salesman Problem(TSP, 순회외판원문제 )
https://www.youtube.com/watch?v=CrBHST9ZK80
유전 알고리즘 활용 예시
② 로봇 주행 성능 향상
https://www.youtube.com/watch?v=KHV7fWvnn_0
③ 모나리자 이미지 만들기
https://www.youtube.com/watch?v=rGt3iMAJVT8
④ 게임에서의 최적화 방법 찾기
https://www.youtube.com/watch?v=PHwMH28wFuM https://www.youtube.com/watch?v=yKN8IhIccVw
STEAM
유전 알고리즘을 적용하여 해결할 수 있는 문제에는 무엇이 있을지 생각하여 글로 작성해 보세요 .
유전 알고리즘으로 문제 해결하기
감사합니다 .
중학교 자유학기제
