진화 전략

진화계산 및 진화디자인 : 황희수, 내하출판사, 2002, Page 61~73

1. 개체의 데이터 구조

2. 돌연변이

3. 재결합 (교배)

4. 진화 과정

5. 활용 분야

1963 년에 독일 베를린기술대학 (TUB) 의 두 학생이 공기저항을 최소화하는 물체의 형상을 찾기 위해 풍동 실험을 하였다. 기존의 경사법에 의한 탐색이 실패하였을 때, 두 학생 가운데 한명이었던 레켄베르그 (Ingo Rechenberg) 는 형상을 정의하는 파라메타를 돌연변이와 같이 랜덤하게 변화시킬 생각을 하였다. 이것이 바로 진화전략이 탄생하게 된 계기다. 1973 년에 레켄베르그는 2 개의 개체로 된 진화전략을 발표하였고 이를 다수의 개체로 확장할 것을 제안하였다.

진화전략을 발전시킨 또 다른 사람인 쉬베펠 (Hans Paul Schwefel) 은 1977 년에 진화전략과 수치 최적화라는 논문을 발표하였다. 진화전략은 목적함수를 해석적 형태로 만들 수 없어서 기존의 최적화 방법을 사용할 수 없었던 기술적인 최적화 문제를 해결하기 위해 고안되었다. 두개의 개체로 구성되는 초기의 (1 + 1) 진화전략에서는, 매 세대마다 하나의 부모 개체에 표준 정규분포를 이용한 돌연변이를 적용해서 부모보다 우수한 자식 개체가 발생하면, 이것으로 부모 개체를 대체한다.

이처럼 단순한 구조를 갖는 초기의 진화전략에 대해서는 돌연변이 양의 제어와 수렴속도와 같은 이론적인 연구가 수행되었다. 이 연구에 따르면, 모든 돌연변이 가운데 성공적인 돌연변이 비율은 1/5 이다. 이를 흔히 1/5 성공 규칙이라 부른다. 돌연변이만을 사용하는 초기의 진화전략은 μ 개의 부모 개체를 사용함으로써 재결합 과정을 포함할 수 있는 (μ + λ) 진화전략으로 발전하게 되었다. 돌연변이 체계와 그 크기를 제어하는 방식은 (1 + 1) 진화전략과 차이가 없다. 쉬베펠은 다수 개체를 갖는 진화전략을 (μ + λ) 진화전략과 (μ, λ) 진화전략으로 일반화시켰다. 여기서 μ 는 집단의 크기를 말하며 λ 는 매 세대에서 발생하는 자식 개체의 수이다.

이 일반화된 진화전략은 다수 개체로 구성된 집단이라는 개념을 도입함으로써 랜덤 교배, 돌연변이와 선택이라는 자연계진화 원리를 모방할 수 있게 되었다. 진화전략은 많은 시험 사례에서 반복적인 다른 방법에 비해 성공적임이 입증되엇다. 진화전략은 개체의 평가 방법 외에는 문제에 대한 정보를 거의 필요로 하지 않기 때문에, 거의 모든 종류의 최적화 문제에 적용될 수 있다. 진화전략은 선형 및 비선형 제약조건을 갖는 고차원, 멀티모달의 비선형 문제를 해결할 수 있다. 목적함수는 해석적 형태일 필요는 없으며, 시뮬레이션 결과가 목적함수로 사용될 수도 있다. 이는 제약조건의 경우도 마찬가지이다.

1. 개체의 데이터 구조

진화전략도 많은 발전을 했기 때문에 다양한 형태가 존재하지만, 이 장에서는 보편적으로 많이 사용되는 방식을 설명하기로 한다. n 차원 공간에서 정의된 목적변수 (목적함수를 최대화하기 위해 탐색해야 할 변수) 에 대해 정의된 목적함수 를 최대화 하는 문제를 생각해 보자. 진화전략은 n 차원의 목적변수를 코딩하지 않고 실수로 다룰 수 있다. 게다가 개체 a 의 적합도 함수 는 목적함수와 동일하다. 즉, . 미래에 보다 낳은 진화를 이루기 위해서는 세대가 변할 때 일부분의 퇴화를 받아들일 수 있어야 한다. 이를 위해 진화전략은 내부 모델이라는 것을 도입하엿으며, 이는 진화전략의 큰 특징 가운데 하나다. 이 모델은 돌연변이 양의 크기를 변화시키기 위한 것으로 전략변수로 표현된다. 자연계에서 유기체의 수명이 제한되어 있는 것은 진화의 실패를 나타내는 것이 아니라 종이 유전적으로 고착화 되는 것을  막는 중요한 수단인 것이다. 따라서, 진화전략에서 개체는 문제의 해에 해당하는 n 개의 실수벡터 (목적변수, x) 와 이에 대응하는 전략변수 (σ, α) 로 구성되기 때문에 개체의 일반적인 형태는 식 (1) 과 같이 표현된다.

                                                                           (1)

m 개의 개체로 이루어진 집단 P 는 식 (2) 와 같이 표시된다.

                                                                      (2)

는 i 번째 개체로 이다. 전략변수는 식 (3) 의 확률밀도함수를 갖는 n 차원의 표준정규분포의 분산 과 상호분산 으로 구성된다. 진화전략에서 개체는 n 개의 목적변수, 개의 분산과 개의 상호분산으로 구성된다.

                                                 (3)

여기서 는 상호분산 행렬을 나타내고 z 는 랜덤 변수이다. 상호분산 행렬이 양의 값을 갖도록 하기 위해 진화전략 알고리즘은 등가인 회전각 을 사용하며, 식 (4) 와 같이 계산된다.

                                                           (4)

와 가 탐색에 미치는 영향 및 이들의 최적 값에 대해서는 이 책에서 논의하지 않겠으며, 관심이 있는 독자는 고나련 참고문헌을 보기 바란다. 는 목적변수를 돌연변이 시키기 위한 표준편차의 차원을 표시한다. 중요한 것은 가 크면 클수록 탐색 범위는 넓어지고, 가 크면 클수록 탐색이 국부 최적 해에 빠질 위험이 감소한다. 그 이유는 각 차원별로 독립적인 최적화를 하는 대신에 동시에 여러 방향으로 최적화를 시도하기 때문이다.

2. 돌연변이

돌연변이가 완전히 랜덤 프로세스이어서는 안된다. 이는 자식 개체와 부모 개체가 완전히 독립적임을 의미하기 때문이다. 자식 개체는 어느 정도 부모 개체를 닮으며, 세대가 지남에 따라 커다란 변화보다는 작은 변화가 보다 빈번하게 발견되는 생물학적 원리와 유사하도록 하기 위해, 돌연변이 연산자는 개체의 형질에 정규분포의 랜덤 값을 더하는 것으로 정의된다. 개체의 목적변수와 전략변수가 돌연변이 된다. 돌연변이의 변화 크기를 돌연변이 시키기 위해 확률 이 사용된다. 전략변수의 돌연변이는 식 (5) 와 같이 계산된다. 은 전체 돌연변이 크기를 변화시키며, 는 개별개체의 돌연변이 크기를 변경한다.

                                         (5)

여기서 은 평균이 0 이고 표준편차가 1 인 표준정규분포에 의한 랜덤 값이고, 은 i 번째에 대한 랜덤 값이다. 쉬베펠에 의하면 인자 , 와 는 다음과 같이 설정된다. 통상 와 에 대한 비례상수는 1 을 사용하며, 는 라디안 5ε 이다. 즉, , , 이다.

탐색 과정에서 전략변수의 돌연변이는 전략변수 (표준편차와 상호분산) 자체를 진화시키며 이를 자기-적응성이라 부른다. σ 는 정규분포의 표준편차로 돌연변이 변화 크기를 나타내며, α 목적변수의 상관 돌연변이를 정의하는 경사율이다. 결국, σ 와 α 는 목적변수를 탐색하는데 사용되는 n 차원의 정규분포 확률밀도함수의 분산과 상호분산을 결정한다. 목적변수의 돌연변이는 와 값의 크기 조정에 따라 선형적으로 상관되며 식 (6) 과 같이 계산된다.

                                                                       (6)

여기서 은 평균 0, 표준편차 와 회전각  을 갖는 표준정규분포에 랜덤 벡터이다.

3. 재결합 (교배)

다양한 개체로 구성된 집단이 그 효과를 나타내기 위해서는 개체가 자신의 정보를 다른 개체와 교환할 수 있어야 하며, 이를 위해 교배가 사용된다. 자연계의 유전자 결합을 모의하는 몇 가지 교배 연산자가 진화전략에 사용된다. 불연속 교배는 유전알고리즘에서의 균일 교배와 유사하다. 결합 연산은 결합 확률 와 함께 적용된다.

    ■ 불연속 교배

두개의 개체 와 의 불연속 교배는 식 (7) 과 같이 된다.





                                               (7)

z = (x | y) 는 z 가 각기 50% 의 확률로 x 또는 y 로 할당됨을 의미한다.

교배된 개체의 형질은 부모 개체의 형질을 동일 확률로 물려받는다.

    ■ 중간 교배

중간 교배는 주로 전략변수를 조정하는데 사용된다. 이 연산자는 개체의 다양성을 훼손시킬 수 있으며, 이를 보완하기 위해서 돌연변이 연산을 추가할 수 있다. 두 개의 개체 와 의 중간 결합은 식 (8) 과 같이 된다.





                                               (8)

결합된 개체의 형질은 부모 개체의 형질을 평균한 값이다.

    ■ 랜덤중간 교배

두 개의 개체 와 의 랜덤중간 결합은 식 (9) 와 같이 된다.





                                               (9)

는 [0.0, 1.0] 사이의 균일 분포를 갖는 랜덤 실수 값이다. 보통 목적 변수에 대해서는 불연속 결합을, 전략변수의 경우에는 중간결합이 추천된다.

4. 진화 과정

메세대에서 부모 개체의 수가 μ 이고 이들의 자식 개체의 수가 λ 라 하자. 일반화된 진화전략은 다음과 같이 두 가지로 분류할 수 있다. 이들은 다음 세대 구성을 위해 부모 개체를 선택하는 방법과 교배의 사용 유무에 따라 차이가 난다.

    ■ (μ, λ) 진화전략

콤마 전략이라고 하며, 반드시 λ ≥ μ 이어야 한다. 이 전략은 엘리트주의 (가장 우수한 개체를 다음 세대에 생존하도록 보장) 와 같은 선택 방식을 보완적으로 사용하지 않으면 해가 발산할 위험성이 있다.

단계 1 : 돌연변이를 사용하여 μ 개의 부모 개체로부터 λ 개의 자식 개체를 생성.

단계 2 : λ 개의 자식 개체에 대한 적합도를 평가.

단계 3 : λ 개의 자식 개체를 적합도 크기 순서로 배열하고, 이 중 적합도가 큰 μ 개의 자식 개체를 다음 세대의 부모 개체로 선택 (결정론적 선택).

    ■ (μ + λ) 진화전략

플러스 전략이라고 하며, 반드시 λ > 1 이어야 한다. 이전 세대에서 적합도가 높은 개체가 다음 세대에서도 생존할 수 있다.

단계 1 : 돌연변이를 사용하여 μ 개의 부모 개체로부터 λ 개의 자식 개체를 생성.

단계 2 : λ 개의 자식 개체에 대한 적합도를 평가.

단계 3 : λ 개의 자식 개체와 μ 개의 부모 개체를 적합도 크기 순서로 배열하고, 이 중 적합도가 큰 μ 개의 자식 개체를 다음 세대의 부모 개체로 선택.

콤마 전략에서는 부모 개체가 선택 과정에 참여하지 않기 때문에, 부모 개체가 한번만 자식 개체를 발생할 수 있다. 즉, 개체의 수명이 한 세대이다. 반면에, 플러스 전략에서는 부모 개체도 선택 과정에 참여하기 때문에, 자식 개체의 적합도 보다 부모 개체의 적합도가 우수하면 부모 개체는 영원히 생존할 수 있다. 실세계에서는 어떤 유기체도 영원히 생존할 수 없기 때문에, 이론적으로 영원히 생존하는 개체가 있을 수 있는 플러스 전략 보다는 콤마 전략이 더 현실적이다. 또한, 진화 과정에서 약간의 퇴화를 포함하는 (자식 개체 보다 더 우수한 부모 개체도 다음 세대에 생존하지 못함) 콤마 전략이 결과적으로 더 우수하게 동작할 수 있다. 그 이유는 우수한 개체를 잃으면 적응 동작을 계속 수행함으로써 잘못 적응된 전략변수에 오래 머물러 있는 것을 막을 수 있기 때문이다. 집단 크기는 현재 가장 좋은 개체와 다른 우수한 개체들이 생식 과정에 참여할 수 있을 만큼 충분히 커야 한다. 다시 말해, 집단 크기는 종이 유전적으로 열성화되어 죽지 않도록 필요한 유전적 다양성을 유지할 수 있을 만큼 커야 한다. μ/λ 의 비율에 따라 진화전략의 수렴성이 영향을 받는데 이 비율이 (5,100) 처럼 작으면 수렴속도는 빠르지만 국부 수렴할 가능성이 커지고, 비율이 (30,100) 처럼 높아지면 수렴속도는 느려지지만 전역 해를 찾을 수 있다. 전자와 같이 선택 비율이 작은 경우를 하드-선택이라 하고 후자를 소프트-선택이라고도 한다. 최근에 새로 소개된 보다 일반화된 진화전략에서는 개체의 수명 과 교배에 참여할 부모 개체의 수 를 정의한다. 진화전략과 진화전략은 각각 가 1 과 ∞ 인 경우에 해당한다. 따라서 이 새로운 진화전략은 양 극단에 있는 와 진화전략의 장단점을 조정할 수 있다. 이상에서 설명한 진화전략의 기본 체계를 그림 1 에 가상 코드로 보였다.

진화전략과 유전알고리즘을 비교한 표 1 을 보면, 서로의 유사점과 차이점을 알 수 있다. 진화전략과 유전알고리즘은 그 탄생이 독립적으로 이루어졌지만, 가능한 해 집단의 진화로부터 최적한 해를 찾는다는 점에서 유사하다. 그러나 문제의 변수를 표현하는 방식에는 차이가 있다. 진화전략에서는 실수 (표현형) 를 직접 사용하지만, 유전알고리즘에서는 실수를 유전자형 (예 : 이진 문자열) 으로 코딩해야 한다. 선택 방식에도 차이가 있다. 진화전략에서의 선택은 결정론적인 반면에 유전알고리즘의 경우에는 확률적이다. 새로운 개체 발생을 위한 탐색 방법에서도 진화전략은 주로 돌연변이에, 유전알고리즘은 교배에 의존한다.

그림 1  진화전략의 계산 과정

표 1  진화전략과 유전알고리즘의 특성 비교

5. 활용 분야

진화전략은 벡터 최적화에도 적용되었고 TSP 문제나 잡음이 있고 응답 평면이 변화하는 문제에도 적용될 수 있다. 여기서는 완전한 응용 사례는 아니지만, 학생들에게 진화전략을 이해시키고 그 능력을 보여주기 위해 만들어진 10 가지 시범 사례 가운데 일부를 소개하고자 한다.

    ■ 볼록/오목 렌즈의 설계

진화전략을 사용하여 평행 광선이 투사면의 한 점에 모이도록 다각형 렌즈를 설계할 수 있다. 이 다각형 렌즈는 n 개의 프리즘으로 구성되기 때문에 (n + 1) 위치에서 렌즈의 두께를 변화시킬 수 있다. 프리즘과 주변 매질의 굴절률을 r2 와 r1 이라 하자. 이때, 굴절률 r2/r1 은 0.2 와 5.0 사이에서 조정될 수 있다. 이 값이 1 보다 작으면 유리에 공기를 주입해서 렌즈를 만들어야 한다. 프리즘의 중앙에 투사되는 광선만을 고려한다면, 렌즈의 품질은 투사면에서 목표지점 P 와 실제 광선이 모인 점 사이의 기하학적 거리를 제곱한 값으로 평가될 수 있다. 즉, 거리 제곱의 합이 작을수록 렌즈의 품질은 우수해지며, 해당 개체의 적합도는 높아진다. 이 때 제약조건으로, 각 렌즈 두께는 최소 허용 값 보다 커야한다. (1, 30) 진화전략을 사용하여 적합도가 우수한 볼록 (오목) 렌즈의 굴절률 비를 탐색할 수 있다. 그림 2 는 진화과정에서 얻어진 오목렌즈를 보여준다. 이때, 얻은 굴절률은 r1/r2 = 0.4 이다.

그림 2  오목렌즈의 진화

    ■ 배관 시스템의 설계

단위 시간당 정해진 유량을 공급하는 배관 시스템을 고려해보자. 이 시스템은 n 개의 노드로 구성되며, 시스템의 배관 토폴로지, 주요 노드 (전체 유량이 공급되는 노드) 의 위치와 단말 노드의 위치는 정해져 있다고 가정하자. 배관의 직경은 수력학 법칙에 계산된다. 이때, 단위 시간당 정해진 유량을 공급하면서 모든 배관의 압력차와 전체 배관의 체적을 최소화시킬 수 있는 가지 노드의 위치를 찾는 문제를 생각할 수 있다. 이는 식 (10) 의 목적함수를 최소화하는 최적화 문제로 정의할 수 있다.

                                             (10)

는 상수, 는 i 번째 단말 노드의 압력, 는 모든 단말 노드의 평균 압력이고 는 전체 배관의 체적이다.

배관 시스템은 그림 3 에 보여진 것처럼 주요노드, 가지노드와 단말노드로 구성되며 노드와 노드를 연결하는 에지는 배관의 직경과 단위 시간당 유량 값을 갖는다. 진화전략을 적용한 결과가 그림 4 에 보여진다. 이 그림을 보면 진화가 이루어질수록 목적함수 값이 작아짐을 알 수 있다.

그림 3  배관 시스템의 기본 구성

그림 4  배관 시스템의 진화 결과

■ 데이터 추종을 위한 다항식 근사화

2 차원 평면에 m 개의 데이터 쌍이 주어졌을 때, 이들을 추종할 수 있는 다항식을 찾는 문제를 생각해 보자. 진화전략을 사용하여 다항식의 형태와 차수도 탐색할 수 있지만, 여기서는 이들을 미리 정한 후 다항식의 계수만 찾기로 한다. 사용할 다항식은 식 (11) 과 같다.

                                               (11)

m 개의 데이터 상인 이 주어지면, 목적함수인 식 (12) 를 최소화하도록 식 (11) 의 계수 를 찾는 최적화 문제를 정의할 수 있다.

                                                               (12)

노이즈가 있는 2 차원 데이터가 있을 때, (1, 10) 진화전략을 사용하여 데이터를 추종할 수 있는 다항식의 계수를 찾은 예가 그림 5 에 보여진다. 다항식의 차수는 6 을 사용하였다.

그림 5  다항식의 근사화

    ■ 비행기 날개 프레임의 설계

비행기 날개 프레임의 토폴로지와 정적인 힘이 주어졌을 때, 전체 중량이 최소가 되도록 프레임 노드의 위치를 정하는 문제를 생각해보자. 프레임은 날개의 외곽을 따라 횡으로 가로지르는 막대로 구성된다. 막대가 모이는 점을 노드라 하고, 이 노드의 좌표 값이 찾고자 하는 목적 변수가 된다. 진화전략을 사용하여 이 노드들의 위치를 찾고자 할 때, 개체의 적합도인 프레임 중량을 계산하기 위해서는 다음과 같은 과정을 거친다. 먼저, 막대의 축방향 하중을 계산하고, 축방향 하중과 최대 응력을 가지고 막대의 단면적을 계산해야 한다. 이때, 모든 막대에는 최대응력이 작용해야 한다. 최종적으로, 프레임 중랴응ㄴ 모든 막대의 전체 체적에 사용된 소재의 단위 체적 중량을 곱하여 얻어진다. 그림 6 에 (6, 60) 진화전략을 사용하여 비행기 날개 프레임을 진화시킨 결과가 보여진다. 진화가 될수록 프레임의 중량은 줄어든다.

그림 6  비행기 날개 프레임의 진화

마술 행렬 (magic square) 은 숫자 이론 (number theory) 의 발명품이다. 이 문제는 n x n 행렬에서 모든 열 단위의 숫자 합, 행 단위의 숫자 합 및 2 개의 대각선에 위치한 숫자의 합이 동일한 값 (S) 이 되도록, 행렬의 각 원소에 1 에서부터 n² 까지의 숫자 가운데 하나를 분포시키는 것이다. 이 동일한 값 S 를 마술 합이라 하며 에 의해 계산된다. (1, 30) 진화전략을 8 x 8 마술 행렬에 적용해 보자. 이때, 마술 합의 값 (S) 은 260 이다. 목적함수는 모든 열, 행 및 대각선 합에 대해서 S 값과 차이를 제곱하여 더 한 것으로 계산한다. 목적함수 값이 적으면 적을수록 개체의 적합도는 증가한다. 초기 개체는 n x n 행렬의 각 원소에 1 에서부터 n² 까지 숫자를 랜덤하게 분포시킨 것이다. 그림 7 에 447 세대에서 얻어진 마술 행렬이 보여진다.

    ■ 색과 형태의 진화

컴퓨터 화면에 랜덤하게 발생된 4 각형으로부터 사용자가 선호하는 크기와 색을 갖는 사각형을 찾는 문제를 생각해 보자. 이 문제에서 개체의 적합도 평가는 정량화된 목적함수 대신에 사용자의 주관적 판단에 의해 결정된다. (μ, λ) 진화전략에서 λ 개의 자식 개체들이 컴퓨터 화면에 보여지면, 사용자는 다음 세대를 위해 이들로부터 μ 개의 부모 개체를 선정한다. 화면에 보여진 사각형 가운데 크기와 색상 면에서 마음에 드는 μ 개의 개체를 마우스로 클릭하는 것으로 부모 개체를 선택할 수 있다.

그림 7  진화를 통해 얻어진 8 x 8 마술 행렬