46
6.5장 진화 알고리즘
6.5장 진화 알고리즘
유전자형과 표현형 : Genotype & Phenotype 유전 형질의 내장 & 발현
유전체: Genom
한 개체 유전자의 총 염기 서열
48
6.5장 진화 알고리즘
진화의 시작
염색체 복제시 오류 & 염색체 구성시 오류
Digital Convergence 제6장 진화론과 융합
아버지 어머니
F1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 F3 = c1 c2 c3 c4 c5 c6 c7 c8 c9 c10
M2 = b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 M4 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 복제 복제
F1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 F3 = c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 M2 = b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 M4 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10
자식 염색체 생성
F1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 M4 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10
6.5장 진화 알고리즘
자식 염색체 의 표현 과정
F1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
M4 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 (1)
F1 = A1 A2 A3 A4 A5 a6 a7 a8 a9 a10 F1 = a1 a2 a3 a4 a5 A6 A7 A8 A9 A10
M4 = d1 d2 d3 d4 d5 D6 D7 D8 D9 D10 M4 = D1 D2 D3 D4 D5 d6 d7 d8 d9 d10 (2) C1 (3) C2
C1 = a1 a2 a3 a4 a5 d6 d7 d8 d9 d10 C2 = d1 d2 d3 d4 d5 a6 a7 a8 a9 a10
(4) C1 의 표현형 (5) C2의 표현형
50
6.5장 진화 알고리즘
진화 알고리즘의 구성 요소
Digital Convergence 제6장 진화론과 융합
구분 종류 내역
개체군 염색체들의 집합 정해진 개수의 염색체로 구성
유전 연산자
선택 적응도 높은 유전자
교배 두 염색체 사이에 유전자 교환
돌연변이 유전자를 강제로 교환
대치 부모의 염색체를 자식 염색체로 대치
알고리즘 준비 코드화 문제의 해를 염색체로 표현 적합도 함수 알고리즘을 평가하는 함수
알고리즘 설계 응용 프로그램 현실 문제를 해결하는 프로그램 개발
6.5장 진화 알고리즘
유전 연산자
단순 교배
복수점 교배
P1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 P2 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10
C1 = a1 a2 a3 a4 a5 d6 d7 d8 d9 d10 C2 = d1 d2 d3 d4 d5 a6 a7 a8 a9 a10
P1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 P2 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10
52
6.5장 진화 알고리즘
유전 연산자
균일 교배
돌연변이
Digital Convergence 제6장 진화론과 융합
P1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 P2 = d1 d2 d3 d4 d5 d6 d7 d8 d9 d10
m = 1 0 0 0 1 0 1 0 0 1 m = 1 0 0 0 1 0 1 0 0 1
C1 = a1 b2 b3 b4 a5 d6 a7 d8 d9 a10 C2 = d1 a2 a3 a4 d5 a6 d7 a8 a9 d10
P1 = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
C1 = a1 a2 a3 a4 A5 d6 d7 d8 a9 a10
6.5장 진화 알고리즘
진화 알고리즘 실례 배낭 문제
Population
Selection Crossover
Mutation
Reproduction Substitution
(1,5,3) (7,0,6) (8,9,6) (3,7,6)
(8,9,6) (7,0,6)
피 피 피 피 피
(8,0,6) (7,9,6)
(8,3,6) (7,9,6)
54
6.5장 진화 알고리즘
진화 알고리즘의 순서도
Digital Convergence 제6장 진화론과 융합
n개의 초기 염색체 생성 repeat {
for i = 1 to k {
두 염색체 p1, p2 선택
offspringi = crossover(p1, p2);
offspringi = mutation(offspringi );
}
offspringi, ... offspringk 를 해집단 안의 k 개의 염색체와 대치
} until (정지조건 만족);
return 최상의 염색체;
시작
종료 4: 선택 실행
5: 교배 실행 2: 초기 집단 생성
1: 유전자형 결정
6: 돌연변이 실행 3: 적합도( ) yes
만족?
Loop
6.5장 진화 알고리즘
진화 알고리즘 응용분야
응용 분야 응용 사례
최적화 순회판매원 문제, 전력 송전망 최적화, 항공기 승무원 배정
설계 반도체 회로 설계, 비행기 날개 설계 인공지능 신경망 합성 및 학습, 자연언어 처리 시스템 분석과 예측 환율 변화 예측, 증권 등 경제분야 예측
56
6.5장 진화 알고리즘
진화 알고리즘 적용 분야의 일반성 효과적인 분야
Digital Convergence 제6장 진화론과 융합
- 어느 정도의 규칙성을 가지고 있는 문제 - 여러 개의 국부적 해가 존재하는 문제
- 문제 영역의 규칙성이 어느 정도 염색체로 표현 가능한 문제
- 부분적인 해들 간에 상대적인 우위 관계가 존재하는 문제
- 잘 정의된 알고리즘이 존재하는 문제 - 최단 경로 탐색 문제, 정렬 등
비효과적인 분야
- 순회 판매원 문제(salesman's problem) - 함수 값을 최대화하는 변수
6.5장 진화 알고리즘
진화 알고리즘의 장점
- 알고리즘의 개념을 이해하기 쉽다.
- 기존 문제 해결 방법과 결합하여 사용하기 쉽다.
- 진화 알고리즘의 계산 모델이 자연현상에 기반을 두고 있다.
- 응용문제와 분리하여 모듈화하기 쉽다.
- 항상 해답이 있으며 시간이 갈수록 효과가 좋아진다.
- 주어진 문제를 해결하기 위한 일반적인 방법이 없다.
- 매개변수들이 너무 많다(개체수, 선택방법, 교배법, 돌연변이의 비율 등).
진화 알고리즘의 단점
58