얇고 많은 지식(박학다식, 薄學多識) 한 보탬 하는 것이 목적으로 어디 가서 비전공자도 "나 그거 알아!"라는 말을 하실 수 있도록 쓰도록 하겠습니다. 의사소통에 큰 어려움을 겪고 있는 흔한 대한민국 공돌이니, 혹시나 설명이 이상하고 이해가 어렵다면 댓글이나 쪽지로 얘기해주시면 다듬도록 하겠습니다! 더불어 저 자신도 공부하면서 쓰는 부분도 있으므로 잘못된 개념이 쓰여있을 수도 있습니다. 전공자, 잘 알고 계신 분들께선 잘못된 개념이 있다면 바로잡아 주시기 바랍니다! ---------- 서론 이번 글은 유전알고리즘에 대해 설명해보려 합니다.
먼저 최적화가 무엇인지 설명하고 유전알고리즘이 왜 사용되는지에 대하여 얘기해보겠습니다.
그리고서 유전알고리즘의 기본개념들을 설명합니다.
마지막으로 간단한 예제를 통해 어떻게 굴러가는지 보여드리겠습니다.
덧붙여서 참고문헌을 간략하게 소개하겠습니다.
[1] 문병로, "쉽게 배우는 유전 알고리즘 : 진화적 접근법", 한빛 미디어, 2008
[2] 진강규, "유전 알고리즘과 그 응용 Genetic Algorithms and Their Applications", 교우사, 2000
참고문헌 [1] : 제가 개념적으로 많은 도움을 얻었던 책이었습니다. 이 책을 보면서 제가 이 알고리즘이 어째서 돌아가는지 깨달음을 얻었던 그림을 나름대로 재구성하여 중간에 집어넣어 봤습니다.
참고문헌 [2] : 제 주력 사용언어가 MATLAB인데, MATLAB으로 된 전체 유전알고리즘 코드가 있어서 눈으로 보면서 타이핑하며 어떻게 코드가 돌아가나 생각해 볼 수 있게 해주었던 책입니다. 1. 최적화란 무엇인가? 최고로 좋은 것을 만드는 과정을 최적화라고 합니다.
몇 개 중에 제일 좋은 것 고르는 것도 최적화라고 칭하는 경우가 있으나, 좀 더 수학(과학)적인 방법으로 구하는 것을 최적화라 하겠습니다.
최적화 방법은 두 가지가 있는데, 민감도 쓰는 방법과 쓰지 않는 방법이 있습니다.
민감도란 내가 결정할 수 있는게(설계변수) 얼마나 목적에 민감하게 영향을 주는지 수학적으로 구한 것입니다.
조금 더 전문적으로 얘기하면, 목적함수를 설계변수들로 편미분한것을 뜻합니다.
민감도를 쓰는 방법은 설계변수들을 좋아지는 방향으로 조금씩 바꿔나가 더이상 좋아질 수 없을 때까지 나아가는 방식입니다.
예를 들어 산속에서 가장 높은 곳으로 가고 싶다면 높이가 최대가 하게 하는 최적화 문제이며 위도와 경도가 설계변수가 됩니다.
높이는 위도와 경도에 따라 바뀌고 민감도는 경사도가 됩니다. 민감도가 가장 큰, 경사도가 가장 높은 방향으로 걸어나가, 정상에 도달하면 됩니다.
그런데, 이 산맥에서 가장 높은 봉우리를 찾아왔다면? 지금 서 있는 봉우리가 진짜 최고로 높은 곳일까요? 봉우리에 섰다는 건 그 근처에서 가장 높은 곳, 정상에 섰기 때문에, 민감도가 0이 되게 되어 움직일 수 없습니다.
낮에 산에 간다면 물론 어디가 가장 높은 데인지 주변을 둘러보면 알 수 있을 것입니다. 그러나 실제 최적화 문제는 깜깜한 밤에, 오직 휴대폰의 가속도계와 gps 고도계만을 믿고 탐사해 나가는 것과 같습니다. 깜깜한 밤에, 모든 부분의 높이를 알고 그중에 가장 높은 곳을 찾아가야 한다고 생각해보세요. 탐색하고자 하는 공간 안에 모든 목적함수 값의 크기비교를 한다는 것은 거의 불가능에 가깝습니다.
따라서 민감도를 이용하는 경우, 봉우리가 많은 문제-이런 문제를 볼록도(convexity)가 떨어지는 경우 라고 합니다-에서 전체영역에서 최적해를 구하는데 어려움이 있습니다.
살다 보면 민감도를 못 구하는 경우도 많고 convexity 가 떨어지는 경우도 많습니다.
그래서 민감도 안 쓰는 방법이 종종 사용되는데 그 방법 중 하나가 유전알고리즘입니다. 2. 유전알고리즘이란? 자연의 진화 과정에 영감을 받은 알고리즘으로 "여러 유전자들 중 좋은 놈들이 오래 살아남아 자신의 속성을 퍼뜨리는 것" 을 이용합니다.
다음과 같은 기본 순서를 따르며 다양한 변종이 존재합니다.
0) 설계변수를 적절히 잘 표현하는 표현법을 적용하여 적당한 수의 초기 유전자 풀을 만든다.
1) 어느 놈이 좋은 놈인지 평가한다.
2) 좋은 놈들을 적절히 잘 뽑는다.
3) 좋은 놈들의 성질을 적절히 잘 짬뽕시켜 다음 유전자를 만든다.
4) 1)로 간다 그만하고 싶을 때 까지 반복!
이게 되도록 만들면 유전알고리즘입니다.
0,1,2,3 모두 많은 방법이 있으나 제가 이 방법 자체를 연구한 것도 아니고 사용만 했던 입장이며, 목적은 "아는 체 할 수 있다!" 이므로 가볍게만 얘기하고 지나가겠습니다.
다음 예제를 통해 단순 유전알고리즘(Simple Genetic Algorithm)이 어떻게 적용되는지 보여드리겠습니다.
목적함수를 다음과 같이 설정하겠습니다.
"1a+2b+4c+8d 최대화"
이때 (a,b,c,d)를 유전자로 하고, 각 알파벳은 0 또는 1이 될 수 있습니다.
예를 들어 (1,0,0,1) 이라고 하면,
1*1+2*0+4*0+8*1 = 9
이렇게 되 는거죠.
자 그럼 a,b,c,d 가 각각 1일때 나올 수 있는 목적함수의 값을 볼까요?
평균이 가장 높은 것은 d가 1일 때 입니다.
따라서 목적함수가 더 큰 것들을 고른다면 d가 1인 녀석들이 더 잘 골라져서, 전체적으로 목적함수 값이 증가하는 것이죠.
*번외 이런 식으로 특정한 부분 패턴들을 "스키마" 라고 하고, 이런 스키마 중 '좋은 스키마를 어떻게 잘 보존해서 다음 세대에 물려줄 수 있는가?' 가 유전알고리즘 자체를 연구하시는 분들 주제인 것 같습니다. 하지만 사용만 하는 입장이라 넘겼습니다 -_- 깊게 보고 싶으시면 책보세요 책. 참고문헌 보시면 됩니다. 최첨단 학문이면 논문을 봐야 하나 유전알고리즘 기본 부분은 책보셔도 무방합니다.
이제 그럼 어떻게 골라야 하는지 생각해 봅시다!
목적함수가 큰 것들을 조금 더 많이 고르고 싶습니다. 작은 것은 조금 더 빨리 도태되게 하고 싶어요.
그러면 어떻게 하면 될까요?
큰 것들이 더 크게 영향을 주도록, 작은 것은 더 작게 영향을 주도록 "적합도" 라는 것을 하나 더 둡시다.
예를 들어서 적합도는 목적함수^2 으로 해볼까요?
그러면 0~15 였던 목적함수가 0~255 라는 훨씬 더 큰 범위로 바뀌게 됩니다.
이런 식으로 보통 적합도를 두어 처리하는데, 적합도를 설정하는 건 알아서, 잘! 선택하시면 됩니다 -_-
단 여기서 주의해야 할 건 빠른 것이 좋다고, 적합도 낮은 애들을 바로바로 버리면, 적합도는 낮지만, 최적점의 스키마를 가지고 있는 것들이 버려져 정말 최적점을 찾지 못할 가능성이 있으니 너무 버리지 말고 적당히 버려야 합니다. 예를 들어 d가 1인 것만 챙기고 나머지는 버린다고 하다가는 잘못하면 a가 0인 것만 골라 진짜 최고의 값인 15에 도달하지 못할 수도 있습니다.
앞서 정의한 적합도를 바탕으로, 다음을 한번 볼까요?
"유전자 - 목적함수 - 적합도" 순으로 4개만 무작위로 적어보겠습니다.
(1,1,0,1) - 11 - 121
(0,1,0,1) - 5 - 25
(0,0,0,1) - 1 - 1
(1,0,0,0) - 8 - 64
자 이제 여기서 적당히 다음 세대에 후손을 남길! 2개를 뽑으면 됩니다. 룰렛휠, 토너먼트 등등 이 있는데 여기도 [2) 좋은 놈들을 적절히 잘 뽑는다] 가 되도록 알아서 잘! 선택하시면 됩니다.
예를 들어 룰렛휠 방법을 설명해보겠습니다.
모든 적합도를 다 더한 전체 적합도 합으로, 각각의 적합도를 나누면 각각이 얼마나 적합한 놈인지 비율이 딱 나옵니다. 위 예에서 전체 적합도 합은 211이므로, 비율까지 추가하면 다음과 같습니다.
(1,1,0,1) - 11 - 121 - 121/211=0.573
(0,1,0,1) - 5 - 25 - 25/211=0.118
(0,0,0,1) - 1 - 1 - 1/211=0.047
(1,0,0,0) - 8 - 64 - 64/211=0.303
이러면 각각 선택될 확률이 57.3%, 11.8%, 4.7%, 30.3%라는 얘기입니다.
다트판에 각각 비율로 표시해주시고 다트 던져서 맞춘 유전자 하나 챙기시면 됩니다 흐흐
아무튼 이렇게 부모로서 자신의 형질을 남길 수 있는 유전자 2개를 뽑아주고, 적절히 잘! 섞어주시면 됩니다.
예를들어 (1,1,0,1),(1,0,0,0) 이 뽑혔다고 합시다.
저는 두개 씩 띠어다 붙일 겁니다.
(1,1,0,1) -> (1,1,0,0)
(1,0,0,0) -> (1,0,0,1)
이렇게 말이죠. 꼭 반인 곳에서 할 필요 없고 다시 한번 말하지만, 적절히 잘! 섞어주시면 됩니다.
이렇게 해서 새로운 세대가 만들어지고, 반복하시면 됩니다.
2. 실전! 나도 할 수 있다!
적절하지못한 개드립과 함께 아주아주 간단한 예제를 보여드리겠습니다.
0) 설계변수를 적절히 잘 표현하는 표현법을 적용하여 적당한 수의 초기 유전자 풀을 만든다.
설계 변수 잘 표현하는 거 정말 중요합니다. 문제에 맞춰서 적당히 잘 써주세요 (..)
4개짜리를 만들어 보겠습니다.
랜덤함수 적당히 돌리세요. 여기선 위의 예제를 사용하겠습니다.
1) 어느 놈이 좋은 놈인지 평가한다.
유전자 - 목적함수 - 적합도
(1,1,0,1) - 11 - 121
(0,1,0,1) - 5 - 25
(0,0,0,1) - 1 - 1
(1,0,0,0) - 8 - 64
2) 좋은 놈들을 적절히 잘 뽑는다.
(1,1,0,1) - 11 - 121 - 121/211=0.573
(0,1,0,1) - 5 - 25 - 25/211=0.118
(0,0,0,1) - 1 - 1 - 1/211=0.047
(1,0,0,0) - 8 - 64 - 64/211=0.303
-> 낮은 것부터 차례로 쌓아 누적 확률 표시
(0,0,0,1) - 1 - 1 - 1/211=0.047 0.047
(0,1,0,1) - 5 - 25 - 25/211=0.118 0.165 (1,0,0,0) - 8 - 64 - 64/211=0.303 0.468 (1,1,0,1) - 11 - 121 - 121/211=0.573 1
축 (0,1,0,1) (1,0,0,0) 한 쌍 탄생!
축 (1,1,0,1) (1,0,0,0) 한 쌍 탄생!
3) 좋은놈들의 성질을 적절히 잘 짬뽕시켜 다음 유전자를 만든다.
축 (0,1,0,1) (1,0,0,0) 두 분 쌍둥이 출산!
(0,1,0,0), (1,0,0,1) 두 분 반씩 닮았네요 ^^
축 (1,1,0,1) (1,0,0,0) 두 분 쌍둥이 출산!
(1,1,0,0), (1,1,0,1) 왼쪽 분 많이 닮았네요 ^^
굵은 글씨와 원래 글씨로 각각 부모 세대에서 뭘 물려받았는지 표시했습니다.
4) 1)로 간다 그만하고 싶을 때 까지 반복!
(1,1,0,1) 네 분 사회진출 시간입니다. 1)로 가세요. 제가 마음에 들 때까지 ^^
3. 마치며 쓰는 여러 뱀다리들
9/1에 쓰겠다고 거창한 가입인사 올렸었는데 인제야 올립니다. 글 쓰는 것이 너무 어렵네요. ㅠㅠ 계실지 모르겠지만 기다리셨던 분들께 사과의 말씀 드립니다. 그나저나 적절히 잘 설명이 된 건지 모르겠습니다. 이해가 가지 않는 부분들은 댓글이나 쪽지 남겨주시면 최대한 노력해서 답변드리겠습니다! 제가 설명을 못 해서 이해가 안 가는 거니까, 부끄러워하지 마시고 어느 부분이 이해가 안 가는지 얘기해주세요!
유전알고리즘을 사용해본 소감은, 손으로 찾는 게 나은 문제도 충분히 있다는 겁니다 (..) 목적함수 구하는데 약 12초가 걸리는 문제였는데, 보통 유전알고리즘 돌린 예들을 보면 목적함수 계산만 만 번 정도는 아주 우습게 사용합니다. 대충 한 달만 풀로! 컴퓨터 한 대를 희생하면 돼요 하하하하하하하하... 물리적으로 어느 정도 유추할 수 있는 문제다 보니, 유전알고리즘 돌리는 시간보다 손으로 계속 돌려 찾는 쪽이 낫더군요 -_- 이틀 parametric sweep 하니깐 대충 나오던데... 손으로 구하면 논문거리가 아니니 억지로라도 유전알고리즘을 써야하는 타당한 이유 창작 및 그에 따른 구현 덕에 연구가 대충 5개월쯤 딜레이 된 것 같습니다. 교수님 못난 제자 용서하시옵서소.
하스스톤으로 유전알고리즘 짠 학생은 칭찬해주는걸로... 엑셀로 했다니 매우 믿음이 갑니다. 엑셀로 한걸 본적이 없거든요 (..) cc+cv 가 아니란건 직접 짰단얘기니까요. 고등학생때 주어진 길 바깥의 이런거 찾아서 한다는건 대단한겁니다. 원래 그때 쓸려고 했는데, 이제 완성하는군요.
글 다쓰고 그림넣고 정렬까지 다한상태에서 맞춤법 검사기 돌렸다가 잠시 굳었습니다. 이거 쓰기전엔 돌렸는데, 다시 돌릴 엄두가 안나네요. 패스
다음주제는... 생각나면 그때 써보겠습니다. 언제가 될지 모르겠네요... 하하.......
2
|
