* 지능 : 끊임없이 변하는 환경에 적응하는 능력 / 자연에 적응해가는 방법, 능력
> 이점을 이용한 인공지능 연산법이 진화 연산이다.
> 진화연산 : 기계 학습에 대해서 진화론적 방법론을 사용한 유전학 계산 모델
* 진화연산
- 종류 : 유전 알고리즘, 진화 전략, 유전 프로그래밍
- 사용 기법 : 선택(Selection), 변이(Mutation), 교배(Crossover)
- 최적화 과정 : 진화 적합성, 적응형 위상 개념을 사용
> 진화 적합성(evolutionary fitness) : 진화 = 특정 환경에서 집단이 생존하여 교배를 하여 재생산하고, 이를 바탕으로
집단의 능력을 유지 향상 시키는 과정
> 적응형 위상(adaptive topology) : 위에서 집단의 능력을 유지또는 향상 시킨다고 했는데,
향상된 개체를 선택하고 유지하는데 필요한 값(적합도)응 이용한다.
: 연속형 함수로 동적인 자연의 위상을 따라한다.
* 컴퓨터에서 진화 과정을 나타내기
- "개체 집단 생성 > 적합도 평가 > 유전 연산자 적용 > 새로운 집단 생성"의 과정이 반복된다.
- "인코딩"과 "평가"를 사용한다.
> 인코딩 : 문제를 풀기 위해서 각각의 개체 집단을 어떻게 표현할 것인가? 모든 문제에 딱맞는 인코딩 법은 없다.
> 평가 : 생성한 집단에서 각각 개체의 성능을 평가할 함수를 생성해야 한다.
- 재생산이 여러번 반보고딘 결과 적합도가 낮은 염색체는 소멸되고 살아남은 염색체가 해집단을 체우기 시작한다.
* 유전 알고리즘
- 인공적인 염색체로 이뤄진 한 해집단에서 다른 해집단으로 넘어가는 절차적 단계에 선택과 교차, 변이 연산을 사용한 것
- 인공적인 염색체를 어떻게 나타내는 가는 인코딩 문제로 대체로 1과 0으로 된 문자열을 사용한다.
- 0과 1로 이뤄진 문자열을 염색체(Chromosome)이라고 하며, 각각의 1과 0 하나하나 원소를 유전자(gene)라고 한다.
- 알고리즘
1단계 : 문제 변수의 영역을 어떻게 표현할 것인지 선택(Encoding), 해집단의 크기 N, 교차율 Pc, 변이율 Pm을 설정
> 해집단 크기 N : Population size라고도 한다. 처리하는 데이터 양(크기)이 클수록 느리지만 원하는 해에 갈 확률이 높다.
(적정 수치 : 50)
> 교차율 Pc : Crossover probability. 두개의 개체가 교배할 확률. 0.7정도의 수치로 정하는 것이 좋다.
> 변이율 Pm : Mutation probability. 선택된 개체의 유전자가 변이될 확률. 0.001 정도가 좋다.
2단계 : 적합도를 측정하는 함수를 정의 한다. 이 함수에 의해서 측정된 적합도는 재생산 과정에서 중요한 역할을 한다.
3단계 : 염색체 N개를 난수를 이용하여 생성한다. 여기서 생성된 난수를 해집단이라고 한다.
###
4단계 : 각각의 염색체의 적합도를 측정한다.
> 적합도가 원하는 값이 나온다면 알고리즘을 빠져 나간다.(종료조건)
######
5단계 : 짝지을 염색체 한쌍을 선택한다. 적합도가 높은 염색체가 적합도가 낮은 염색체보다 더 많이 선택되야 한다.
> 어떻게 해야 적합도가 높은 염색체가 더 많이 선택될까?
> 염색체 선택 기법으로 가장 많이 쓰이는 것은 "룰렛 휠 선택"이다.
~ 룰렛 휠 선택 : 각각의 염색체에 대한 적합도를 100분위 비율로 나타낸 후, 0부터 각각의 염색체를 그려논다.
~ 0~100까지의 난수를 생성하여 나온 숫자를 포함하고 있는 염색체가 선택된다.
~ 적합도가 높을 수록 차지하는 범위가 넓기 때문에 더 많이 선택 될 것이다.
6단계 : 교차와 변이를 적용하여 자식 염색체 한쌍을 만든다.
> 0~1 사이의 난수를 발생하여 교차율 Pc보다 작을 경우 교배를 한다.
> 교배를 할 때에는 1에서 염색체의 길이까지의 난수를 발생시켜, 염색체를 교환할 지점을 정한다.(교차점)
> 교차점 뒤의 염색체를 선택된 한쌍이 서로 교환을 한다.
> 각각 하나의 유전자를 이동 하면서, 0~1 사이의 난수를 발생하여 교차율 Pm보다 작을 경우 변이를 시킨다.
7단계 : 새로 만들어진 한쌍의 염색체를 새로운 해집단으로 만든다.
8단계 : 새로운 해집단의 크기가 N이 될때까지 5단계(#####)부터 현단계 까지 반복한다.
9단계 : 새로운 해집단을 현재의 해집단으로 변경한다.
10단계 : 4단계(###)로 돌아가서 현재까지의 과정을 반복한다.
- 종료조건은 4단계에서 측정한 적합도를 이용하거나, 특정 세대 즉, 4~10을 어느 정도 반복하면 그만두게 설정을 한다.
(무한의 loop을 돌아도 원하는 적합도가 나오지 않을 경우가 있기 때문에...)
- 난수로 시작하므로 원하는 겨로가가 나오지 않으면 다시 프로그램을 실행한다.
- 몇번 실행해도 결과가 나오지 않으면 교차율, 변이율등의 변수를 변경한다.