민서 개발일기

https://youtu.be/Yr_nRnqeDp0

어느 날 유튜브 알고리즘에서 해당 영상이 뜨게 되었고 스스로 학습하는 AI라는 것에 흥미를 느껴 개발을 시작하게 되었다.

해당 영상에서는 '유전 알고리즘'을 이용하여 AI에게 그네를 더 넓은 폭으로 움직이도록 탈 수 있도록 학습하게 하였다.

그렇다면 개발을 시작하기 전 '유전 알고리즘'의 원리부터 알아보자

유전 알고리즘이란

유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 한다. -위키피디아 글 인용

조금 더 쉽게 정리하면 최적해를 찾기 위해 탐색을 반복해가며 더 좋은 해를 찾아가는 알고리즘이라고 할 수 있을 것 같다.

즉 유전 알고리즘을 구현하기 위해선 '해'를 유전자의 형식으로 표현할 수 있어야 하고 '더 좋은 해'를 구분하기 위한 적합도 함수를 짤 수 있어야 한다.

유전자의 형태는 여러 형태가 있을 수 있지만 가장 설명하기 쉽고 간단한 배열로 설명할 것이다.

유전 알고리즘을 구현할 때 우선 초기 해 집단은 랜덤으로 구성된다. 그 후 적합도 함수에 따라 우수한 해들을 선택하고 선택한 유전자들 중 보통 2개를 합쳐 교배하여 후대 유전자를 만든다. 그리고 그 과정에서 낮은 확률로 변이를 일으키고 현재 유전자를 후대 유전자로 교체하는 과정을 반복해야 한다.

이때 변이가 필요한 이유는 지역최적점에 빠지지 않게 하기 위해서인데 변이를 통하여 한 경로만 탐색하지 않고 여러 경로를 탐색하여 더 좋은 경로가 있는지 확인할 수 있다.

선택(Selection)

선택의 종류는 매우 다양한데 예를 들면 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.

해의 선택 방식에 따라 최적해를 구하는 속도가 빨라지고, 지역 최적점에 빠지지 않게 할 수 있으므로 선택의 과정은 매우 중요하다 할 수 있다.

일반적으로 선택을 하는 방식은 가장 좋은 해일수록 선택될 확률이 높아진다. 반대로 말하면 나쁜 해라도 선택될 가능성이 있다는 것을 의미하고 이를 통해 지역 최적점에 빠지지 않게 할 수 있다.

균등 비례 룰렛 휠 선택

유전자의 적합도에 비례하여 선택될 확률을 결정하는 선택 방식이다. 주로 전체 적합도 합에서 본인 적합도를 나누어 확률을 결정한다.

토너먼트 선택

K개의 랜덤한 해를 고르고 그 중 가장 적합도가 높은 해를 결정하는 방식이다.

음수인 적합도값에도 사용할 수 있다.

순위 기반 선택

적합도 점수를 기준으로 정렬하여 순위가 높을수록 선택될 확률을 높게 하는 방식이다.

ex) 1위 : 40%, 2위 : 30%, 3위 : 20%, 4위 10%

필자는 해당 방식을 사용했다.

교배, 교차(Crossover)

유전자를 교차하여 다음 세대의 유전자를 만드는 과정이다. 일반적으로 두 개의 유전자를 선택하여 교차 연산을 수행하며 이렇게 생성된 유전자는 각각의 부모 유전자의 교차 연산을 통한 서로 겹치지 않는 유전인자를 받아 새로운 유전자를 구성한다.

교차 연산에는 N-점 교차, 일정 교차, 산술 교차 등이 있다.

N-점 교차

해당 방식처럼 N개의 점을 골라 해당 점을 지날 때마다 다른 부모의 유전 인자를 가져가는 방식이다.

일정 교차

비트열 등을 이용한 마스크를 사용하여 일정한 형태로 교차하는 방식이다.

필자는 해당 방식을 사용했다.

산술 교차

실수 값이 사용되는 경우에 사용하며, 각 인자에 대해 두 부모 인자의 평균값을 사용한다.

변이

교차 과정에서 지역 최적점에 빠지지 않기 위해 낮은 확률로 인자 값을 랜덤 한 값으로 변환하는 것을 의미한다.

정적 변이와 동적 변이가 존재하는데 정적 변이는 변이될변이 될 확률이 고정이지만 동적 변이는 세대를 지날수록 변이 될 확률이 점점 낮아진다.

동적 변이를 사용하는 이유는 세대가 지날 수록 최적해에 가까워졌을 것이라고 판단했기 때문일 것이다.

유전 알고리즘의 기본적인 원리 설명은 끝났으니 결과물을 확인해 보자

해당 프로젝트는 https://github.com/s53809/Genetic-Algorithm를 통하여 열람, 다운로드할 수 있다.

해당 프로젝트에서는 크게 3개의 시스템으로 유전 알고리즘을 이용한 길 찾기 프로그램을 설계하였다.

유전 알고리즘의 전반적인 연산을 담당하는 GenerationManager.cs 와 GenerationManager에서 받아온 정보를 가지고 이동하고 최적해를 계산하여 다시 GenerationManager로 전달하는 EntityController.cs, 그리고 몇 세대인지, 해당 세대에서 가장 최적의 결괏값을 가졌던 유전자의 정보를 사용자에게 보여주는 UIManagement.cs 가 있다.

Entity

Entity는 실제로 탐색하는 객체들이며 GenerationManager에서 들어온 정보를 토대로 움직이고 그에 따라 최적해를 계산하는 간단한 연산을 수행한다.

GenerationManager

유전 알고리즘 연산을 수행하는 메인 시스템으로 유전자들을 생산하고, 선택, 교차, 변이, 교체 등 여러 연산을 수행하며 각 Entity에게 유전자 정보를 전달하는 역할을 한다.

Setting 헤더에 포함된 해당 변수들은 사용자로부터 Entity 객체의 개수, 변이 확률, 행동 변화 간격 시간, 행동(유전자) 개수, 움직임 속도를 입력받게 할 수 있다.

Init()에서는 초기 해 집단을 랜덤으로 구성하기 위하여 생성된 함수이다.

Select()에서는 선택 연산을 위한 함수,

DestroyObj ()에서는 교차 연산이 끝나고 새로운 유전자로 교체하기 위해 기존 Entity 객체들을 삭제하는 함수이다.

Crossover()에서는 교차 연산을 위한 함수이지만 선택, 교차, 변이의 과정이 모두 들어가 있다. 또한 선택 연산을 위하여 유전자 정보들을 정렬하기 위하여 정렬되는 대상인 EntityController에 IComparable <EntityController> 인터페이스를 상속시켜 원하는 순서대로 정렬되게끔 설계하였다. ICompareable 인터페이스에 관해서는 요긴하게 써먹을 수 있기 때문에 모르고 있었다면 찾아보는 것을 추천한다.

UIManagement

세대 정보와 해당 세대에서의 최적해의 정보를 사용자에게 표시하는 시스템이다.

결과물

https://youtu.be/LlMiof0 cqHo

느낀 점

유전 알고리즘을 공부하면서 시행착오가 많았다.

불필요한 움직임으로 인하여 내가 생각했던 것과 같은 매우 효율적인 움직임을 300세대를 거쳐도 나오지 않았으며 내가 설계한 알고리즘에 따르면 세대를 지나면 지날수록 지역 최적점에 수렴하기 쉬워졌기 때문에 도착지까지 도달하는 시간이 단축되는 빈도가 점점 줄어들었다.

교차 방법을 N-점 교차에서 일정 교차로 교체해보기도 하고 변이 확률을 늘려보았지만 개선되긴 하였으나 결국엔 세대를 지나면 지날수록 효율적인 움직임을 위해 변이에 의존하는 수밖에 없었다. 왜 사람들이 AI 분야에서 유전 알고리즘 대신 다른 알고리즘을 쓰는지 어느 정도 체감이 되었던 것 같다.

하지만 처음으로 AI라는 분야를 다뤄보면서 스스로 학습하여 경로를 찾아가는 AI를 구현했다는 사실이 나에겐 너무 신기했고 재밌었다.

빅오표기법과 stack 자료구조에 대해서 배웠다
수업 종료 10분전 문제 하나를 과제로 내주셨는데 내용은 이러하다
이런식으로 그래프가 주어지면 막대 그래프 맨 위쪽에 빨간 선을 그 그래프 기준 왼쪽으로 긋는데
이때 빨간 선이 닿는 그래프가 몇번인지 출력하는 문제이다.

그럼 한번 이 문제를 풀어보자

첫번째로 1번 배열에 있는 정보를 스택에 넣는다.

탐색을 2번 배열부터 시작하며 탐색하려는 값과 스택을 비교한다.
비교하는 도중 스택의 top에 자신보다 작은 값이 있으면 그 값은 결국 지금 탐색하는 값에 가려져 더이상 닿을 레이저가 없기 때문에 pop한다.

위와 같은 행동을 자신보다 큰 값이 나올 때 까지 반복한다.

i) 자신보다 큰 값이 나왔으면 현재 탐색하고 있는 값의 빨간 선은 그 값을 가리킨다.
ii) 자신보다 큰 값이 없다면 (스택이 비었다면) 현재 탐색하고 있는 값은 가장 큰 값이 된다.
즉 빨간 선은 제일 왼쪽 끝으로 간다.

이것은 실제로 학원에서 집으로 돌아오기 전에 짠 순서도이다. 선생님께서는 항상 문제를 풀 때 키보드에 바로 손을 대지 말고 먼저 내가 어떻게 코드를 짤 것인지 생각을 하라고 강조하셨다.
이 조언과 미리 짜둔 순서도 덕분에 나는 코드를 짤 때 전보다 더 수월하게 짤 수 있었다.
그렇게 해서 나온 코드이다.

HM(최대치) 를 10으로 설정하여 돌려봤을 때 잘 나오는 것을 확인 할 수 있었다.

이런식으로 코드를 짜면 스택을 바로바로 비워줄 수 있기 때문에 속도가 조금 빨라 질 수 있다.
시간복잡도는 탐색할 때 한번 스택으로 다시 검사할 때 한번으로 O(2N)이 나온다

※ 이 글은 그래프 탐색을 이해했다는 것을 전제 하에 쓰였습니다.
이 문제는 DFS(깊이우선탐색)을 연습하는게 딱 좋은 맵이라고 생각한다. 영어라고 겁먹을 필요없다.
우리에게는 파파고라는 좋은 친구가 있으니까

우리 파파고가 말해준 문제를 약간 요약했을때 이 문제는 저 사진에 나와있는 피라미드로 되어있는 숫자들이 보일것이다. 그래서 맨위의 숫자부터 밑으로 한층씩 내려오는데 이때 자신의 위치에서 바로 왼쪽, 오른쪽 밖에 갈 수가 없다. 그렇게 끝까지 내려왔을때의 합이 가장 큰 경우에서 그 합을 출력하면 되는것이다.
입력으로는 첫번째로 몇층으로 할건지 받고
그이후 피라미드가 만들어졌을때의 갯수 만큼의 숫자를 입력받는다.
출력은 가장 큰 합을 출력한다.
예시로

저 원을 노드라하고 빨간선을 간선이라고 했을때 맨 위에 있는 노드로 부터 시작해서 점점 탐색을 하는데 만약 탐색을 하던 도중 노드에서 외부 노드로 향하는 간선의 갯수가 0일때를 가장 피라미드의 밑부분까지 왔다고 판단하여 지금까지 지나온 경로를 합으로 더하는 방식으로 코드를 짰다.

#include <iostream>
#include <vector>
using namespace std;

int Num = 0;
int* answer;
int Real_answer = 0;
int N;

typedef struct Node {
	int score = 0;
	vector<int> adj;
} Node;

vector<Node> x;
int real_box = 0;
void DFS(int num, int a) {
	answer[a] = x[num].score;
	if (x[num].adj.size() == 0) {
		for (int i = 0; i < N; i++) {
			real_box += answer[i];
		}
		if (Real_answer < real_box) {
			Real_answer = real_box;
			
		}
		real_box = 0;
		return;
	}
	for (int i = 0; i < x[num].adj.size(); i++) {
		DFS(x[num].adj[i], a + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	answer = new int[N];
	for (int i = N; i >= 1; i--) {
		Num = Num + i;

	}
	for (int i = 0; i < N; i++) {
		answer[i] = 0;
	}
	x.resize(Num);
	int as = 1; 
	int ad = 0;
	for (int i = 0; i < Num; i++) {
		if (ad == as) {
			ad = 0;
			as++;
		}
		cin >> x[i].score;
		if (as < N) {
			x[i].adj.push_back(i + as);
			x[i].adj.push_back(i + as + 1);
		}
		ad++;
	}
	DFS(0, 0);
	cout << Real_answer;
	return 0;
}

이 코드는 처음 짰을 당시 보여주기 용으로 짠 코드가 아니기에 보기에 다소 불편한 구조들이 많다. ex) 변수명

DFS 기초 문제이기 때문에 방식만 안다면 쉬울 것 이므로 코드를 보기보다는 방식만 알아둬도 푸는데 지장이 없다.

막상 일기를 쓰려하니 무엇을 써야할지 고민하던 찰나 고맙게도 친구에게 해당 카톡이 왔다.

이게 보통 C언어에서 발생하는 문제인데 이걸 처음 직면하면 답이 없다.
왜냐하면 컴파일할때 로그를 봐도 뭐가 문제인지 안보이기 때문이다.
문제는 해당 변수를 입력하고 엔터를 입력할 때 입력버퍼에게 엔터가 남아있어서 다음 입력을 받을때 scanf가 남아있는 입력버퍼로 입력을 받아들인다는 것이다.
입력버퍼는 scanf() 같은 입력을 받는 함수에서 입력을 받을 때 입력버퍼라는 저장소에 한번 저장이 되었다가 변수로 대입하는 것이다.
그래서 저 엔터를 입력버퍼에서 지워줘야 하는데
입력버퍼를 비우는 방법은 간단하다.
사이에 getchar(); 코드를 넣어줘서 입력버퍼를 비워버리자

그거 말고도 여러방법이 있지만 나는 이 방법이 제일 간단한 것 같다.
근데 이게 처음에 말했듯이 오류창도 로그에도 안떠서 뭐가 문젠지 모른다.
이 글이 도움이 됬으면 좋겠다.

혹시 틀린것이 있으면 댓글로 말해주시면 감사하겠습니다.