[NENGA] Lecture7 - Genetic Algorithms

◈ TB2 >

TB1에서는 Neural Network을 배웠다면, TB2에서는 Genetic Algorithm 배울 예정.

3월까지 제출해야하는 Coursework와 학기말 Exam이 있을 것.

1. Auxiliary reproductive operators

1-1. Inversion 도치 알고리즘

Binary는 2진법, GA에서는 상동 염색체를 뜻한다.

도치 알고리즘은 Binary가 아닌 Unary 즉 단일 염색체일 때 적용되는 알고리즘으로, 부모 염색체에서 무작위로 선택한 구간을 역순으로 나열하여 자식 염색체를 얻는 것이다. 

위 그림에서 부모 염색체에서 무작위로 지정된 efg 구간 원소들이 도치에 의해 역순으로 나열되어 gfe 순서로 자식 염색체에 나타난 것을 확인할 수 있다.

** offspring : 자식

1-2. Partially matched crossover (PMX) 부분 일치 교차 알고리즘

부모 염색체가 상동인 경우, 무작위로 지정된 구간을 서로 교환하여 자식 염색체를 얻는 알고리즘이다.

위 그림과 같이 abcdefghij, jehibcafgd 라는 부모 상동 염색체가 있을 때, 4-7 구간을 임의로 지정했다고 생각해보자.

그러면 두 부모의 해당 구간에 해당하는 원소들을 이용해 exchange map을 만들 수 있고, 부모의 원소에 이 exchange map을 대입하여 새로운 자식 염색체를 얻을 수 있다. 

자식 A'는 부모 A로부터 만들어진 것으로, 부모의 각 원소들이 map에 의해 a는 g로, b는 e로, c는 f로, d는 i로 치환된 것을 확인할 수 있다. exchange map에 정의되어있지 않은 h와 j는 치환되지 않고 부모 원소가 그대로 자식에게 전해졌다.

2. Basic theory of GA

각각의 염색체들은 {0,1,*}를 이용한 스키마로 표현될 수 있다. 여기서 *는 don't care로 0, 1 둘 다 취할 수 있음을 뜻한다.

예를 들어 *000라는 스키마가 있다면, 1000, 0000이라는 염색체를 포함하는 것이다. 또한 염색체의 자릿수가 m개라면 이 염색체에 대해 2^m개의 스키마가 존재할 수 있다.

1****라는 스키마가 있다면 이는 맨 앞자리가 무조건 1이어야한다는 뜻이고, 맨 앞자리가 1인 최소 이진수는 10000=16이고 최대 이진수는 11111=31이므로 왼쪽 그래프의 16~31까지의 수를 커버할 수 있다.

.>. Draw a diagram of 1*1**

스키마가 1*1**이므로, 10100(20) ~ 11111(31) 범위의 수를 커버할 수 있음.

하지만, 110** 형태의 수들은 해당 스키마에 포함이 되지 않으므로 그래프에서 제외되는 범위이다.

질문에서 물어보는 plane은 *1*plane!!

2.1 Schema properties

스키마는 order, defining length라는 속성을 갖는다. 

order : o(S)는 정의된 스키마의 자릿수, 

defining length : d(S)는 정의된 스키마의 마지막 자리번호 - 첫번째 자리번호

o(1*0****) = 2

d(1*0****) = 2

d(1******) = 0

2.2 Schema Theorem

3. implicit Parallelism

길이가 m개인 n개의 염색체가 있다면, n개 염색체 전체에 적용가능한 스키마의 갯수는 최소 2^m개부터 최대 n(2^m)개까지임.

n개의 스키마가 모두 같을때가 최소이고, n개 스키마가 전부 다를때 최대이다.

또한 스키마가 존재하고 crossover 등 연산될 때, 이 스키마가 온전히 살아남을 수도 있지만 스키마의 중간이 breaking point가 되어 파괴될 수도 있다.

이에 따라 우리는 각 스키마의 destroying probability 와 survivng probability를 계산할 수 있다.

길이가 m인 염색체가 있을때, 선택할 수 있는 원소와 원소사이 breaking point는 m-1개이다.

ex) m=6이면 [*/*/*/*/*/*]    선택가능한 breaking point(/) => 5개 

그러므로 스키마가 파괴될 확률은 스키마의 defining length / m-1. 스키마의 defining length가 길수록 연산될 때 쪼개지기 쉽다.

파괴와 생존이 반대개념이기 때문에 스키마의 생존확률은 1-destroying probability이 된다.

Example>. 길이가 8인 스키마 S1, S2가 있다. o(S)는 모두 2이고, d(S1)=5, d(S2)=2일 때 S1, S2로 가능한 스키마 예를 들고 각 스키마의 파괴, 생존확률을 구하라.

Sol>. S1의 예 = 1****0**

  S2의 예 = ****1*1*

destroying probability를 P(s)라 하면

P(S1) = d(S1) / (8-1) = 5/7

따라서 surviving probability = 1-P(S1) = 2/7

같은 방법으로 

P(S2) = d(S2) / (8-1) = 2/7, S2의 생존확률은 5/7