JANGUN


쉽게 배우는 유전 알고리즘


지음 : 문병로 (2001)



목차

Chapter 1. 유전 알고리즘의 개괄
Chapter 2. 문제의 표현
Chapter 3. 유전 알고리즘의 연산들
Chapter 4. 스키마와 문제 공간
Chapter 5. 확장된 주제들
Chapter 6. 유전 알고리즘의 응용 예들
Chapter 7. 유전 알고리즘의 구체적 예(1) : 그래프 분할
Chapter 8. 유전 알고리즘의 구체적 예(2) : TSP
Chapter 9. 다른 스토캐스틱 탐색 기법들
맺음말


Chapter 1. 유전 알고리즘의 개괄

유전 알고리즘은 진화의 원리를 문제 해결에 이용하는 대표적인 방법론 중 하나다.
독일의 Rechenberg(1965)가 진화 전략을 제안.
유전 알고리즘의 대부는 존 홀랜드(John Holland) : 집단에 근거하고 교차와 변이를 포함한 골격을 완성 “Adaptation in Natural and Artificial Systems”
유전 알고리즘의 용어:
- 염색체(chromosome) : 문제 해결상의 임의의 해를 유전 알고리즘이 이해하는 형태로 표현한 것
- 유전자(gene) : 염색체 상의 각 인자로 유전 알고리즘에서 최소 단위
- 스키마(schema) : 염색체에 깃들어 있는 부분 패턴. (예) 네 자리 염색체 1101에는 1****, *1**, 11**, 1**1, *10*, 110*, *101, **** 등 16개의 부분 패턴이 포함
※ 유전 알고리즘은 외형상 염색체를 이용해 작업하지만, 안을 들여다보면 결국 이러한 작은 스키마들이 결합하여 점점 더 큰 스키마를 이루어가는 과정
- 교차 : 두 해의 특징을 부분 결합하여 하나의 새로운 해를 만들어 내는 연산. 교차 연산자를 선택 또는 고안하기 전에 먼저 문제의 표현 방법이 결정함.
- 변이 : 부모해에 없는 속성을 자식해에 도입하는 역할. 변이 확률을 높이면 보다 다양한 해를 생성 ==> 역동성 ↑, 수렴성 ↓, 수행시간 ↑, 개선속도 ↓
- 대치 : 해집단의 다양성을 합리적으로 유지시킬 수 있는 연산을 선택해야 함

[유전 알고리즘의 전형적 구조]
n개의 초기 염색체 생성;
repeat {
for i=1 to k {
두 염색체 p1, p2 선택;
offspring(i) = crossover(p1, p2);
offspring(i) = mutation (offspring);
}
offspring(1) ~ offspring(k)를 population 내의 k개의 염색체와 대치;
} until (정지조건 만족)
return 남은 염색체 중 최상의 염색체

유전 알고리즘은 대부분 정해진 수의 해로 구성되는 해집단을 갖는다. 이 알고리즘에서 해집단의 해의 수는 n이다. 먼저 n개의 해를 임의로 생성한다.
이 해집단으로부터 k개의 새로운 해를 만들어 내는데 각각의 해는 선택, 교차, 변이의 단계를 거쳐 만들어진다.
이렇게 만들어진 k개의 해는 해집단 내의 k개의 해와 대치된다.
이러한 과정을 임의의 정지 조건이 만족될 때까지 수행한 후 해집단에 남은 해 중 가장 좋은 해를 답으로 삼는다.
K : 해집단이 한번에 얼마나 많이 대치되느냐를 결정, (k/n : 세대차(generation gap)

Murray Gell-Mann : 쿼크 이론을 확립하여 노벨 물리학상을 받은 소립자 물리학자로 1984년 산타페 연구소를 태동시킴. “제3의 문화“ 적응적 복잡계에 이르는 데이터의 흐름 속에 존재하는 규칙성은 스키마로 설명할 수 있으며, 다양한 스키마 간의 경쟁이 존재한다고 주장
- 환원론적 과학 : (데카르트, 뉴턴 이후 200년) 물질을 쪼개고 쪼개어 가장 기본적인 것(쿼크, 초끈)의 존재를 밝혀보자는 방식
- 복잡성 과학 : 하유 계층 사물들의 결합으로 하위 구조에는 존재하지 않는 새로운 개념 또는 구조가 ‘창발'되는 원리를 밝혀보려는 종합적인 과학


Chapter 2. 문제의 표현

단 하나의 해를 요구하는 문제도 있고, 여러 개의 해 중 하나만 요구하는 문제도 있다. 수없이 많은 해 중에서 품질이 좋은 것과 그렇지 않은 것들이 있다.
이들 중 가장 품질이 좋은 해를 찾는 것을 찾는 것이 최적화 문제다. 유전 알고리즘은 대부분 최적화 문제를 대상으로 한다.
해의 표현 방법
- k-진수 표현 : 2진수, 8진수, 16진수 등
- 그레이 코딩 : 이진 표현의 한 갈레로, 인접한 수는 단 한 비트만 차이가 나도록 만들 이진수 코딩 체계
(의미상으로 유사한 두 해가 문제 공간에서 가까이 위치하도록 하는 것이 사용 동기)
- 산술적 교차(실수 표현) : 동일 위치에 있는 두 부모의 유전자들의 값을 평균 내어 자식의 동일 위치 유전자 값으로 삼는 방법
- 가변 표현 (표현 방식을 미리 고정하지 않고 유전 알고리즘의 수행 중에 표현 방식이 변할 수 있도록 하는 방법) : 역치 연산, 메시 유전 알고리즘
※ 유전자 재배치 : 문제에 깃든 정보를 사용하지 않고 유전 알고리즘의 수행 중에 표현이 바뀌는 동적인 재배열 방법
- 위치 기반 표현 : 유전자의 위치가 해당 유전자의 속성을 결정
- 순서 기반 표현 : 유전자의 위치는 별 의미가 없고 유전자 값들의 상대적 순서가 의미를 갖는 표현 방법
- 일차원 ~ 다차원 표현 : 인접 관계에 의한 정보 손실로 인해 발생하는 비효율성이 있을 수 있다.
- 80년대 중반 존 코자(John Koza)는 LISP 프로그램을 자동 생산하는 유전 알고리즘을 제안하고 유전 프로그래밍이라 명명함
: 임의의 프로그램은 트리 형태로 표현하고, 트리 자체를 염색체로 사용함.

최근까지 프로그래밍은 인간의 전유물이었다. 사람만이 프로그래밍을 할 수 있었다.
유전 프로그래밍은 프로그램의 품질을 외부에서 평가할 수만 있으면 컴퓨터가 프로그램을 자동으로 만들어 줄 수 있다는 특성으로 많은 호기심을 자극했다.


Chapter 3. 유전 알고리즘의 연산들

1. 선택연산 : 교차에 쓰이는 두 개의 부모해를 고르기 위한 연산. 우수한 해가 선택될 확률이 높아야 한다.
우수한 해들과 열등한 해들 사이의 적합도 차이를 조절함으로써 선택 확률을 조절할 수 있는데, 이 차이의 정도를 선택압이라 한다. 선택압이 높을수록 수렴은 빠르나 설 익은 수렴의 가능성이 높아진다. 반면 선택압이 너무 낮으면 해집단의 평균 품질이 좋아지지 않을 가능성이 많다.
- 품질 비례 룰렛휠 선택 : 각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절하는 방법
fi = (Cw-Ci) + (Cw-Cb) / (k-1), (k>1 보통 3~4, Cw 해집단에서 가장 나쁜 해의 비용, Cb 해집단에서 가장 좋은 해의 비용, Ci 해i의 비용) - 토너먼트 선택 : 두 개의 염색체를 임의로 선택하여 [0, 1) 범위의 난수를 발생시킨 다음, 이것이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택
- 순위 기반 선택 : 해집단 내의 해들을 품질 순으로 ‘순위'를 매긴 다음 가장 좋은 해부터 일차 함수적으로 적합도를 배정하는 방법
fi = max + (i-1) x (min-max) / (n-1) - 공유 : 해집단의 다양성을 보다 오래 유지하고자 하는 목적에서 고안되었다. 먼저 품질 비례 선택이나 순위 기반 선택에서 쓰는 적합도를 구한다.
여기에 해당 염색체가 해집단 내의 나머지 염색체들과 유사한 정도가 높을수록 큰 값으로 나누어 적합도를 조정한다.
공유는 해집단 내의 해들을 문제 공간 상에서 지리적으로 분산되게 도와주는 효과가 있다.


2. 교차 연산 : 해의 표현은 교차와 관계될 때만 의미가 있다.
- 일점 교차 : 길이가 n인 일차원 문자열로 된 염색체 상에서 일정 교차로 자르는 방법의 총 수는 ‘n-1’ 가지다.
- 다점 교차 : 염색체의 길이가 n일때, k점 교차로 자르는 방법의 총 수는 ‘n-1Ck’ 가지다. 다점 교차는 일점 교차보다 교란의 정도가 크다. 따라서 보다 넓은 탐색 공간을 탐색할 수 있다. 하지만 교란이 강하면 수렴성이 떨어져 주어진 시간 내에 수렴하지 않을 가능성이 있다. 교란이 강하다는 것은 스키마가 파손될 확률이 높다는 것이다. 대신 새로운 스키마의 생성은 더 다양하게 할 수 있다.
- 균등 교차 : 먼저 임계 확률을 설정한다. 그리고 두 부모해의 각각의 유전자 위치에 대하여 난수를 발생한 다음, 임계 확률에 따라 어느 부모의 유전자를 복사할 지 결정한다. 균등 교차는 자름선을 이용하지 않으므로 일정 교차나 다점 교차에 비해 스키마의 결합 형태가 다양하다
- 싸이클 교차, 순서 교차, PMX : 염색체가 순열로 표현되는 경우 적용 가능
- 산술적 교차 : 실수 염색체를 사용하는 경우이며, 염색체 각 위치에 대해 두 부모 염색체의 두 유전자 값에 대한 평균을 구해 자식해의 해당 위치로 배정
- 휴리스틱 교차 (간선 재조합) :
- 다차원 교차 연산 : 직선만으로 염색체를 분할하는 방법은 다양성이 줄어 새 스크마의 생성 능력이 떨어진다. 블록 균등 교차, 지오그래픽 교차, 내추럴 교차
※ 정규화 : 하나의 해를 표현하기 위한 염색체가 여러 개인 경우가 있다. 즉, 하나의 표현형에 대해 여러 개의 유전자형이 대응되는 경우이다. 동일한 해에 대해 복수 개의 염색체가 존재할 때, 두 부모 염색체 중 하나의 염색체를 바꾸어서 부모해의 특성을 보다 잘 반영하도록 하는 것

3. 변이 연산 : 부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산, 임의로 일어나므로 변이는 절대적인 비율로 해의 품질을 저하시킨다
- 전형적 변이 : 각각의 유전자에 대하여 [0, 1) 범위의 난수를 생성하여 미리 정한 임의의 임계값 (0.015~0.01) 미만의 수가 나오면 해당 유전자를 임의로 변형
- 비균등 변이 : 유전 알고리즘이 진행됨에 따라 변이의 강도를 점점 줄여가는 비균등 변이 연산
- 수선 : 교차와 변이가 모두 해의 적법성(예, 0과 1의 수가 같아야 함)을 깰 수 있으므로 대부분 수선은 변이까지 수행한 후에 행한다.

4. 대치 연산 : 한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해(들)와 대치하게 되므로 대치될 대상을 고르는 작업이 매우 중요한 영향을 미친다.
가장 손쉬운 방법은 해집단 내에서 가장 품질이 낮은 해를 대치. 해집단에서 가장 우수한 해는 대치되어 없어지지 않도록 하는 것 (엘리티즘)
해집단에서 자신과 닮았을 가능성이 가장 높은 해가 부모해이므로 다른 해보다 부모해 중의 하나를 제거하는 것은 다양성 유지에 도움이됨
해집단의 다양성을 유지하기 위해 해집단 전체를 비교하여 자신과 가장 가까운 해를 대치하는 방법을 쓰기도 함.


Chapter 4. 스키마와 문제 공간

스키마 : 염색체들에 포함되어 있는 패턴을 의미. 일차원, 다차원 스키마
유전 알고리즘은 초기의 염색체들에 포함되어 있던 ‘소규모의‘ 스키마들이 결합되어 점점 규모가 더 큰 고품질의 스키마로 만들어져 가는 과정.
스키마 길이(length) : 스키마의 맨 왼쪽 특정 기호에서 맨 오른쪽 특정 기호에 이르는 길이
스키마 차수(order) : 스키마에 포함된 특정 기호들의 총 수
스키마 정리 (홀랜드, 1975) : 일정 교차를 사용하는 유전 알고리즘에서 스키마의 생존에 스키마의 길이와 품질이 큰 영향을 미친다는 의미

- 스키마 정리는 스키마의 생존 가능성에 대한 하한선을 제시한다.
- 내재적 동시성 : 홀랜드는 해집단의 해들의 품질을 평가함으로써 그 속에 깃든 많은 수의 스키마의 품질을 동시에 평가하게 되는 유전 알고리즘의 성질
빌딩 블록 가설 : 스키마 정리는 교차와 변이의 파괴적 성질과 관련시켜 분석한 것이고, 교차의 건설적 성격은 명시적으로 나타나 있지 않다. 빌딩 블록 가설은 유전 알고리즘의 동작 원리를 교차의 건설적인 측면과 관련해 설명하는 핵심적인 가설인데, 유전 알고리즘이란 궁극적으로 작은 (저차수의) 스키마들의 ‘ 병렬 배치'에 의해 점점 더 큰 (고차수의) 스키마로 발전하는 과정이라는 것이다.

스키마의 생존 확률 : 기본적인 사실은 모든 특정 기호들 사이에 짝수 개의 자름선이 존재하면 (0인 경우 포함) 스키마는 생존한다는 것이다.
생존 확률은 중요하지만 유전 알고리즘의 성능을 향상시키는 데 절대적인 조건은 아니다. 염색체 표현이 바뀜으로써 한 스키마의 생존 확률이 높아지면 그에 따라 생존 확률이 낮아지는 스키마가 필연적으로 생긴다. 중요한 것은 대체로 고품질의 스키마의 생존 확률이 높아지도록 할 수 있으면 유리하다는 것이다.
- 임의의 교차 연산이 채굴의 경향이 강하면 탐험의 경향이 약해지고, 탐험의 경향이 강해지면 채굴성이 떨어진다.
- 공간 탐색의 관점에서 본다면 채굴이란 이미 가본 곳 근처를 좀 더 심도 있게 보려는 경향이고, 탐험은 여태껏 가보지 않은 곳을 가보려는 경향이다.
- 이 두 경향을 적절한 선에서 조절하는 것이 유전 알고리즘의 성능에 중요한 영향을 미친다.

상위(epitasis) : 원래 유전학에서 한 유전자가 다른 유전자의 발현을 억제하는 역할을 할 때 사용되지만, 유전 알고리즘이나 복잡계 연구에서는 유전자 또는 인자들 간의 상호 관계를 총칭하는 말로 사용한다. 상위가 작은 문제는 유전자들을 ‘비교적‘ 독립적으로 취급할 수 있으므로 문제 공간의 적합도 지형은 단순해지고 문제는 쉬워진다.
유전 알고리즘은 ‘중간‘ 정도의 상위도를 가진 문제에 가장 적합한 것으로 인식되고 있고 상위도가 지나치게 낮으면 언덕 오르기와 같은 간단한 방법들이 더 효율적이다. 상위도가 높은 문제를 표현 방식이나 적합한 연산을 통하여 상위도를 떨어뜨릴 수 있으면 유전 알고리즘에게 더 쉬운 문제로 변한다.
문제 공간 상에서 해의 품질과 전역 최적해와의 거리간의 상관 관계를 나타내는 적합도-거리 상관관계를 조사함으로써 문제의 난이도를 예측하려는 시도

문제 공간은 최상의 해를 중심으로 ‘큰 계곡(big valley)’을 이루고 있음을 강하게 시사한다. 큰 계곡에 대한 통찰은 문제의 해결에 최적해들끼리 부분 결합하여 새로운 해를 만드는 혼합형 유전 알고리즘도 효율적일 것임을 아울러 암시하고 있다.
문제 공간 중앙 부근의 매력 – 지역 최적해(최상해, 평균해, 중점해, 상관계수) 중 중점해는 핵심으로, 지역 최적해들의 유클리드 공간 중심점의 품질이다.

문제 공간의 모양이나 지역 최적해들의 분포에 대한 제대로 된 이해 없이 공간 탐색을 시도하는 것은 눈을 감은 채로 길을 찾는 것과 같다.
끌개 : 지역 최적해는 끌개(attractor)라고도 한다. 문제 공간에서 해의 이동을 통해 탐색을 하려면 해를 바꾸는(이동시키는) 기본 연산이 있어야 한다.
이 연산에 따라 문제 공간의 모양이 결정된다.
문제 공간은 연산자에 따라 결정된다. 연산자가 탐색 알고리즘이 문제 공간에서 어떻게 이동할 것인지를 결정해주기 때문이다.
A라는 연산자로는 끌개가 되는 해가 B라는 연산자로는 끌개가 아닐 수 있다.


Chapter 5. 확장된 주제들

정규화는 한 개의 해를 표현하기 위한 염색체가 여러 개인 경우, 즉 하나의 표현형에 여러 개의 유전자형이 대응되는 경우 교차 연산에 초래하는 혼란을 줄일 수 있는 기법이다. 정규화(normalization)는 문제 공간의 크기를 줄여주는 함수 효과가 있다.
정규화로 인해 공간 탐색의 범위를 제한하는 효과가 있어 유용한 공간을 놓칠 가능성도 있다. 그렇지만, 현실적인 시간에 최적해를 보장할 수 없는 방대한 공간을 가진 문제들의 경우, 제한된 시간을 효율적으로 사용하는 것이 놓칠지 모르는 공간을 염려하는 것보다 중요하다.
- 고급 정규화
- 그래프 분할 : 임의의 그래프를 같은 수의 노드를 갖는 두 부분 집합으로 분리하되 두 부분 집합을 연결하는 간선의 개수, 즉 교차 간선의 수를 최소화하는 분리 방법을 찾는 문제
- 정렬 네트워크 : 다수의 비교자를 통해 버스의 데이터를 교환하면서 정렬을 한다. (하드웨어 정렬 로직)
- 신경망

복수 개의 목적 함수를 동시에 만족시켜야 하는 경우가 있다. 만일 이 복수 함수를 독립적으로 최적화할 수 있다면 논란거리가 되지 못한다. 그렇지만, A라는 목적에 잘 맞는 해가 B라는 목적에도 꼭 맞는 것이 아니라면 이들을 모두 고려하기는 쉽지 않다. 이것은 OR 분야에서는 오래 전부터 문제가 되어 온 주제인데, 모든 목적 함수에 대해 최적인 해는 근본적으로 존재하지 않는 경우가 많다.
복수 개의 목적 함수를 다루는 가장 단순하고 전형적인 방법은 각 목적 함수에 대해 실수 가중치를 주어 하나의 목적 함수로 통일하는 방법이다.

아래와 같이 요구 수준 벡터 y를 설정해 놓고 이를 기준으로 적합도를 계산하는 방법도 있다.


미미틱 유전 알고리즘 (혼합형 유전 알고리즘) : 유전 알고리즘은 방대한 문제 공간 탐색 능력이 있으며 이미 만들어진 해들의 특징을 효율적으로 이용할 수 있지만 지역 최적점으로의 접근 속도는 느린 편이다. 정도의 차이는 있지만 교차와 변이 연산이 임의적으로 이루어지므로 지역 최적점 근처에서의 미세 조정 능력이 떨어지기 때문이다. 이를 보완하기 위해 교차와 변이로 만들어진 해에 지역 최적화 알고리즘
지역 최적화 알고리즘은 일반적으로 초기해에 매우 민감하다. 미미틱 유전 알고리즘은 두 가지 관점에서 볼 수 있는데,
첫째는 지역 최적화 알고리즘이 유전 알고리즘의 지역 최적점 근처에서의 미세 조정을 돕는다는 관점이다.
그리고 둘째는 유전 알고리즘이 지역 최적화 알고리즘을 위한 다양한 초기해를 제공한다는 점이다.
지역 최적화 알고리즘의 몇 가지 예로 일반적인 언덕오르기 알고리즘, 그래프 이등분 문제를 위한 Kernighan-Lin 알고리즘, TSP를 위한 2-OPT, 3-OPT 등등
미미틱 유전 알고리즘은 크게 라마르크형과 볼드윈형이 있다.
- 라마르크형 유전 알고리즘은 염색체에 지역 최적화 알고리즘을 적용한 다음 염색체를 덮어쓴다. 즉, 지역 최적화의 결과로 염색체가 바뀐다.
- 볼드윈형 유전 알고리즘은 지역 최적화 알고리즘을 적용은 하되 염색체는 그대로 둔다. 결과로 나온 해는 염색체의 적합도 평가를 위해서만 참조만 된다.
미미틱 유전 알고리즘은 유전 알고리즘의 미세 조정 능력을 향상시키고 수렴 시간을 단축시키는 장점이 있지만,미세 조정에 이용되는 지역 최적화 알고리즘의 공간 탐색 스타일에 큰 영향을 받는다.

개체군집최적화(PSO, Particle Swarm Optimization) : 개체들을 군집으로 관리하면서 이들이 상호간의 관계 네트워크를 통해 진화를 하도록 하는 방식으로 새들이 먹이를 찾아 무리지어 이동하는 모양을 상상하면 된다.
- 복수의 군집을 가지고 운영된다. 각 군집의 개체들은 다른 개체들과 교류하면서 진화한다. 하지만 각 객체가 모두 교류할 수 있는 것은 아니고 현재 운영 중인 모든 개체 중 가장 좋은 개체와 ‘이웃'의 범주에 드는 개체와만 교류한다. 이웃은 미리 정의된다.
- PSO 알고리즘이 한 라운드는 각 개체에 대해 위치 조정을 한다. 해당 개체의 인접 개체들 중 가장 좋은 개체와 전체에서 가장 좋은 개체의 방향을 참조해서 수정된다. 이웃의 크기를 작게 하면 개체간의 교류가 제한적이라 수렴 속도는 느려지고, 이웃의 크기를 크게 하면 교류가 활발해 수렴이 빨라진다.
- PSO는 진화를 위해 집단을 운영한다는 점에서는 유전 알고리즘과 유사하나 유전 알고리즘과 같이 교차나 변이 연산은 사용하지 않는다. 다만 이동 방향을 결정할 때 사용하는 세 랜덤수가 일종의 변이 효과를 내기는 한다.

병렬 유전 알고리즘 : 복수의 해를 동시에 관리하면서 수행되고 이 해들을 생성하는 데 있어 그 순서는 특별한 의미를 갖지 않는다.
- 복수의 프로세스를 두고 한 프로세서에 하나 또는 두어 개의 염색체를 할당하는 방식
- 각 프로세서가 각자의 해집합을 갖고 진행하는 방식으로 프로세서들의 연결 방식에 따라 해 집합들 사이의 교신 방식이 결정된다.
- 서버가 전체 해집합을 생성, 관리하되 해의 적합도 평가나 지역 최적화 부분만 각 클라이언트에 맡기는 방식

유전 알고리즘의 해집단이 어느 정도 수렴을 하면 해집단의 다양성이 떨어져 새로운 최적해를 찾기가 점점 어려워진다. 선택압을 낮추면 해집단의 수렴 속도를 떨어뜨릴 수는 있다. 적당한 선택압을 유지하면서 해집단의 다양성을 높이는 다양한 방법들이 개발되어 왔다.
- Hollstien(1971)은 복수 개의 종족을 두고 해집단의 평균 적합도가 향상되는 동안은 종족 내에서만 교차를 시키고, 그렇지 않을 때는 종족 간의 교차 연산
- Booker(1982, 1985)는 교배 주형을 이용한 제한 적 교차. 예) 교배 주형 ( *10* / *01* )에 맞는 염색체에 대하여 교차 연산을 하도록 함. 이것은 적합도를 가지고 교차를 조절하지 않고 교차의 경향성을 제한함으로써 유전 알고리즘의 성능을 향상시키고자 하는 의도에서 제안된 방법이다. 이렇게 함으로써 몇 개의 지역 최적점 근처로 해들이 분산되어 수렴하는 경향을 기대할 수 있는데 이러한 현상을 종족화(speciation)라 한다
- 섬식 방법(island method) : 종족화 방법 중 Hollstien(1971)의 방법과 같이 복수 개의 해집단을 두고 각 해집단 내에서 유전 알고리즘을 폐쇄적으로 운영하다가 적당한 시기에 (예를 들어, 개별 해집단 내에서 더 이상의 개선이 없거나, 개별 해집단에서 주어진 시간 예산만큼 진행하다가) 해집단 간의 교차 또는 이동을 허용하는 방법

분류자 시스템은 협동을 유발할 수 있는 환경과 유전 알고리즘을 결합하여 분류자(classifier)라 불리는 간단한 규칙을 생성하고 학습시키는 시스템
- 큰 범주에서 ‘진화를 이용하는 기계 학습'에 속하는 데, 이 분야는 미시간 접근 방식과 피츠버그 접근 방식으로 나뉜다.
- 구성 요소 : 규칙/메시지 시스템, 신용 할당/관리 시스템, 분류자를 진화시키는 유전 알고리즘
- 분류자 시스템은 학습이 필수적인 요소이므로 Learning Classifier Systems(LCS)라는 용어도 일반화되어 사용됨


공진화 :
- 치타는 가젤을 잡으려 한다. 가젤은 치타에게 포획되지 않도록 피하는 것이 생존에 절대적이다. 이들은 상대방의 능력이 개선되는 속도에 맞추어 서로 진화를 한다. (비대칭적 군비확장 경쟁)
- 숲의 나무들이 키를 키우는 이유는 다른 나무들이 높기 때문이다. 낮은 키로는 햇볕을 받을 수 없다. 키가 크면 아무래도 유지하는 데 비용이 많이 들므로 키가 지나치게 클 필요가 없는데도 인접하는 나무들과의 경쟁 때문에 그렇게 진화한다. (대칭적 군비 확장 경쟁)

에코 모델 : 공진화와 더불어 유전 알고리즘에 관한 최근 연구로 빼놓을 수 없는 것이 홀랜드의 에코 모델이다. (Holland, 1992)
- 유전 알고리즘은 기본적으로 열린 시스템이다. 즉, 개체의 적합도를 외부에서 평가해주어야 한다. 이에 반해 자연 생태계는 적합도의 개념이 그 속에서 저절로 발생한다. 고정되어 있지도 않다.
- Holland : 적합도를 미리 정의해주지 않고 자발적으로 발생하는 닫힌 유전 알고리즘을 연구
- 에코는 외부로부터 명시된 적합도 평가를 제거함으로써 유전 알고리즘 분야에서 최초의 닫힌 시스템이다. 실제의 생태계에서는 개체들이 복잡한 공진화의 어울림에 의해 끊임없이 순환하며 서로를 뒤쫓는다. 획일적으로 정의할 수 있는 적합도란 존재하지 않는다. ‘현재의’ 생태계에서 공존하는 개체들에 대해 충분한 경쟁력이 있으면 충분히 적합한 개체가 된다. 당연히 생태계는 변하고 이에 따라 적합도의 특성도 달라진다.
- 에코는 유전 알고리즘을 생태적 환경으로 확장하고, 지리적 분포의 개념을 도입하며, 제한된 자원에 대한 경쟁과 개체들간의 상효 관계를 포함한다. 에코는 생태계의 중요한 성질에 대한 통찰을 얻기 위한 것이지 특정한 생태계를 모델링하려는 것은 아니다. 에코는 공진화를 보다 실체적으로 이해하기 위한 것이다. 공진화는 복잡한 적응적 시스템에서 창발과 자기 조직화를 이루는 근원으로 작용한다. 이 현상을 보다 깊게 이해하려면 외부로부터의 보상을 제거할 필요가 있다. 에코는 최초로 외부로부터의 보상을 제거한 닫힌 시스템이다
- 에코 월드 (Forrest & Jones, 1994) : 정해진 수의 구역(site)을 갖는다. 각 구역에는 에이전트들이 존재. 자원 종류, 세율, 복제율, 사망률
- 에코 싸이클
① 에이전트들간의 상호 관계를 각 구역 내에서 일어난다. 각 에이전트는 교역, 짝짓기, 또는 전투를 통해 관계한다.
② 에이전트는 자신이 속한 구역에서 자원을 모은다. 각 구역은 자원을 생산하고 이 자원은 해당 구역에 있는 에이전트들에게 배분된다.
③ 에이전트는 세금을 낸다 (확률적으로). 세금 낼 자원이 없으면 에이전트는 사망하고, 잔여 자원은 구역에 반환된다.
④ 에이전트들은 낮은 확률로 임의 사망한다.
⑤ 각 구역은 자원을 생산한다. 구역별로 다른 자원을 다른 양으로 생산할 수 있다.
⑥ 한 싸이클에서 자원을 전혀 추가하지 못한 에이전트는 이웃 구역으로 이주한다.
⑦ 자기 복제를 할 수 있는 양만큼의 자원을 가진 에이전트는 복제를 한다.
- 에이전트: 자원의 종류 유전자, 태그 유전자(공격/방어/짝짓기), 조건 유전자(전투/교역/짝짓기 조건), 교역 자원 유전자를 가진 염색체로 표현된다.
- 에이전트들 간의 교류 : 전투, 교역, 짝짓기 (교차 연산)
- 에이전트의 이동 (구역 내, 구역 외)
- 에코의 한계와 장래 : 에코는 아직 생태계의 시뮬레이션에 초점을 맞추고 있다. 외부적 보상에 의해 움직이지 않는 복잡 적응 시스템의 참된 출발점에 해당하는 역사적 의미를 가진 시스템이다.

복잡계 : 단순한 하위 구조들의 결합에 의해 하위 구조에는 없는 특성을 가진 상위 구조가 창발(emergent)하는 시스템.
- 질서와 혼돈의 사이에 어딘가에 복잡계가 존재한다. => 역동적 균형, 아슬아슬한 균형
- 역동적 균형의 상태에서 창발성을 나타낼 수 있는 가능성이 가장 높아지는 것으로 보인다.
- 적응적 복잡계(생태계, 유전 알고리즘)와 비적응적 복잡계(카오스, 전기 회로 등)


Chapter 6. 유전 알고리즘의 응용 예들

1. 함수 최적화는 유전 알고리즘의 대표적인 응용 분야 중 하나다. 주어진 함수 값을 최대화 또는 최소화하는 변수(들)을 찾는 문제.

2. 시스템 최적화 : 데이터로부터 이를 가장 잘 설명하는 시스템을 찾아낸 것으로 시스템 규명(system identification)이라고 부른다. 다시 말하면 훈련 데이터들로부터 알려지지 않은 시스템의 수학적 모델을 찾아내는 것이다. 여기서 모델은 함수나 신경망 또는 기타 다른 시스템이 될 수 있다.
- 함수 근사 : 함수 최적화는 주어진(고정된) 함수를 가지고 최적의 변수 값(들)을 찾는데 반해, 함수 근사는 함수 자체를 찾는다. 예) 회귀 분석
- 신경망 최적화 : 뉴런들과 연결망을 고정한 다음 각 간선들의 가중치만을 조절해 최적의 가중치 집합을 찾거나, 연결망을 고정하지 않고 연결망의 구조를 진화시키는 방법이 있다.
- 퍼지 시스템 최적화
- 엘리베이터 그룹 스케줄링

3. 조합적 최적화 (combinatorial optimization)
- 순회 세일즈맨 문제 (TSP)
- 차량 라우팅 : 복수 개의 차량으로 복수의 고객에게 서비스하는 가장 효율적인 방법을 찾는 문제
- 그래프 분할 : 그래프 이등분 문제는 임의의 그래프를 같은 수의 노드를 갖는 두 부분집하으로 분리하되, 두 부분 집합 간에 걸치는 간선의 개수를 최소화 하는 문제
- 단백질의 3차원 구조 : 단백질은 연속된 아미노산들의 띠로서 고유의 3차원 구조를 갖는다. 이 3차원 구조에 의해 담백질의 성격이 결정된다. 임의의 단백질이 물과 같은 임의의 용액 중에 놓일 때 용액은 친수성 아미노산을 끌어당기고, 소수성 아미노산은 밀친다. 가능한 3차원 구조들 중 최소의 에너지를 갖는 구조를 찾는 것이 유명한 단백질 접기 문제다.
- VLSI 회로 배치
- 네트워크 배치
- 직교형 스타이너 트리 문제 : 이차원 공간에 n개의 점이 주어진다. 이 점들을 다 잇되 이에 사용되는 간선의 길이의 총합을 최소화하는 문제
- 영상 압축을 위한 벡터 양자화
- 정렬 네트워크
- 지수귀문도 : 일존의 마방진
- 죄수의 딜레마 문제

창발성 : 하위 구조의 작은 구성 요소들이 결합하여 상위 구조를 만들어 내는데, 하위 구조의 구성 요소들 각각에는 존재하지 않는 새로운 특성이 상위 구조에서 나타나는 현상으로 우리의 지적 역량이 진화해가는 과정을 살펴보면 다름 아닌 이러한 창발의 과정이다.
개인의 힘으로 한계가 있는 연구나 개발은 학제간 협력 작업으로 보완할 수 있다. 학제간 연구라는 것도 개인이 갖지 못한 하위 구조를 남으로부터 빌어 창발적 결과를 도출하고자 하는 것이다.
고급의 창조력을 갖기 위해서는 다소 고통스런 기본기 수련의 기간을 거칠 필요가 있다.


Chapter 7. 유전 알고리즘의 구체적 예(1) : 그래프 분할

Kernighan-Lin (KL) 알고리즘 : 임의의 이등분으로 시작하여 양쪽에서 같은 사이즈의 부분 집합을 교환함으로써 품질을 개선시켜가는 방법
시뮬레이티드 어닐링(Simulated Annealing, SA) : 추이통계적 최적화 기법의 하나로 확률적 언덕오르기

그래프 이등분을 위한 유전 알고리즘 – 전처리된 미미틱 유전 알고리즘

; 문제 표현 – 초기화 – 선택 – 교차 연산 – 변이 연산 – 지역 최적화 – 대치 – 수행 중단 기준


Chapter 8. 유전 알고리즘의 구체적 예(2) : TSP

TSP (Traveling Salesman Problem) : 순회 세이즈맨 문제
지역 최적화 알고리즘
- 2-OPT 알고리즘 : 가능한 2-change를 계속 시도해 보면서 개선이 있으면 택하고 그렇지 않으면 없었던 일로 한다. 이런 식으로 해를 변경해 가면서 어떠한 2-change로도 개선이 불가능할 때까지 수행한다.
- 3-OPT 알고리즘 : 2-OPT 알고리즘에 비해 성능이 ‘훨씬‘ 좋다. 단 시간이 오래 걸린다.
- Or-OPT 알고리즘 :
- Lin-Kernighan(LK) 알고리즘) : 초기해로부터 시작하여 간선을 하나 삭제하고 이 간선의 끝점에 연결된 다른 간선 중 가장 매력적인 간선을 하나 삽입한다. 같은 방법으로 또 다른 간선을 삭제하고 가장 매력적인 간선을 하나 삽입한다. 이 때 새로 삽입되는 간선을 통해 연결된 정점은 다시 선택되지 못하도록 고정(lock)된다. 이런 과정을 더 이상 진행할 수 없을 때까지 반복하는 과정에서 이득의 합이 가장 큰 지점까지만 유효하게 하고 나머지는 없었던 것으로 한다. 이렇게 하면 하나의 새로운 해가 만들어진다. 이것을 초기해로 더 이상 개선이 없을 때까지 앞의 과정을 반복한다.

다시 강조하면, 다른 NP-Hard 문제들과 마찬가지로 문제의 사이즈가 어느 정도 이상 되면 지역 최적화 알고리즘을 사용하지 않는 지역 최적화 알고리즘을 사용하지 않는 순수 유전 알고리즘은 한계가 있다. 지역 최적화 알고리즘이 양질의 해를 얻는 데 가장 큰 기여를 한다면 유전 알고리즘의 나머지 프로세스는 최고 품질의 해로 만드는 역할을 한다.
멀티 스타트 알고리즘 : 초기해를 임의로 여럿 만들어 지역 최적화를 반복한 다음 이 과정에서 찾은 가장 좋은 해를 답으로 삼는 것


Chapter 9. 다른 스토캐스틱 탐색 기법들

진화 연산은 유전 알고리즘, 유전 프로그래밍, 진화 전략, 진화 프로그래밍으로 나누어 진다.
- 진화 전략(Evolution Strategies) : 하나의 해로 시작하여 이를 계속 바꾸어 가는 형태, 해집단의 크기가 1이고 변이 연산만을 사용.
- 진화 프로그래밍(Evolutionary Programming) : 유한 오토마타를 진화시키기 위한 목적으로 제시. 교차를 사용하지 않음
- 유전 프로그래밍(Genetic Programming) : 프로그램의 자동 생성을 위해 유전적 원리를 이용. 교차와 변이는 진화 연산의 네 분파 중 유일하게 트리 구조의 염색체를 대상으로 한다. 교차는 투 개의 트리를 부분 결합하여 하나의 트리를 만들어 낸다.

시뮬레이티드 어닐링(SA) : 담금질의 통계 역학으로부터 유래한 최적화 기법. 담금질 할 때 초기에 금속이 뜨거울 때는 분자들이 높은 운동성을 갖고 금속의 온도가 내려감에 따라 운동성이 떨어지는 성질을 이용하여 금속의 조직을 치밀하게 한다. SA는 초기에는 온도 인자를 높게 주어 해가 자유로이 이동할 수 있게 하고 시간이 지남에 따라 온도 인자를 떨어뜨려 해의 품질이 좋아지는 쪽으로 이동을 강화시킨다.
- 본질적으로 언덕오르기 휴리스틱을 변형한 것
- 부정적 이동 : 품질이 더 나쁜 지점으로도 약간의 확률로 이동할 수 있다. 탐험 능력을 제공한다. 지역 최적점을 벗어날 수 있다.

큰 스텝 마르코프 체인(Large Step Markov Chain) : 공간 탐색 기법으로 교란과 지역 최적화를 결합한 탐색 방법이다.
- 지역 최적해를 구한 다음 그 곳을 기준으로 다시 교란을 한 후 지역 최적화 알고리즘을 적용하고, 이렇게 얻은 지역 최적해를 다시 교란 후 지역 최적화 알고리즘을 적용하고 하는 식으로 반복한다.

타부 서치 (Glover, 1977) : 공간 탐색 방법으로서 지역 최적점을 벗어나는 효율적 방법 중 하나다.
- 최근에 방문한 적이 있는 해들의 목록을 유지하면서 이들에 대한 반복적인 방문을 피함으로써 공간 탐색의 효율을 꾀한다.


맺음말

20세기를 지배한 사고 방식 중 가장 중요한 것은 데카르트-뉴튼의 결정론적 사고 방식이다. 이것은 유물론적이고 일차원적인 사고 방식을 전파시키는 데 큰 역할을 하였다. 문제를 대할 때도 원인과 결과가 선형적 관계를 가지는 단순 관계의 발견을 주로 추구한다. 이것은 근세 이전까지의 주술적 사고 방식을 ‘과학적‘ 사고 방식으로 변화시키는 데 더 없는 역할을 하였으나 이제는 더 이상 ‘과학적'이라는 표현을 대표하지 못한다. 어떤 관점에서 보면 이것은 문화적 집단광기였을 수도 있다.
유전 알고리즘이 현재 가장 효과적인 공간 탐색 능력을 가진 대표적인 기법인 것은 분명하나 모든 문제를 해결해주는 마법의 손은 아니다. 순수 유전 알고리즘은 넓은 탐색 능력을 가진 대신 지역 최적점 근처에서의 미세 조정 기능은 약하고, 일정 규모 이상의 문제에 대해서는 다소 낭비라 할 정도로 시간을 소비할 수 있다.
유전 알고리즘은 해를 집단적으로 운영하므로 일부 과정에서 파괴적인 현상이 발생하더라도 다른 해에서 복원할 수 있다는 점에서 결함에 대한 내성이 강한 평니다. 또한 교차는 기존의 해들의 특성을 부분 조합하여 새로운 해를 만들어 내므로 과거의 기록을 효율적으로 이용하는 매력적인 성질을 갖고 있다. 교차가 과거의 해들에 있는 특성을 부분 결합하는 데 반해 변이는 과거의 해에 없는 특성을 발현 가능하게 해준다. 유전 알고리즘이 교차와 변이의 상이한 공간 탐색 유형을 결합함으로써 시너지 효과를 얻는다고 볼 수 있다.
최근에 복잡성 과학이 부상하고 있다. 유전 알고리즘은 복잡성 과학에서 중요한 한 축을 차지하고 있어 이 분야의 발전과 더불어 발전하는 혜택을 누리게 될 것이다. 유전 알고리즘은 가능성은 크지만 약점과 한계를 갖고 있는 기법이라는 점도 분명히 해야 할 것이다. 그리고 그 기본 구조가 단순하여 적용하기가 용이한 반면, 알고리즘, 수학 등과의 유기적 결합에 의해서 큰 문제에 대하여 제대로 된 결과를 내는 학제적 성격이 강한 학문임도 잊지 말아야 할 것이다.