📂최적화이론

유전 알고리즘에서 혼돈 연산이란?

용어 ¹

유전 알고리즘에서 혼돈 연산^{chaos operation}이란 돌연변이를 일으킬 때 캐어릭한 맵을 사용하여 해의 다양성을 높이는 기법을 말한다.

설명

혼돈 연산은 유전 알고리즘에서 돌연변이 연산을 수행할 때, 변이를 일으킬 차원의 도메인이 폐구간 $[a, b]$ 와 같이 나타난다고 하면 정규화를 취한 후 다음과 같은 로지스틱 맵 등을 이용하여 새로운 해를 생성한다. $$ x_{n+1} = r x_{n} \left( 1 - x_{n} \right) $$ 로지스틱 맵에서 $r = 4$ 인 경우 $x_{n+1}$ 은 완전히 결정론적^{deterministic}이면서도 특정 몇가지 초기조건을 제외하고는 초기조건에 민감하므로 해공간 전체를 넓게 탐색할 수 있다.

이론적 근거?

로지스틱 연산의 고정점^{fixed point}를 제외하고는 혼돈 연산이 해공간을 크게 탐색할 수 있는 건 알겠는데, 단순 균등분포에서 샘플링하는 것과 다른 점이 무엇일까?

여러 문헌에서 혼돈 연산이 좋은 성능을 보인다는 결과가 보고되었다는데, 그 이유는 정확히 잘 모르겠지만 개인적으로 보기에는 로지스틱 맵의 네츄럴 인베리언트 메져를 생각해봤을 때 해가 폐구간의 양끝에 가까이 위치할 경우 충분히 유리할만하다는 생각이 든다.

로지스틱 맵의 $\rho$ 는 마치 베타분포를 닮은 확률밀도함수처럼 보이는데, 구현 그 자체를 포함해서 랜덤 샘플리 보다는 유리한 측면이 있는 것 같다.