홈

퍼뮤테이션 엔트로피

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.88.174102 http://materias.df.uba.ar/dnla2019c1/files/2019/03/permutation_entropy.pdf

오토마타

• 폰 노이만 네이버후드

MEP

https://arxiv.org/pdf/2110.00367

• 유전 알고리즘
• 자연선택
  • 엘리트주의(순위 선택 이야기 추가)
  • 토너먼트
• 교차혼합
  • 근친상간 방지
  • 성선택: 프락시멀 오퍼레이터 Kirkpatrick 메이팅 태그
• 돌연변이
  • 크라우딩
  • 적합도 공유
  • 미분 진화

유전 알고리즘에서 엘리트주의

정의 ^{1 2}

유전 알고리즘에서 엘리트주의^elitism란 자연선택이 일어나는 매 세대마다 가장 적합도가 높은 개체 몇 개를 다음 세대로 무조건 넘기는 전략을 말한다.

설명

엘리트주의는 자연선택에서 말하는 랭크 선택^{rank selection}을 극단화 했다고 볼 수 있으며, 확률적 요소 없이 조건을 만족한 일부 개체를 다음 세대로 넘기는 절삭선택^{truncation selection}의 다른 이름이라고 볼 수도 있다. 엘리트주의를 채택한 유전 알고리즘에서 세대에 따른 목적함수의 개형은 단조함수의 꼴이 된다.

의외로 최적화 문제에서 ‘역사상 가장 뛰어났던’ 해를 잃어버리는 것은 흔한 일이며, 이것은 심지어 경사하강법에서도 마찬가지다. 가령 학습 중에 꽤 빠른 타이밍에 가장 좋은 해를 얻었는데, 에포크를 끝까지 가져가자 오버피팅이 일어나면서 막상 마지막 해는 그보다 못한 경우가 그렇다. 물론 보통은 체크포인트를 두어 가장 좋은 해를 저장해두는 식으로 피할 수 있는 문제다.

한편 유전 알고리즘에서 엘리트주의는 체크포인트로써 계속 전승될 뿐만이 아니라 진화의 과정에서 해집합에 계속해서 영향을 미치는 점이 다르다. 아무래도 자식 세대는 엘리트 부모를 닮아 비슷한 유전형을 가지며, 사실 자식들도 높은 적합도를 가질 확률이 높아 그 다음 세대로도 그 유전자가 계속 전해질 가능성이 크기 때문이다. 인구 메서드의 관점으로 보면 국소최적해 근방을 조금 더 꼼꼼하게 탐색하겠다는 의도로 볼 수 있다.

DBSCAN: 밀도 기반 군집화

알고리즘 ¹

DBSCAN^{Density-Based Spatial Clustering of Applications with Noise}은 거리공간 $\left( X , d \right)$ 에서 점의 밀도에 기반하여 클러스터링을 수행하는 알고리즘이다. 두 개의 하이퍼파라미터인 반경^radius $\varepsilon > 0$ 와 밀도의 기준이 될 최소점수^{minimal number of points} $m$ 이 주어진다.

1. 유한집합 $D \subset X$ 를 데이터베이스^database라 한다.
2. $p \in D$ 에 대해 $N_{\varepsilon} \left( p \right) = \left\{ q \in X \mid d \left( p , q \right) \le \varepsilon \right\}$ 를 $p$ 의 이웃^neighborhood이라 한다.
3. $p \in D$ 가 $| N_{\varepsilon} \left( p \right) | \ge m$ 을 만족하면 $p$ 를 핵심점^{core point}이라 한다.
4. $p \in D$ 가 핵심점은 아니지만, $N_{\varepsilon} \left( p \right)$ 이 다른 핵심점을 포함하면 $p$ 를 경계점^{border point}이라 한다.
5. 핵심점 $q$ 에 대해 $p \in N_{\varepsilon} \left( q \right)$ 이면 $q$ 는 $p$ 에 직접 도달가능^{directly reachable}하다고 한다. $$ p = p_{1} , \cdots , p_{n} = q $$ 위와 같이 $p_{k}$ 가 $p_{k+1}$ 에 직접 도달가능하면서 $p = p_{1}$ 이고 $q = p_{n}$ 인 시퀀스가 존재하면 $p$ 는 $q$ 에 도달가능^reachable하다고 한다.
6. 두 $p , q \in D$ 에 도달가능한 핵심점 $o \in D$ 가 존재하면 $p$ 와 $q$ 는 연결^connected되었다고 한다.
7. 공집합이 아닌 $C \subseteq D$ 의 모든 $\forall p, q \in C$ 들이 다음 두 조건을 만족하면 클러스터^cluster라 한다.
   • (i) 최대성: 만약 $p$ 에서 $q$ 로 도달가능하면, $q \in C$ 이다.
   • (ii) 연결성: $p$ 와 $q$ 는 연결되었다.
8. 그 어떤 클러스터에도 속하지 못하는 점을 노이즈^noise라 한다.

설명 ¹

도달가능성과 연결성의 차이는 핵심점에 한정되는지 아닌지가 다르다. 연결성은 대칭적인 관계인 것과 달리, 도달가능한 주체가 되려면 핵심점이라는 조건이 필요하기 때문에 $p$ 가 $q$ 에 도달가능할지라도 그 반대는 불가능할 수 있다.

유전 알고리즘에서 돌연변이란?

유전 알고리즘에서 교차혼합이란?