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

Presentation on theme: "제 4 장 유전자 알고리즘 (Genetic Algorithm)"— 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 진화적 알고리즘 종류 비교 진화적 전략(ES) 진화적 프로그래밍(EP) 유전자 알고리즘(GA) 유젼자 프로그래밍(GP) 기원
진화적 전략(ES) 진화적 프로그래밍(EP) 유전자 알고리즘(GA) 유젼자 프로그래밍(GP) 기원 Rechenberg, I.(1963) Fogel, L.J. Holland, J.H.(1975) Koza, J.(1990) 표현 방식 실수. 길이 고정 실수, 이산치. 크기 고정 이진 문자열 실수형도 가능(0/1). 기본함수. 크기가변 자기 적응성 표준편차와 상호분산 표준편차(메타-진화프로그래밍의 경우) 없음(메타-유전자 알고리즘의 경우는 가능) 적합도 목적함수 값 비율에 의해 조정된 목적함수 값 문제표현 벡터 그래프 스트링 트리

9 진화적 알고리즘 종류 비교 진화적 전략(ES) 진화적 프로그래밍(EP) 유전자 알고리즘(GA) 유젼자 프로그래밍(GP) 교배
진화적 전략(ES) 진화적 프로그래밍(EP) 유전자 알고리즘(GA) 유젼자 프로그래밍(GP) 교배 자기-적응성에 중요 없음 주요 연산자 선택 결정론적이며 소멸성있음 승자승 원리를 통한 확률적 선택 소멸성 있음 확률적이지만 보존성이 있음 특징 및 응용분야 종에 속한 개체의 수준에서 진화를 모방한 것으로 다양한 교배 과정이 있을 수 있음. 실수치 탐색 종의 수준에서 진화를 모방한 것으로 교배 과정이 없음. 오토마타 합성 종에 속한 개체의 수준에서 진화를 모방한 것으로 다양한 교배과정이 있을 수 있음. 자연 진화원리에 가장 가까움. 문자열 벡터열 탐색 프로그램 합성

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

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

12 생물학과 GA 용어비교 (1) 생물학 유전자 알고리즘(GA) 개체 (individual)
염색체에 의해 특징지어지는 자율적인 하나의 작은 집단 집단 (population) 집단 내의 개체의 수 유전자 (gene) 개체의 형질을 규정하는 기본 구성요소 즉, 특성(feature), 형질(character) 등 염색체 (chromosome) 복수의 유전자 모임. 문자열(string)로 표현 대립 유전자 (allele) 유전자가 갖는 특성 값(feature value). 유전자 자리 (locus) 염색체상의 유전자의 위치 즉, 문자열의 위치 (string position)

13 생물학과 GA 용어비교 (1) 생물학 유전자 알고리즘(GA) 적합도 또는 적응도 (fitness)
유전자의 각 개체의 환경에 대한 적합의 비율을 평가하는 값 즉, 평가치로 최적화 문제를 대상으로 하는 경우 목적함수 값이나 제약조건을 고려하여 페널티 함수 값의 적응도로 설정된다. 코딩(coding) 표현 디코딩에서 유전자형으로 매핑하는 것 디코딩 (decoding) 유전자 형에서 표현형으로 역 매핑하는 것 유전자형 (genotype) 형질의 염색체에 의한 내부적으로 표현하는 방법으로 구조체(structure)로 표현 표현형 (phenotype) 염색체에 의해 규정된 형질을 외부적으로 표현하는 방법으로 파라메터 집합(parameter set), 대체해(alternative solution),디코드화를 위한 구조체(decoded structure)로 표현

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