Previous Contents/Evolutionary Computation

EA 의 군집간 이주 형태

shhyun 2008. 12. 18. 20:40


1. 군집간 이주

GA 나 GP 와 같은 진화 알고리즘에서 무시할 수 없는 문제 중에 하나가 조기수렴 문제이다. 이를 해결 하기 위한 여러 가지 방법들이 제안되고 있으며, 대표적으로 유전 연산자의 조절, 선택 연산자의 조절, 군집 형태의 조절 등이 있다. 그 중에서도 다중의 군집 사용과 그것의 조절에 대해서 설명한다.


2. 다중 군집(Multi Population)

군집은 다수의 개체가 하나의 그룹으로 묶여있는 단위이다. 본래 GA 나 GP 에서는 단일의 군집을 사용하여 연산을 수행했었다. 그러나 단일 군집의 효율성을 증가 시키기 위해 군집을 여러 개로 나누어 사용하는 다중 군집 방식이 도입되기 시작했다. 초기에는 군집을 격리시켜 각각의 군집으로 분류해서 이를 발전시켜나가는 방식이 수행 되었으나, 후에는 이 군집들간의 몇몇 데이터를 서로 다른 군집으로 이동시켜서 이를 발전시켜 나가는 방식이 수행되곤 했다.

서로 다른 군집들간의 데이터가 어떤 원리에 의해 이동을 하는지에 따라 여러 가지 방식이 존재한다. 가장 기본적인 형태로 원형이주가 있고, 발전된 형태로 HFC 나 ALPS 와 같이 특정 조건에 의해 서로 다른 군집으로 격리 시키는 형태가 있다. 이 방식들은 전체적으로 알고리즘 자체의 조기수렴은 방지 하면서 최적해를 찾아가는 성능은 발전 시키는 방향을 염두로 설계한 방식들이다.



3. 원형 이주 방식(Ring Migration)

원형 이주 방식은 군집들 간의 데이터 이동 방향이 하나의 흐름을 가진다. 그리고 일정한 주기마다 특정 개체를 다음의 군집으로 이동시키는 방식이다. 이 때, 이동되는 개체들을 수용할 공간을 할당하는 방식과 이동 시킬 개체를 선택하는 방식의 조절이 가능하며, 이에 따라서 각기 다른 효과가 나타난다.

일반적으로 많이 쓰이는 방식은 가장 높은 적합도의 개체를 다음 군집의 가장 적합도가 낮은 개체로 대체 시키는 방식이고, 일반적으로 해당 군집의 10%의 개체를 변경하는 방식을 사용한다. 여기서 너무 많은 개체를 변경하는 방식을 사용할 경우 전체적으로 군집 전체가 비슷한 개체들로 수렴해버리는 현상이 나타나며, 이로 인해 오히려 더 빠르게 조기수렴하는 현상이 나타나는 경우도 있다.


4. 주입형 이주 방식(Injection Migration)

주입형 이주 방식은 여러 개의 개체군에서 최고의 적합도를 갖는 개체들이 한 군집으로 모여 경쟁을 하는 방식이다. 기본적인 원리는 가장 좋은 형질의 유전자들끼리의 교배를 통해 좀 더 좋은 결과를 기대하는 방식이지만, 여러 군집이 수렴될 경우에 오히려 비슷한 유전자들이 하나의 군집에 모이게 되어 조기에 수렴하는 결과가 나타나는 경우도 있다.

주입형 이주 방식도 원형 이주 방식과 같이 일정 주기에 약 10% 의 개체를 주입 받아 사용하는 것이 대부분이며, 단일 적합도 함수를 가진 경우보다는 다수의 적합도 함수를 갖는 경우에 주로 사용된다.

5. HFC(Hierarchical Fair Competition)


HFC는 교육이론으로부터 파생된 군집의 교환 방식이다. 일반적인 교육 시스템은 같은 학년의 학생들, 즉 비슷한 수준의 학생들끼리의 경쟁을 모토로 한다. 그러나 일반적 진화연산의 경우에는 적합도가 높고 낮음에 관계 없이 모두 같은 환경에서 경쟁을 하게 된다. 이로 인해 적합도가 높은 개체만이 살아남고, 적합도가 낮은 개체가 비록 좋은 형질을 지녔더라도 이것이 보존되지 않는 현상이 발생한다.

HFC 에서는 이러한 불공정한 막기 위해 적합도에 따른 개체간의 분류가 이루어지고, 이를 이용해 적합도가 비슷한 개체들끼리만 공정한 경쟁을 하도록 한다. 이로 인해 조기수렴 효과가 억제되는 효과를 가지며, 적합도는 낮을 지라도 우수한 형질을 가지고 있는 개체들이 탈락되는 현상을 억제하는 효과를 가진다. 구체적인 알고리즘의 여러 가지의 파라미터 및 제한 요건은 아래에 정리되어 있다.


(*)HFC 모델의 구성요소


The Hierarchical Organization of Subpopulations to Establish a Fitness Gradient


낮은 적합도의 개체들은 낮은 레벨에 머무는 것을 허용한다.

낮은 적합도의 개체들은 더 낮은 레벨의 군집으로 이주할 수 있다.

허용 범위의 적합도 아래로 생성된 자손들은 해제시킬 수 있으며, 반복적으로 연산을 수행할 수 있다.

그들의 부모보다 낮은 적합도를 가진 생성된 어떠한 자손도 해제 당할 수 있다.

선택된 부모로부터 생성된 자손들은 적어도 한 부모의 적합도보다 높은 경우 생성될 수 있다.

   

Random Individual Generator : The Source of Genetic Material

   

최하위 레벨의 군집은 지속적으로 새로운 임의의 개체를 유입한다.

   

The Migration Policy from Lower to Higher Fitness Levels

   

몇몇 레벨의 군집에서 해당 군집의 허용 범위에 적합하며 이주되는 개체들은 몇몇의 적합도가 좋지 않은 개체들을 대체하게 된다.

만약에 허용된 버퍼로부터 개체가 이주된 후에 빈 공간이 생기게 되거나 혹은 그 허용 버퍼에 빈 공간이 생길 경우, 그것은 현재 멤버로부터 변이 연산을 수행하거나 두 개의 멤버를 크로스 오버 연산하여 필요한 만큼의 새로운 개체로 추가하거나, 더 낮은 레벨로부터 개체를 이주할 수 있다.(최 하위 레벨의 개체는 새롭게 생성하여 추가한다.)

이주는 오직 한 레벨에 대해서만 허용한다.

   

Setting the Parameters of the HFC Model

   

적합도 레벨의 개수,

각 레벨의 적합도 범위

6. ALPS(Age-Layered Population Structure) (2)

ALPS 는 HFC 와 비슷한 개념을 가지고 탄생한 알고리즘이다. ALPS 에서 공정한 경쟁의 요소로 사용되는 것은 개체의 나이가 된다. 여기서 나이란 해당 개체가 얼마나 오랜 시간 동안 진화가 되어 왔느냐를 의미하는 것이다. 즉, 비슷한 시간 동안 진화가 되어온 개체 들 간의 교배만을 허용하는 알고리즘이다.

마찬가지로 HFC 와 같이 조기수렴의 효과를 획기적으로 억제하는 효과를 보여주며, 특히 매우 어려운 문제에서 아주 오랜 세대에 걸쳐 진화연산을 수행할 때에 그 효과가 뛰어난 것으로 알려져 있다.


(*) 약 10만 세대까지는 비슷하지만, 그 세대수가 80만, 100만이 넘어서는 경우에는 확실한 성능차를 보여줌. ((2)참조)


이 ALPS 알고리즘의 구체적인 파라미터나 제한요소들은 아래에 정리되어 있다.


  1. 흐름
    1. 새롭게 임의로 생성되는 개체는 나이 0 을 부여 받는다.
    2. 변이나 재조합에 의해 생성된 개체는 가장 오래된 부모의 나이에 +1만큼 부여 받는다.
    3. 엘리티즘과 같은 방식에 의해 변형 없이 복사될 경우, 나이를 1 증가 시킨다.
    4. 만약에 한 개체가 그 세대에서 여러 번 선택되어 변이될 경우에는 오직 나이를 1만 증가시킨다.
    5. 각각의 개체들은 나이에 의한 계층으로 구분된다.
    6. Age-gap parameter 는 계층에 곱해지는 수치이다. 예를 들어 Polynomial Aging-scheme 에 age gap 20이 곱해질 경우, 20, 40, 80, 180, 320, … 이 된다.

         

  2. 기존의 EA와 다른 몇가지 형태
    1. 개체들은 오직 자신의 계층과 그 이전의 계층과 교배연산을 수행할 수 있다. 예를들어 layer n 의 경우 layer n-1 과 n 의 계층이 교배연산에서 선택될 수 있다.
    2. Layer 0 은 age-gap 세대 마다 새롭게 생성된 개체로 대치된다.
    3. 현재 계층의 개체가 너무 늙게 되면, 이것은 다음의 늙은 계층과 비교하게 되어 만약에 이것이 적어도 하나의 개체보다 좀더 좋은 적합도를 갖는다면 그것은 다음 계층의 개체와 교체하게 된다.
    4. 각각의 계층은 고정된 개체수를 가짐. 논문에서는 총 10개의 계층으로 구분 하여 100개씩의 개체를 갖도록 만들어졌음.
    5. 처음부터 모든 계층이 활성화 되는 것이 아닌, 초기 계층부터 age-gap 마다 새롭게 생성되는 계층에 대해 점증적으로 수행되는 방식. 만약 age-gap 이 20 일 경우, 초기 20 세대에는 첫번째 계층만 수행, 그리고 40세대 까지 첫번째와 두번째 계층만을 유전연산 및 수행, 60 세대 까지는 첫번째, 두번째, 세번째 계층만을 수행하는 방식.


7. 정리

이주 방식 자체는 조기수렴의 감소를 타겟으로 계획된다. 어떤 특정 문제에 대해 연산 자체의 획기적 성능 개선이나 전체적인 리소스의 점유와 같은 것을 염두 하는 것이 아니다. 이주 방식은 오히려 어떠한 문제에서든지 연산 자체의 효율성을 극대화 시켜주는 것을 타겟으로 하기 때문에 범용적인 사회적 문제나 현상을 토대로 알고리즘 화 된 것이 많다. 그러므로 실제적인 문제의 해결에 있어서 문제의 성질에 따른 연산자의 선택이 가장 우선적이며, 그 연산자의 올바른 발전 양상을 유도할 수 있는 이주 방식의 설정은 부차적인 문제가 될 수 있다.


참고 문헌

1. Jianjun Hu, Erik Goodman, Kisung Seo, Zhun Fan, Rondal Rosenberg The Hierarchical Fair Competition(HFC) Framework for Suitable Evolutionary Algorithms. Evolutionary Computation, 2005.

2. G. S. Hornby, "ALPS : The Age-Layered Population Structure for Reducing the Problem of Premature Convergence. " GECCO'06, pp. 815-822, July 8–12, 2006.