유전자 알고리즘의 사용과 고찰 (2014)

Ⅰ. 개요 (Instruction)

1. 연구의 목적 및 필요성

• 유전자 알고리즘이 사용될 수 있는 경우의 예시 자료에 도움이 된다.
• 유전자 알고리즘이 어떤 상황에 효과적이고 타 알고리즘과 어떤 경향의 차이를 보이는지에 대한 비교 자료에 도움이 된다.

2. 연구 범위 및 내용

• 유전자 알고리즘의 배경과 내용, 적용 방법에 대해서 알아보고 다양한 사례의 시뮬레이션을 기획하여 통계 자료를 분석한다.

Ⅱ. 이론적 배경 (Theory)

1. 알고리즘이란?

(승강기 운행 문제에 사용되는 알고리즘의 예)

• 알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작의 유한한 모임이다.
• 알고리즘은 적용되는 문제와 환경에 따라 문제를 해결하기 위한 해결과 동작 방식, 효율이 차이 날 수 있다.

(정렬 알고리즘의 예시 ‘Bubble Sort’ 알고리즘)

예를 들어 나열된 숫자를 정해진 비교 규칙에 맞추어 순서대로 정렬해주는 정렬 알고리즘들을 서로 다른 데이터 리스트에 적용했을 때 보이는 양상을 보면 각 알고리즘이 적용되는 문제와 환경에 따라 문제를 해결하기 위한 해결과 동작 방식, 효율이 차이 남을 알 수 있다.

(큰 막대가 큰 숫자를 의미함)

(같은 시각에 시작한 정렬 알고리즘들이 일정 시간 후에 보여주는 정렬된 정도)

2. 유전자 알고리즘의 개요

1975년 심리학, 전기공학, 컴퓨터과학 교수를 역임한 미국 미시간 대학의 John Holland 교수가 세포의 작용을 연구하던 중 제안, 저서 "Adaptation on Natural and Artificial Systems"에서 처음 소개한 자연도태의 원리를 기초로 한 최적화(Optimization) 알고리즘이다. 진화적 알고리즘(evolutionary algorithm)이라고도 일컬어지고, 탐색(Search), 최적화 및 기계학습(Machine Learning)을 위한 도구로 많이 사용된다.

기계 학습 : 기계 학습(machine learning)은 인공 지능의 한 분야로, 컴퓨터가 학습할 수 있도록 하는 알고리즘과 기술을 개발하는 분야를 말한다. 가령, 기계 학습을 통해서 수신한 이메일이 스팸인지 아닌지를 구분할 수 있도록 훈련할 수 있다.

3. 유전자 알고리즘의 특징

• 적자생존, 유전자 교차 등의 자연 진화 메커니즘에 기반을 둔 문제 해결 알고리즘
• 현세대를 구성하는 모집단에서 적합도(fitness)에 따라 염색체들을 선택
• 유전 연산자를 적용하여 새로운 세대의 모집단을 생성해 나가는 과정
• 최적화 문제에 대해 다른 종류의 확률적 해법 제공

4. 유전자 알고리즘과 생물학의 용어 비교

용어	생물학	유전자 알고리즘
Chromosome(염색체)	생물 세포의 핵 속에 있는 DNA를 주성분으로 하는 자기 증식성의 소체(小體).	임의의 해답(solution)
Gene(유전자)	염색체상의 각 인자	개체의 형질을 규정하는 기본 구성요소 특성(feature), 형질(character) 등
Genotype(유전자형)	생물이 가지고 있는 특정한 유전자의 조합.	염색체 자체
Phenotype(표현형)	관찰되는 형질	유전자형에 대응하는 해의 모양

5. 유전자 알고리즘의 구성 요소

가. 개체 표현 방법(Encoding Scheme)

문제의 해가 될 가능성이 있는 것의 유전자적 표현 방법, 전형적인 표현 양식은 이진수 0과 1을 이용한 일차원적 표현이다, 유전 연산자는 각 표현 양식에 알맞은 것을 사용해야 한다.

1) 이진 표현(Binary Encoding)

11010011101001, 11010011101001, ~......

이진수로 표현할 경우 교차 연산자 적용 시 자름 선 위치가 많아져 교차의 다양성을 제공한다.

2) 순열 표현(Permutation Encoding)

1234, 1243, 1324, 1342, 1423, ~......

순열을 유전자형으로 표현하는 방법. 이에 따라 유전 연산자는 순열 표현을 유지하는 방식으로 사용되어야 한다.

나. 유전 연산자(Genetic Operators)

자손의 합성과 변화를 조율하는 유전자 알고리즘의 연산자.

1) 선택 연산자(Selection Operator)

해 집단(population)에서 더 적합한 해를 가려내기 위해서 일부를 선택하는 유전 연산자. 해의 선택은 유전자 알고리즘의 성능에 큰 영향을 미치는데, 어떤 선택 방법을 쓰느냐에 따라 최적의 해로 다가가는 속도가 더디게 되거나 국소적인 위치의 지역 해에 빠지는 경우가 생길 수 있기 때문이다.

일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법이 많이 사용되는데, 이는 반대로 말하면 나쁜 해라 할지라도 그 해에 포함된 좋은 유전 인자를 퍼트릴 기회를 준다고 볼 수 있다.

현세대에서 가장 좋은 해라고 할지라도 사실은 지역 해에 가까운 해일 수도 있고 반대로 현세대에서 나쁜 평가를 받은 해라고 할지라도 전역 최적 해에는 더 가까울 수도 있기 때문이다.

실제로 전역 최적해가 어디에 있는지는 알 수 없는 일이므로 가능한 해들의 평균적인 적합도를 높여 가면서도 유전자의 다양성을 유지하는 것이 지역 최적 해에 빠지는 것을 가능한 한 방지하는 방법이며, 이는 실세계의 생명체들 역시 유전적 다양성을 유지하는 종이 장기적인 생존 가능성이 높은 것과 비견할 수 있다.

전역 최적 해와 지역 최적해(국소 해)란?

(유전자 알고리즘으로 3차원 함수의 최댓값을 찾는 과정에서 3차원 함수의 표면과 등고선 상에 그려진 염색체 위치)

위 그림에서 볼 수 있듯이 해가 지역적으로 우수한 위치에 놓인 것을 지역 최적해, 모든 위치를 통틀어 가장 우수한 위치에 놓인 것을 전역 최적해라고 한다.

2) 교차(교배) 연산자(Crossover Operator)

(실제 염색체의 교차 형태)

다음 세대에 사용할 개체를 만들기 위해서 두 부모의 염색체를 부분적으로 바꾸어 자식의 염색체를 생성하는 유전 연산자.

생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다. 이와 마찬가지로 유전 알고리즘에서 자연 선택된 해들은 교배를 통하여 다음 세대의 해들을 생성하게 된다. 일반적으로 두 개의 해를 선택한 후 둘 간에 교배 연산을 수행하게 되며, 이를 통해 생성된 해는 각각의 부모 해의 교차 연산을 통해서 서로 겹치지 않는 위치의 유전인자를 받아 새로운 유전자를 구성하게 된다. 실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다.

유전 알고리즘의 교차 연산은 이 현상을 본떠 만들어진 것으로, 부모 해의 유전자들을 서로 교차시켜서 자식 해를 만들어낸다.

또한, 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버림에 따라 세대의 최고 우수해가 보존되지 않는 상황이 발생할 수 있는데 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용된다.

3) 돌연변이 연산자(Mutation Operator)

(실제의 염색체에서의 돌연변이의 형태)

해의 다양성을 추가하기 위해 염색체를 임의로 변이시키는 유전 연산자.

일반 생명체에서, 유전자의 교배뿐 아니라, 하나의 유전자가 직접 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다.

변이 연산은 주어진 해의 유전자 내의 유전 인자의 순서 혹은 값이 임의로 변경되어 다른 해로 변형되는 연산이다. 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적 해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수 있으며, 해 집단의 다양성을 높여준다.

(돌연변이 연산자가 함수의 최댓값인 전역 최적해을 찾는 과정에서 지역 최적해 탐색에서 벗어나게 해주는 예)

다. 적합도 함수(Fitness Function)

염색체의 해(solution)로서의 적합도를 평가하는 함수.

(적합도 평가의 예시)

라. 알고리즘 제어 파라미터(Parameter Setting)

유전자 알고리즘이 사용하는 여러 가지 매개변수의 값. 개체 집단의 크기, 유전 연산자를 적용하는 확률 등이 있음.

6. 유전 연산자의 구현과 종류

• 유전자를 이진 표현(Binary Encoding)한 경우를 가정하고 소개

가. 선택 연산자(Selection Operator)

1) 룰렛 선택(Roulette Wheel Selection)

(룰렛 선택 방식의 그래픽 표현)

(표에 따른 룰렛의 그래픽 표현)

각 염색체의 적합도에 비례하는 만큼 룰렛의 영역을 할당한 다음, 룰렛을 돌려 화살표가 가리키는 영역의 염색체를 선택하는 선택 방법.

적합도가 높은 것은 선택될 확률이 그만큼 높고 적합도가 낮은 것은 선택될 확률이 상대적으로 낮다.

2) 엘리트 보존 선택(Elitist Preserving Selection)

확률에 따라 개체를 선택하게 될 때, 우수한 개체가 소실되는 것을 막기 위해 가장 좋은 해를 보존하여 다음 세대에 넘기는 선택 방법이다. 엘리트 개체의 유전자가 개체군 전체로 급속히 퍼져나갈 가능성이 높아서 국소적인 해로 수렴할 위험이 있기 때문에 보통 다른 선택 방법과 융합하여 사용한다.

3) 토너먼트 선택(Tournament Selection)

개체군 중에서 일정한 개수의 개체를 임의로 선택하여 그중에 최고의 적합도를 가지는 개체를 다음 세대에 남기는 방법.

나. 교차 연산자(Crossover)

대개 교차 연산자는 두 개의 부모의 유전자를 서로 맞바꾸어 두 개의 자식(변형된 부모)을 생산하지만 두 개의 부모로부터 한 개의 자식을 생산하는 방식으로 구현하기도 하며 아래 교차의 설명에서는 한 개의 자식을 생산하는 예를 들었다.

1) 1점 교차(Single Point Crossover)

한 점을 기준으로 두 염색체의 유전자들을 서로 바꾸어 자식 개체를 만들어내는 교차 연산자.

2) 2점 교차(Two Point Crossover)

두 점을 기준으로 두 염색체의 유전자들을 서로 바꾸어 자식 개체를 만들어내는 교차 연산자.

3) 균등 교차(Uniform Crossover)

(Po = 0.6인 균등 교차의 한 예)

위와 같은 일점 교차와 다점 교차(자름 선을 n개 둔 교차 방법)가 자름 선을 이용하여 이루어지는 데 반해 균등 교차는 자름 선을 이용하지 않고, 임계 확률 Po를 설정한 뒤 각각의 유전자 위치에 대하여 난수를 발생한 다음, 이 값이 Po 이상이면 s1의 같은 위치로부터 유전자를 복사하고, 그렇지 않으면 (Po 미만) s2의 같은 위치로부터 복사한다.

다. 돌연변이 연산자(Mutation Operator)

해의 다양성을 추가하기 위해 염색체를 임의로 변이시키는 유전 연산자.

(돌연변이 연산의 예)

7. 유전자 알고리즘의 진행 과정

(유전자 알고리즘의 진행 과정)

초기 집단 생성 : 모집단을 최초 생성하는 부분이다.

선택 : 선택 연산자를 이용하여 개체들을 걸러내는 부분이다.

교차 : 교차 연산자를 이용하여 모집단으로부터 자식 집단을 생성하는 부분이다.

돌연변이 : 생성된 집단에 돌연변이를 적용하는 부분이다.

적합도 평가 : 각 개체들의 적합도를 평가하는 부분이다.

8. 물리 엔진의 이해와 사용

가. 물리 엔진이란?

물리 엔진(physics engine) 또는 물리 연산 엔진은 강체동역학(충돌 감지 포함), 연체동역학, 유동역학과 같은 단순한 특정 물리 시스템을 최대한 시뮬레이션하려고 하는 컴퓨터 소프트웨어이다.

강체

현상을 쉽게 기술하기 위해 도입한 것으로, 외력을 가해도 크기나 형태가 변하지 않는 이상적인 물체를 말한다. 아주 큰 힘을 받지 않는 한 부서지지 않는 대부분의 고체를 강체로 간주한다.

나. Box2D 물리 엔진

(Box2D 물리 엔진의 로고)

2007년 9월 11일 출시된 Box2D 물리 엔진은 2D 강체 시뮬레이션을 도와주는 라이브러리로써 많은 물리적 시뮬레이션 구현에 사용되고 있다.

라이브러리(library)는 소프트웨어를 만들 때 쓰이는 코드 조각들의 모임을 가리키는 말이다.

(가장 대중적으로 알려진 Box2D의 사용 예, 게임 Angry Bird)

Ⅲ. 연구 방법 및 실험 (Procedure & Method)

1. 유전자 알고리즘의 특징 분석을 위한 시뮬레이션 준비

유전자 알고리즘의 특징과 진행 양상 등을 알아보고 유전자 알고리즘에 기반을 둔 시뮬레이션 프로그램의 초석을 다지기 위해서 그를 위한 시뮬레이션을 준비했고 함수의 최댓값을 유전자 알고리즘을 적용해 탐색하는 시뮬레이션을 기획하였다.

2. 함수 최댓값 탐색 시뮬레이션 구현

(시뮬레이션 프로그램의 모집단 생성 화면)

시뮬레이터의 파라미터

사용자 정의 함수 : 최댓값을 구할 함수이자 적합도를 구하는 데 사용되는 함수.

(수식 인식과 함수 그래프 표현은 http://www.flashandmath.com/intermediate/mathparser/mp1.html의 Mathematics Expression Parser와 Simple Function Grapher 모듈을 사용하여 제작하였다.)

상위 선택 : 해당 파라미터의 %만큼 선택 연산이 개체를 선택한다.

돌연변이 확률 : 해당 파라미터의 %만큼 돌연변이의 적용 확률이 조절된다.

돌연변이 강도 : 해당 파라미터의 값만큼 이진 유전자의 변이 횟수가 조절된다.

개체 수 : 해당 파라미터의 값만큼 개체 집단의 수가 유지된다.

진화 종료 : 해당 파라미터의 값만큼 세대를 진행하게 한다.

기본적인 유전자 알고리즘의 구도인

“모집단 생성 → 선택 연산 → 교차 연산 → 돌연변이 연산 → 다음 세대 연산 시작”에 맞추어 제작하였다.

가. 모집단 생성

첫 번째로 최초 개체 생성(모집단 생성)은 무작위로 0과 1 사이 중 하나를 골라 16개를 배치하는 방법으로 생성하였고, 이는 다시 말해 총 16개의 비트로 개체를 구성한 것이므로 개체의 이진 유전자들은 10진법으로 변환했을 때 0부터 65565의 값을 가질 수 있으며 (즉 탐색하는 정의역이 0<= x <= 65565로 제한됨) 사용자 정의 함수에다가 유전자의 10진 값을 넣었을 때의 함숫값을 적합도 함수의 값으로 매겨 계산하였다.

나. 선택 연산

선택 연산은 룰렛 선택 방식을 적용하였는데, 개체의 적합도가 이진 표현된 유전자들을 다시 십진 표현한 뒤 사용자 정의 함수에 넣은 값으로 평가되게 설계하니 적합도가 음수가 나오는 경우가 있어 “해당 개체의 적합도 / 모든 개체의 적합도 합“의 방법으로는 해의 정상적인 룰렛 선택 확률을 구할 수 없어서 룰렛 확률을 계산할 때에는 해당 세대의 가장 나쁜 해(적합도가 낮은)를 찾아서 이 해의 적합도 값의 절댓값의 2배를 룰렛 확률을 구할 때 기본 점수로 설정하고 기존의 방법을 적용하여 확률을 구하는 방식을 택했다. 위 방법을 통해 “시뮬레이터의 전체 개체 수 × 상위 선택 파라미터“만큼의 해를 선별해낸다.

다. 교차(교배) 연산

교차 연산 방식은 선택 연산으로 선별된 개체 집합에서 무작위로 두 개체를 뽑아 원래의 개체 수가 될 때까지 1점 교차를 유전자 배열의 반이 되는 곳을 기준으로 갈라 각각 유전자의 반씩을 가져와 새로운 자식 개체를 생성하는 방식으로 적용하였다.

라. 돌연변이 연산

돌연변이 연산 방식은 교차 연산이 진행된 후 원래 개체 수로 돌아온 개체 집단에 속해있는 개체가 설정한 돌연변이 확률에 의해 돌연변이 연산이 일어나면 돌연변이 강도의 횟수만큼 무작위로 해당 개체의 이진 유전자 중 하나를 골라서 해당 유전자에 대해서 NOT 연산(0 → 1, 1 → 0)을 한 값을 적용했다.

마. 적합도 평가

유전자의 적합도는 사용자 함수에 개체의 이진 표현된 유전자를 넣어 나온 함숫값으로 평가하였다.

바. 파라미터 설정

돌연변이(5%)와 상위 선택(25%)의 파라미터는 각각 실제 생태계와 비슷한 값에서 크게 다르지 않은 값을 넣었다.

3. 다른 알고리즘과 비교에 적합한 시뮬레이션 준비

유전자 알고리즘을 다른 알고리즘과 비교해보고 평가하기 위해서 비교에 적합한 시뮬레이션을 기획했다.

기획한 시뮬레이션은 목표물을 쫓아오는 인공지능 미사일에 잡히지 않고 목표물이 도망치는 최대 시간의 경로의 해를 구하는 시뮬레이션이다.

좀 더 구체화하자면 지정한 그리드 지도 위에

• 목표물을 쫓아오는 미사일
• 미사일을 피하려고 움직이는 목표물
• n번 해당 방향으로 진행해야 통과할 수 있는 장애물

이 3개의 개체가 배치되고 시뮬레이션 되는데, 미사일은 지정된 인공지능으로 항상 같은 위치의 목표물에 대해 같은 방향으로 이동하고, 목표물은 미사일을 피해 최대한 오래 살아남는 것이 목표가 되는 시뮬레이션이다.

미사일은 목표물보다 2배 빠르게 이동하도록 기획에 두고 시뮬레이션을 제작할 것이다.

(그리드 지도 위에 장애물(검), 미사일(보), 목표물(빨)이 배치된 모습)

4. 2차원 미사일 피하기 시뮬레이션 구현

가. 미사일 이동 인공지능의 구현

우선 시뮬레이션 구현을 위해서는 미사일의 인공지능 구현이 필요했는데. 아래와 같이 미사일의 인공지능을 구현하였다.

(미사일 이동 인공지능의 순서도)

나. 목표물 이동 알고리즘의 구현

미사일 인공지능과 함께 유전자 알고리즘을 이용한 목표물의 이동 시뮬레이션과 비교할 목표물의 인공지능도 구현하였다. 인공지능의 작동 방식은 미사일과 유사하며 미사일이 대상을 쫓아가는 방향으로 이동한다면, 목표물의 인공지능은 대상을 피하는 방향으로 이동하게끔 설계했다.

(목표물 이동 인공지능의 순서도)

다. 유전자 알고리즘을 이용한 목표물 이동의 구현

위의 함수 시뮬레이션에서는 이진 표현 방식으로 해를 설정했지만, 해당 시뮬레이션에서는 해를 시간에 따른 이동 방향으로 표현하고 사용하였다.

(시간에 따른 이동 방향 유전자의 그래픽 표현) 만약 위 그림과 같이 개체의 염색체가 표현되었다면 해당 개체는 목표물을 지정한 시간 단위(쉬운 예를 위해 1초라고 하자)가 지남에 따라

1초 : 북쪽으로 이동
2초 : 동쪽으로 이동
3초 : 북쪽으로 이동
4초 : 서쪽으로 이동
n초 : direction(n) 방향으로 이동

유전자 알고리즘의 진행 방식은 함수 최댓값 찾기와 같은 방식으로 구현하였는데, 시간에 따른 이동 방향으로 유전자를 표현한 만큼 유전자의 길이가 길어지기 쉬운데, 함수 최댓값 찾기에서 사용했던 자름 선을 중앙으로 배치한 교차(교배) 연산 방법으로는 다양한 자식 해들을 얻을 수 없을 것을 고려하여 자름 선의 위치를 각 교차(교배) 연산이 진행될 때마다 무작위로 설정하여 교차(교배) 연산을 수행하는 방법으로 교차(교배) 연산의 방법을 변경했다.

돌연변이 연산도 무작위로 선택된 위치의 유전자에 대해서 이진 표현된 유전자처럼 NOT 연산을 수행하여 적용할 수 없으므로 해당 위치의 유전자를 제외한 3개의 방향 유전자중 무작위로 선택된 하나로 유전자를 변이시키는 방식으로 돌연변이 연산의 방법도 변경하였다.

적합도의 평가는 해가 미사일로부터 좀 더 멀리 도망쳤다는 것이 좀 더 우수한 해라고 기준을 잡고 제한 시간(유전자의 길이) 내에 미사일에게 잡히지 않았다면 그리드 지도의 각 좌표 간의 거리를 피타고라스의 정리인 a²＋b²=c² 수식을 사용하여 구한 값을 양수로 가지게 설정하였고 만약 제한 시간 내에 미사일에게 잡혔다면 적합도를 “-(유전자의 길이 – 잡힌 시간)”으로 설정하여 늦게 잡힌 개체가 더 좋은 점수가 나오게 평가했다.

5. 물리 & 공학적 문제에 응용 가능한 시뮬레이션 준비

유전자 알고리즘을 다양한 공학 또는 실생활(물리적인, 가령 공을 골대에 넣을 때 필요한 힘의 최적 해 구하기) 등에 응용하면 어떤 양상을 보이는지 분석하기 위해 물리적인 속성을 가진 시뮬레이션을 기획하였다.

기획한 시뮬레이션은 실제 우리가 사는 세계와 비슷한 환경을 갖춘 2차원 물리 세계에서 공과 도달점, 장애물을 배치하고 공에 시간대에 따라 같은 크기의 방향이 다른 힘을 주었을 때 공이 장애물을 헤치고 최단 시간에 도달점에 도착하는 해를 구하는 시뮬레이션이다.

6. 현실과 비슷한 물리 세계의 구현

현실과 비슷한 물리 세계를 구현하려면 가상 물리 세계에 다양한 설정을 해주어야 하는데 대표적으로 고려할 값들은 다음과 같다.

가. 중력가속도(Gravitational Acceleration)

실제 지구와 가장 비슷한 환경을 조성하기 위해서 9.80665 m/s²로 적용하였다.

나. 공기 저항(Air Resistance)

공기 저항은 내부 함수로 설정할 수 없어 직접 구현하였다. 공기 저항력은 다음과 같이 정의된다.

Fd : 저항력
p : 공기의 밀도
v : 물체의 속도
Cd : 끌기 계수
A : 물체의 단면적

(온도에 따른 공기의 밀도 표)

(마하 (340m/s) 속도에 따른 Drag 계수)

공기의 밀도는 상온 15도의 1.225를 적용하고 Drag 계수는 마하 1 부근에서 급격하게 상승하는 계형을 보여주지만 시뮬레이션 편의상 속도가 1 마하(340m/s)를 넘지 않을 것이라 가정하고 0.2로 적용하였다.

각 값들을 설정하고 시간에 따라 물체에 공기 저항력을 계속 작용시켜준 결과

(북동쪽으로 힘을 한번 가해준 공기저항이 있는 공과 없는 공의 궤적 차이)

위 그림과 같이 공기 저항력을 적용해준 공의 궤적이 좀 더 왼쪽에 있는 것을 확인할 수 있었다.

다. 마찰(Friction)

Box2D의 가상 물리 세계에서는 물체에 마찰 계수를 설정할 수 있는데, 값이 0이면 마찰 없음, 1이면 마찰이 가장 강하다. (두 물체 간의 마찰이 계산될 때는 기하평균의 값으로 마찰 인수가 계산된다.) 기본적으로 공과 나머지 모든 물체에 0.3의 마찰 계수를 적용하였다. 마찰 계수

수직항력과 마찰력의 비례관계를 주는 수치. 맞닿은 두 표면 사이의 마찰 정도를 뜻한다.

라. 탄성(Elasticity)

Box2D의 가상 물리 세계에서는 물체에 탄성 계수를 설정할 수 있는데, 값이 0이면 비탄성 충돌, 값이 1이면 완전 탄성 충돌로, 잘 튀길만한 공이 가질 정도의 탄성 계수인 0.75로 탄성 계수를 적용하였다.

7. 물리 시뮬레이션의 구현

(물리 시뮬레이터의 화면)

시뮬레이션에 사용된 유전자 알고리즘은 미사일 시뮬레이션과 거의 유사한 방법을 사용했고 방향을 나타내는 유전자의 해석 방법을 물리 세계에 적용하기 위해서 이전과 달리하였다.

Box2D는 적분기(integrator)라는 컴퓨팅 알고리즘을 이용하는데, 적분기 알고리즘은 물리공식을 이산시간에 대해서 시뮬레이션한다. 이산시간 시간을 연속적으로 보지 않고 일정한 간격으로 잘라 사용하는 것을 의미. Physical World Setting 탭의 Step Time은 한 번에 진행할 이산 시간을 정하는 파라미터인데 위에 설정된 값대로 시뮬레이션하면 1/60초가 기본 이산 시간이 된다.

시뮬레이터는 위와 같은 방향 유전자를 가진 개체에 유전자 힘 크기 값과 유전자의 방향 값을 이용하여 힘을 만들어내고 이것을 지정한 시간 동안 개체에 적용해준다. 만들어진 힘은 (힘 적용시간 × Step Time)의 시간만큼 해당 개체의 공에 적용된다. 그리고 힘 간격 시간만큼 물리 세계를 진행한 뒤에 다시 다음 힘을 만들어 적용하는 방식으로 시뮬레이션이 이루어진다. Step Time : 1/60, 힘 적용 시간 : 20, 힘 간격 시간 40, 유전자 힘을 5로 설정하고 시뮬레이션을 가동했을 때에는 위 유전자들을 가진 개체 공은 이런 식으로 움직인다.

⓵ 설정한 초기 위치에 공이 배치된다.
⓶ 왼쪽의 시작 힘 Vector가 Step Time인 1/60초만큼 적용된다.
⓷ 1/60 ~ 20/60초 동안 북쪽으로 5만큼의 크기를 가진 힘을 받는다.
⓸ 21/60 ~ 60/60초 동안 힘을 주지 않고 시뮬레이션이 이루어진다.
⓹ 61/60 ~ 80/60초 동안 동쪽으로 5만큼의 크기를 가진 힘을 받는다.
⓺ 81/60 ~ 120/60초 동안 힘을 주지 않고 시뮬레이션이 이루어진다.
⓻ 3~4 과정을 모든 유전자 방향을 적용할 때까지 반복.
※ 설정한 중력, 공기저항력은 모든 시간에서 적용받는다.

적합도의 평가는 만약 공이 도달점에 도착한 경우가 우수한 해이므로 “(유전자의 길이 × 힘 적용시간) + (유전자의 길이 × 힘 간격 시간) - 도착 시각”으로 평가하였고 도착하지 못한 경우에는 공과 도달점 사이의 거리를 피타고라스의 정리로 구한 뒤에 –1을 곱해준 값으로 평가하였다.

Ⅳ. 실험 결과 (Result)

1. 함수 최댓값 탐색 시뮬레이션의 자료 분석

가. 이차함수의 시뮬레이션 통계

상위 선택 : 25%
돌연변이 확률 5%
개체 수 : 30개체

위의 설정대로 -0.0001x^2 + 10x – 200000 함수에 대한 최댓값 탐색을 시뮬레이션하였다. (설명 시 지명하는 개체의 숫자는 함숫값이다.)

시뮬레이터가 그래픽 표현한 모집단 개체들의 일부

그래프 위에 막대로 표시한 모집단의 개체들(색이 진할수록 최댓값에 가까움)

(룰렛 선택 연산이 적용되어 뽑힌 개체들, 적합도가 좋은 개체가 주로 선별되었지만, 확률상에 의해 그렇지 않은 개체도 같이 선별되었다.)

(교차(교배) 연산이 진행되어 새 자식 개체가 만들어지는 모습)

(돌연변이 연산이 이루어지는 과정, 위 사진에서 볼 수 있듯이 개체의 다양성을 유지하는 데 도움이 되고 있다)

한 세대 사이클이 끝난 후에 그래프 표현한 개체들의 모습 (이전 그림보다 막대 수가 줄어든 것은 해당 값을 가진 개체들이 여러 개 존재하기 때문이다)

2세대 초에서 일어난 교차 연산으로 49618보다 우수한 개체인 49637

룰렛 선택에서 살아남은 49637과 위의 3세대 초의 개체들의 모습

13세대 초의 개체들의 모습

13세대에 돌연변이가 일어난 모습

14세대 초의 개체들 모습(49872 1개, 나머지 모두 49637)

15세대 초의 해 모습 (우수 개체가 룰렛 선택에서 떨어짐)

50세대의 그래프 모습(해 전체가 모두 49871의 값으로 수렴함)

각 세대의 최고 적합도를 지닌 개체들의 변화 양상

세대별 최고 적합도 개체변화 그래프 (진할수록 후세대)

세대별 평균 함숫값 그래프

나. 일차 함수의 시뮬레이션 통계

파라미터는 사용자 정의 함수를 제외하고 모두 위와 같음.

세대별 최고 적합도 개체변화 그래프 (진할수록 후세대)

세대별 평균 함숫값 그래프

다. 다른 파라미터 조건에서의 시뮬레이션 양상 분석

일차 함수인 상황에서 개체 수가 5인 경우(적은 개체 수)의 경우와 돌연변이 확률을 50%(과다한 돌연변이)로 설정한 경우를 시뮬레이션하였다.

1) 적은 개체 수의 경우

쉽게 해들이 틀어지는 경향을 보인 적은 개체 수의 경우

2) 과다한 돌연변이의 경우

해들이 안정되지 않는 경향을 보이는 과다한 돌연변이의 경우

2. 미사일 피하기 시뮬레이션의 자료 분석

유전자 수 : 400개
장애물 내구도 : 5
그리드 지도 크기 : 25
상위 선택 : 30%
돌연변이 확률 : 25%
돌연변이 강도 : 400
개체 수 : 30개체

(유전자 수를 많이 설정함에 따라 돌연변이 연산의 돌연변이 유전자 선택 부분이 무작위로 선정되어 작동하기 때문에 이전 시뮬레이션과 같은 변이율을 보기가 힘들어 돌연변이의 확률을 높게 설정하였다.) 위와 같은 상황에서 시뮬레이션을 진행하였다.

위와 같이 배정된 그리드 지도 위에서 시뮬레이션을 수행하였다.

가. 인공지능의 경우

해당 그리드 지도에서의 AI의 궤적, 28번의 이동 후 미사일에게 잡힘.

나. 유전자 알고리즘의 경우

첫 세대에서 나쁜 해는 위 AI와 비슷한 궤적을 그리며 잡혔지만 좋은 평가를 받은 해는 아래의 궤적을 그렸다, 43번의 이동 후 미사일에게 잡힘.

7번째 세대, 좀 더 왼쪽으로 가게끔 진화함, 49번의 이동 후에 미사일에게 잡힘.

65번째 세대, 왼쪽으로 가는 경향을 보이고, 56번째의 이동 후에 미사일에게 잡힘.

100번째 세대, 중앙의 가장 왼쪽 끝쪽의 장애물이 많이 배치된 공간으로 피신해서 미사일이 뚫고 오는데 많은 시간이 걸리게 함으로써 시간을 벌음, 61번의 이동 후에 미사일에게 잡힘.

3. 물리 시뮬레이션의 자료 분석

위 시뮬레이터 화면의 파라미터와 같은 상황에서 시뮬레이션을 진행하였다.

가. 1자 단순 장애물 지형

(모집단) 0세대 Gene Progress : 0 / 20

유전자에 따른 각 방향 힘을 받아서 4방향으로 공들이 펴졌음.

(모집단) 0세대 Gene Progress : 1 / 20

네 방향으로 퍼진 공들이 중력의 영향을 받아 아래로 내려오고 다시 한 번 힘을 받아 퍼졌음.

(모집단) 0세대 Gene Progress : 4 / 20

몇 번 더 유전자에 따라 힘을 받아 퍼진 상태, 오른쪽의 두 개체는 도달점에 가장 먼저 도달하였음.

(모집단) 0세대 Gene Progress : 13 / 20

왼쪽으로 힘을 받거나 튕겨서 장애물 벽 왼쪽으로 간 개체들은 그대로 이리저리 움직이다가 시간을 마감했고 벽 오른쪽으로 간 개체들도 왼쪽과 오른쪽으로 힘을 받다가 시간을 마감했다.

1세대 Gene Progress : 2 / 20

공이 시작점에서 오른쪽으로 힘을 받아 장애물 벽 위쪽에 맞아 튕기고 올라온 뒤 현재 그림의 가장 위쪽에 배치된 개체 무더기들은 서로 다른 힘을 받아 분열되었다.

2세대 Gene Progress : 4 / 20

위쪽으로 올라간 개체 무더기들이 내려와서 살짝 다른 궤적을 보이며 도달점에 도달했다.

24세대 공이 위 그림과 같은 궤적을 보이며 분열되지 않고(모든 개체가 같은 유전자를 가지게 됨) 도달점까지 도달했다.

나. 삼평고 글씨 장애물 지형

(모집단) 0세대 Gene Progress : 4 / 20 초기에 겹쳐져 있던 공들이 서로 다른 방향의 힘을 받으면서 퍼진 모집단 개체들의 모습

2세대 전 세대보다는 안정된 경로로 많은 개체가 조금씩 다르게 도달점에 많이 도착했다.

25세대 일부 돌연변이로 추정되는 몇 개체가 빨간색 궤적이 아닌 궤적을 보이면서 운동했고(많이 겹쳐진) 대다수의 개체가 빨간색 궤적을 보이면서 빠르게 도달점에 도달하였다.

Ⅴ. 토론 (Discussion)

1. 최댓값 탐색 시뮬레이션을 통해 알아본 유전자 알고리즘의 특징과 고찰

• 생태계의 적자생존 법칙을 그대로 모방하여 적용해본 결과가 상당히 효과적이라는 것을 알 수 있었다.
• 유전자 알고리즘에서 교차와 돌연변이 연산자가 중요한 유전자 알고리즘의 핸들링 역할을 한다는 것을 알 수 있었다.
• 유전자 알고리즘이 대개 시뮬레이션의 기획한 의도에 다가가는 방향으로 나아가긴 하지만 예외도 있고 항시 그렇지 않다는 것을 알 수 있었다.
• 시뮬레이션의 파라미터를 적은 개체 수로 설정하고 시뮬레이션 한 결과 쉽게 해들이 틀어지는 경향을 볼 수 있었고, 과다한 돌연변이가 일어나게 설정하고 시뮬레이션 한 결과 해들이 안정되지 않는 경향을 볼 수 있었다.
• 이 두 가지 경우의 결과를 보아 유전자 알고리즘에서 설정한 파라미터들이 중요한 역할을 한다는 것을 알게 되었다.

2. 미사일 피하기 시뮬레이션을 통한 각 알고리즘의 비교와 고찰

• 두 시뮬레이션을 행하고 비교한 결과 위에서 설정한 인공지능은 장애물의 관계 분석이 어려워 나쁜 이동 경로를 보였고, 유전자 알고리즘을 적용한 시뮬레이션에서는 각양각색으로 진화하며 좀 더 미사일을 피할 수 있는 방향으로 진화하며 경로를 보였는데 이를 통해 다양한 지형에서의 미사일을 피하는 인공지능을 제작할 때,
• 제작의 지표로 유전자 알고리즘을 이용한 시뮬레이션으로 경로 탐색을 하여 사용하면 좀 더 좋은 성능의 목표물 인공지능을 제작하는데 보탬이 될 것 같다는 결론을 얻음.

3. 유전자 알고리즘을 이용한 물리 문제의 해결에 대한 고찰

• 유전자 알고리즘을 통해 이러한 물리 문제의 근사해를 얻을 수 있다는 것을 알게 되었음.
• 해당 시뮬레이션의 결과를 보아 공기 저항 등을 적용한 쉽게 모든 해를 탐색할 수 없거나 어려운 문제나 상황에서 유전자 알고리즘을 통해 탐색 지표와 근사해를 얻는 것이 효과적임을 알게 되었음.

4. TSP 에서의 유전자 알고리즘의 이용에 대한 고찰

TSP란 Traveling Salesman Problem(외판원 문제)의 약어이다. 이 문제는 간단히 말하면 “모든 도시(지점)들을 한 번씩 방문하는데 드는 최소 비용을 구하여라”로 일축되는데, 예를 들자면

(도시와 각 도시에 방문하는 데 필요한 비용이 그려져 있는 그림) 위의 경우에서 모든 도시를 방문하는 방법의 예를 들면

1→2→3 (비용 30)
3→2→1 (비용 30)
3→1→2 (비용 50 [최악])

등을 예로 들 수 있는데 위와 같이 최악의 선택을 하지 않고 해를 구하려면 “가능한 모든 경로를 조사해야 한다.” 그렇다면 위 그림의 경우

1→2→3
1→3→2
2→1→3
2→3→1
3→1→2
3→2→1

의 총 6가지로 3!의 경우를 모두 검사해봐야 한다. 위의 경우처럼 소규모의 경우에는 문제가 되지 않지만 도시 수가 더 많은 경우는 n!의 기하급수적인 경우의 검사를 시행해야 하는데 이는 무리가 있어서, 모두 검사하는 방법 대신 효율적인 알고리즘을 TSP의 해결에 사용하고는 하는데, 유전자 알고리즘은 이 문제를 풀기 위한 알고리즘 중 많은 지지를 받고 있는 알고리즘이다.

유전자 알고리즘을 이용해 순열 표현의 방식으로 해를 표현하고 유전 연산을 수행하여 적용하면

(TSP Simulator – with GA [http://wonderfl.net/c/msq8])

11세대의 해 모습

139세대의 해 모습

50000세대의 해 모습 이처럼 근사해가 구해지는 모습을 볼 수 있다. 이와 같은 사례에서 유전자 알고리즘이 모든 경우를 검사하기 힘든 경우 또는 알아볼 수 없는 경우 근사해를 구하는 수단으로서 효과적임을 알 수 있었다.

5. 최종적인 결론

위의 다양한 시뮬레이션과 결과 분석으로 유전자 알고리즘은 생태계의 적자생존을 모방한 진화 알고리즘으로 다양한 사례와 문제에 적용될 수 있다는 것을 알게 되었으며, 특히 모든 경우를 검사할 수 없거나 알아보기 힘든 경우 근사해를 실제 적용 시에는 유전자를 해당 문제에 맞는 형식으로 표현한 뒤 알맞은 적합도 함수를 설계하고 해당 유전자에 맞는 유전 연산자, 적당한 파라미터 등을 설정하고 시뮬레이션해야 한다는 것을 알 수 있었다.

6. 탐구를 마치며

이 탐구를 진행하게 되면서 컴퓨터와 과학의 응용이 무한한 가능성을 지니고 있다는 것을 깨닫게 되었으며, 기회가 된다면 과학에 컴퓨터를 접목하는 주제로 탐구를 다시 진행해 보고 싶다.

위키피디아 Drag coefficient – http://en.wikipedia.org/wiki/Drag_coefficient 삼성 소프트웨어 멤버십 쉽고 즐거운 유전자 알고리즘 – http://blog.secmem.org/search/%EC%9C%A0%EC%A0%84%EC%9E%90%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그림으로 쉽게 보는 유전자 알고리즘 – http://blog.naver.com/jiehyunkim/112909555

유전자 알고리즘(Genetic Algorithm) 시스템 트레이딩 활용하기 – http://pepic.tistory.com/248

21세기를 지향한 지능 정보 시스템 원론 – 정환묵 편저, 21세기사 http://www.aistudy.com/biology/genetic/genetic_jeong.htm#%EC%A7%84%ED%99%94%EC%A0%81%20%EC%97%B0%EC%82%B0

How Do Genetic Algorithms Work? - http://www.aistudy.co.kr/biology/genetic/work_mitchell.htm

위키피디아 유전 알고리즘 – http://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Introduction to Genetic Algorithms - http://www.scribd.com/doc/54585910/Introduction-to-Genetic-Algorithms

Simple Genetic Algorithms - http://googleperson.blogspot.kr/search/label/%EC%9C%A0%EC%A0%84%EC%9E%90%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

밀도 – http://ko.wikipedia.org/wiki/%EB%B0%80%EB%8F%84

유전자 알고리즘을 이용한 최적화 – http://dooole.tistory.com/154

유전자 알고리즘 – http://wolfsi.egloos.com/viewer/2302126

위키피디아 Box2D – http://en.wikipedia.org/wiki/Box2d

Box2D 공식 사이트 - http://box2d.org/

위키피디아 외판원 문제 – http://en.wikipedia.org/wiki/Travelling_salesman_problem

부록

GeneticAlgorithmJava

자바로 작성된 유전 알고리즘 테스트 코드 수록

GeneticAlgorithmFlash

본 탐구에 수록된 플래시 시뮬레이션 코드와 간이 발표 프리젠테이션 코드 수록

PModePresentation

상세 발표 프리젠테이션 코드 수록

build - GeneticAlgorithmFlash

exe 프로젝터로 빌드된 시뮬레이터 수록

build - PModePresentation.app

독립 실행 가능한 상세 발표 모드 프로그램

build - Presentation.app

• 간이 발표(S), 상세 발표(P) 모드 시작 전 우클릭으로 전환 가능, 클릭으로 시작

• 간이 발표 모드에서는 화살표로 발표 이동, 상세 발표 모드에서는 Page Up/Down으로 발표 이동

• q로 전체화면