유전 알고리즘 1.유전 알고리즘과 유전

이번 포스팅은 2022년 과학탐구실험과 수업량 유연화에서 사용하였던 유전 알고리즘 탐구입니다.

필요하신분들은 참고하세요.

 

유전 알고리즘에 대한 공부는 아래 링크인 "유전 알고리즘으로 진화하기 - STEAM 교육" 여기 문서를 참고하였습니다.

(정말 감사합니다!)

이 문서는 유전, 유전 알고리즘, 실습으로 4회 포스팅으로 계획하였습니다.

https://steam.kofac.re.kr/wp-content/plugins/download-attachments/includes/download.php?subject=&title=%EC%9C%A0%EC%A0%84%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9C%BC%EB%A1%9C%20%EC%A7%84%ED%99%94%ED%95%98%EA%B8%B0-%EC%A4%91%EB%93%B1-%EA%B5%90%EC%82%AC%EC%9A%A9&post_id=15399&id=15400

(링크를 클릭하면 '문서'가 다운됩니다.)

 

 

1. 개요

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

 

유전 알고리즘은 자연계의 생물 유전학에 기본 이론을 두며, 병렬적이고 전역적인 탐색 알고리즘으로서, 다윈의 자연선택 이론을 기본 개념으로 한다. 유전 알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 여기에서 해들을 나타내는 자료구조는 유전자, 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다.

 

 

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

 

2.용어정리

많은 개념들이 있지만 유전 알고리즘을 풀기 위한 핵심 개념만 알아보자. (각잡고 들어가면 생명 선생님 모셔야 함)

 

1) 형질(genotype)

생물에서 발현된 유전적 특징(키, 귓불 모양, 보조개 여부 등)으로 쉽게 생각해서 생명체의 특성(feature)임.

 

2) 유전(heredity)

부모의 유전형질이 자손에게 전달되는 것

3) 유전자(gene)

DNA로 구성된 유기물질로 유전의 기본단위, 형질의 정보가 담겨 있으며 생식을 통해 자손에게 유전된다.

 

4) 자연선택(natural selection)

생존에 적합한 형질을 지닌 개체군이, 그 환경 하에서 생존에 부적합한 형질을 지닌 개체군에 비해 ‘생존’과 ‘번식’에 이익을 본다.

※ 생존과 번식은 다른 개념, 초파리의 수명은 40일~50일로 생존력은 짧지만 번식력은 어마어마하여 종이 유지가 되는 개념. 사실 중요한 것은 ‘번식’ 이다.

 

5) 유전 법칙(멘델의 법칙) ★

오스트리아의 유전학자/식물학자/성직자였던 그리고어 멘델(Gregor Mendel)의 완두콩 실험을 기반으로 정리된 유전학 법칙(1865년) 멘델의 유전법칙은 유전학의 기본적인 원리로 제시되고 있으며, 3개의 법칙으로 구성된다.

 

6) 돌연변이(Mutation)

돌연변이란, 유전정보가 기록된 DNA 분자가 여러 가지 요인(전자기파, 방사선, 화학물질, 외부/내부 유전자 등)에 의해 원본과 달라지는 것을 말한다.

돌연변이가 일어나면 그 유전자에 의해 생산되는 단백질에 변화가 생기고, 이는 유전형질의 변화를 불러오게 된다. 이러한 돌연변이의 축적은 유전자 집단 안에 다양한 유전적 변이를 축적시키게 되며, 이렇게 만들어진 유전적 변이는 자연선택에 의해 진화의 가능성을 주게 된다.

3.멘델의 유전 법칙

(1) 우열의 원리(예외가 많아 법칙이 아닌 원리로 이해)

• 특성 형질에 대한 대립유전자가 있으며, 우성(Dominant)과 열성(Recessive)으로 나뉨
• 순종의 대립 형질을 교배했을 때, 우성 대립유전자만이 표현형으로 나타남
• 불완전 우성(빨강 + 흰색 교배 하였을 때 분홍이 나타나는 등 중간 유전 현상도 많음) , 유전 알고리즘에서도 사용하지만 우리가 배우는 유전 알고리즘에서는 사용하지 않기로 한다. 필요하면 여러분이 자료를 찾고 직접 구현해 보길 바란다.

 

 

(2) 분리의 법칙

- 감수분열 시, 대립유전자는 서로 다른 생식세포로 분리되는 현상

- 분리된 대립유전자는 수정 시 무작위로 재결합.

- F2 세대에서 3:1의 표현형을 보임.

- 이번 시간에 배우는 유전 알고리즘에서 새로운 개체 생성 시 분리의 법칙을 이용한다.

 

 

(3) 독립의 법칙

• 두 쌍 이상의 대립 형질이 함께 유전되는 경우(R : 노랑, r : 초록 / Y : 매끈, y : 쭈글) 각각의 형질은 서로 독립적으로 발현된다.
• 다른 염색체에 있는 다른 유전자는 서로 영향을 주지 않고 유전됨
• F2 세대에서 9:3:3:1의 표현형을 보임.
• 마찬가지로 유전 알고리즘에서도 사용하지만 우리가 배우는 유전 알고리즘에서는 사용하지 않기로 한다. 필요하면 여러분이 자료를 찾고 직접 구현해 보길 바란다.