[Data Mining] Genetic Algorithm 유전 알고리즘 / 퀴즈

유전 알고리즘이란?

• Genetic Algorithm: GA
• 생물학적 진화 원리에 기반한 Directed Search Algorithm

 

유전 알고리즘의 응용 예

• 함수 최적화
• 시스템 최적화
• 조합적 최적화
• 분류기

 

유전 알고리즘의 기본 구조

• 생물학에서의 의미
  • 4만 개 내외의 유전자를 포함하고 있는 개체들은 교차에 의해 염색체를 부분 결합하고, 돌연변이에 의해 미소하게 변화된 새로운 염색체를 가진 개체를 만들어 낸다.
  • 개체는 환경에 적응하기 유리한 정도에 따라 선택적(경쟁적으로)으로 번성한다. -> 자연 선택, 적자 생존
• 이러한 생물의 진화 과정을 문제 해결과정으로 옮겨 놓은 것이 유전 알고리즘의 기본 구조

 

유전 알고리즘의 용어 및 특징

• 염색체(chromosome)
  • 문제의 임의의 해를 유전 알고리즘이 이해하는 형태로 표현한 것 
  • 염색체에는 유전자가 들어있다.
• 해집단(population)
  • 정해진 수의 염색체 집단
  • 유전 알고리즘은 복수개의 해를 유지하면서 운용
• 유전자(gene)
  • 염색체상의 각 인자
  • 유전 알고리즘에서 최소 단위

 

유전 알고리즘의 전형적인 구조

• N개의 임의의 해를 해집단(population)으로 생성
• 해집단으로부터 선택(selection), 교차(crossover), 변이(mutation)의 단계를 거쳐 k개의 새로운 해를 생성
• K개의 해를 해집단 내의 K의 해와 대치 
  • 즉, N개의 해집단에서 선택, 교차, 변이를 통해 새로운 k개의 새로운 해를 만들어 N개 중 일부를(K개) replace 하는 것
• 임의의 정지 조건이 만족될 때까지 수행한 후 해집단에 남은 해 중 가장 좋은 해를 반환

 

간단한 유전 알고리즘

{
	population 초기화;
    population 평가;
    
    while (종료 조건 만족하지 않으면){
    	reproduction을 위한 parents 선택;
        recombination과 mutation 수행;
        population 평가
    }
}

 

 

선택(Selection)

• 교차를 위해 해집단에서 임의의 해를 선택하는 연산.
• 우수한 해에게 선택될 확률을 높게 준다.
• 이렇게 선택된 해를 부모해(parent)라 한다.

 

재생산(reproduction)의 GA Cycle

 

Reproduction

• parents는 염색체 평가에 기반해서 랜덤하게 선택된다.

 

Chromosome Modification

• Modification은 확률적으로 발생한다
• 연산 -> mutation(변이), crossover(recombination)(교차)

 

Evaluation

• 유전자의 fitness를 측정

 

Deletion

• 해집단에서 일부만 replace할지, 전체 replace할지 결정

 

 

간단한 예:

• The Traveling Salesman Problem(TSP) -> NP-hard 문제
  • 한 번씩 모든 도시를 방문
  • 전체 이동 거리를 최소화

 

Representation

• Representation은 도시를 방문한 순서를 리스트이다.
• ex)

CityList1     (3   5   7   2   1   6   4   8)

CityList2     (2   5   7   6   8   1   3   4)

 

 

Crossover

• *처럼 자름선을 설정한 하여 교차
• 이러한 연산을 Order1 crossover이라고 한다.

 

Mutation

• * 있는 곳 서로 교환 7<->6

 

* 이렇게 crossover과 mutation을 수행하면서 최적의 cost를 찾는다

 

 

 

GA의 장점

• 이해하기 쉬운 개념
• multi-objective optimization을 지원
  • 목적 함수가 여러개일 때, GA는 이들을 쉽게 optimization할 수 있다.
  • 제약 조건이 많아도 잘 만족시킨다.
• noisy 환경에서 좋다. -> noisy-robust
• 항상 답이 있다. 시간이 지날 수록 좋은 답을 얻는다
• 병렬적으로 상속된다. -> 분산처리가 쉬움

 

GA는 다음과 같을 때 사용한다.

• Alternate solutions이 너무 느리거나 복잡할 때
• 새로운 접근법을 조사하기 위해 exploratory tool이 필요할 때
• GA를 이용해서 이미 해결한 문제와 유사한 문제인 경우
• 존재하는 솔류션과 함께 hybridize를 원할 때
• GA 기술의 문제의 주요 제약조건을 충족하는 경우

 

용어 정리

정지

• 유전 알고리즘이 정지하기 위한 조건
• 대표적인 방법 2가지
  1. Repeat-until 루프를 일정 횟수만큼 수행한 다음 정지시키는 방법
  2. 해집단에 있는 해들의 다양성이 어느 정도 이하로 떨어지는 시점에 정지시키는 방법

 

스키마

• 임의의 염색체가 가지고 있는 부분적인 패턴 

 

표현

• :모든 해를 염색체로 표현하는 방법
• 해는 유전 알고리즘이 이해하는 형태로 표현되어야 한다.
  • 이해 -> 염색체 안에 문제를 푸는 유전 단위를 해석할 수 있도록 구조나 내용을 이해할 수 있는 형태로 표현해야함.

 

역치 연산

• :유전 알고리즘의 수행 중에 일군의 유전자들의 순서를 바꾸어 다시 표현하는 방법
• 만일 유전자 e와 유전자 i가 밀접한 관계를 갖는다면 역치 연산을 통하여 두 유전자가 인접하게 위치함으로써 더 좋은 패턴을 만들 수 있다.

 

위치 기반 표현

• 유전자의 위치가 해당 유전자의 속성과 의미를 결정하게끔 하는 표현
• 한 염색체에서 15번째 유전자는 15번째 변수의 값을 나타냄

 

순서 기반 표현

• 유전자의 위치는 별 의미가 없고 유전자 값들의 상대적 순서가 의미를 갖는 표현 방법

 

* 정리

- 문제의 해는 유전 알고리즘에서 염색체로 표현된다.

- 염색체의 표현 방법이 결정되어야 이에 맞춰서 교차연산(recombination)과 변이 연산(mutation)을 결정할 수 있다.

 

 

 

선택 연산

• :교차에 쓰이는 두 개의 부모해를 고르기 위한 연산
• 우수한 해가 선택될 확률이 높아야 함
• but! 열등하다고 다 배제하면 안된다.
• 선택압이 너무 낮으면 해집단의 평균 품질이 좋아지지 않을 가능성이 많다.
  • 선택압: 적합도 차이의 정도로 프로그래머가 조절할 수 있는 파라미터 

 

 

품질 비례 룰렛 휠 선택

• 가장 대표적인 방법으로, 적합도에 비례하여 확률로 배정된 공간의 크기에서 선택하는 방법
  • ex) 좋은 해의 적합도가 나쁜 해의 적합도가 k배가 되도록 조절

 

교차 연산

• :선택된 두 개의 해를 이용하여 이들을 부분 결합하여 새로운 해를 만드는 방법
• 교차는 두 부모해의 속성을 부분 복사해 새로운 해를 만든 것이므로 교차로 만들어지는 해의 유전자는 모두 부모해로부터 물려받은 것이다.

 

일차원 교차 연산: 일점 교차

• 두 부모해의 동일한 위치에 하나의 자름선을 정하고, 각 부모해로부터 자른 두 부분에서 한 부분 씩 가져와 합쳐 새로운 해를 만드는 방법

 

이차원 교차 연산: 다점 교차

• 두 부모해의 동일한 위치에 여러 개의 자름선을 정하고, 각 부모해로부터 자른 부분에서 한 부분 씩 가져와 합쳐 새로운 해를 만드는 방법
• ex) 삼점 교차

 

 

이차원 교차 연산: 균등 교차

• threshold를 정해서, threshold보다 크면 parent1의 것, 작으면, parent2의 것을 선택

 

 

일차원 교차 연산: 사이클 교차

• : 두 개의 부모해로부터 싸이클을 형성하며 교차하는 연산
• TSP 예처럼 염색체가 순열로 표현되는 경우에 적용 가능한 교차 연산이다.

• 가장 왼쪽부터 시작해서 다음과 같이 8 0 3 5 채우고
• 그 다음은 7->2해서 2 이런식으로 채워 나감

 

일차원 교차 연산: 순서 교차

• 두 자름선 사이에 있는 부분을 S1으로부터 복사 (0, 6, 3)

• 나머지 부분은 S2로부터 복사하되, 두 번째 자름선 바로 다음위치부너 시작해서 이미 사용된 기호는 제이ㅗ하고 순서대로 복사한다. (2, 4, 1, 5, 7, 8, 9)

 

 

일차원 교차 연산: 산술적 교차

• 두 부모 염색체의 두 유전자 값에 대한 평균을 구해 자식해의 해당 위치로 배정하는 교차 연산

 

 

다차원 교차 연산: 지오그래픽 교차

• 자름선에 대해 직선의 제약을 없앤 이차원 교차

 

 

변이 연산

• 교차 연산이 만들어 놓은 해를 미소하게 변형하여 부모해에 없는 속성을 자식해에 도입하는 연산
• 확률적으로 발생시킨다
  • 난수를 생성해 미리 정해 놓은 임계값 미만이면 해당 유전자를 임의로 변형시킴
• 다양성을 높이는 역할을 함
• 해집단의 수렴성이 떨어져 수행시간이 길어지고 개선 속도가 느려 짐
• 생물적으로는 변이가 생물의 경쟁력에 큰 영향을 미치지 않지만, 유전 알고리즘에서 대부분의 변이가 해의 품질에 영향을 미친다.

 

비균등 변이

• 유전 알고리즘이 진행됨에 따라 변이의 강도를 점점 줄여가는 변이 방법
  • 초반에는 변이의 정도가 다소 강해도 품질 향상이 일어날 가능성이 있지만, 해가 상당한 수준에 이른 후반에는 변이가 강하면 품질 향상이 일어나기 힘들기 때문

 

수선

• 교차와 변이가 해의 적법성을 깰 경우, 예를 들어 임의의 두 부모해로부터 교차와 변이를 수행했을 때 미리 정해 놓은 1의 개수와 0의 개수가 일치하지 않는 것을 해결하기 위한 방법
• 그래프 이등분 문제의 경우 1의 개수와 0의 개수의 차이는 항상 짝수이다. 

 

 

병렬 유전 알고리즘

• 유전 알고리즘은 효율적이지만 속도가 느리다
• 이를 병렬로 작동시켜 속도를 향상 시킨다. 
• 복수의 프로세서를 두고 한 프로세서에 하나 또는 두어 개의 염색체를 할당하는 방법

 

 

 

 

 

 

 

 

 

Quiz

1. 유전 알고리즘이란, 생물학적 진화 원리에 기반한 (          )이다.

2. 4만 개 내외의 유전자를 포함하고 있는 개체들은 (          )에 의해 염색체를 부분 결합하고, (          )에 의해 미소하게 변화된 새로운 염색체를 가진 개체를 만들어 낸다.

3. 개체가 환경에 적응하기 위해 선택적으로 번성하는 것을 뭐라고 하는가? (          )

4. 문제의 임의의 해를 유전 알고리즘이 이해하는 형태로 표현한 것을 (          ), 정해진 수의 염색체 집단을 (          ), 염색체상의 각 인자이자 유전 알고리즘의 최소 단위를 (          )라고 한다.

5.  N개의 해집단으로부터 (          ), (          ), (          ) 단계를거쳐 K개의 새로운 해를 생성한다.

6. 교차를 위해 해집단에서 임의의 해를 선택하는 연산을 (          )이라고 하며, 이렇게 선택된 해를 (          )라고한다.

7. 유전 알고리즘 빈 칸 채우라

{
	(          ) 초기화;
    (          ) 평가;
    
    while (종료 조건 만족하지 않으면){
    	(          ) 위한 (          ) 선택;
        (          )와 (          ) 수행;
        (          ) 평가
    }
}

8. 다음의 예제에서 Order1 crossover을 수행한 후, child 결과를 작성하라

Child:  

 

9. 적합도 차이의 정도로 프로그래머가 조절할 수 있는 파라미터는? (          )