| 분자생물학·생화학 Molecular Biology · Biochemistry | |||||||
| {{{#!wiki style="word-break: keep-all; margin:0 -10px -5px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-6px -1px -11px" | <colbgcolor=#717845> 기반 | 생물물리학 · 물리화학 (둘러보기) · 분자화학 (유기화학 · 무기화학 · 고분자화학) · 수학 (미분방정식 · 이산수학 · 매듭이론) | |||||
| 기본 물질 | 아미노산 (카복실산) · 리간드 | ||||||
| 유전체 | 유전체 기본 구조 | 아데닌 · 타이민 · 구아닌 · 사이토신 · 유라실 · 리보스 · 디옥시리보스 · 뉴클레오타이드 (핵산) | |||||
| 유전체 혼합 구성 | 인트론 · 엑손 · 오페론 · 프로모터 | ||||||
| 유전체 세부 종류 | RNA | MRNA · TRNA · RRNA(리보솜) · 리보자임 · miRNA · siRNA · RDDM | |||||
| DNA | A형 구조 · B형 구조 · Z형 구조 · Alu · 게놈 · 텔로미어 · 유전자 · 유전자 목록 | ||||||
| 관련 물질 | 효소 | 보조인자 · 조효소 (NADH · NADPH · FAD) · 뉴클레이스 · 디하이드록실레이스 · 레닌 · 루비스코 · 루시페레이스 · 라이소자임 · 라이페이스 · 말테이스 · 셀룰레이스 · 아데닐산고리화효소 · 아밀레이스(디아스타아제) · 역전사효소 · 트립신 · 펩신 · 유전체 중합 효소 · 리보자임 · 미카엘리스 멘텐 방정식 | |||||
| 제어 물질 | 사이토카인 · 신경전달물질 (ATP) · 수용체 (GPCR) | ||||||
| 기타 | 뉴클레오솜 · 히스톤 · 프리온 · 호르몬 · 샤페론 | ||||||
| 현상 및 응용 | 물질대사 · 펩타이드 결합 (알파 헬릭스 구조 · 베타병풍) · 센트럴 도그마 · 전사 (전사 인자) · 번역 · 복제 · 유전 알고리즘 · 유전 부호 · 대사경로 · TCA 회로 · 산화적 인산화 · 기질 수준 인산화 · 해당과정 · 오탄당 인산경로 · 포도당 신생합성 · 글리코겐 대사 · 아미노산 대사 · 단백질 대사회전 · 지방산 대사 · 베타 산화 · RNA 이어맞추기 · 신호전달 · DNA 메틸화 (인핸서) · 세포분열 (감수분열 · 체세포분열) · 능동수송 · 수동수송 · 페토의 역설 · 하플로그룹 | ||||||
| 기법 | ELISA · PCR · 돌연변이유도 · 전기영동 (SDS-PAGE · 서던 블로팅 · 웨스턴 블롯) · 유전체 편집 (CRISPR) · DNA 수선 · 바이오 컴퓨팅 (DNA 컴퓨터) · DNA 시퀀싱 · STR · SNP · SSCP | ||||||
| 기타 문서 | 일반생물학 · 분자유전학 · 생리학 · 유전학 · 진화생물학 · 면역학 · 약학 (약리학 둘러보기) · 세포학 · 구조생물학 · 기초의학 둘러보기 · 식품 관련 정보 · 영양소 · 네른스트 식 · 샤가프의 법칙 · 전구체 | }}}}}}}}} | |||||
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
| 유전 알고리즘 작동 예시 |
1. 개요
"결국 살아남는 종은 강인한 종도 아니고, 지적 능력이 뛰어난 종도 아니다. 종국에 살아남는 것은 변화에 가장 잘 적응하는 종이다."
- 찰스 다윈
Genetic Algorithm- 찰스 다윈
Evolutionary Algorithm
유전 알고리즘은 존 홀랜드(John Holland)가 1975년에 저서 "Adaptation on Natural and Artificial Systems" 에서 처음 소개한 최적화 기법이며 실제 생물 진화를 모방해서 문제를 해결하는 진화 연산의 대표적인 방법이다.
유전 알고리즘은 자연계의 유전학에 바탕을 두며, 특히 다윈의 자연 선택 이론을 기본 개념으로 한다. 유전자 프로그래밍에서는 문제에 대한 가능한 해들을 나열한 뒤, 점점 유전자들을 변화시켜 정확도가 높고 좋은 해들을 만들어 낸다. 여기서 문제의 해들을 유전자 라고 부르고, 그리고 이런 유전자들을 변형시켜 좋은 해를 얻는 것을 진화라고 볼 수 있다. 즉, 더 좋은 답을 찾아 가기 위해 진화를 모방한 탐색 알고리즘이라고 할 수 있다.
유전자 알고리즘으로 잘못 알고 있는 경우도 있는데, '유전 알고리즘'이 맞다.
NN(Neural Network)이 나오기 전까지 가장 핫했던 알고리즘이며, 인공신경망이 나오며 쇠퇴할 줄 알았으나 딥러닝에서의 초깃값을 설정할 때 쓰이는 등 아직도 중요한 역할을 하고있다.
Evolutionary Algorithm(진화 알고리즘)이라는 이름으로 불리기도 한다.
2. 전체적인 과정
일반인도 알 수 있게끔 간단하고 유명한 예시를 곁들여 설명한다.예시 목표: 이진수 0000(2)~1111(2)까지의 수 중에서 가장 큰 수를 찾고 싶다.[1]
2.1. 초기화 (Initialize)
- 유전 알고리즘으로 해결하고자 하는 해를 유전자로 표현한다.
- 예시에서는 간단하게 해 그 자체를 유전자로 표현해본다.
유전자 : [#, #, #, #] (#은 0 또는 1) - 랜덤한 유전자를 적당한 개수만큼 준비한다.
- 여기서는 10개를 준비했다. 실제로는 이거보단 많아야 한다!
[1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 0, 1]
2.2. 선택 (Selection)
- 배치한 각 유전자에 대해 적합도(Fitness, 점수라고 봐도 좋다.)를 측정한다.
이때 점수를 계산하는 방법에 따라 해를 빨리 찾을 수도, 영원히 찾지 못할 수도 있으니 신중해야 한다. - 여기선 1의 개수를 점수로 매긴다.
[1, 0, 0, 0]: 1, [0, 1, 0, 0]: 1, [0, 0, 1, 0]: 1, [1, 1, 0, 1]: 3, [0, 0, 0, 0]: 0, [0, 0, 0, 0]: 0, [1, 0, 0, 0]: 1, [1, 0, 1, 1]: 3, [0, 0, 1, 1]: 2, [0, 0, 0, 1]: 1 - 점수가 큰 순서대로 정렬하면 다음과 같다.
[1, 1, 0, 1], [1, 0, 1, 1] / [1, 0, 0, 1], [0, 0, 1, 1] / [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1] / [0, 0, 0, 0], [0, 0, 0, 0] - 현재 세대에서 다음 세대로 전해질 후보를 선택한다.
선택하는 방법에는 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다. - 여기서는 순위 기반 선택을 사용해서 상위 4개의 유전자만 골랐다.
[1, 1, 0, 1], [1, 0, 1, 0], [1, 0, 0, 1], [0, 0, 1, 1]
2.3. 교차 (Crossover)
- 선택한 유전자들을 가지고 여러 방법을 이용해서 후대 유전자를 만든다.
- 여기서는 후보 중 두 유전자를 랜덤으로 골라서 각 자리에서 확률적으로 물려받아 후대를 생성한다.
좌측의 유전자를 물려받은 자리는 -를, 우측의 유전자를 물려받은 자리는 +를, 좌우가 같은 경우는 *를 수 옆에 붙였다.[1, 0, 1, 0] + [1, 0, 1, 0] → [1*, 0*, 1*, 0*][1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 0-][1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 1+][1, 1, 0, 1] + [1, 0, 1, 0] → [1*, 0+, 1+, 1-][1, 1, 0, 1] + [1, 0, 0, 1] → [1*, 1-, 0*, 1*][1, 0, 0, 1] + [1, 1, 0, 1] → [1*, 0-, 0*, 1*][1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 1+][1, 0, 1, 0] + [1, 0, 0, 1] → [1*, 0*, 1-, 0-][1, 0, 0, 1] + [1, 0, 1, 0] → [1*, 0*, 1+, 1-][0, 0, 1, 1] + [1, 0, 0, 1] → [1+, 0*, 1-, 1*]
결과:[1, 0, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1]
2.4. 변이 (Mutation)
- 만든 후대 유전자에서 낮은 확률로 변이를 일으킨다.
[1, 0, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1 → 0, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1]
보다시피 정답이었던 유전자가 변이를 일으키는 바람에 정답의 수가 줄었다. 이렇듯 유전 알고리즘을 동작시킬 때 항상 답에 근접하는 것은 아니다.
2.5. 대치 (Replace)
- 현재 유전자를 후대 유전자로 교체시킨다.
[1, 0, 1, 0], [0, 1, 0, 0], [0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 0, 1]
↓[1, 0, 1, 0], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 0, 1, 1]
보다시피 전체적으로 정답에 좀 더 가까워졌다.
2.6. 반복 (Loop)
- 거의 모든 유전자가 같아졌고 전체적으로 변화가 거의 없어질때까지 선택, 교차, 변이, 대치를 반복한다.
- 눈치챘겠지만 이런 방법으로는 운이 나쁘면 1111(2)에 도달하지 못하고 종료될 수도 있다. 이걸 방지하기 위해서 변이가 있는 것이지만 좀 더 복잡한 문제에서는 항상 최선의 결과가 나오지 않을 수 있다.
2.7. 종료
- 얻은 유전자의 해가 원하던 것인지 확인하고 종료한다.
- 1111(2)라는 결과를 얻었고, 범위 내의 가장 큰 수인 듯하다!
이렇게 놓고 보면 그냥 간단히 계산기 돌려서 구할 수 있는 문제를 뭣 하러 이렇게 복잡하고 확률의존적인 방식을 써서 구하나 의문이 들 수도 있는데, 쉬운 설명을 위해 단순하고 답이 정해져 있는 문제로 예시를 들어서 그렇게 보이는 것. 실제로는 답이 정해져 있는 것도 아니고 최적해가 이미 알려져있지도 않은 복잡한 문제에 활용을 하게 된다. 이를테면 인공지능에게 이족보행 방법을 가르친다든지. 참고영상
3. 학교 교과목의 일종으로서
학부과정에서는 인공지능 과목의 일부 단원에서 이를 다룬다. 동서대학교 강의자료컴퓨터학과 대학원 과정에서 종종 '유전 알고리즘' 과목이 개설된다. 'Evolutionary Algorithm'(진화 알고리즘)이라고도 개설된다. 강의계획서(콜로라도 대학교)
주된 주제로는 다음이 있다. 각 수업은 교재나 관련 논문 1편을 주 텍스트로 잡고 이뤄진다.
- binary genetic algorithm
- Continuous Genetic Algorithm
- Hybrid Genetic Algorithm
- Evolutionary visual art and design
- Genetic Algorithm-based Clustering Technique
- micro-genetic algorithm
- effective heuristic algorithm
- parallel genetic algorithm
- evolutionary multi-objective optimization
- Differential Evolution (DE)
- particle swarm algorithm
- 개미 군집(ant colony) system: agent(개미)들이 목적지를 향해 나아가는 동안 각 경로에 페로몬을 분비하고, 이후에 지나가는 개미들은 그 경로에 쌓여 있는 페로몬 정보를 이용해 다음 경로를 선택하는 원리를 휴리스틱 탐색에 적용한 것. 1992년경 만들어졌다.
[1] 물론 1111(2)인 것을 바로 계산할 수 있지만 어디까지나 예시이다.