GA : 그들은 무엇인가?

 

유전자 알고리즘 : Zbigniew Michalewicz 저서, 공성곤.김인택.박대희.박주영.신요안 공역, 도서출판 그린 (원서 : Genetic Algorithm + Data Structure = Evolution Programs, 1996), Page 20~42

 

1. 단순한 함수의 최적화

  1) 표현방법

  2) 초기 개체집단

  3) 평가함수

  4) 유전 연산자

  5) 매개변수

  6) 실험 결과

2. 죄수의 딜레마

  1) 전략의 표현

  2) 유전자 알고리즘의 윤곽

  3) 실험 결과

3. 순회 판매원 문제

4. 등반, 시뮬레이티드 어닐링, 그리고 유전자 알고리즘

5. 결론

 

충분히 빠른 알고리즘이 개발되지 않은 많은 부류의 흥미있는 문제들이 있다. 이러한 문제들은 여러 응용에서 흔히 제기되는 최적화 문제이다. 어려운 최적화문제가 주어졌을 때 근사 최적해를 제공하는 효과적인 알고리즘을 찾아내는 것이 종종 가능하다. 어떤 어려운 최적화 문제에 대하여 확률적인 알고리즘을 사용할 수 있는데, 이러한 알고리즘들은 최적값을 보장해 주지는 못하지만, 충분히 많은 "목격자" 들을 임의로 선택함으로써 오차 확률을 원하는 만큼 작아지도록 할 수 있다.

그러한 고품질의 알고리즘들을 적용할 수 있는 중요한 실제적인 최적화 문제가 많이 존재한다 [53]. 예를 들어 VLSI 의 설계에서 선로의 라우팅 및 부품의 배치문제에 대해 또는 순회 판매원 문제에 시뮬레이티드 어닐링기법을 적용시킬 수 있다. 게다가 많은 다른 대규모 조합최적화 문제들 (이러한 문제들은 NP-hard 라고 알려져 있다) 이 이러한 종류의 몬테 칼를로 기법에 의해 현재 수준의 컴퓨터에서 근사적으로 해결될 수 있다.

일반적으로 성취되어야 할 어떤 추상적인 과제는 해가 될 가능성이 있는 것들의 공간에서의 탐색문제로 생각할 수 있다. 우리는 "최적" 해를 추구하고 있으므로 이러한 과제를 최적화 과정으로 볼 수 있다. 보통 작은 공간에서는 고전적인 완전검색 방법으로 충분하지만, 큰 공간에서는 특수한 인공지능 기법이 사용되어야 한다. 유전자 알고리즘 (GA) 은 그러한 기법들 중 하나인데, 유전적 계승과 다아윈적 생존 경쟁이라는 자연의 현상을 모델링한 확률적인 탐색방법이다. [54] 에서 언급된 바와 같이 :

유전자 알고리즘의 배후의 아이디어는 자연이 행하는 것을 그대로 실현하는 것이다. 예를 들어 토끼를 생각해 보자. 어떤 시점에 토끼들의 집단이 존재하고, 그들 중 어떤 것들은 다른 것에 비해 더 빠르고 영리하다. 빠르고 영리한 토끼는 여우에게 잡아 먹힐 가능성이 작으므로 많은 수가 생존할 수 있으며 더 많은 토끼를 만들어 낼 것이다. 물론 느리고 영리하지 못한 토끼는 운이 좋아야만 생존할 수 있다. 살아남은 토끼들의 집단은 번식하기 시작하고 번식 결과로 토끼의 유전재료들이 잘 혼합된다 : 느린 토끼와 빠른 토끼의 혼합, 빠른 토끼와 빠른 토끼의 혼합, 영리한 토끼와 영리하지 않은 토끼의 혼합, 등. 이밖에도 자연은 가끔씩 토끼의 유전재료에 돌연변이를 주어 '야생토끼' 의 기회를 준다. 빠르고 영리한 부모 토끼들이 여우로부터 생존하였으므로 결과적으로 어린 토끼들은 (평균적으로) 원래의 개체집단보다 더 빠르고 영리할 것이다 (토끼들이 빠르고 영리해져서 그들을 잡을 수 없게 되면 여우들도 비슷한 과정을 겪는다).

유전자 알고리즘은 토끼의 이야기와 밀접하게 대응되는 단계별 과정을 따른다. 유전자 알고리즘의 구조를 주의 깊게 살펴보기 전에 유전학의 역사를 간략히 살펴보도록 하자 ([289] 로부터).

유전자 알고리즘은 자연의 유전학으로부터 빌어 온 어휘를 사용한다. 개체집단에서 개체 (또는 유전자형, 구조) 에 관하여 이야기하는데, 흔히 이들 개체들은 스트링 또는 염색체라고도 불린다. 이것은 약간 오해를 불러일으킬 수도 있는데, 어떤 종의 조직세포는 일정한 수의 염색체 (예를 들어 인간은 46 개) 를 갖는다. 그러나 이 책에서는 하나의 염색체를 가지는 개체, 즉 반수 염색체만을 취급한다. 배수, 즉 염색체의 쌍에 관한 추가적인 정보와 유전자 알고리즘과 연관되는 다른 관련된 문제를 위해서는 [113] 과 Greene [124] 의 최근 연구를 참고하라). 염색체들은 선형적으로 배열되어 있는 유전인자 (특징, 특성, 해독기) 라는 단위로 구성되어 있는데, 모든 유전인자는 하나 또는 여러 특징의 유전성을 통제한다. 어떤 특징의 유전인자들이 염색체에 놓여 있는 위치를 로커스 (스트링 위치) 라고 부른다. 개체의 어떤 특징들 (머리카락 색깔과 같은) 은 스스로를 다르게 보일 수도 있는데, 이 유전자는 대립유전자 (특징값) 라 불리는 여러 상태를 가질 수 있다.

각 유전자형 (이 책에서는 하나의 염색체) 은 문제에 대한 해가 될 가능성이 있는 것을 나타낸다 (특별한 염색체의 의미, 표현형은 사용자에 의해 정의된다). 염색체의 개체집단 위에서 진행하는 진화과정은 해가 될 가능성이 있는 것들의 공간을 통한 탐색에 해당한다. 그러한 탐색은 최선의 해를 이용하는 것과 탐색공간을 조사하는 것이라는 두 개의 (분명히 서로 상충되는) 목적들 사이에 균형을 필요로 한다 [35]. 등반은 개선시키기 위해 최선의 해를 이용하는 반면에 탐색공간의 전역탐색을 무시하는 전략의 한 예이다. 임의 탐색은 전체공간에서 해가 존재할 가능영역을 이용하지 않고 공간을 전역 탐색하는 전형적인 전략이다. 유전자 알고리즘은 탐색과 해의 가능영역들을 놀랄만큼 균형있게 이용하는 일반성있는 (문제영역과 무관한) 부류의 탐색방법이다.

GA 는 선로 라우팅, 스케줄링, 적응제어, 게임놀이, 인지 모델링, 운송문제, 순회판매원문제, 최적제어문제, 데이터베이스의 질의 최적화문제에 상당히 성공적으로 적용되어 왔다 (참고문헌 [25], [34], [64], [113], [126], [129], [130], [209], [206], [259], [299], [300]). 그러나 De Jong [64] 은 GA 를 최적화 도구로 간주하는 것에 대해 다음과 같이 경고하였다 :

그렇지만 최적화는 GA 의 적용가능성의 주된 분야이다. [263] 에서 (1981) Schwefel 은 다음과 같이 말하였다 :

지난 10년간 최적화의 중요성은 더욱 크게 증가하고 있는데, 많은 중요한 대규모 조합 최적화 문제와 구속조건이 많은 공학문제들이 현재 수준의 컴퓨터상에서 근사적으로 해결될 수 있다.

유전자 알고리즘은 그러한 복잡한 문제를 겨냥한다. 그들은 확률적인 알고리즘의 부류에 속해 있지만 방향성있는 탐색과 확률탐색의 요소를 결합하였으므로 임의 알고리즘과는 상당히 다르다. 이 때문에 GA 는 현존하는 방향성있는 탐색방법보다 더 강인하다. 유전자기반 탐색방법은 해가 될 가능성이 있는 개체집단을 유지하지만, 다른 방법들은 탐색공간에서 단 하나의 점을 처리한다는 것이 또다른 중요한 특징이다.

등반 방법은 반복적인 개선기법을 사용하는데, 탐색공간내에서 하나의 점 (현재점) 에 적용된다. 하나의 반복과정동안 새로운 점이 현재점의 이웃에서부터 선택된다 (이 때문에 이 기법은 이웃탐색 또는 국소탐색이라고도 불린다 [173]). 만일 새로운 점이 더 좋은 목적함수값을 제공한다면, 새로운 점은 현재의 점이 된다. 그렇지 않으면 다른 이웃점이 선택되고 현재점과 비교된다. 이 방법은 더 이상 개선이 불가능할 때 멈추게 된다.

등반 방법이 국소 최적값만을 제공하고 이 값들은 시작점의 선택에 따라 좌우된다는 사실은 분명하다. 더욱이 구해진 해의 (전역최적값에 대한) 상대적인 오차에 대하여 아무런 정보를 얻을 수 없다.

성공할 기회를 증가시키기 위하여, 등반 방법은 보통 많은 수의 다른 시작점에 대하여 시행된다 (이 점들은 임의로 선택될 필요는 없고 하나의 실해에 대한 시작점의 선택은 이전의 실행의 결과에 의해 좌운된다).

시뮬레이티드 어닐링 기법 [1] 은 등반 방법의 대부분의 단점들을 제거하는데, 해는 더 이상 시작점에 의해 좌우되지 않으며 (보통) 최적점에 아주 가깝게 된다. 이것은 수락확률  (현재점을 새로운 점으로 바꾸는 확률) 를 도입함으로써 이루어진다. 만일 새로운 점이 더 나은 목적함수 값을 제공하면 이고 그렇지 않으면 이다. 나중의 경우에 수락확률 는 현재점과 새로운 점, 그리고 추가적인 제어 매개변수인 "온도" 에 대한 목적함수값의 함수이다. 일반적으로 온도 가 낮을수록 새로운 점이 수락될 기회가 더 작아진다. 알고리즘의 실행동안 시스템의 온도 는 단계적으로 낮아지며, 실질적으로 더 이상 아무런 변화가 일어나지 않는 작은 값에서 멈춘다.

앞서 언급된 바와 같이, GA 는 해가 될 가능성이 있는 개체지반을 유지함으로써 여러방향의 탐색을 실행하고 이들 방향간의 정보형성과 교환을 장려한다. 개체집단은 진화과정을 흉내내는데, 각 세대에서 비교적 "좋은" 해들이 재생산되고, 반면에 비교적 "나쁜" 해들은 소멸된다. 다른 해들간의 차이를 구별하기 위해 환경의 역할을 수행하는 목적 (평가) 함수를 사용한다.

등반, 시뮬레이티드 어닐링, 그리고 유전자 알고리즘기법의 한 예가 1.4 절에 주어져 있다.

단순한 유전자 알고리즘의 구조는 어떠한 진화 프로그램의 구조와 동일하다 (서론의 그림 0-1 참조). 순환 동안에 유전자 알고리즘은 해가 될 가능성이 있는 것 (염색체 벡터), 의 개체집단을 유지한다. 각 해 는 평가되어 "적합도" 의 척도를 준다. 그러면 더 적합한 개체들을 선택함으로써 새로운 개체집단 (과정 t+1) 이 구성된다. 이 새로운 개체집단의 어떤 회원들은 교배와 돌연변이에 의해 변경과정을 겪어 새로운 해를 구성한다. 교배는 부모의 염색체의 일부분을 서로 바꿈으로써 부모의 특징을 결합하여 두 개의 유사한 자손들을 구성한다. 예를 들어 만일 부모가 5 차원 벡터 와 에 의해 표현된다면, 두 번째 유전인자 이후의 염색체를 교차시키면 두 개의 자손 와 이 생성된다. 직관적으로 교배연산자는 해가 될 가능성이 있는 것들 사이의 정보 교환을 위해 적용된다.

돌연변이는 돌연변이율과 동일한 확률을 가지고 임의로 변화시킴으로써 선택된 염색체에서 하나 또는 그 이상의 유전인자를 임의로 변경하는 것이다. 직관적으로 돌연변이 연산자는 개체집단에 추가로 변화를 도입하기 위해 적용된다.

유전자 알고리즘은 (모든 진화 프로그램처럼) 특정한 문제에 대해 다음과 같은 다섯가지의 요소를 가져야만 한다 :

세 가지 예제를 통하여 유전자 알고리즘의 주요 특징을 논의해 보자. 첫 번째 예제에서 하나의 실수 변수의 단순한 함수의 최적화에 대하여 유전자 알고리즘을 적용하였다. 두 번째 예제는 유전자 알고리즘을 사용하여 간단한 게임 (죄수의 딜레마) 에 대한 전략을 학습하는 방법을 보여줄 것이다. 세 번째 예제는 조합적 NP-hard 문제인 순회 판매원 문제에 대한 유전자 알고리즘의 적용 가능성에 대해 논의하였다.

 

1. 단순한 함수의 최적화

이 절에서는 한 개의 변수의 간단한 함수의 최적화를 위한 유전자 알고리즘의 기본적인 특징을 논의할 것이다. 이 함수는 다음과 같이 정의되며 그림 1 에 나타내었다.

 

그림 1  함수 의 그래프

문제는 구간 [-1, 2] 에서 함수 를 최대화하는, 즉 다음 조건을 만족시키는 를 찾아내는 것이다.

함수 를 해석하는 것은 비교적 쉽다. 다음과 같이 1 차 도함수 의 영을 결정하면 된다.

이 식은 다음과 같이 된다 :

위 방정식이 다음과 같이 무한히 많은 수의 해를 갖는다는 것은 분명하다.

여기서 항은 ( 그리고 에 대해) 0 으로 감소하는 실수의 수열을 나타낸다.

만일 가 홀수이면 에서 함수 의 국소최대값에 도달하고, 만일 가 짝수이면 에서 함수 의 국소최소값에 도달한다 (그림 1 참조).

문제의 정의영역이 이므로 이 함수는 에서 최대값에 도달하는데, 여기서 는 보다 약간 더 크다.

위의 문제를 풀기 위하여, 다시 말하여 함수 를 최대화하기 위해 유전자 알고리즘을 구성하기를 원한다고 가정하고, 유전자 알고리즘의 주 요소들에 대하여 생각해 보자.

 

1) 표현방법

변수 의 실수값을 표현하기 위한 염색체로서 이진 벡터를 사용한다. 벡터의 길이는 요구되는 정밀도에 의해 좌우되는데, 이 예제에서는 소숫점이하 6 번째 자리를 사용한다.

변수 의 정의영역은 길이 3 이다. 정확도에 대한 요구조건은 정의영역 [-1, 2] 가 최소한 3ㆍ1000000 개의 동일한 크기의 영역으로 나뉘어져야 한다는 것을 암시한다. 이것은 이진 벡터 (염색체) 로서 22 비트가 필요하다는 것을 의미한다.

이진 스트링 를 정의영역 [-1, 2] 사이의 실수 로 매핑하는 것은 직접적이고 다음의 두 단계에서 완결된다 :

이진 스트링 을 이진수로부터 10 진수로 변환한다.

이에 해당하는 실수 를 구한다.

여기서 -1.0 은 정의영역의 왼쪽 경계이고 3 은 정의영역의 길이이다.

예를 들어 염색체

는 숫자 0.637197 을 나타낸다. 왜냐하면

이고

이기 때문이다. 물론 염색체들 (000000000000000) 과 (111111111111111) 는 각각 정의영역의 경계값들인 -1.0 과 2.0 을 나타낸다.

 

2) 초기 개체집단

초기화 과정은 매우 간단한데, 각 염색체가 22 비트가 이진 벡터인 염색체의 개체집단을 만들어 내면 된다. 각 염색체에 대한 모든 22 비트들은 임의로 초기화된다.

 

3) 평가함수

이진 벡터 v 에 대한 평가함수  은 함수 와 동일하다.

여기서 염색체 v 는 실수값 를 나타낸다.

앞에서와 같이 평가함수는 적합도의 관점에서 해가 될 가능성이 있는 것들은 평가하는 환경의 역할을 수행한다. 예를 들어 세 개의 염색체

은 값 = 0.637197, = -0.958973, 그리고 = 1.627888 을 각각 나타낸다. 결과적으로 평가함수는 다음과 같이 평가할 것이다.

분명히 염색체 는 평가함수의 값이 가장 크므로 세 염색체중에서 가장 좋다.

 

4) 유전 연산자

유전자 알고리즘의 변화과정중에서 두 가지 고전적인 유전 연산자들인 돌연변이와 교배를 사용할 것이다.

앞서 언급한 바와 같이 돌연변이는 돌연변이율과 동일한 확률을 가지고 하나 또는 그 이상의 유전인자들 (한 염색체내에서의 위치들) 을 변화시킨다. 염색체 로부터 다섯 번째 유전인자가 돌연변이를 위해 선택되었다고 가정하자. 이 염색체에서의 다섯 번째의 유전인자가 0 이므로 1 로 바뀌어진다. 그래서 돌연변이 후에 염색체 는 다음과 같이 된다.

이 염색체는 과 = -0.082257 을 나타낸다. 이것은 돌연변이가 염색체 의 값을 상당히 감소시켰다는 것을 의미한다. 반면에 만일 염색체 에서 10 번째 유전자가 돌연변이를 위해 선택되었다면

이 된다. 이것에 해당하는 값 = 1.630818 그리고 = 2.343555 가 되어 원래의 값 보다 개선되었다.

염색체 와 에 대한 교배 연산자의 예를 들도록 하자. 교배위치가 (임의로) 5 번째 유전인자 이후에 선택되었다고 가정하자 :

두 개의 결과적인 자손세대는 다음과 같다.

이들 자손 세대들은 다음과 같이 평가된다.

두 번째 자손이 부모들보다 더 좋은 평가값을 가지고 있다.

 

5) 매개변수

이 문제에서는 다음 매개변수들이 사용되었다 : 개체집단의 크기 pop_size = 50, 교배확률 = 0.25, 돌연변이 확률 = 0.01. 다음 절은 이 유전자 시스템에 대한 몇 가지 실험 결과들을 보여준다.

6) 실험 결과

표 1 은 평가함수의 값이 개선된 세대번호를 그때의 함수값과 함께 나타낸 것이다. 150 세대 이후의 최적의 염색체는

이며 이것은 = 1.850773 에 해당한다.

기대했던 바와 같이 = 1.85 + ε 이고 는 2.85 보다 약간 더 크다.

표 1  150 세대 이후의 결과

세대번호

평가함수값

1

6

8

9

10

12

39

40

51

99

137

145

1.441942

2.250003

2.250283

2.250284

2.250363

2.328077

2.344251

2.345087

2.738930

2.849246

2.850217

2.850227

 

2. 죄수의 딜레마

이 절에서는 유전자 알고리즘이 죄수의 딜레마 (prisoner's dilemma) 라고 알려진 단순한 게임에 대한 전략을 학습하기 위하여 어떻게 사용될 수 있는지 설명할 것이다. Axelrod [10] 에 의해 얻어진 결과를 제시한다.

두 명의 죄수가 독립된 방에 수감되어 있어서 서로 통신할 수가 없다. 죄수들은 각각 상대방을 이탈하고 배신하도록 요구된다. 만일 한명만이 배신하면 그는 상을 맡고  다른 죄수는 벌을 받는다. 만일 둘 다 배신하면 모두 감옥에 남아 있게 되며 고문을 당한다. 만일 아무도 배신하지 않으면 둘 다 적당히 상을 받는다. 그래서 이기적인 선택의 배신은 다른 죄수가 어떻게 하든 상관없이 항상 협력보다는 더 나은 보상을 가져다 준다. 그러나 둘 다 배신하면 협력한 것보다 더 나쁜 결과를 얻는다. 죄수의 딜레마는 다른 죄수를 배신할 것인가 또는 협력할 것인가를 결정하는 것이다.

죄수의 딜레마는 두 사람 사이의 게임으로 할 수 있는데, 각 차례마다 플레이어는 다른 죄수를 배신하거나 또는 협력한다. 그러면 플레이어는 표 2 에 주어져 있는 보상에 해당하는 점수를 얻는다.

표 2  죄수의 딜레마 게임에 대한 보상표 ( 는 플레이어 에 대한 보상이다)

플레이어 1

플레이어 2

P1

P2

내    용

배신 (D)

배신 (D)

1

1

상호 배신에 대한 처벌

배신 (D)

협조 (C)

5

0

배신의 유혹과 배신자의 보상

협조 (C)

배신 (D)

0

5

배신자의 보상과 배신의 유혹

협조 (C)

협조 (C)

3

3

상호 협력에의 보상

이제 유전자 알고리즘이 죄수의 딜레마에 대한 전략을 학습하는데 어떻게 사용될 수 있는지 고려해 보자. GA 접근은 "플레이어들" 의 개체집단을 유지하는 것이고, 각 플레이어는 특별한 전략을 가지고 있다. 초기에 각 플레이어의 전략은 임의로 선택된다. 그 이후에 각 단계에서 플레이어는 게임을 진행하고 그들의 점수가 집계된다. 어떤 플레이어들은 다음 세대를 위하여 선택되고 그들 중 어떤 것들은 결합된다. 두 플레이어가 결합될 때 생성된 새로운 플레이어는 부모의 전략들로부터 구성된 전략을 갖게 된다 (교배). 보통 돌연변이가 도입되어 이 전략들의 표현에 임의적인 변화를 가함으로써 플레이어들의 전략에 변화를 부여하게 된다.

 

1) 전략의 표현

먼저 전략 (가능한 해) 을 표현하기 위한 방법이 필요하다. 간단하게, 결정적인 전략을 고려하고 이전의 세 가지 행동의 결과를 사용하여 현재 행동을 선택한다. 매 행동마다 네 가지의 가능한 결과가 존재하므로 4 × 4 × 4 = 64 개의 서로 다른 이전 행동들이 존재한다.

이 형태의 전략은 가능한 각 이전 행동들에 대해 어떠한 행동을 결정하여야 하는지 지시함으로써 규정될 수 있다. 그래서 한 전략이 64 비트의 (또는 D 와 C 의) 스트링에 의해 표현될 수 있는데, 각각은 64 개의 가능한 이전 행동에 관한 초기 가정을 규정할 필요가 있다. 이것은 추가로 6 개의 유전인자를 필요로 하므로, 염색체에 총 70 개의 로커스를 구성한다.

이 70 비트의 스트링은 플레이어가 각 가능한 상황에서 어떻게 하여야 하는지를 규정하고 따라서 어떤 특별한 전략을 완전히 정의한다. 70 개의 유전인자의 스트링은 진화과정에서 사용될 플레이어의 염색체로 행동한다.

 

2) 유전자 알고리즘의 윤곽

죄수의 딜레마에 대한 전략을 학습하기 위한 Axelrod 의 유전자 알고리즘은 다음과 같은 네 가지 과정으로 이루어진다 :

이러한 네 단계 이후에 새로운 개체 집단을 얻는다. 새로운 개체집단은 이전 세대의 성공적인 개체들의 행동패턴과 유사하지만 성공적이지 못한 것들의 패턴과는 유사하지 않은 행동패턴을 보여준다. 각 새로운 세대와 함께 비교적 높은 점수를 가진 개체들은 자신의 전략의 일부분을 전달해 주는 반면에, 상대적으로 성공적이지 못한 개체들은 어떤 부분의 전략도 전파하지 못하는 경향이 있다.

 

3) 실험 결과

이 프로그램을 실행하고 나서 Axelrod 는 상당히 놀랄 만한 결과를 얻었다. 완전히 임의적인 시작으로부터 유전자 알고리즘은 중앙값 회원이 지금까지 가장 잘 알려진 경험적인 알고리즘만큼 성공적인 개체집단으로 진화시켰다. 어떤 행동패턴들은 대다수의 개체들로 진화하였는데 이들은 다음과 같다.

더 자세한 설명을 위해서는 [10] 을 참고하라.

 

3. 순회 판매원 문제

이 절에는 순회 판매원 문제 (Traveling Salesman Problem, TSP) 에 어떻게 유전자 알고리즘을 적용하는지 설명한다. 여기서는 단 하나의 가능한 접근을 논의하는데, 10 장에서는 TSP 에 대한 다른 접근방법도 논의하겠다.

간단히 말하여 순회판매원은 문제영역내의 모든 도시를 단 한번만 방문하고 출발점으로 돌아와야 한다. 모든 도시들 사이의 방문에 대한 여행 경비가 주어졌을 때, 전체 여행의 총경비를 줄이기 위해서 여행 일정을 어떻게 계획하여야 하는가?

TSP 는 조합최적화문제이고 여러 가지의 응용분야에서 제기된다. 이 문제에 접근하는 여러 가지의 가지-경계 알고리즘, 근사 알고리즘, 그리고 경험적인 탐색 알고리즘들이 존재한다. 지난 몇 년동안 유전자 알고리즘에 의해 TSP 를 근사화하려는 여러 가지의 시도들이 있어 왔는데 [113, 페이지 166-179], 여기서는 그들 중 하나를 제시한다.

우선 염색체 표현과 관련된 중요한 질문을 제기해야 한다 : 염색체를 정수 벡터로 해야 하는가 또는 이진 스트링으로 변환하여야 하는가? 이전의 두 예제 (함수 최적화와 죄수의 딜레마) 에서는 염색체를 다소간 자연스러운 방식으로) 이진 벡터로 표현하였다. 이로 인하여 이진의 돌연변이와 교배를 사용하였고, 이러한 연산자들을 적용하여 적합한 자손, 즉 탐색공간내에 존재하는 자손들을 얻었다. 순회판매원문제에 대한 경우는 이것과 다르다. 개의 도시의 TSP 문제의 이진표현에서 각 도시는 비트의 스트링으로 코딩되어야 하는데 염색체는 비트의 스트링이다. 돌연변이에 의해서는 여행이 되지 않는 도시 수열이 될 수도 있는데, 그 이유는 한 수열에서 같은 도시를 두 번 얻을 수도 있기 때문이다. 게다가 20 개의 도시를 가진 TSP 에서 (한 도시를 나타내는데 5 비트가 필요하다) 어떤 5 비트의 열 (예를 들어 10101) 은 아무도시에도 해당되지 않을 수도 있다. 교배연산자를 적용시킬 때에도 유사한 문제가 나타난다. 만일 앞에서 정의된 것과 같은 돌연변이 및 교배 연산자를 사용한다면 분명히 염색체를 "복구" 하여 탐색공간으로 되돌려 보내는 일종의 "복구 알고리즘" 이 필요할 것이다.

복구 알고리즘을 사용하는 대신 정수벡터로 표현하는 것이 더 나은 것처럼 보인다. 문제고유의 지식을 연산자와 결합하여 부적합한 개체가 생성되는 것을 "지능적으로" 피할 수 있을 것이다. 이 접근 방식에서는 정수 표현을 받아들인다 : 벡터 은 에서 로, 에서 으로, 그리고 다시 으로 여행하는 것을 나타낸다. (는 <1 2 ... > 의 순열이다).

초기화 과정에서는 휴리스틱을 사용하거나 (예를 들어 다른 도시로부터 출발하는 TSP 에 대한 경사 알고리즘으로부터의 몇 가지 결과를 받아들일 수 있다), 또는 <1 2 ... > 의 순열의 랜덤표본에 의해 초기 개체집단을 생성할 수 있다.

염색체의 평가는 단순하며, 각 도시 사이의 여행 경비가 주어졌을 때 전체 여행의 총경비를 쉽게 계산할 수 있다.

TSP 에서는 가장 좋은 여행을 위한 도시의 배열을 탐색한다. 더 좋은 스트링의 배열을 탐색하는 어떤 단일 연산자 (단일 형태 연산자) 를 고안해 내는 것은 비교적 쉽다. 그러나 단일 연산자만을 사용하면 (가장 좋은 것은 차지하고) 좋은 배열을 찾는다는 희망이 적다 [119]. 게다가 유전자 알고리즘의 능력은 아주 적합한 개체들의 교배 조합의 구조화된 정보 교환으로부터 제기된다. 그래서 염색체들간의 중요한 유사성들을 이용하는 교배와 같은 연산자가 필요하다. 그 목적으로 OX 연산자 [51] 의 변형을 이용하는데, 그것은 주어진 두 부모에 대해 한 부모로부터 여행의 일부분을 선택하고 다른 부모로부터 도시의 상대적인 순서를 유지시킴으로써 자손을 구성한다. 예를 들어 만일 부모가

이고, 선택된 부분이

이라면 결과로 다음과 같은 자손이 생성된다.

요구되는 대로 자손은 양쪽 부모에 대한 구조적인 관계를 포함한다. 두 번째 자손을 구성하는데 있어서 부모의 역할들이 반전될 수 있다.

위의 연산자에 기초한 유전자 알고리즘은 랜덤탐색보다 성능이 우수하지만 더욱 개선시킬 수 있는 여지를 남겨 놓고 있다. 이 알고리즘의 전형적인 결과는 (20 번 이상의 랜덤수행의 평균에서) 전체 여행의 값이 (2000 세대 이후에) 최적점이상 9.4 % 이었다.

사용된 표현문제와 유전 연산자등 TSP 에 대한 완전한 토의에 대해서는 10 장을 참고하라.

 

4. 등반, 시뮬레이티드 어닐링, 그리고 유전자 알고리즘

이 절에서는 단순한 최적화 문제에 적용된 세 가지 알고리즘들, 등반 시뮬레이티드 어닐링, 그리고 유전자 알고리즘에 관하여 논의한다. 이 예제는 GA 접근 방식의 독특함을 강조하고 있다.

탐색공간은 길이 30 의 이진 스트링 의 집합이다. 최대화되어야 할 목적함수 는 다음과 같이 주어진다.

여기서 함수 는 스트링 내의 1 의 개수를 알려준다. 예를 들어, 다음과 같은 세 개의 스트링

은 다음과 같이 평가된다.

함수 는 선형이고 최적화 과제로서 아무런 어려운 문제를 가지고 있지 않지만 이들 세 알고리즘의 배후의 아이디어를 보이기 위해 사용한다. 함수 의 흥미로운 특징은 에 대해 하나의 전역 최대값을 가지고 있다는 것이다.

이고 에 대해 하나의 국소 최대값을 가지고 있다.

이다.

몇 개의 등반 알고리즘들이 있는데, 새로운 스트링이 현재의 스트링과 비교되기 위하여 선택되는 방식에서 차이점이 있다. 한 단순한 (순환되는) 등반 알고리즘 (MAX 순환) 이 그림 2 에 주어져 있다 (최급상승 등반). 초기에 모든 30 개의 이웃들이 고려되고, 가장 큰 값을 제공하는 이 선택되어 현재의 스트링 와 경쟁한다. 만일 이면, 새로운 스트링이 현재의 스트링이 된다. 그렇지 않으면 국소적인 개선이 불가능한데, 알고리즘은 (국소 또는 전역) 최적값에 도달한다 ( = TRUE). 그러한 경우에 알고리즘의 다음 순환 () 이 임의로 선택된 새로운 현재 스트링을 가지고 수행된다.

procedure interated hillclimber

begin

    t←0

    repeat

      local←FALSE

      select a current string

      repeat

        select 30 new strings in the neighborhood of

          by flipping single bits of

        select the string from the set of new strings

          with the largest value of objective function

        if

          then

          else local←TRUE

      until local

    until = MAX

end

그림 2  간단한 (순환적인) 등반

이상의 등반 알고리즘의 한번의 순환 (전역 또는 국소 최적값의 계산) 의 성공 또는 실패가 (임의로 선택된) 초기 스트링에 의하여 결정된다는 것은 흥미있는 일이다. 만일 초기 스트링이 13 또는 그 이하의 1 들을 가지고 있다면 그 알고리즘은 분명히 항상 국소 최적점에서 끝나게 된다 (실패). 그 이유는 13 개의 1 을 가진 스트링이 목적함수의 값 7 을 주고, 전역 최적값을 향한 한 단계 개선이 1 의 개수를 14 로 증가시키고 목적 함수의 값을 4 로 감소시키기 때문이다. 반면에 1 의 수의 감소는 함수의 값을 증가시키는데, 12 개의 1 을 가진 스트링은 18 의 값을 제공하고 11 개의 1 을 가진 스트링은 29 의 값을 제공한다. 이것은 탐색을 "잘못된" 방향, 국소 최대값쪽으로 밀어낸다.

국소 최적값들이 많은 문제에 대해서 전역최적값을 찾아내기 위한 기회는 (단 한번의 순환에서) 적다.

시뮬레이티드 어닐링 과정의 구조를 그림 3 에 나타내었다.

procedure simulated annealing

begin

    t←0

    initialize temperature T

    select a current string at random

    evaluate

    repeat

      repeat

        select a new string

          in the neighborhoof of

          by flipping a single bit of

        if

          then

          else if random [0, 1] <exp{

            then

      until (termination-condition)

    until (stop-criterion)

end

그림 3  시뮬레이티드 어닐링

함수 random (0, 1) 은 범위 (0, 1) 사이의 난수를 제공한다. (termination-condition) 은 '열적평형' 에 도달했는지, 즉 선택된 새로운 스트링의 확률 분포가 볼쯔만 분포 [1] 접근하였는지를 체크한다. 그러나 어떤 구현에서 [2] 이 반복루프는 번만 수행된다 ( 는 이 방법의 추가적인 매개변수이다).

온도 T 는 단계적으로 낮아진다 (모든 에 대해서 ). 알고리즘은 작은 T 값에 대해서 종료한다 : (stop-criterion) 은 이 시스템이 '얼어붙었는지,' 즉 실질적으로 아무런 변화도 받아들여지지 않는지 체크한다.

앞서 언급한 대로 시뮬레이티드 어닐링 알고리즘은 국소 최적값들로부터 탈출할 수 있다. 12 개의 1 로 구성되어 있는 다음 스트링을 고려하자.

이때 이다. 시작 스트링으로 를 고려하면 등반 알고리즘은 (앞에서 논의한 대로) 13 개의 1 을 가진 어떤 스트링 (전역최적값을 '향한' 한단계) 도 7 (18 이하) 로 평가되므로 다음의 국소 최대값으로 접근할 것이다.

반면에 시뮬레이티드 어닐링 알고리즘은 13 개의 1 을 가진 스트링을 다음 확률에 의거하여 새로운 현재 스트링으로 받아들일 것이다.

여기서 어떤 온도, 이를테면 T = 20 에 대해서 다음과 같이 된다.

즉 받아들여질 확률은 50 퍼센트 이상이다.

1. 절에서 논의한 것처럼 유전자 알고리즘은 스트링의 개체집단을 유지한다. 두 개의 비교적 나쁜 스트링들

은 각각 16 으로 평가되고, 훨씬 더 좋은 자손을 생산할 수 있다 (만일 교배 위치가 5 번째와 12 번째 위치 사이에 어느 곳이라고 하면) :

새로운 자손 은 다음과 같이 평가된다.

여러 가지 다른 특성들을 가진 여러 함수들에 대하여 테스트된 이들 그리고 다른 알고리즘들 (여러가지 변형된 형태의 등반, 유전자 탐색, 그리고 시뮬레이티드 어닐링 기법들) 에 관한 더 자세한 설명을 위해서는 [2] 를 참고하라.

 

5. 결론

함수 최적화, 죄수의 딜레마, 그리고 순회판매원문제에 대한 유전자 알고리즘의 예제들은 유전자 알고리즘의 광범위한 응용 가능성을 보여주고 있다. 그러나 동시에 잠재하고 있는 어려움의 우선 신호를 관찰해야 한다.순회판매원문제에 대한 표현문제는 단순하지 않았다. 사용된 새로운 연산자 (OX 교배) 는 전혀 간단하지 않다. 다른 종류의 (어려운) 문제들에 대해 직면하게 되는 더욱 어려운 점들은 어떠한 것들인가? 첫 번째와 세 번째 예제 (함수 최적화와 순회판매원문제) 에서 평가함수는 분명히 정의되었다. 두 번째 예제 (죄수의 딜레마) 에서 간단한 모의실험 과정이 염색체의 평가를 제공할 것이다 (각 플레이어를 테스트하여 유효성을 테스트하였는데, 각 플레이어는 염색체에 의해서 정의된 전략을 사용하여 다른 플레이어와 게임을 하였고 그 플레이어의 점수는 그가 한 모든 게임에 대한 평균이다). 평가 함수가 분명하게 정의되지 않은 경우에는 어떻게 진행하여야 하는가? 예를 들어 Boolean 만족문제 (SAT) 는 자연스러운 스트링의 표현방법을 가지고 있는 것 같다 ( 번째 비트는 번째 Boolean 변수의 진리 값을 나타낸다). 그러나 평가 함수를 선택하는 과정은 그렇게 간단하지 않다 [68].

구속조건이 없는 함수의 최적화의 첫 번째 예제에서는 편리한 표현 방법을 사용할 수 있는데, 어떠한 이진 스트링도 문제영역 (예를 들어, [-1, 2]) 으로부터의 한 값에 해당한다. 이것은 어떠한 돌연변이와 교배도 적합한 자손을 만들어 낼 것이라는 것을 의미한다. 두 번째 예제에서도 마찬가지로 어떠한 비트들의 조합도 적합한 전략을 표현한다. 세 번째 문제에서는 각 도시는 하나의 적합한 여행에서 단 한번만 나타나야 한다는 구속조건을 가지고 있다. 이것은 약간의 문제를 야기하였으므로 (이진표현 대신에) 정수 벡터를 사용하였고 교배연산자를 변경하였다. 그러나 일반적으로 어떻게 구속조건이 있는 문제에 접근할 것인가? 어떠한 가능성을 가지고 있는가?

이러한 해답은 쉽지 않으며, 이 책의 나머지 부분에서 이들에 관하여 탐구할 것이다.