대단한건 아니지만;;
어쨌든,
(1) 조기수렴 문제?
조기수렴 문제의 해결에 대해서 연구를 좀 했습니다.
그러던 중에 나온 많은 알고리즘들,
적합도 공유방식(Fitness Sharing),
군중 분산 방식(?, 말이 좀 이상합니다만, 본래는 Crowding 방식입니다. 제 생각에 저 표현이 의미와 잘 부합되는것 같습니다.),
다중군집을 기반으로한 새로운 모델들(Multi-pop 을 기반으로한 HFC(Hierarchical Fair Competition) 혹은 ALPS(Age-Layered Population Structure))
이 있습니다.
우선 적합도 공유방식은 적합도가 높은 개체들이 적합도가 낮은 개체들에게 자신의 적합도를 나눠준다고 생각하면 간단합니다. 즉, 비슷한 수준의 적합도를 이용해서 다른 적합도 낮은 개체들도 선택될 확률을 높혀주는 것 입니다.
군중분산방식은 매 세대의 끝에 유저가 선택해준 갯수만큼의 개체를 주위의 개체들에 비해 개체의 본래 타입이 틀린 개체들로 강제적으로 대체시켜주는 방식입니다. 많은 다양성의 확보를 통해 본래의 수렴속도를 늦추는 것이 초점입니다.
다중 군집 기반으로한 모델들은 여러개의 군집으로 나눌때, HFC 같은 경우는 적합도를 기반으로하여 나누게 됩니다. 적합도가 높은 개체는 상위 군집, 낮은 개체를 하위 군집 등으로 분류를 하고 격리시킨후에 교배연산을 수행합니다. 기본 생각은 초등학생은 초등학생끼리, 대학생을 대학생끼리 경쟁을 시켜야 좋은 결과가 나오지 않겠냐 라는 것입니다. ALPS 는 개체들의 나이를 이용해 격리시켜서 교배연산을 수행 합니다. 마찬가지로 비슷한 연령대의 경쟁이 가장 효율적이지 않은가 라는 것에서 시작되었다고 보면 됩니다.
(2) HFC 모델의 단점
위와 같이 조기수렴 문제를 해결하기 위한 많은 방법들이 있습니다. 하지만 위의 방법들은 단점을 가지고 있습니다. HFC 의 다층 군집화 를 하나의 군집으로 만든 CHFC(Continuous HFC) 모델이 있습니다. 이 모델은 다층이 아닌 단일군집에서 HFC의 격리 수용모델을 구현 한 모델입니다. 성능이 기본적 알고리즘 보단 좋았지만, 다른 HFC모델에 비해서 뛰어난 성능을 보여주지는 못했습니다. 저는 그중에서도 위의 CHFC 모델을 타겟으로 잡고 개선을 시도했습니다. 그래서 우선 단점에 대해서 생각해 보았습니다.
첫번째 단점으로는 적합도만을 가지고 군집화를 이룬다는 것이라고 생각했습니다. 왜냐하면 만약에 적합도, 즉 해석된 상태의 결과물이 나쁜 결과를 갖고 있다고 해도 잠재적인 성능향상의 요소를 가지고 있을지도 모르는 것 입니다. 단일 군집에서는 완전 격리효과가 떨어지기 때문에 위의 잠재적 성능향상 요소를 잃게 될 확률이 높다고 생각했습니다.
둘째로는 일반적 세대형 알고리즘(Generational)에 있다고 생각했습니다. 일반적인 세대형 알고리즘이란 한 세대에서 다음 세대로 세대를 넘어갈때에 군집 전체가 바뀌는 것을 의미합니다. 이는 점진적 알고리즘(Steady-State) 에 비해서 수렴속도가 매우 빨라지는 것을 확인할 수 있습니다. 하나의 군집을 이용하는 CHFC의 경우에는 이것이 더 가속화 될 것이라고 판단 했습니다.
세번째로는 매우 큰 군집(여기서 군집이란 총 개체수를 의미합니다)을 가지고 있어야 한다는 것 입니다. 개체의 수가 적을 경우에는 상대적으로 다음 세대로 넘어갈때에 수렴이 급격히 일어나기 때문에, 일정수 이상(약 500~1000개 이상)의 개체를 확보하지 못할 경우에는 HFC나 CHFC 알고리즘의 지연효과가 거의 나타나지 않을 수가 있습니다.
(3) 퍼지추론 기반의 유전알고리즘 선택 연산자
그래서 퍼지추론을 이용해서 잠재적 성능향상이 있을수 있는 개체들을 골라내서 그들간의 경쟁을 유도해 보자는 게 제 의견입니다. 퍼지 추론은 여기서 데이터의 분류 방법이 됩니다. 즉, 기존의 HFC나 CHFC 등이 유도하는 군집화를 퍼지추론의 모호성을 통해 간접적으로 유도해 낼 수 있으며, 잠재적 성능향상이 가능할 법한 개체들에 대해 경쟁을 유도하기 때문에 기존의 알고리즘 보다 나은 성능을 보여 줄 것이라고 판단 했습니다.
하지만 퍼지 추론을 통해 나타난 결과로서 무조건적인 경쟁을 시킬 경우에는 마찬가지로 급격한 수렴을 보일수 있다고 생각했습니다. 그래서 임의의 개체풀 N 에서 몇개만 추려내서 경쟁시키는 방식을 이용 했습니다.
(4) 퍼지모델
간단한 간략추론 방식을 이용했습니다. 전반부 변수 2개는 적합도와 유사도, 후반부 변수 1개는 계층 으로 이용했으며, 멤버쉽 함수로는 가우시안 함수를 이용했습니다.
(5) 성능 및 결과
첨부해놓은 발표자료를 첨부해 보시면 됩니다. 전체적으로 이번에 제시한 연산자가 좋은 성능을 발휘한 것을 확인하실 수 있고, 다른 알고리즘 들에 비해서 더 높은 강인성을 가지고 있는 것을 확인하실 수 있습니다.
(6) 결론
이번 발표때 말씀드린 연산자는 퍼지추론 기반의 유전알고리즘 선택 연산자 입니다. 정확히 의도하고자 하는 것은 기존에 이용하던 적합도 단일 기반의 선택 연산자보다 거기에 다른 요소를 추가해서 기준으로 이용하게 되면, 기존의 다중군집 알고리즘의 효과를 얻을 수 있으면서, 좋은 결과를 도출시킬수 있다고 생각한 것 입니다. 결과적으로 당장의 논문에서 제시한 Deceptive문제에 대해서는 좋은 결과를 얻었습니다만, 문제가 다르게 될 경우에는 퍼지 함수의 조정이 이루어 져야 좋은 결과를 도출 시킬 수 있다고 판단합니다. 소수의 군집으로도 어려운 난이도의 문제를 해결할 수 있고, 구현자체도 어려운 편이 아니기 때문에 임베디드 시스템이나 로봇분야와 같이 제한된 리소스에서 결과를 내야하는 분야에 적용해보면 좋은 결과가 나오리라고 생각 합니다.
퍼지선택연산자슬라이드.ppt