안녕하세요 lee5입니다.

지난 포스팅에서는 진화알고리즘에 대한 소개와 개념 및 이론적인 내용을 알아보았습니다.
https://steemit.com/kr/@lee5/a-story-about-evolutionary-algorithms

오늘은 개념적으로는 대충 알겠는데 그럼 어디에 쓰고 구현은 대체 어떻게 해야할까에 대해서 설명드리려고 합니다.

지난번 다른 글의 저작권 논란과 관련해서 미리 말씀드리면 포스팅에 사용되는 강의 이미지 자료들은 저작권이 문제되지 않는 강의 자료들입니다.
그리고 진화 알고리즘에 대해서 steem에 설명되는 글들은 제가 학습하고 이해한 내용들을 직접 작성하는 것들입니다.^^

본론으로 돌아와서.. 유전 알고리즘은 주로 최적화 문제에서 사용됩니다.
단순하게 경우의 수들을 모두 계산해서 풀수 있는 문제들에는 적합하지 않고 시간적으로 유한시간내에 모두 계산이 불가능한 경우(NP문제)에 사용됩니다.

대표적인 문제로 세일즈맨 문제, 냅색(knapsack) 문제가 있습니다.
위 그림은 냅색 문제인데요.
무게와 가치가 다른 여러 물건들을 가방에 담을때 최적의 조합을 찾아내는 문제입니다.

여러가지 접근방법이 있겠지만, 가장 단순하게 넣을 수 있는 조합들을 선택해 보는식으로 접근할 수 있습니다.
물건의 집합에서 조합을 하는 문제는 물건의 개수가 증가하면서 지수적으로 경우의 수가 증가하게 되는데요.
바로 이런 형태의 문제에서 유전 알고리즘의 잘 동작하게 됩니다.

문제의 모든 영역을 탐색할 수 없을때 우리는 어떤 방향으로 탐색할지를 선택해야 하는데요.
완전히 랜덤하게 계속 시도해볼 수도 있고.. 하나씩 바꿔가면서 순차적으로 찾아볼 수도 있습니다.

이때 유전 알고리즘은 여러개의 후보들을 분산시켜두고 경쟁과 협력에 기반한 진화연산을 통해 최적의 해를 탐색해 나가게됩니다.

개념적으로는 지난번의 이 그림을 다시한번 떠올리시면 됩니다. ^^

유전 알고리즘의 구현을 위해서는 위 내용에 대한 이해가 필요합니다.

위에서부터 차근차근 살펴보면

encoding

현실의 문제를 최적화와 진화연산이 용이한 형태로 변경해 줘야합니다.
냅색을 예를들면, 만약 백개의 물건이 있다면 길이가 100인 배열을 설정하고 1번물건이 가방에 들어가면 배열1번을 1로 들어가지 않으면 0으로 표현할 수 있습니다. 그래서 백개의 물건 중 가방에 들어가는 물건이 무엇인지 정의할 수 있습니다.

population

여러개의 후보들을 생성해야 합니다. 다시 냅색을 생각하면 길이가 100인 배열이 여러개 생성된다고 생각하시면 됩니다.
그리고 이렇게 생성된 후보들은 각각 랜덤한 값으로 초기 값이 설정됩니다. (후보들을 넓게 분산시키기 위해서 랜덤하게 설정됩니다.)

fitness function

각 후보에 대해서 각각이 갖는 적합도를 평가해야 합니다. fitness function은 후보들을 하나씩 문제에 대입시켜 어느정도의 점수를 갖는지 평가하기 위한 함수입니다. 냅색문제를 생각하면, 제한 무게를 만족하면서 가방에 있는 물건들의 가치가 적합도가 될 수 있습니다. (1번후보:5$, 2번후보:150$, 3번후보:75$, 4번후보:무게초과)와 같은 식으로 적합도가 나타나겠죠.

genetic operator

진화 연산자들입니다. selection, crossover, mutation이라는 세가지의 대표적 연산자 들이 있습니다.

selection은 적합도가 높은 후보를 선택하는 연산자 입니다. 유전 알고리즘에서는 자연의 적자생존 개념을 이런식으로 접근 했습니다. 다시 냅색문제로 살펴보면 위의 2번후보(150$)와 3번후보(75$)는 선택받을 확률이 다른 후보들 보다 높습니다. 1번후보와 4번후보는 상대적으로 적은 확률일것이구요.

crossover는 선택된 개체들이 가지고 있는 값을 믹싱하는 개념입니다. 냅색 문제의 길이가 100인 배열에서 임의의 점들을 crossover point로 선정하여 두개의 후보가 가지고 있는 값을 잘라서 서로 교환해줍니다.

mutation은 실제 돌연변이를 모사한 것으로 냅색으로 보시면 배열의 임의의 포인트의 값을 바꿔주는 연산을 합니다.
랜덤하게 몇개의 점을 선택해서 0이면 1로, 1이면 0으로 바꿔주는 식으로 동작합니다.

그래서 위의 알고리즘 순서도에서 처럼 문제의 인코딩-->적합도평가-->진화연산-->적합도평가-->진화연산-->적합도평가-->(계속 반복)-->종료의 순서로 진행되고. 충분히 반복되고 종료가 되면 최적의 해를 얻을 수 있게됩니다.

이야기하다보니 내용이 너무 많아져서 다음으로 이어서 작성하도록 하겠습니다.

영어 댓글은 없었고해서 따로 번역은 하지 않았습니다.

감사합니다.

@lee5