유전자 알고리즘(Genetic Algorithm)

Presentation on theme: "유전자 알고리즘(Genetic Algorithm)"— Presentation transcript:

1 유전자 알고리즘(Genetic Algorithm)
자연의 진화 과정을 모델링 신경망과 같이 자연 현상을 모델로 해를 탐색 60/70년대에 시작(Holland 등) 장점 기본적인 구조가 간단, 구현이 용이 대규모 후보 해답(가설)을 병렬로 처리 지역적 최적해에 멈추지 않고, 발견될 것이 있으면 항상 발견한다. (If there is something there to be found, it usually is.) 신경망은 local minima에 빠질 위험이 있음 단점/유의사항 종의 개량이 우연적인 요소에 의존 주어진 문제를 제한된 형태의 스트링(string)으로 표현할 수 있어야 함 코딩(표현 공학: representation engineering)과 효과적인 돌연변이 연산자 발견이 중요

2 알고리즘 적용 절차 문제를 제한된 알파벳의 스트링으로 코딩 해답들이 경쟁하고 결합할 수 있는 인공환경을 생성
Bit-string(다른 표현도 있음) Outlook={Sunny,Overcast,Rain}, Wind={String,Weak} (Outlook = Overcast  Rain)  (Wind = Strong) Outlook Wind IF Wind=Strong THEN PlayTennis = yes Outlook Wind PlayTennins => “ ”: 개체(individual) 해답들이 경쟁하고 결합할 수 있는 인공환경을 생성 적합도 함수(fitness function)의 정의 주어진 문제에 대해 개체로 표현된 해가 얼마나 좋은지를 판단 예) “ ”라는 개체가 전체 학습 예제 14개 중 12개에 대해 맞추면 6/7의 적합도를 가진다

3 후보 해답의 결합 방법 개발 잘 분포된 초기 개체의 생성 및 진화 교차(crossover) 돌연변이(mutation)
예) 부모: , (교차지점=3) => 자식: , 돌연변이(mutation) 예) 돌연변이 전: (변이비트=4) 돌연변이 후: 잘 분포된 초기 개체의 생성 및 진화 각 세대에서 부실 해답 개체를 제거(도태)하고 우수 해답 개체의 자손으로 ‘진화’하도록 함

4 기본 알고리즘 GA(Fitness, f-임계치, p, r, m) 개체군의 초기화: P ← p개의 가설을 무작위로 생성
p: population(개체군)에 포함되는 가설의 수 r: 각 단계에서 교차(crossover)에 의해 대체되는 개체군의 비율 m: 돌연변이 비율(mutation rate) 개체군의 초기화: P ← p개의 가설을 무작위로 생성 평가(evaluate): P의 각 가설 h에 대하여 Fitness(h)를 계산 While (최대 fitness < f-임계치) do 다음 세대(generation), Ps를 생성: 1. Select: 아래 확률에 따라 P에서 (1-r)p개의 개체를 선택하여 Ps에 추가

5 P에서 가장 높은 적합도를 가진 가설을 반환한다
2. Crossover: P로부터, 앞의 확률 Pr(hi) 에 따라, r•p/2 쌍의 가설을 선택한다. 각 쌍 <h1, h2>에 대해, 교차(Crossover) 연산에 의해 두 자식(offspring)을 생성하여 Ps에 추가 3. Mutate: Ps 중에서 동일한 확률로 m 퍼센트를 골라, 각기 하나의 무작위 선택된 비트를 바꾼다(invert) 4. Update: P ← Ps 5. Evaluate: P의 각 가설 h에 대하여, Fitness(h)를 계산 P에서 가장 높은 적합도를 가진 가설을 반환한다

6 유전자 알고리즘의 구조 selection cross over mutation 적합도(fitness) 평가 selection
1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 3 2 4 1 2 3 4 5 1 reproduction 1 Gene 1 2 3 4 5 1 1 1 1 적합도(fitness) 평가 1 1 1 Chromosome 1 1 5 3 2 4 1 1 1 Population (Generation 0) 1 Next Generation 1 1 1 Population (Generation 1) selection

7 Auto Composer 하나의 gene은 단위 음을 표현
음 높이 chromosome과 음 길이 chromosome의 쌍으로 한 소절(네 마디)을 표현 chromosome 미 솔 도 파 레 12 6 18 마디 경계 쉼 gene

8 Auto Composer Fitness 함수의 구성
Harmony of balance, symmetricity, and variance 균형, 대칭, 변화의 조화 반복 요소(balance or symmetricity) 평가 음의 한 단계 증가/감소 반복 도-레-미, 솔-파-미-레, … double evaluate_continuous_notes(CRO c); 음의 화음 내 점프 반복 미-솔-도-미(C), 솔-시-레-파(G7), … double evaluate_jumping_notes(CRO c); 박자 조합의 반복 동일한 형태의 박자 조합의 반복 6-6-12, , ….. double evaluate_rhythm_repetitions(CRO c);

9 Auto Composer 변형(variance) 요소 평가 적절한 빈도의 반음 사용 반복 전후의 음의 커다란 점프
미-레-도-미-피(F#)-솔 : 미국 국가 double evaluate_half_notes(CRO c); 반복 전후의 음의 커다란 점프 파미미-파미미-파미 미-도 : 모짜르트 교향곡 40번 double evaluate_big_Jump_notes(CRO c); 같은 음 길이의 반복 전후의 음 길이 변화 double evaluate_big_Jump_notes(CRO c); 베토벤 합창

10 랜덤

11 Auto Composer 생성 사례 개선 사항 코드 정보의 활용 (화성학에서의 코드 진행)
테마 generation => 전곡 generation

12 Auto Paint Generator

13

14