[NENGA] Lecture7 - Genetic Algorithms
◈ TB2 >
TB1에서는 Neural Network을 배웠다면, TB2에서는 Genetic Algorithm 배울 예정.
3월까지 제출해야하는 Coursework와 학기말 Exam이 있을 것.
1. Auxiliary reproductive operators
위 그림에서 부모 염색체에서 무작위로 지정된 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까지의 수를 커버할 수 있다.
질문에서 물어보는 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