유전자 알고리즘(Genetic Algorithm)

Slides:



Advertisements
Similar presentations
Local Search and Optimization 부산대학교 인공지능연구실 김민호
Advertisements

주기율표 제 8장제 8장 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Ⅱ 세포의 주기와 생명의 연속성 Ⅱ 세포의 주기와 생명의 연속성 - 1. 세포주기와 세포분열.
Deep Learning.
컴퓨터프로그래밍 1주차실습자료 Visual Studio 2005 사용법 익히기.
Chap. 9 Genetic Algorithms
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
신호처리 실험 (Signal Processing Lab)
제 4 장 유전자 알고리즘 (Genetic Algorithm)
Java로 배우는 디자인패턴 입문 Chapter 5. Singleton 단 하나의 인스턴스
제 9 장 구조체와 공용체.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
제4장 자연언어처리, 인공지능, 기계학습.
Open Graphics Library 팀 명 : Spes 송정웅 김정환
공개키 암호화 프로그래밍 전자상거래보안.
제3장 스택과 큐.
08. 선천성 및 유소아 질환 1. 선천성 유전질환 1) 유전학적으로 본 병인의 분류
Error Detection and Correction
23장. 구조체와 사용자 정의 자료형 2.
임베디드 실습 # LED, 7’Segment 제어
Automatic Music Transcription
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
프로그래밍 랩 – 7주 리스트.
<소스코딩(Source Coding)> 제4장 가변길이 코드
11장. 1차원 배열.
C#.
9장. 특징 선택 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
프로그래밍 개요
Genetic Programmed Soccer Softbot
군집 분석.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
시뮬레이션 기반 가상 보조기구 알고리즘 최적화
작곡자 베토벤( ) 고전파 시대 음악가, 독일 빈 음악가 집안에서 태어나 어린시절부터 아버지에게 피아노를 배웠다. 하이든과 여러 음악가들에게 가르침을 받으면서 성장하였다. 하이든, 모차르트의 뒤를 이어 고전파 음악을 완성시켰고, 고전파와 낭만파 음악의.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
2장. 변수와 타입.
두 모집단에 대한 검정.
기상 레이더 정보를 이용한 획기적인 LID시설 제어 방법 GIST대학 물리학부 정희원 GIST대학 기초교육학부 박연준, 기태윤
제19장 솔로우 모형 제1절: 인구가 일정하고 기술진보가 없는 경우 제2절: 인구가 증가하는 경우
Ch07_진화 연산.
논문작성을 위한 연구모형 설정 양동훈.
VHDL를 이용한 DES 설계 정보통신컴퓨터공학부 5조 김인옥, 백미숙
공명과 화음(resonance and harmony)
알고리즘 알고리즘이란 무엇인가?.
클러스터 시스템에서 효과적인 미디어 트랜스코딩 부하분산 정책
제 4 장 유전자 알고리즘 (Genetic Algorithm)
개 념 개요 지능을 가진 객체의 특징 컴퓨터에게 지능 부여 학습의 일반적 정의 새로운 환경에 적응
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
Flow Diagram IV While.
제 8장. 클래스의 활용 학기 프로그래밍언어및실습 (C++).
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
Coding for Kids.
9 장 오류 검출 및 오류 정정 9.1 오류 종류 9.2 검출 9.3 오류 정정 9.4 요약.
19장 소진화와 변화하는 유전자.
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
Additional fitness measures for Sequence Generation
수치해석 ch3 환경공학과 김지숙.
DNA Implementation of Version Space Learning
Chapter 7. A3C Ho-Bin Choi A3C.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
어서와 C언어는 처음이지 제21장.
NACST progress report 신수용.
작곡자 베토벤( ) 고전파 시대 음악가, 독일 빈 음악가 집안에서 태어나 어린시절부터 아버지에게 피아노를 배웠다. 하이든과 여러 음악가들에게 가르침을 받으면서 성장하였다. 하이든, 모차르트의 뒤를 이어 고전파 음악을 완성시켰고, 고전파와 낭만파 음악의.
문제의 답안 잘 생각해 보시기 바랍니다..
강화학습: 기초.
C++ Espresso 제15장 STL 알고리즘.
생명의 청사진 분자유전체의학 김 경 원.
Presentation transcript:

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

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

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

기본 알고리즘 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에 추가

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에서 가장 높은 적합도를 가진 가설을 반환한다

유전자 알고리즘의 구조 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

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

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, 18-18-18-24, ….. double evaluate_rhythm_repetitions(CRO c);

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

랜덤

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

Auto Paint Generator