유전 알고리즘

덤프버전 :

분류


'''이론 컴퓨터 과학
{{{#fff

Theoretical Computer Science
'''

[ 펼치기 · 접기 ]
이론
기본 대상
수학기초론(수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론) · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학] · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론
재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론
FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
계산 복잡도 이론
점근 표기법 · 튜링 기계^고전, PRAM, 양자, 비결정론적^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법)
수학적 최적화
조합 최적화
외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화
내부점 방법 · 경사하강법
선형계획법
심플렉스법
정보이론
데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
컴퓨팅 방법론
병렬 컴퓨팅(병렬 아키텍처 · 암달의 법칙 · 병렬 알고리즘) · 분산 컴퓨팅(분산 알고리즘 · 클러스터 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅) · 멀티코어 컴퓨팅 · 대칭형 다중 처리(SMP)
암호학
해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식
블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식
공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
프로그래밍 언어이론
프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초
정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현
배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^
계산 수론 및 암호학
밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘
계산기하학
볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론
탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학




[ 펼치기 · 접기 ]
기반 학문
수학 (해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학 (환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학 (형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학
SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술
기계어 · 어셈블리어 · C(C++ · C\#) · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍(디자인 패턴) · 해킹 · ROT13 · OTP · IoT · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화
연구및 기타 문서
논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 디자인 패턴 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 정보처리이론 · 재귀 이론 · 자연 언어 처리(기계 번역 · 음성인식)
}}}



1. 개요
2. 전체적인 과정
2.1. 초기화 (Initialize)
2.2. 선택 (Selection)
2.3. 교차 (Crossover)
2.4. 변이 (Mutation)
2.5. 대치 (Replace)
2.6. 반복 (Loop)
2.7. 종료
3. 학교 교과목의 일종으로서



유전 알고리즘 작동 예시


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)[편집]

  1. 유전 알고리즘으로 해결하고자 하는 해를 유전자로 표현한다.
    1. 예시에서는 간단하게 해 그 자체를 유전자로 표현해본다.
유전자 : [#, #, #, #] (#은 0 또는 1)
  1. 랜덤한 유전자를 적당한 개수만큼 준비한다.
    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)[편집]

  1. 배치한 각 유전자에 대해 적합도(Fitness, 점수라고 봐도 좋다.)를 측정한다.
이때 점수를 계산하는 방법에 따라 해를 빨리 찾을 수도, 영원히 찾지 못할 수도 있으니 신중해야 한다.
  1. 여기선 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, 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]

  1. 현재 세대에서 다음 세대로 전해질 후보를 선택한다.
선택하는 방법에는 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.
  1. 여기서는 순위 기반 선택을 사용해서 상위 4개의 유전자만 골랐다.
[1, 1, 0, 1], [1, 0, 1, 0], [1, 0, 0, 1], [0, 0, 1, 1]



2.3. 교차 (Crossover)[편집]

  1. 선택한 유전자들을 가지고 여러 방법을 이용해서 후대 유전자를 만든다.
    1. 여기서는 후보 중 두 유전자를 랜덤으로 골라서 각 자리에서 확률적으로 물려받아 후대를 생성한다.
좌측의 유전자를 물려받은 자리는 -를, 우측의 유전자를 물려받은 자리는 +를, 좌우가 같은 경우는 *를 수 옆에 붙였다.
[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. 만든 후대 유전자에서 낮은 확률로 변이를 일으킨다.
    1. [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. 현재 유전자를 후대 유전자로 교체시킨다. 
    1. [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)[편집]

  1. 거의 모든 유전자가 같아졌고 전체적으로 변화가 거의 없어질때까지 선택, 교차, 변이, 대치를 반복한다.
    1. 눈치챘겠지만 이런 방법으로는 운이 나쁘면 1111(2)에 도달하지 못하고 종료될 수도 있다. 이걸 방지하기 위해서 변이가 있는 것이지만 좀 더 복잡한 문제에서는 항상 최선의 결과가 나오지 않을 수 있다.


2.7. 종료[편집]

  1. 얻은 유전자의 해가 원하던 것인지 확인하고 종료한다.
    1. 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년경 만들어졌다.


파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-12 04:49:48에 나무위키 유전 알고리즘 문서에서 가져왔습니다.

[1] 물론 1111(2)인 것을 바로 계산할 수 있지만 어디까지나 예시이다.

관련 문서