유전 알고리즘으로 진화하기

중학교 STEAM 교사용 교재

유전 알고리즘으로 진화하기

“이 교재는 2019년도 교육부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물임”

"This work was supported by the Korea Foundation for the Advancement of Science and Creativity(KOFAC) grant funded by the Korea government(MOE)"

차 례

프로그램 안내 및 사용방법 1

교육과정 연계 2

주제개요 3

STEAM 단계요소 4

평가계획 5

1차시 교수학습과정안 10

1차시 학생용 활동지 및 참고자료 14

2차시 교수학습과정안 21

2차시 학생용 활동지 및 참고자료 26

3차시 교수학습과정안 39

3차시 학생용 활동지 및 참고자료 43

부록 46

프로그램 안내

본 프로그램은 인공지능을 주제로 한 융합교육으로 학생들에게 과학, 수학, 기 술, 공학 그리고 인문학을 바탕으로 하여 창의적 문제해결력을 기를 수 있는 교수 학습과정으로 구성하였습니다.

인공지능 기술에 대한 기본적인 개념, 원리에 대한 이해뿐만이 아니라 이로 인 해 개인적, 사회적 차원에서 우리에게 미치는 긍정적인 부분과 부정적인 부분에 대해서도 함께 탐구하고 토론할 수 있도록 하였습니다. 빠른 기술의 발달이 우리 에게 미치는 영향을 살펴보고 이를 바탕으로 우리의 아이들이 살아나갈 미래의 모습을 구현하는데 바른 이해와 가치관을 정립시킬 수 있게 될 것입니다. 이러한 이해를 돕기 위해 진로와 연계한 읽을거리와 생각할 문제를 함께 제시하였습니다.

제안된 프로그램을 통해 인공지능이라는 주제의 적시교육을 실천하여 학생들이 겪어가야 할 실생활 문제를 고민해 보고, 창의적인 아이디어로 문제를 해결해 나 갈 수 있는 인재로 성장하기를 기대해 봅니다.

프로그램 사용방법

본 프로그램의 교재는 교사용과 학생용으로 나뉘어져 있습니다.

교사용은 학교현장에서 선생님들께서 손쉽게 사용하실 수 있도록 최대한 자세 하고 쉽게 안내하였습니다. 그리고 각 차시별로 교수・학습 과정안을 제시하고, 수업의 이해를 돕기 위하여 학습활동 장면을 추가하여 제시하였습니다. 또한 과정 안이나 수업 활동 내용에 유의점과 사용할 자료를 제시하여 수업 적용 시 어려움 이 없도록 안내하였습니다.

학생용은 중학생을 대상으로 하고 수업대체용 교수·학습 자료라는 점을 고려하

여 작성하였습니다.

교육과정 연계

관련교과 2015 개정 교육과정 연계 (내용 요소 및 성취수준)

과학

[9과03-01] 생물의 다양성을 이해하고, 변이의 관점에서 환경과 생물 양성의 관계를 설명 할 수 있다.

[9과21-04] 멘델 유전 실험의 의의와 원리를 이해하고, 원리가 적용되는 유전 현상을 조사 하여 발표할 수 있다.

[9과21-05] 사람의 유전 형질과 유전 연구 방법을 알고, 사람의 유전 현상을 가계도를 이 용하여 표현할 수 있다.

[9과07-01] 과학과 관련된 직업의 종류와 하는 일을 조사하고, 그 직업에 필요한 역량에 대해 토의할 수 있다.

[9과07-02] 현대 사회의 다양한 직업이 과학과 어떤 관련성이 있는지 예를 들어 설명하고, 미래 사회에서의 직업의 변화를 토의할 수 있다.

[9과24-01] 과학기술과 인류 문명의 관계를 이해하고 과학의 유용성에 대해 설명할 수 있다.

[9과24-02] 과학을 활용하여 우리 생활을 보다 편리하게 만드는 방안을 고안하고 그 유용 성에 대해 토론할 수 있다.

도덕

[9도02-05] 정보화 시대에 요구되는 도덕적 자세와 책임의 도덕적 근거와 이유를 제시하 고, 타인 존중의 태도를 통해 다양한 방식으로 의사소통할 수 있다.

[9도04-02] 과학 기술이 현대인의 삶에 미치는 긍정적인 영향과 가치를 설명하고, 동시에 과학 기술이 지닌 문제점과 한계를 열거하며, 과학 기술의 바람직한 활용 방안 을 제시할 수 있다.

정보

[9정03-03] 논리적인 문제 해결 절차인 알고리즘의 의미와 중요성을 이해하고 실생활 문 제의 해결 과정을 알고리즘으로 구상한다.

[9정03-04] 문제 해결을 위한 다양한 방법과 절차를 탐색하고 명확하게 표현한다.

기술·가정

[9기가04-18] 정보통신기술과 관련된 문제를 이해하고, 해결책을 창의적으로 탐색하고 실 현하며 평가한다.

[9기가05-01] 기술의 발달에 따른 사회, 가정, 직업의 변화를 이해하고 미래 기술 활용 및 사회의 변화에 대하여 예측한다.

[9기가05-09] 적정기술과 지속가능 발전의 의미를 이해하고 적정기술 체험 활동을 통하여 문제를 창의적으로 탐색하고 실현하고 평가한다.

주제개요

유전 알고리즘은 자연계의 생물 유전학에 기본 이론을 두며, 병렬적이고 전 역적인 탐색 알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 한다.

유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자 료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 여기에서 해들을 나타내는 자료구조는 유전자, 이들을 변형함으 로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다.

유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적 으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분 받아들일 수 있는 수 준의 해를 보여줄 수 있다.

본 수업에서는 이러한 유전 알고리즘의 원리와 개념을 간단한 놀이활동을 통해 이해하고자 하며 이를 통해 실제 생활 문제의 적용 사례와 해결할 수 있는 방법을 탐색할 수 있는 기회를 제공하고자 한다.

(참고: https://ko.wikipedia.org/wiki/유전_알고리즘)

유전 알고리즘으로

진화하기

STEAM 단계 요소 ²

1 상황 제시

유전 알고리즘을 적용한 이족보행 시뮬레이션을 보여주며 시뮬레이션 속 나무인형의 두 발로 걷기까지의 과정을 함께 살펴본다. 나무인형의 처음 걷는 모습과 마지막 걷는 모습의 차이를 보며 그 과정 안에서 어떠한 일이 일어났 는지를 함께 이야기를 나누며 호기심을 불러일으킨다.

2 창의적 설계

모둠을 이루어 사람의 모습을 직접 구현해보는 놀이 활동을 한다. 상자 속 에서 직사각형과 원 모양의 조각을 꺼내어 사람의 몸을 이룰 수 있는 부분에 매칭하며 사람의 몸에 가까운 모습을 완성하는 것이다. 유전자 알고리즘의 원 리인 무작위 생성하기, 선택하기, 교배하기, 돌연변이 만들기 단계로 진행하 며, 반복되는 과정을 통해 최적의 값을 찾는다.

3 감성적 체험

각 모둠에서 사람을 만들어가는 과정을 발표하며 힘들었던 점, 알게 된 점,

개선하고 싶은 점에 대한 생각들을 서로 공유한다. 또한 실제 유전자 알고리

즘의 적용 사례를 살펴보며 이를 응용할 수 있는 문제들에 대한 생각도 함께

이야기 나누어 본다.

평가계획 ³

○ 수행, 관찰 평가 기준표

평가영역 평가항목 도달 노력하여 도달 미도달

감성적 체험

집중과 끈기

과제에 대한 집중력이 좋으며 과제를 끈기 있 게 해결함

과제에 대한 집중력은 있으나 끈기가 부족함

과제에 대한 집중력과 끈기가 부족함

호기심과 자신감

새로운 내용을 배우고 싶어 하며 문제를 해결 할 때 어려워하지 않고 적극적으로 참여함

새로운 내용에 대해 약간의 흥미가 있으며 문제를 해결할 때 어 려워하지만 참여함

새로운 내용에 대해 흥미가 거의 없으며 문제를 해결할 때 어 려워하고 참여하지 않 음

창의성

문제를 해결하는 과정 에서 유창성, 융통성, 독창성, 정교성이 두드 러지게 나타남

문제를 해결하는 과정 에서 유창성, 융통성, 독창성, 정교성이 가 끔씩 나타남

문제를 해결하는 과정 에서 유창성, 융통성, 독창성, 정교성이 거 의 나타나지 않음

창의적 설계

해결방안 및 계획

유전 알고리즘의 단계 와 규칙 설계가 명확함

유전 알고리즘의 계획 과 규칙에 대한 이해 가 다소 부족하여 설 계가 미흡함

유전 알고리즘의 계획 과 규칙에 대한 이해 가 부족하여 설계를 세우지 못함

문제해결 과정 및 산출물 도출

유전 알고리즘의 단계 적용 과정이 명확하고 사람의 모습을 가장 가 깝게 구현해냄

유전 알고리즘의 단계 과정이 명확하지 못하 고 사람 모습의 구현 이 미흡함

유전 알고리즘의 단계 를 적용하지 못해 사 람 모습을 구현해내지 못함

총평

○ 수행, 관찰 평가 기록지

평가 영역

이름

감성적 체험 창의적 설계

집중과 총평 끈기

호기심과

자신감 창의성 해결방안 및 계획

문제해결 과정

산출물 도출

○ 면접기록지

면접기록지

면접대상 ( )학년 ( )반 이름 : 성별 :

일시 2019년 월 일 : ~ : 면접교사 면접계획

(면접 목적 면접 진행 계획 등)

· 유전 알고리즘 기술의 특징과 필요성에 대해 알고 있는가?

· 유전 알고리즘을 적용한 사람 모습의 구현 과정을 설명할 수 있는가?

· 유전 알고리즘을 적용하여 해결할 수 있는 문제의 예를 제시할 수 있는가?

면접 내용 (면접 과제 질문과 잡변

학생 특성)

· 유전 알고리즘의 기술의 특징과 필요성을 말할 수 있는가?

· 문제 해결을 위한 설계 과정과 사람 모습의 구현과정을 설명하는가?

· 유전 알고리즘을 적용하여 해결하고자 하는 문제를 창의적으로 제시하는가?

평가 결과

평 가 영 역

융합적 사고 창의적 설계 감성적 체험

교 사 총 평 면접 후 학생의

○ 구술 평가에 대한 평가 요소 체크리스트

요소

이름 융합적 사고 창의적 설계 감성적 체험 의사소통

○ 구술 평가 기준표

평가영역 평가기준 평가척도

상 중 하

융합적 사고

◆ 유전 알고리즘의 기술을 이해하고 있는가?

◆ 유전 알고리즘의 기술이 사람의 문제를 해결하는 데 도움 을 주는 것으로 이해하고 있는가?

◆ 컴퓨팅 사고의 과정이 나타나는가?

창의적 설계

◆ 유전 알고리즘을 적용하기 위한 단계와 규칙을 창의적으로 설계하였는가?

◆ 유전 알고리즘을 다른 문제 해결에 적용할 수 있는 방안을 생각해내는가?

감성적 체험

◆ 자신이 설계한 활동에 대해 자긍심을 갖고 있는가?

◆ 느낀 점 발표 시 타인의 의견을 경청하고 비판적으로 수용하는 태도를 지니고 있는가?

의사소통

◆ 자신의 경험을 바탕으로 논리적으로 발표 하는가?

◆ 경청 및 발표 태도는 바람직한가?

○ 학생 동료 평가 계획

평가

방법 평가영역 평가기준 평 가

상 중 하

자기 평가

감성적

체험 ◆ 즐거운 마음으로 활동에 참여하였는가?

창의적 설계

◆ 유전 알고리즘을 적용하기 위한 단계와 규칙을 창의적인 설계과정으로 이루어졌는가?

◆ 유전 알고리즘의 기술이 사람의 문제를 해결하는 데 도움을 주는 것으로 이해하고 있는가?

◆ 유전 알고리즘을 다른 문제 해결에 적용할 수 있는 방안 을 생각하기 위해 노력하였는가?

동료 평가

감성적 체험

◆ 모둠별로 역할 분담이 잘 되었으며 협동하고 배려하며 활 동이 이루어졌는가?

○ 학교생활기록부 기재 예시

교과 학교생활기록부 기재 예시자료 기재 상황 예시

정보

유전 알고리즘의 연산 과정을 이해하고, 이를 적용하여 주어진 문제 를 해결해냄. 또한 문제해결과정에서 필요로 하는 규칙을 모둠 친구 들과 협동하여 만들어 문제를 해결하는데 도움을 줌.

유전 알고리즘의 적용하여 해결할 수 있는 다양한 문제 사례를 창의 적으로 제시함

컴퓨터과학 기술의 원 리 이해 및 적용과정에 서의 모습과 모둠 활동 에서의 모습을 관찰하 여 기술하는 경우

동기유발에서는 매우 호기심 있어 하는 모습을 보였으나 단계별 활 동에서 이해가 좀 부족하여 힘들어하기는 하였지만 모둠 친구들과의 계속적인 의사소통을 통해 문제를 완수해냄

성장과정 중심으로 기 술하는 경우

1차시

1차시 ⁴ 프로그램 지도안

프로그램명 유전 알고리즘의 원리 이해하기 학교급 중학교 차시 1/3

학습목표 유전 알고리즘의 원리를 이해하고 이를 응용하여 숫자카드 놀이를 해본다.

학습자료 가위, 멀티미디어, 학습지, 교수용 ppt, 숫자카드

성취기준

과학

[9과03-01] 생물의 다양성을 이해하고, 변이의 관점에서 환경과 생물 양성의 관 계를 설명할 수 있다.

[9과21-04] 멘델 유전 실험의 의의와 원리를 이해하고, 원리가 적용되는 유전 현 상을 조사하여 발표할 수 있다.

[9과21-05] 사람의 유전 형질과 유전 연구 방법을 알고, 사람의 유전 현상을 가 계도를 이용하여 표현할 수 있다.

정보

[9정03-03] 논리적인 문제 해결 절차인 알고리즘의 의미와 중요성을 이해하고 실생활 문제의 해결 과정을 알고리즘으로 구상한다.

[9정03-04] 문제 해결을 위한 다양한 방법과 절차를 탐색하고 명확하게 표현한다.

흐 름 차시 교수·학습 내용 학습자료( )

유의점( )

상황 제시

1 차시

개별 학습

유전 알고리즘 시뮬레이터 영상 살펴보기

• 영상 보며 궁금한 점 이야기 나누기

- 영상 속에서 어떤 까만 색들이 살아남을 것 같나 요?

유전 알고리즘의 이 실행되는 과정을 보여 주는 시뮬레이션 영상

https://youtu.be/WZnf0

C8HfJc

모둠 학습

니다..)

- 까만색 점들이 어떤 속성을 물려주었나요?

(속도, 크기, 활동성 등을 물려주는 것 같습니다. ) - 세대가 반복 될 때 어떤 까만색 점만 선택하여 복

제하였나요?

(빨간색에 먹히지 않고 살아남은 점들만 선택하여 복제하였습니다.)

- 화면 속에서 마지막에 어떤 점들이 살아남았나요?

(안전지대를 벗어나지 않을 정도의 활동성과 크기 가 작은 점들만 살아남았습니다.)

- 이러한 과정은 과학시간에 배운 진화의 방법과 비 슷하다고 생각하나요?

(네, 적자생존, 살아남은 개체의 유전적 형질이 후 대에 전해진다는 점에서 비슷한 것 같습니다.)

• 학습목표 확인

- 유전 알고리즘의 원리를 이해하고, 이를 응용하여 사람의 모습을 구현해본다.

유전 알고리즘 알아보기 - 유전 알고리즘은 무엇일까요?

(생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적의 값을 찾아내는 검색 방법이다.

연산 과정은 선택, 교차, 변이, 대치로 구성된다.)

• 숫자 카드 놀이하기 : 유전 알고리즘을 적용하기 - 문제 : {1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3개를 골라

서 20으로 만들어라.

처음 시뮬레이션 을 보는 경우에는 이 과정을 낯설어 할 수 있으므로 학생들이 필 요로 하면 여러 번 재 생하여 보여주어 학생 들의 이해를 도울 수 있다.

교사가 해당하는 발문

을 함과 동시에 영상

자료를 부분적으로 제

시해 주어도 좋다.

●

●●

●

●●

●●

●●

●●

●●●

●●

●●●

●

●

●

●●

●●●

●●

●

●

●

●●

●

●●

●●●

●●●

●●●

●

+

●●

●

●●

+

●

●

●

=9 적합도 20-9=11

유전자로 가정한다. 세 개의 카드 를 뽑아 그 합을 구한 뒤 20이 되는지 확인한다.

예를 들어 (1,5,3) 카드를 뽑았다면 그 합이 9이다.

찾고자 하는 20에서 9의 차이가 11이 되는데 이것 을 적합도라고 한다. 적합도가 0이 되면 문제를 해결하는 것이다.

- 무작위 생성하기 : 숫자 세 개를 뽑아 4개의 조합을 만들고, 각각의 적합도를 구한다.

만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 각각 카드를 뽑았다고 하자. 각각의 적합도를 구하면, {11, 3, 6, 5}이 되며, 이 값이 높을수록 20에서 멀 기 때문에 해로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다.

- 선택하기 : 다음 세대를 만들기 위해, 이 세대의 개 체 중 2개의 유전자를 선택한다.

이때 선택은 적합도가 높은 3과 5의 값 즉, (8,0,9)와 (3,7,5)를 선택하고 나머지를 제거한다.

- 교배하기 : 선택된 2개의 유전자의 유전체는 두 번째 자리를 서로 교환해서 새로운 세대가 형성된다. 예로 (8,0,9), (3,7,5)가 선택되었고 다음 세대의 개체는 (8,7,9), (3,0,5)가 되며, 각각의 적합도는 4, 12가

유전 알고리즘 단 계별 안내 PPT, 점카 드뽑기 프로그램 (https://scratch.mit.edu/

projects/337554002)

컴카드를 무작위 로 뽑아주는 프로그램 을 활용한다.

학습지

적합도를 함수로

나타내기에는 선행학

습에 대한 우려가 있

어 적합도의 값을 숫

자로만 표기한다.

●●●

●●

●●●

●●●

●●●

●●●

●

●

●

●●

●●●

●●

●●

●

●●

⇓

●●●

●●

●●●

●●

●●●

●●

●●●

●●●

●●●

●

●

●

●●

●

●●

- [2세대] 만들기 : 다음 세대에서 다시 앞에서 했던 선택하기, 교배하기 과정을 거치 도록 한다. 교배 시에 [1세대]때 와 다른 세 번째 자리의 유전자 가 바뀌도록 한다.

- [3세대] 만들기 : [1세대], [2세대] 때와 만찬가지로 선택하기, 교배하기 과정을 거치 도록 한다. 교배 시에 첫 번째 자리의 숫자가 바뀌도록 한다.

- 돌연변이 만들기 : 자손 개체의 마지막 자리를 무 작위 수를 뽑아서 채워 적합도 를 확인한다.

- 최적의 값에 가까워질 때까지 세대를 반복한다.

• 정리하기

- 이러한 과정을 반복한다면 어떻게 될 것 같 나요?

(합이 20이 되는 경우를 많이 찾아낼 수 있을 것 같습니다. 점점 합이 20에 가까워질 것 같습니다.)

- 이번 시간 활동을 통해 알게 된 점, 재미있 던 점 등에 관해 다양하게 이야기 나누어 봅 시다.

교배에 사용한 현 재의 방법은 하나의 예일 뿐 다양한 방법 이 있음을 알려준다.

프로그래밍에서 돌연변이는 0.1%, 0.05% 등 아주 낮은 확률로 발생하게 설 정하는 것이 일반적 이지만 우리는 경우 의 수가 적은 관계 로 30%라는 높은 확 률로 발생하게 설정 했다는 점을 안내해 준다.

완벽하게 20이 나

오지 않더라도 20에

가까운 적합도 값이

나오기까지의 과정을

이해할 수 있도록 한

다.

활동 1 유전 알고리즘, 넌 누구?!

유전 알고리즘 1차시

◆ 다음 동영상을 보며 ‘유전 알고리즘’에 대한 다음 물음에 답해 봅시다.

(영상 주소: https://youtu.be/WZnf0C8HfJc)

1. 영상 속에서 어떤 까만 색들이 살아남을 것 같나요?

(빨리 움직여서 잘 피하는 것이 살아남을 것 같습니다..) 2. 까만색 점들이 어떤 속성을 물려주었나요?

(속도, 크기, 활동성 등을 물려주는 것 같습니다. )

3. 세대가 반복 될 때 어떤 까만색 점만 선택하여 복제하였나요?

(빨간색에 먹히지 않고 살아남은 점들만 선택하여 복제하였습니다.) 4. 화면 속에서 마지막에 어떤 점들이 살아남았나요?

(안전지대를 벗어나지 않을 정도의 활동성과 크기가 작은 점들만 살아남았습니다. ) 5. 이러한 과정은 과학시간에 배운 진화의 방법과 비슷하다고 생각하나요?

(네, 적자생존, 살아남은 개체의 유전적 형질이 후대에 전해진다는 점에서 비슷한 것 같습

니다.)

▶ 유전 알고리즘

유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모 델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으 로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연 산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 가져왔으며, 변이 (돌연변이), 교배 연산 등이 존재한다.

유전 알고리즘은 풀고자 하는 문제에 대한 가능한 답들을 정해진 형태의 자 료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 답들을 만들어 낸다. 여기에서 답을 나타내는 자료구조는 유전자, 이들을 변형함으로 써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다.

달리 표현하면, 유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 말할 수 있다.

유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기보다는 문제를 풀 기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바 꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최 적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접 근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋 은 성능을 보여주지는 못하지만, 대부분 받아들일 수 있는 수준의 답을 보여줄 수 있다.

이러한 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘 들로 진화 전략(Evolutionary strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 최근에 활발히 연구되고 있다. 유전 알고리즘 은 이 중에서 가장 기본이 되고 대표적인 알고리즘으로, 자연과학/공학 및 인 문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있다.

출처: 위키피디아, 유전 알고리즘

교사용 자료

▶ 진화에서 인공지능까지

다윈은 진화의 원리를 발견한 사람이다. 처음에 다윈이 진화론을 주장할 때 는 ‘우리 할아버지가 원숭이냐?’ 라는 조롱도 받았지만 , 현재는 많은 사람 들이 자연스럽게 받아들이는 과학적 사실이 되었다. 게다가 다윈이 발견한 진 화의 원리를 이용해 컴퓨터 프로그램도 만들고, 어려운 수학 문제도 해결하고 있다. 그렇다면 이러한 일을 해내고 있는 유전 알고리즘은 무엇일까?

다윈은 비글호를 타고 갈라파고스 군도를 여행하던 중 진화의 원리를 발견 했다고 한다. 이곳의 섬들은 적당히 떨어져 있어 섬마다 독립적 생태계를 이루 고 있는데, 다윈은 각 섬에 사는 동물들이 독자적으로 진화한 모습을 관찰했 다. 그중 대표적인 동물이 ‘핀치 새’였다. 섬마다 이 새들은 부리의 모양, 크 기, 골격이 조금씩 달랐다. 가장 큰 차이는 부리였다. 왜냐하면 섬에서 구할 수 있는 먹이에 따라 부리의 크기와 모양이 달라졌기 때문이다.

다윈은 이렇게 부리가 달라진 이유가 자연선택 때문이라고 했다. 처음에 핀 치 새들은 딱딱한 먹이를 잘 먹는 부리, 벌레를 잘 먹는 부리, 열매의 속만 파 먹는 부리 등 다양한 부리를 가지고 있었다. 이 중 섬에서 나는 먹이를 먹는 데 적당한 부리를 가진 새들이 살아남아서 자식 새를 낳은 것이다. 부리가 그대 로 자식 새에게 전해지는 것이 아니라, 교배로 두 마리 새의 특징이 섞이기도 한다. 또 전혀 새로운 (돌연)변이가 나타나 유전되기도 한다.

자연선택설은 이처럼 자연계에서는 환경에 적합한 생물체는 계속 살아남고, 적합하지 않은 것은 사라진다는 학설이다. 자연선택설에 따르면 환경에 잘 적 응한 생물체만이 자손을 남겨, 생존에 유리한 특성을 자손에게 전한다. 여러 세대를 거듭하면서 이런 특성이 점차 쌓이게 되고, 결국에는 선조와 다른 특성 을 가진 종으로 변한다.

교사용 자료

활동 2 숫자 카드 놀이하며 유전 알고리즘 이해하기

유전 알고리즘 1차시

◆ 다음 숫자 카드 중 세 개를 골라서 합이 20이 되도록 만들어 보세요.

●

●●

●

●●

●●

●●

●●

●●●

●●

●●●

●

●

●

●●

●●●

●●

●

●

●

●●

●

●●

●●●

●●●

●●●

각 숫자 카드는 유전자로 가정한다. 세 개의 카드를 뽑아 그 합을 구한 뒤 20이 되는지 확인한다. 예를 들어 (1,5,3) 카드를 뽑았다면 그 합이 9이 다. 찾고자 하는 20에서 9의 차이가 11이 되는데 이것을 적합도라고 한다.

이 문제의 경우 적합도가 0이 되면 문제를 해결하는 것이다.

[1단계] 무작위 생성하기(gg.gg/randcard) 숫자 세 개를 뽑아 4개의 조합을 만들고, 각각의 적합도를 구하세요.

뽑은 숫자로 유전자 구성하기

( , , ) ( , , ) ( , , ) ( , , )

적합도

만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 각각 카드를 뽑았다고 하자. 각각의 적 합도를 구하면, { 11, 3, 6, 5 }이 되며, 이 값이 높을수록 20에서 멀기 때문에 해 로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다.

[2단계] 선택하기

다음 세대를 만들기 위해, 위에서 만든 세대의 개체 중 적합도가 양호한 2개의 유전자를 선택하세요.

내가 선택한 유전자 ( , , ) ( , , )

이때 선택은 적합도가 양호한 3과 5의 값 즉, (8,0,9)와 (3,7,5)를 선택하고 나머 지를 제거한다.

[3단계] 교배하기

두 번째 자리 카드끼리 숫자를 교환하여 적합도 값을 구하세요.

유전자 교환하기 ( , , ) ( , , ) 적합도

선택된 2개의 유전자의 유전체는 두 번째 자리를 서로 교환해서 새로운 세대가 형성된다. 예로 (8,0,9), (3,7,5)가 선택되었고 다음 세대의 개체는 (8,7,9), (3,0,5)가 되며, 각각의 적합도는 4, 12가 된다.

●●●

●●

●●●

●●●

●●●

●●●

●

●

●

●●

●●●

●●

●●

●

●●

⇓

●●●

●●

●●●

●●

●●●

●●

●●●

●●●

●●●

●

●

●

●●

●

●●

2세대

[1단계]선택하기

2단계, 3단계에서 만들어진 개체 중 적합도가 양호한 두 개를 선택하세요.

내가 선택한 유전자 ( , , ) ( , , )

[2단계]교배하기

세 번째 자리 카드끼리 숫자를 교환하여 적합도 값을 구하세요.

유전자 교환하기 ( , , ) ( , , )

적합도

3세대

[1단계]선택하기

1단계, 2단계에서 만들어진 개체 중 적합도가 양호한 두 개를 선택하세요.

내가 선택한 유전자 ( , , ) ( , , )

[2단계]교배하기

첫 번째 자리 카드끼리 숫자를 교환하여 적합도 값을 구하세요.

유전자 교환하기 ( , , ) ( , , ) 적합도

돌연변이 만들기

자손개체의 마지막 자리를 무작위 수를 뽑아서 채워 돌연변이를 만든다.

유전자 ( , , ) ( , , ) 적합도

돌연변이는 0.1%, 0.05% 등 아주 낮은 확률로 발생하게 설정하는 것이 일반적이지 만 우리는 경우의 수가 적은 관계로 30%라는 높은 확률로 발생하게 설정해 보자.

적합도가 1보다 크거나 작을 때까지 반복하여 최적의 조합을 찾는다.

내가 찾은 최적의 조합 무엇인가요?

( , , )

- 이러한 과정을 계속 반복한다면 어떻게 될 것 같나요?

2차시

2차시 ⁵ 프로그램 지도안

프로그램명 유전 알고리즘 적용하여 구현하기 학교급 중학교 차시 2/3

학습목표 유전 알고리즘의 원리를 적용하여 사람 모습을 구현해볼 수 있다.

유전 알고리즘의 과정에서 돌연변이의 규칙을 다양하게 만들 수 있다.

학습자료 가위, 멀티미디어, 학습지, 교수용 ppt, 숫자카드

성취기준

과학

[9과03-01] 생물의 다양성을 이해하고, 변이의 관점에서 환경과 생물 양성의 관 계를 설명할 수 있다.

[9과21-04] 멘델 유전 실험의 의의와 원리를 이해하고, 원리가 적용되는 유전 현 상을 조사하여 발표할 수 있다.

[9과21-05] 사람의 유전 형질과 유전 연구 방법을 알고, 사람의 유전 현상을 가 계도를 이용하여 표현할 수 있다.

정보

[9정03-03] 논리적인 문제 해결 절차인 알고리즘의 의미와 중요성을 이해하고 실생활 문제의 해결 과정을 알고리즘으로 구상한다.

[9정03-04] 문제 해결을 위한 다양한 방법과 절차를 탐색하고 명확하게 표현한다.

기술 가정

[9기가04-18] 정보통신기술과 관련된 문제를 이해하고, 해결책을 창의적으로 탐 색하고 실현하며 평가한다.

[9기가05-09] 적정기술과 지속가능 발전의 의미를 이해하고 적정기술 체험 활동 을 통하여 문제를 창의적으로 탐색하고 실현하고 평가한다.

흐 름 차시 교수·학습 내용 학습자료( )

유의점( )

창의적 설계

2 차시

모둠 학습

• 전시학습 상기

- 지난 시간에 학습한 내용을 떠올려 봅시다.

무엇에 대해 살펴보았었나요?

(유전 알고리즘이 무엇인지 숫자카드놀이를 통해 알아보았습니다.)

- 이번 시간에는 유전 알고리즘을 응용하여 인 간의 모습을 구현해보도록 하겠습니다.

★도전, 협동, 배려, 열정,

창의

• 유전 알고리즘 적용사례

- 그네 타는 동작을 구현하기 위해 동작을 어 떻게 단순화시켰나요?

(앉았다, 일어나기 두 가지 동작으로 단순화 시켰습니다.)

- 진화를 위해 어떤 과정을 거쳤나요?

(무작위로 뽑은 후, 선택, 교배 과정을 반복 하고 가끔 돌연변이를 일으켰습니다. )

- 그네를 잘 타게 하기 위해 몇 세대를 반복했 나요?

(22세대를 반복하였습니다.)

유전 알고리즘을 응용하여 인간 모습 구현하기

[활동1] 사람의 모습 분석하기

• 사람의 신체 부위를 분해하기

- 사람의 모습을 간단한 도형으로 나타낸다면 몇 개의 부분으로 나눌 수 있을까요?

(허리를 기준으로 위로 여섯 부분, 아래로 여섯 부분으로 나눌 수 있습니다.)

유전 알고리즘의 이 실행되는 과정을 보여 주는 그네타기 시뮬레이션 영상

유전 알고리즘의 과정을 복습하고 여러 세대와 시간을 거쳐서 완성됨을 보여준다.

신체 부위를 위,

아래로 나누었을 때

같은 수가 되도록 구

분 지어야 교배하기

단계에서 규칙을 쉽게

적용할 수 있다.

머리 팔 몸통 팔 손 손 허벅지 허벅지 종아리 종아리

발 발

- 신체 부위를 나누었을 때 어떤 도형으로 표 현하면 좋을까요?

(간단히 원과 직사각형으로 표현할 수 있습니다.)

[활동2] 사람의 모습 구현하는 놀이하기

• 활동목표 : 왼쪽과 같은 신체 부위를 가진 사람을 만들자.

- 신체 부위는 12조각

• 준비하기 : 5명을 한 팀으로 구성한다. 4명은 사람의 모습을 구현하고, 1명은 적합도를 판별 한다.

• 1단계 : 무작위 생성하기

- 4명이 각자 프로그 램을 실행시켜 원 모 양, 직사각형 모양의 조각 모양을 학습지 에 표시한다.

도형의 모양은 최 소한으로 적게 사용할 수 있도록 한다.

랜덤휴먼 프로그램 (https://scratch.mit.edu/

projects/337568127) 학생들이 프로그 램을 이용할 수 있도 록 안내한다.

활동지4-1, 4-2

‘활동지4’는 종 이를 오려서 활동하는 방법과 프로그램을 이 용해서 활동하는 방법 두 가지로 안내하였다.

학생들의 상황에 맞추 어 선택하여 이용하도 록 한다.

친구들과 오린 조

각으로 사람의 모양을

완성해본 뒤 최상의

모습이라고 생각하는

상태를 서로 만들어

확인한 뒤 놀이활동을

시작하도록 한다.

• 2단계 : 선택하기

- 나머지 한 명의 친구는 적합도 값을 계산 한다.

- 해당 신체 부위의 도형이 완성하고자 하 는 도형과 일치하면 그 값을 1씩 누적하 여 적합도를 계산한다. 신체 부위가 12 개이므로 12가 되면 사람이 완성된다.

(왼쪽 그림의 경우 각 신체 부위에 맞는 조각들이 6개이므로 적합도는 6이 된다.)

- 5명 중 만들고자 하는 사람의 모습과 가장 적합 도가 높은 개체 2개만 남긴다.

개체모양

적합도 4 8 2 6

선택여부 탈락 선택 탈락 선택

• 3단계 : 교배하기

- 모두에 협의하여 분할지점(division point)를 어디로 할지 결정한다. 분할지점을 기준으로 반전시켜 만 든다.

(같은 위치에 해당하는 유전자끼리 교배하기, 순서

[최상의 상태]

신체의 부위의 위 치를 활동지를 이용하 여 고정된 곳에 색종 이를 놓도록 한다.

모둠별로 단계에

맞게 활동하는 과정에

서 모둠원이 서로의

의견을 존중하고 배려

하는지 상호 평가한다.

선택된 개체

교배 하기

적합도 6 10 6 8

<예: 분할지점을 6번으로 선택한 경우>

• 다음 세대 반복하기

- 다음 적합도가 높은 개체가 나올 때까지 다음 세 대로 활동을 반복한다.

• 돌연변이 찬스

- 더 이상 적합도가 높아지지 않는 교착 상태가 빠 지게 되면 돌연변이 찬스 학습지를 받아가서 다음 활동을 한다.

- 4개의 개체 중 무작위(주사위 사용)로 한 신체부위의 모양(원-직사각형)을 바꾸기

- 사람의 모습이 될 때까지 2-4단계를 반복하기

• 정리하기

- 이번 시간 활동을 통해 알게 된 점, 재미있던 점 등에 관해 다양하게 이야기 나누어 봅시다.

교배하기의 규칙은

예시로 제시한 것 외에

모둠 친구들끼리 정하

여 추가하여도 무방하

다.

활동 3 유전 알고리즘 – 걷기

유전 알고리즘 2차시

[이 활동을 통해]

• 유전 알고리즘의 원리를 이용하여 사람의 모습을 구현할 수 있다.

• 유전 알고리즘의 과정에서 돌연변이의 규칙을 다양하게 만들 수 있다.

◆ 다음 동영상을 보며 ‘유전 알고리즘’에 대한 다음 물음에 답해 봅시다.

(영상 주소: https://www.youtube.com/watch?v=c-qePE1GCQY&t=173s )

1. 동영상 속의 나무 인형은 처음에는 어떻게 걸었나요?

(걷는 모습이 이상해요. 한 두 발자국 걷다가 넘어졌습니다.) 2. 영상 속의 나무 인형이 걷도록 하기 위해 고려한 것은 무엇이었나요?

(걷기에 필요한 신체 부위를 분해하였다. 허리를 일정하게 흔들게 한다. 보폭을 신장의 1/4 로 정한다. 관절의 각도를 제한한다. 동작을 느리게 한다 등 )

3. 매 횟수마다 어떤 나무 인형만 선택하여 복제하였나요?

(제일 많이 걸어간 나무 인형을 선택하였습니다.) 4. 왜 그렇게 선택하였나요?

(적자 생존의 원리로 우수한 인형만 남기기 위해서입니다.) 5. 화면 속에서 나무 인형은 마지막에는 어떻게 걸었나요?

(완벽하지는 않지만 조금씩 흔들며 잘 걷게 되었다) 6. 왜 이렇게 복잡한 단계를 거쳐 나무 인형을 걷게 하였나요?

(나무 인형이 스스로 걷는 것을 배우며(기계학습) 진화해가는 과정을 컴퓨터가 구현하기 위

활동 4 유전 알고리즘을 응용하여 인간 구현하기1

유전 알고리즘 2차시

◆ 유전 알고리즘을 응용하여 인간을 만들어 봅시다.

- 가장 먼저 사람의 모습을 분석해 보세요. 사람의 모습을 표현하기 위해 몇 개 의 부분으로 나눌 수 있을까요?

(허리를 기준으로 위로 여섯 부분, 아래로 여섯 부분으로 나눌 수 있습니다.)

※ 신체 부위를 위, 아래로 나누었을 때 같은 수가 되도록 구분 지어야 교배하기 단계에 서 규칙을 쉽게 적용할 수 있습니다.

- 신체 부위를 어떤 도형으로 표현하면 좋을까요?

(간단히 원과 직사각형으로 표현할 수 있습니다.)

머리 팔 몸통 팔 손 손 허벅지 허벅지 종아리 종아리

발 발

◆ 사람의 모습 구현하는 놀이하기

왼쪽과 같은 신체부위를 가진 사람을 만들어 봅시다.

[놀이 방법]

1. 6명을 한 팀으로 구성한다. 5명은 사람의 모습을 구현하고, 1명은 적합 도를 판별합니다.

2. 부록의 자료에 있는 12개의 모양을 오립니다. 상자에 각자 오린 모양을 담습니다.

3. 1단계 : 무작위 생성하기

- 5명이 각각의 뽑기상자에서 원 모양, 직사각형 모양의 색종 이 조각 12개를 뽑는다.

- 뽑는 순서대로 위에서 아래로, 왼쪽에서 오른쪽으로 각 신 체 부위에 도형을 배치한다.

4. 2단계 : 선택하기(적자생존)

- 나머지 한 명의 친구는 적합도 값을 계산한다.

- 해당 신체 부위의 도형이 완성하고자 하는 도형과 일치하면 그 값을 1 씩 누적하여 적합도를 계산한다. 신체 부위가 12개이므로 12가 되면 사람이 완성된다.

※ 왼쪽 그림의 경우 각 신체 부위에 맞는 조각들이 6개이므로 적합도는 6이 된다.

- 5명 중 만들고자 하는 사람의 모습과 가장 적합도가 높은 개체 3개만 남기고 나머지 2개의 개체 조각들은 다시 상자 속에 넣는다.

개체모양

적합도 6 4 8 2 6

선택여부 선택 탈락 선택 탈락 선택

5. 3단계 : 교배하기

- 선택한 3개의 개체를 위, 아래 반씩 나누어 서로의 유전자를 교배하여 5개의 개체를 만듭니다.

※ 같은 위치에 해당하는 유전자끼리 교배하기, 순서를 바꾸어 교배하기 등

선택된 개체

교배하 기

적합도 6 10 6 8 6

6. 4단계 : 돌연변이 만들기

- 돌연변이의 기준은 모둠 친구들과 논의하여 정해보도록 합니다.

(예시: 5개의 개체 중 무작위(주사위 사용)로 한 신체부위의 모양(원-직사각형)을 바꿉니다. )

- 사람의 모습이 될 때까지 2-4단계를 반복하기

◆ 뽑은 도형을 아래의 사람 신체 부위가 나누어진 칸 안에 넣고, 적합도를 계산하 세요.

머리

팔

몸통

팔

손 손

허벅지 허벅지

종아리 종아리

발 발

◆ 해당하는 단계와 적합도를 계산하여 기록하세요.

단계

적합도

단계

적합도

단계

적합도

단계

적합도

단계

적합도

활동 4 유전 알고리즘으로 사람 모습 구현하기2

유전 알고리즘 2차시

◆ 뽑은 도형을 아래의 사람 신체 부위가 나누어진 칸 안에 넣고, 적합도를 계산하 세요. (gg.gg/randman)

- 사람 모습을 구현하기 위해서 어떤 모양을 사용했나요?

- 사람 모습 그림을 더 간단하게 나타낼 수 있는 방법에는 어떤 것이 있을까요?

◆ 1차 시도 - 무작위 생성

모양 (○ 또는

■로 표시)

적합도

선택여부

- 교배

- 각자 분할지점(division point)를 어디로 할지 정하고 시행 후 종이에 옮기세요.

모양 (○ 또는

■로 표시)

적합도

선택여부

◆ ( )차 시도 - 교배

- 각자 분할지점(division point)를 어디로 할지 정하고 시행 후 종이에 옮기세요.

모양 (○ 또는

■로 표시)

적합도

선택여부

◆ ( )차 시도 - 교배

모양 (○ 또는

■로 표시)

적합도

선택여부

◆ 돌연변이 찬스

- 주사위를 던져 나온 자리를 반대로 만들어 주세요.(gg.gg/randdice)

모양 (○ 또는

■로 표시)

적합도

선택여부

활동 5 컴퓨팅 사고로 유전 알고리즘 이해하기

유전 알고리즘 2차시

◆ 컴퓨팅 사고로 유전 알고리즘을 이해해 봅시다.

- 유전 알고리즘으로 ‘그네 타는 법’ 학습과정 영상을 보며 생각해 보세요.

(영상 주소: https://www.youtube.com/watch?v=Yr_nRnqeDp0&t=106s)

- 그네를 잘 타려면 관절을 어떻게 움직여야 하나요?

(관절을 구부렸다가 편다. 일부 관절은 고정한다 )

- 그네를 타는 인형의 관절의 움직임을 무엇으로 표현하였나요?

(0과 1로 나타내었습니다 )

- 색종이 놀이로 만든 사람의 신체 부위를 0과 1로 표현하여 생각해 보세요.

0 1 1 1

0 0 = 010110110110 1 1

1 1

0 0

▶ 0과 1로 구현하는 유전 알고리즘

유전 알고리즘은 컴퓨터로 데이터를 처리하여 구현하기 때문에 과학에서 배 운 진화 과정을 표현하기 위해 0과 1의 값을 사용한다. 수업 시간에 배운 내용 을 개발하기 위해서는 실제 현실의 문제를 유전자로 표현하고 유전자의 진화 과정을 모델링하여 구현된다.

유전자 알고리즘은 일반적으로 선택(selection), 교차(crossover), 그리고 돌연 변이(mutation) 이렇게 세 가지 종류의 유전자 조작(genetic operation) 과정을 사용하여 해결책을 탐색해 나간다.

(참고 : 김영민, 안재준, 2016. ‘탄소배출권 거래시장 특성을 반영한 배출권가격 예측모델 개발’)

교사용 자료

3차시

3차시 ⁶ 프로그램 지도안

프로그램명 유전 알고리즘 활용 사례 살펴보기 학교급 중학교 차시 3/3

학습목표 유전 알고리즘의 활용 사례와 적용할 수 있는 문제를 탐색할 수 있다.

학습자료 가위, 멀티미디어, 학습지, 교수용 ppt, 숫자카드

성취기준

과학

[9과07-01] 과학과 관련된 직업의 종류와 하는 일을 조사하고, 그 직업에 필요한 역량에 대해 토의할 수 있다.

[9과07-02] 현대 사회의 다양한 직업이 과학과 어떤 관련성이 있는지 예를 들어 설명하고, 미래 사회에서의 직업의 변화를 토의할 수 있다.

[9과24-01] 과학기술과 인류 문명의 관계를 이해하고 과학의 유용성에 대해 설명 할 수 있다.

[9과24-02] 과학을 활용하여 우리 생활을 보다 편리하게 만드는 방안을 고안하 고 그 유용성에 대해 토론할 수 있다.

도덕

[9도02-05] 정보화 시대에 요구되는 도덕적 자세와 책임의 도덕적 근거와 이유 를 제시하고, 타인 존중의 태도를 통해 다양한 방식으로 의사소통할 수 있다.

[9도04-02] 과학 기술이 현대인의 삶에 미치는 긍정적인 영향과 가치를 설명하 고, 동시에과학 기술이 지닌 문제점과 한계를 열거하며, 과학 기술의 바람직한 활용 방안을 제시할 수 있다.

기술 가정

[9기가05-01] 기술의 발달에 따른 사회, 가정, 직업의 변화를 이해하고 미래 기 술 활용 및 사회의 변화에 대하여 예측한다.

흐 름 차시 교수·학습 내용 학습자료( )

유의점( )

감성적 체험 (성공의

경험) 3 차시

개별 학습

• 전시학습 상기

- 지난 시간에 학습한 내용을 떠올려 봅시다.

무엇에 대해 살펴보았었나요?

(유전 알고리즘을 응용하여 사람의 모습을 구현해 보았습니다.)

- 이번 시간에는 유전 알고리즘을 응용하여 문

제를 해결하고 있는 다양한 사례를 살펴보고

여러분의 생각을 함께 나누어 보도록 하겠습 니다.

활동 소감 이야기 나누기

- 알게 된 점, 어려웠던 점, 개선시키고 싶은 점 등에 관해 반 친구들과 함께 이야기 나누기

• 과학기술의 필요성 이해하기

- 유전자 알고리즘의 실제 문제해결사례 찾아 보기

① Travelling Salesman Problem(TSP, 순회외판 원문제)

순회외판원 문제는 대표적인 NP 문제로 문제의 해결 에 많이 사용이 된다. 영상에서 메인 GUI의 오른편 상자에서 20개의 색으로 구분된 가로줄은 하나의 염 색체를 나타내고, 세로 3000줄은 해를 탐색하는 집단 의 수가 3000개라는 것을 의미한다. 시간이 흐를수록 좋다고 생각되는(또는 충분히 반복 연산해서 검증된) 해 부분이 동일한 색깔을 갖추어가는 모습을 보여주 기 때문에 유전 알고리즘의 특징을 잘 보여주고 있다.

② 로봇주행성능 향상

★ 지적 만족감, 성취감, 도전, 공감

TSP(순회외판원) 영상

https://www.youtube.

com/watch?v=CrBHS T9ZK80

제시하는 영상들의

계산과정을 직접적으로

이해하기에는 내용이

어려우므로 유전 알고

리즘을 통해 컴퓨터가

문제를 개선하고 해결

해 가는 과정을 경험

해 보도록 한다.

유전 알고리즘을 이용한 로봇의 주행성능을 향상시 키는 영상으로 그 과정을 실제 로봇의 움직임으로 확인할 수 있다. 6개의 독립된 다리를 제어하는 명 령을 랜덤으로 생성해서 실제 로봇의 주행거리, 자 세 등을 센서로 입력받고, 더 나은 움직임을 보인 명령들을 계속해서 발전시켜 나간 것으로 생각해볼 수 있다.

③ 모나리자 이미지 만들기

<150개의 원으로 모나리자 그리기>

150개의 원으로 모나리자와 흡사한 이미지를 얻어 내는 과정을 나타낸 영상이다. 먼저 랜덤하게 추출 하여 조합을 만든 뒤 이 조합과 원본 이미지의 컬러 값 차이를 점수로 만들어 저장한다. 여기에 돌연변 이를 시켜 개체를 만들고, 색을 바꾸거나 도형을 더 하거나 빼는 식으로 계산한다. 새로운 개체와 원본 이미지의 컬러값의 차이를 점수로 만들어 저장하고, 새로운 개체가 우수할 경우 살아남기고, 값이 적은 것은 삭제한다. 이러한 과정을 반복하며 알고리즘을 완성한다.

로봇주행성능향상 https://www.youtube.

com/watch?v=KHV7f Wvnn_0

모나리자 이미지 만들기

https://www.youtube.

com/watch?v=rGt3iM AJVT8

https://www.youtube.

com/watch?v=f5g8k-

n4j_o

④ 게임에서의 최적화 방법 찾기

위 영상은 마리오가 목적지까지 가기 위해 어떤 타 이밍에 ‘점프’를 해야 하는지 유전 알고리즘으로 연 구한 과정을 보여주고 있다. 오른쪽 영상은 테트리 스 게임을 이용하여 유전 알고리즘을 적용하면서 자 동으로 게임 실력을 향상해 가는 과정을 보여주고 있다.

• 유전 알고리즘을 적용할 수 있는 문제에 대해 생각해보기

- 유전 알고리즘을 적용하여 해결할 수 있는 문제에는 무엇이 있을지 생각하여 글로 작성 해 보세요.

• 진로 탐색하기

- 유전 알고리즘과 같은 인공지능, 기계학습 기술을 통한 문제해결 방법을 이해하고 그와 관련된 직업 탐색하기

게임의 최적화 방법 마리오 게임 https://www.youtube.

com/watch?v=PHwM H28wFuM

테트리스 자동 게임 https://www.youtube.

com/watch?v=yKN8Ih IccVw

적용할 문제에 대한 글을 쓸 때에 는 막연한 상상보다 는 구체적인 문제해 결과정이 드러나게 알고리즘으로 작성 하여도 좋다.

다양한 진로에 대

한 호기심을 갖도록

한다.

유전 알고리즘으로 문제 해결하기

유전 알고리즘 3차시

활동 6

◆ 유전 알고리즘을 어떠한 문제에 적용하여 해결하고 싶은지 여러분의 생각을

정리해보세요.

인간 모형 만들기 도형 그림 자료

부 록

교사용

PPT