제 4 장 유전자 알고리즘 (Genetic Algorithm)

14 slides
0.1 MB
396 views

Similar Presentations

Presentation Transcript

1

제 4 장 유전자 알고리즘 (Genetic Algorithm)

2

Genetic Algorithm (1)1975년 미국 미시간 대학의 John Holland 교수가 세포의 작용을 연구하던 중 제안 생물학계의 적자생존 원리(자연도태 원리)를 기초로 한 최적화 알고리즘. 적용 분야 Job shop scheduling 훈련신경회로망 이미지 특징 추출 및 인식 최적화 문제등에 응용

3

Genetic Algorithm (2)생물의 유전과 진화알고리즘을 공학적으로 모델화하여 문제해결이나 시스템의 학습등에 응용하려는 알고리즘 생물의 진화 과정을 알고리즘으로 모델링 개체군중에서 환경에 대한 적합도가 높은 개체가 높은 확률로 살아 남아 재생 교배 및 돌연변이로서 다음 세대의 개체군을 형성 개체군 : 어떤 세대를 형성하는 개체들의 집합 진화적 알고리즘(evolutionary algorithm)이라고도 함

4

Genetic Algorithm (3)용어 세대 (Generation) 개체 (Individual) 개체군 (Population) 적합도 (Fitness) 재생 (Reproduction) 교배 (Crossover) 돌연변이 (Mutation)

5

진화적 연산 (1)진화적 알고리즘 (Evolutionary Algorithm, EA) 문제에 대한 가능한 해들을 정해진 형태의 자료 구조로 표현 점차적으로 변형하면서 점점 더 좋은 해를 생성 각각의 가능한 해 하나의 유기체 또는 개체로 보며, 이들의 집합을 개체군 개체 한 개 또는 여러 개의 염색체로 구성 유전 연산자 염색체를 변형하는 연산자 탐색, 최적화 및 기계 학습의 도구로 많이 사용

6

진화적 연산 (2)진화적 알고리즘 흐름 문제해결 전략에 따른 분류 유전자 알고리즘(Genetic Algorithm, GA) 협의의 알고리즘으로 고정길이의 이진 스트링 염색체 사용 유전자 프로그래밍(Genetic Programming, GP) 그래프와 트리 등을 염색체 표현에 사용 진화적 프로그래밍(Evolutionary Programming, EP) 그래프와 트리 등을 염색체 표현에 사용 진화적 전략(Evolutionary Strategy, ES) 실수의 값을 갖는 염색체 사용 연산자 교배(Crossover) : GA, GP 돌연변이(Mutation) : EP, ES

7

진화적 연산 (3)진화적 연산의 다른 형태 개미 식민지 모델(ant colony model) 스웜(군중, swarm) 미메틱 알고리즘(memetic algorithm)

8

진화적 알고리즘 종류 비교

9

진화적 알고리즘 종류 비교

10

진화적 연산 (4)진화적 연산에 대한 기본 구성 요소 적응도(fitness) 개체가 장래의 세대에 영향을 주는 범위를 결정 생식 오퍼레이터(reproduction operator) 개체가 다음 세대에 자손을 생성 유전자 오퍼레이터(genetic operator) 부모의 유전자 정보로부터 자손의 유전자 정보를 결정

11

진화적 연산 (5)진화적 프로세스 선택(Selection) 돌연변이(Mutation) 생식(Reproduction) 기존의 최적화 알고리즘과 차이점 기존의 최적화 알고리즘 점에서 점으로의 해를 구하는 국소 탐색 법 진화적 알고리즘 개체군을 이용해서 해를 구함 목적 함수의 연속성과 미분 가능성에 관계없이 적용 가능 결정 법칙이 아닌 확률론적으로 변화하는 법칙 사용

12

생물학과 GA 용어비교 (1)

13

생물학과 GA 용어비교 (1)

14

생물학과 GA 용어비교 (1)길이가 n인 염색체 염색체 벡터 유전자(gene) xi 알파벳 : 이진수로 구성 Schema 우수한 형질의 생성에 기여한 문자열의 집합

Browse More Presentations

Last Updated: 8th March 2018