유전 알고리즘 - 기계 학습 발표 2008년 5월 15일 Computer Vision Lab. 이 득 용

Computer Vision Lab. (cv.chonbuk.ac.kr) Index 개념 해 표현 유전 연산 선택 연산 교차 연산 변이 연산 대치 적합도 계산 매개 변수 설정과 선택압 찬반 논쟁 Computer Vision Lab. (cv.chonbuk.ac.kr)

유전 알고리즘 -개념 자연세계의 진화과정을 컴퓨터 상에서 시뮬레이션 함으로 써 복잡한 실세계의 문제를 해결하고자 하는 계산 모델 적응적 탐색과 학습 및 최적화를 통한 공학적인 문제의 해 결에 많이 이용되고 있음

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 -개념 1960년대 독일인 대학원생인 Rechenberg 와 Schwefel에 의 해 제안 현재 해에 정규 분포로 얻은 값을 합하는 것으로 유전 알고리즘의 변이 연산에 해당, 지역 최적점에서 탈출할 수 있도록 해줌. 기존 미분에 기반한 최적화 알고리즘과의 차이점 초기 해를 여러 개 생성하여 이것을 조금씩 개선 Computer Vision Lab. (cv.chonbuk.ac.kr)

유전 알고리즘 -개념 procedure SGA() initialize(Population); evaluate(Population); while not (terminal condition satisfied) do MatingPool = reproduce(Population); MutationPool = crossover(MatingPool); Population = mutation(MutationPool); end while end procedure

유전 알고리즘 -개념 유전자 알고리즘과 다른 탐색, 최적화 방법과 다른점 파라메터를 코딩한 것을 직접 이용한다. 점(point)이 아닌 다점(multi points, : 군 (population) )탐색 방법이다. 탐색에 비용 정보(fitness function)를 이용하며, blind search를 한다. Blind search : 미분값이나 다른 부가적인 지식을 요구하지 않는다. 결정론적인 규칙이 없고 확률적 연산자를 사용하여 수행 된다. 이와 같은 특징으로 다른 탐색 또는 최적화 방법 중 하나인 계산에 의존하는 방법(calculus-based method: hill-climbing)에 비하여 전역적 해를 구할 가능성이 높으며 다른 여러 탐색 방법에 비하여 효 율적이다.

유전 알고리즘 -염색체 염색체(Chromosome) 1 2 3 4 5 6 7 8 유전자(gene) 염색체는 생물의 염색체처럼 각 해의 특성을 표기할 수 있어야 한다. 유전자 알고리즘으로 문제를 효율적으로 풀기 위해서는 이 염색체의 정의가 가장 중 요함 염색체(Chromosome) 1 2 3 4 5 6 7 8 유전자(gene)

유전 알고리즘 -염색체 이진수 표현 실수 표현 위치 기반 표현

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 -선택 연산 교차에 쓰이는 두 개의 부모해를 고르기 위한 연산 우수한 해가 선택될 확률이 커야 하지만, 열등한 해도 낮은 확률이지만 선택될 기회가 주어져야 함. 연산의 종류 품질 비례/ 룰렛휠 선택(Propartionate selection / roulete selection) 토너먼트 선택(tournament selection) 순위 기반 선택(ranking selection) 엘리트 보존선택(Elitist preserving selection) 공유(sharing) Etc. Computer Vision Lab. (cv.chonbuk.ac.kr)

유전 알고리즘 -선택 연산 적합도 함수(Fitness Function) 목적함수(Objective function)즉, 최적화 하고자 하는 함수는 각 개체의 적합도를 평가하는 기반 목적함수 ? 보통 정해진 구간 사이의 양수값을 갖도록 표준화된 값을 사용 표준화 하기 이전 값을 row fitness라고 하며, 표준화 되어서 실제로 개체 선택의 기준이 되는 함수를 적합도 함수(fitness function)라고 한다.

유전 알고리즘 -선택 연산 품질 비례/ 룰렛휠 선택(Propartionate selection / roulete selection) 각 해들은 각각 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도 보다 k배가 되도록 조절한다. 예) 해집단 내의 해 I의 적합도는 Fi=(Cw-Ci)+(Cw-Cb)/(K-1), k>1 Cw : 해집단 내에서 가장 나쁜 해의 비용 Cb : 해집단 내에서 가장 좋은 해의 비용 Ci : 해 i의 비용 K값을 높이면 선택압이 높아 진다. 일반적으로 k의 값은 3~4 이 적합도 값을 기준으로 룰렛휠 선택을 한다. 각 염색체의 개수만큼 룰렛휠을 만들고 적합도에 맞게 룰렛휠의 영역을 할당함. 룰렛휠의 공간배정 [룰렛휠의 구현] point=random()%SumOfFitnesses; sum=0; For i=0 to N-1{ sum=sum+Fi; if(point<sum) return i; } F2 F1 F3 F4 F5 F6 F7

유전 알고리즘 -선택 연산 토너먼트 선택(tournament selection) 가장 간단한 토너먼트 선택은 두 개의 염색체를 임의로 선택한 다음 [0,1) 범위의 난수 t를 발생시킨 다음 이것이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택하고 그렇지 않으면 품질이 나쁜것을 선택하는것 t는 파라미터화 할 수 있는 것으로 t값이 높을수록 선택압이 높아 진다. 토너먼트 선택은 대체로 수행에 필요한 시간이 매우 짧은 것이 매력임.

유전 알고리즘 -선택 연산 순위 기반 선택(ranking selection) 해집단 내의 해들을 품질 순으로 ‘순위’를 매긴 다음 가장 좋은 해 부터 일차 함수적으로 적합도를 배정하는 방법 예) Fi=MAX+(i-1)*(MIN-MAX)/(N-1) MAX와 MIN 값의 차이를 바꿈에 의해 선택압을 조절할 수 있고 해들의 적합도는 MAX와 MIN사이에서 ‘균일’한 간격으로 분포하게 된다.

선택 연산 엘리트 보존선택(Elitist preserving selection) “De Jong의 엘리트 선택 정의 “ 확률에 따라 개체를 선택하여 교배 및 돌연변이의 결과로 특별히 좋은 해가 소실되는 것을 막기 위하여 가장 좋은 해를 보존하여 다음 세대에 남기는 방법 일반적으로 다른 선택방법과 융합하여 사용 “De Jong의 엘리트 선택 정의 “ S(t)를 세대 t의 가장 좋은 개체라 하자 또 X(t+1)을 보통의 방법으로 생성할 때 X(t+1)중에 S(t)가 존재하지 않으면 S(t)를 X(t+1)의 N+1번째 개체로 추가한다. 가장 좋은 해를 잃지 않고 보존하는 대신 엘리트개체의 유전자가 개체군 전체로 급속히 퍼져나갈 가능성이 높기 때문에 국소적인 해로 수렴할 위험이 있음

유전 알고리즘 -선택 연산 엘리트 보존선택(Elitist preserving selection) T세대 T+1세대 Elistist Preserving Selection F(x)=10 F(x) = 8 F(x) = 12 F(x) = 5 F(x) = 10 F(x) = 3 F(x) = 7 F(x)=12 Roulette Wheel Selection 7/55 10/55 8/55 3/55 10/55 12/55 T세대 5/55 T+1세대

선택 연산 공유(sharing) 해집단의 다양성을 보다 오래 유지하고자 하는 목적에서 고안 되었다 품질 비례선택이나 순위 기반 선택에서 쓰는 적합도를 구한다. 여기에 해당 염색체가 해집단 내의 나머지 염색체들과 유사한 (특징을 ‘공유’)정도가 높을 수록 큰 값으로 나누어 적합도를 조정한다. 예) 공유는 두 염색체의 차이를 계산하는 기준을 잡는 방법에 따라 유전자형 공유와 표현형 공유로 나눌수 있다. 유전자형 공유: dij를 위해 염색체의 모양 그 자체가 다른 정도를 사용 (예, 해밍거리:Hamming distance) 표현형 공유 : 표현형의 차이를 계산 기준으로 삼는것

유전 알고리즘 -교차 연산 교차 연산에서는 부모의 선택뿐 만 아니라 어떠한 부분 을 교차할 것인가도 중요 교배의 종류 일점교차(one point crossover) 다점교차(multi point crossover) 균등교차(uniform crossover) 사이클교차(cycle crossover) 순서교차(ordered crossover) 부분일치교차(partially matched crossover: PMX) 산술적교차(arithmetical crossover)

유전 알고리즘 -교차 연산 일점교차(one point crossover) 대표적인 교차 연산 길이가 N인 일차원 문자열로 된 염색체 상에서 일점 교차로 자르는 방법의 총 수는 N-1가지임.

유전 알고리즘 -교차 연산 다점교차(multi point crossover) 스키마의 파손 확률 일점 교차 보다 자르는 방법의 수가 많음 염색체의 길이가 n일때 k점 교차로 자르는 방법의 총 수는 n-1Ck가지 다점 교차는 일점 교차보다 교란(Perturbation)의 정도가 크다. 보다 넓은 탐색 공간을 탐색할 수 있다 교란이 강하면 수렴성이 떨어짐 스키마가 파손될 확률이 높다. 대신에 새로운 스키마의 생성을 더 다양하게 할수 있다. 혼합형 유전 알고리즘에 어울림 지역 최적화 기능으로 교란에 대한 회복력이 있음. 스키마의 파손 확률 자름선의 개수에 영향을 많이 받는다. 자름선의 개수가 짝수일 때가 홀수일 때보다 스키마의 길이에 덜 영향을 받음 염색체의 첫번째 유전자와 마지막 유전자가 인접한것 같은 효과가 있어 사실상 고리모양을 하고 있음

교차(Cross over) Po=0.6 균등교차(uniform crossover) 자름선을 이용하지 않음 균등교차는 자름선을 이용하지 않으므로 일점 교차나 다점 교차에 비해 스키마의 결합 형태가 다양함. 스키마의 특정 기호의 위치가 거의 영향을 미치지 않는다. 교란의 정도가 크므로 수렴 시간이 오래 걸린다. j i h g f e d c b a t s r q p o n m l k 0.19 0.42 0.72 0.44 0.66 0.91 0.89 0.33 0.27 0.83 s1 s2 offspring 난수 ㅣ Po=0.6 두 부모해를 S1,S2라 하고 각각의 유전자 위치에 대하여 난수를 발생한 다음 이 값이 Po 이상이면 해당 S1의 같은 위치로 부터 유전자를 복사해 오고 그렇지 않으면 S2의 같은 위치로 부터 복사를 한다.

유전 알고리즘 -교차 연산 사이클교차(cycle crossover) : 염색체가 순열로 표현되는 경우에 적용 s1 2 5 9 4 3 6 1 7 8 s1 S1의 첫 번째 유전자(8)로 부터 복사를 시작. S2의 유전자는 0이므로 S1상의 0이 있 는 위치를 찾아 자식해의 같은 위치에 0을 복사 한다. 같은 방법으로 복사를 수행 9 8 7 6 5 1 3 4 2 s2 offspring 5 3 8 2 5 9 4 3 6 1 7 8 s1 다음으로 자식해의 유전자 값이 아직 결정되지 않은 위치들중 가장 왼쪽의 위치로 부터 시작하는데 이번에는 S2로 부터 시작한다. 9 8 7 6 5 1 3 4 2 s2 offspring 9 5 7 3 2 8 이렇게 S1과 S2를 번갈아 시작하면서 더 이상 결정되지 않은 값이 없을 때 까지 수행 offspring 9 5 7 4 3 6 1 2 8

유전 알고리즘 -교차 연산 순서교차(ordered crossover) 염색채가 순열로 표시되는 경우를 위하여 고안 2 5 9 4 3 6 1 7 8 s1 먼저 임의의 두개의 자름선을 정한 다음 두 자름선 사이에 있는 부분중 S1의 값을 복사한다. 9 8 7 6 5 1 3 4 2 s2 offspring 3 6 2 5 9 4 3 6 1 7 8 s1 나머지는 S2로부터 복사하되 S2의 기호들중 나타나지 않은 것들을 두번째 자름선 부터 시작한다. 9 8 7 6 5 1 3 4 2 s2 6 7 8 9 2 4 3 1 5 offspring 5 1 4 2 3 6 9 8 7 중복은 제거한다.

유전 알고리즘 -교차 연산 부분일치교차(partially matched crossover: PMX) 염색체가 순열로 표시되는 경우를 위하여 고안된 교차 연산 2 5 9 4 3 6 1 7 8 s1 임의로 두 개의 자름선을 정한 다음 두자름선 사이에 있는 부분을 S1으로 부터 복사 한다. 9 8 7 6 5 1 3 4 2 s2 offspring 3 6 2 5 9 4 3 6 1 7 8 s1 나머지 위치는 S2로 부터 복사하되 만일 해당값이 이미 사용 되었으면 같은 값을 가진 S1의 위치를 찾아 같은 위치의 S2로 부터 복사한다. 9 8 7 6 5 1 3 4 2 s2 offspring 9 8 7 6 3 4 2 offspring 9 8 7 1 3 6 4 2 2 5 9 4 3 6 1 7 8 s1 마지막으로 이미중복이 일어난 유전자 는 고쳐 준다. 9 8 7 6 5 1 3 4 2 s2 offspring 9 8 7 1 3 6 4 2 offspring 9 8 7 1 3 6 4 2 5

유전 알고리즘 -교차 연산 산술적교차(arithmetical crossover) 실수 염색체를 사용하는 경우에 사용할 수 있는 교차 연산 산술적 교차는 수의 ‘크기’라는 개념을 교차 행위에 사용하는 점에 큰 매력이 있음 매우 빠른 수렴을 보임(변이를 적절히 조절하여 완전하지 않은 수렴이 되지 않도록 해야 한다. 염색체의 각 위치에 대해 두 부모 염색체의 두 유전자의 값의 평균을 내어 자식해의 해당 위치의 값으로 배정 98.86 8.34 -2.31 12.01 20.43 3.31 1.98 S1 87.44 3.55 2.45 1.44 12.39 2.21 11.28 S1 93.15 5.95 0.06 6.73 16.41 2.76 6.63 offspring

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 -변이 연산 변이: 부모해가 가지지 못한 성질을 부여하여 더 광범위한 탐색 범위 를 확보하는 것. 선택과 교차만으로는 초기 유전자의 조합 이외의 공간을 탐색 할 수 없음 Local Menima에 빠질수 있음 각 유전자 별로 난수 발생, 미리 설정한 변이 확률보다 작으면 0은 1로 1은 0으로 반전 균등 변이와 비균등 변이 수행 후반 최적점에 가까워 지므로 낮은 교차 확률을 사용하여 교란을 줄이는 것 Computer Vision Lab. (cv.chonbuk.ac.kr)

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 -대치 해 집단의 크기는 일정하므로 기존 해 k개를 들어 내고 자식 해를 넣어야 한다. 엘리티즘 (elitism) 현 세대에서 가장 좋은 해 s가 다음 세대에 반드시 생존하도록 보장. Computer Vision Lab. (cv.chonbuk.ac.kr)

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 매개 변수 설정과 선택압 공간 탐색 탐사: 어느 지점을 중심으로 그 근방만을 뒤져 가장 좋은 점을 찾는다. (내리막 경사법, 순차 탐색 알고리즘) 탐험: 전체 공간을 두루두루 살핀다. (임의 탐색 알고리즘) 유전 알고리즘 탐험과 탐사의 절묘한 조화 해 집단의 다양성을 유지함으로써 탐험 실현 우수한 해에게 더 많은 기회를 줌으로써 탐사 실현 Computer Vision Lab. (cv.chonbuk.ac.kr)

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 유전 연산 적절한 선택압의 선택이 중요 높은 선택압: 설익은 수렴 낮은 선택압: 해 집단의 향상이 너무 느려 프로그램의 수행을 중도에 그만두어야 하는 상황 발생 Computer Vision Lab. (cv.chonbuk.ac.kr)

Computer Vision Lab. (cv.chonbuk.ac.kr) 유전 알고리즘 찬반 논쟁 확률 알고리즘 (stochastic algorithms) 찬 새로운 개념과 연산들이 재미 있다. 기존 알고리즘의 한계를 극복할 것 같다. 시간이 더 주면 더 좋은 해를 기대 할 수 있다. 문제에 대한 제약 조건이 적고 응용 범위가 넓다 실제 실험해 보니 성능이 기존 알고리즘보다 좋다. 반 수학적 토대가 약하며 미덥지 못하다. 수행할 때마다 다른 해를 내면 어떻하나? 수행 시간이 길어 실시간 환경에서 활용이 불가능 하다. 실제 실험해 보니 성능이 기존 알고리즘보다 나쁘다. Computer Vision Lab. (cv.chonbuk.ac.kr)

Thanks…