유전알고리즘 ( Evolution Algorithms )
컴퓨터공학/알고리즘&자료구조 2011. 5. 2. 20:44
유전알고리즘.
내가 소속한 연구실에서 유전알고리즘을 학습하면서
정리도 할 겸 유전알고리즘에 대해서 포스팅하게 되었다.
보통 알고리즘이라하면, 주어진 문제를 제한된 자원하에 풀 수 있는 일련의 절차"를 생각하기 쉽지만,
유전알고리즘은 지금까지와의 알고리즘과는 살짝 성격을 달리하는 알고리즘이다.
유전알고리즘은 그 이름에서도 알 수 있듯이 주어진문제에 대한 '답'을 진화시켜서 찾아낸다.
그래서 항상 최적해를 찾는다는 보장은 없지만, 준최적해를 구하는 뛰어난 알고리즘이다.
일반적으로 유전알고리즘이 다루는 문제는 일반 알고리즘으로 풀 수 있는 그런 문제를 대상으로 하지 않는다.
예를들어 정렬이라던가, 다익스트라알고리즘, 선형계획알고리즘 등 다항시간내에 풀 수 있는 문제는 유전알고리즘의 대상이 아니다.
유전알고리즘은 주로 다항시간내에 풀기 곤란한 문제라던가, 답이 존재하는지 존재하지 않는지 모르는 문제에 적용된다.
예를들면, 다목적순회판매원문제를 생각해볼수가 있겠다.
다목적순회판매원문제는 유명한 NP완전문제이다.
다항시간내에 풀기가 매우 곤란한 문제이다.
이런 문제에 유전알고리즘을 적용시켜서 준최적해를 구하기는 '비교적간단'하다.
구체적으로 유전알고리즘을 알아보기전에, 유전알고리즘의 특징에 대해서 좀 살펴보자.
유전알고리즘은 뛰어난 유전자를 가진 개체가 다음 세대에도 살아남는다는 아이디어를 이용한다.
그렇다. 다윈의 '진화론'과 매우 비슷하다.
매우 많은 세대교체가 이루어지고 난 다음의 개체들중 가장 뛰어난 개체을 답으로 제시하는 방법, 그것이 유전알고리즘의 개요이다.
유전알고리즘에서 파생된 여러 알고리즘중 진화알고리즘은 유전알고리즘의 성질을 가장 솔직하게 적용시키는 알고리즘 중 하나이다.
물론, 진화알고리즘(Genetic Algorithms)에도 여러 갈래가 있지만 그 중에서 가장 간단한 Simple Genetic Algorithms 을 살펴보자.
문제마다 파라미터를 변경시켜서 가장 성능을 좋게 만드는 작업이 필요하다는 것이 여느 알고리즘과는 달라서 생소할것이다.
이른바, Do And Fix 를 다소 필요로한다.
문제를 설정해 보자.
실수함수 f(x, y) 가 주어졌다고 할 때, 이 실수함수의 최소값이 존재하는지, 존재하면 그 값은 얼마인지를 찾는다.
어떻게 풀것인가? 잠시 생각해보길바란다.
이 문제에 유전알고리즘을 적용시켜서 준최적해를 찾아보도록하자 ( 찾은해가 최적해이지 않을 수 있다는것을 전제로 한다. )
1. 개체수는 3000 개 정도로 설정해보자. ( 이 값을 높게 설정할수록 성능은 좋아진다. == 해의 정밀도가 높아진다 )
2. 1세대부터 1000 세대까지 진화시켜보자. ( 이 값을 높게 설정할수록 성능은 좋아진다. == 해의 정밀도가 높아진다 )
3. 하나의 개체가 가지는 유전자를 설정하자.
>> 이 문제같은 경우, 유전자를 double gene[2] ( x, y 값 ) 로 설정한다. 즉, gene[0] 이 x 값, gene[1] 이 y 값이 되는것이다.
4. (중요) 하나의 개체가 문제에 대해서 얼마나 적합한지를 판단하는 적응도함수를 설정하자.
>> y=x^2 과 같은 함수라면, 문제를 풀기전에 이미 최대값은 없고, 최소값은 0 이라는 사실을 알기에 0 에 가까울수록 높은 적응도를 주는 함수로 설정하면 된다. 하지만, 최소값의 존재여부를 모르기에 이 함수를 어떻게 작성하는가에 따라서 준최적해의 정밀도가 달라진다. 이 적응도 함수의 작성법에는 여러가지가 있겠지만, 여기서는 충분히작은수를 미리 정의하여놓고 이값에 얼마나 가까운지에 따라서 적응도를 리턴하는 함수를 작성한다. 예를들어 -10000000 에 가까울수록 높은 적응도를 리턴한다고 하자.
===============================================================================================================
5. 첫 세대는 랜덤하게 생성한다.
6. n 번째 세대의 모든 개체에 대하여 적응도 함수를 적용시켜 적응도를 구한 후, 적응도에 대해여 내림차순으로 정렬한다.
7. 엘리트(적응도가 높은 개체)들은 다음세대에 그대로 남긴다.
8. 엘리트 개체들을 부모로 하여 자식을 생성한다.
>> 엘리트개체에서 랜덤하게 2개의 개체를 선택하여 유전자를 랜덤하게 섞어서 자식을 생성한다. 쌍방교환이 아니라 유전자를 섞는것임에 주의.
9. 엘리트가 아닌 개체들에 대해서 돌연변이를 일으킨다.
>> 엘리트가 아닌 개체들중 낮은 확률로 개체의 유전자를 재할당한다.
10. n+1 세대로 세대를 교체한다.
>> 6번으로 돌아간다. 루프를 돌며 세대를 교체한다.
이것이 가장간단한 진화알고리즘이다.
코드를 작성하는것도 매우 간단하다. 직접 아무 함수를 정의하여서 적용시켜보길바란다.
연속함수에대해서 매우 높은 정밀도로 준최적해를 구할 수 있음이 알려져있지만,
불연속함수에대해서는 조금 더 개선된 진화알고리즘을 쓴다.
내가 소속한 연구실에서 유전알고리즘을 학습하면서
정리도 할 겸 유전알고리즘에 대해서 포스팅하게 되었다.
보통 알고리즘이라하면, 주어진 문제를 제한된 자원하에 풀 수 있는 일련의 절차"를 생각하기 쉽지만,
유전알고리즘은 지금까지와의 알고리즘과는 살짝 성격을 달리하는 알고리즘이다.
유전알고리즘은 그 이름에서도 알 수 있듯이 주어진문제에 대한 '답'을 진화시켜서 찾아낸다.
그래서 항상 최적해를 찾는다는 보장은 없지만, 준최적해를 구하는 뛰어난 알고리즘이다.
일반적으로 유전알고리즘이 다루는 문제는 일반 알고리즘으로 풀 수 있는 그런 문제를 대상으로 하지 않는다.
예를들어 정렬이라던가, 다익스트라알고리즘, 선형계획알고리즘 등 다항시간내에 풀 수 있는 문제는 유전알고리즘의 대상이 아니다.
유전알고리즘은 주로 다항시간내에 풀기 곤란한 문제라던가, 답이 존재하는지 존재하지 않는지 모르는 문제에 적용된다.
예를들면, 다목적순회판매원문제를 생각해볼수가 있겠다.
다목적순회판매원문제는 유명한 NP완전문제이다.
다항시간내에 풀기가 매우 곤란한 문제이다.
이런 문제에 유전알고리즘을 적용시켜서 준최적해를 구하기는 '비교적간단'하다.
구체적으로 유전알고리즘을 알아보기전에, 유전알고리즘의 특징에 대해서 좀 살펴보자.
유전알고리즘은 뛰어난 유전자를 가진 개체가 다음 세대에도 살아남는다는 아이디어를 이용한다.
그렇다. 다윈의 '진화론'과 매우 비슷하다.
매우 많은 세대교체가 이루어지고 난 다음의 개체들중 가장 뛰어난 개체을 답으로 제시하는 방법, 그것이 유전알고리즘의 개요이다.
유전알고리즘에서 파생된 여러 알고리즘중 진화알고리즘은 유전알고리즘의 성질을 가장 솔직하게 적용시키는 알고리즘 중 하나이다.
물론, 진화알고리즘(Genetic Algorithms)에도 여러 갈래가 있지만 그 중에서 가장 간단한 Simple Genetic Algorithms 을 살펴보자.
문제마다 파라미터를 변경시켜서 가장 성능을 좋게 만드는 작업이 필요하다는 것이 여느 알고리즘과는 달라서 생소할것이다.
이른바, Do And Fix 를 다소 필요로한다.
문제를 설정해 보자.
실수함수 f(x, y) 가 주어졌다고 할 때, 이 실수함수의 최소값이 존재하는지, 존재하면 그 값은 얼마인지를 찾는다.
어떻게 풀것인가? 잠시 생각해보길바란다.
이 문제에 유전알고리즘을 적용시켜서 준최적해를 찾아보도록하자 ( 찾은해가 최적해이지 않을 수 있다는것을 전제로 한다. )
1. 개체수는 3000 개 정도로 설정해보자. ( 이 값을 높게 설정할수록 성능은 좋아진다. == 해의 정밀도가 높아진다 )
2. 1세대부터 1000 세대까지 진화시켜보자. ( 이 값을 높게 설정할수록 성능은 좋아진다. == 해의 정밀도가 높아진다 )
3. 하나의 개체가 가지는 유전자를 설정하자.
>> 이 문제같은 경우, 유전자를 double gene[2] ( x, y 값 ) 로 설정한다. 즉, gene[0] 이 x 값, gene[1] 이 y 값이 되는것이다.
4. (중요) 하나의 개체가 문제에 대해서 얼마나 적합한지를 판단하는 적응도함수를 설정하자.
>> y=x^2 과 같은 함수라면, 문제를 풀기전에 이미 최대값은 없고, 최소값은 0 이라는 사실을 알기에 0 에 가까울수록 높은 적응도를 주는 함수로 설정하면 된다. 하지만, 최소값의 존재여부를 모르기에 이 함수를 어떻게 작성하는가에 따라서 준최적해의 정밀도가 달라진다. 이 적응도 함수의 작성법에는 여러가지가 있겠지만, 여기서는 충분히작은수를 미리 정의하여놓고 이값에 얼마나 가까운지에 따라서 적응도를 리턴하는 함수를 작성한다. 예를들어 -10000000 에 가까울수록 높은 적응도를 리턴한다고 하자.
===============================================================================================================
5. 첫 세대는 랜덤하게 생성한다.
6. n 번째 세대의 모든 개체에 대하여 적응도 함수를 적용시켜 적응도를 구한 후, 적응도에 대해여 내림차순으로 정렬한다.
7. 엘리트(적응도가 높은 개체)들은 다음세대에 그대로 남긴다.
8. 엘리트 개체들을 부모로 하여 자식을 생성한다.
>> 엘리트개체에서 랜덤하게 2개의 개체를 선택하여 유전자를 랜덤하게 섞어서 자식을 생성한다. 쌍방교환이 아니라 유전자를 섞는것임에 주의.
9. 엘리트가 아닌 개체들에 대해서 돌연변이를 일으킨다.
>> 엘리트가 아닌 개체들중 낮은 확률로 개체의 유전자를 재할당한다.
10. n+1 세대로 세대를 교체한다.
>> 6번으로 돌아간다. 루프를 돌며 세대를 교체한다.
이것이 가장간단한 진화알고리즘이다.
코드를 작성하는것도 매우 간단하다. 직접 아무 함수를 정의하여서 적용시켜보길바란다.
연속함수에대해서 매우 높은 정밀도로 준최적해를 구할 수 있음이 알려져있지만,
불연속함수에대해서는 조금 더 개선된 진화알고리즘을 쓴다.
'컴퓨터공학 > 알고리즘&자료구조' 카테고리의 다른 글
| [알고리즘&자료구조] 힙 구조 & 힙 정렬 (0) | 2011.03.05 |
|---|---|
| [정렬알고리즘] Quick Sort 퀵소트 (0) | 2011.03.05 |
어떻게 살아야하는걸까..
생각들 2011. 4. 16. 16:35
요즘들어 부쩍 '어떻게 살야야하나...'를 생각하게 된다.
어떻게 살아야하나..
삶에 목적이라는것이 있을까?
삶에 목적이 있다면, 그 목적을 달성하려고 사는것일테지만..
내 삶에 목표가 무엇인지 잘 모르겠다.
행복해지려고 사는걸까?
행복은 뭐지?
돈이 행복인가?
사람마다 '왜 사는가?'에 대한 답은 다 다를것이다.
따라서, '어떻게 살아야하는가'에 대한 답도 사람마다 다를것이다.
따라서, 나는 나를 좀더 알 필요가 있다.
그래야 어떻게 살아야 할것인가를 생각할 수 있을것이다.
그렇다면 '나 자신을 알기'를 어떻게 알 수있을까?
가장 먼저 떠오르는 방법은,
가까운 타인에게 나를 물어보는 것이 있겠다.
나를 잘 알고있을법한, 또는 그럴 가능성이 높을것으로 추정되는 사람에게
나에대해 물어봄으로써 나를 관찰하는 방법이 있다.
다음 방법으로는,
나를 알기위한 일을 해 보는것이다.
항상 나는 나를 관찰해야한다.
어떤 상황에서도 나를 관찰하는 것에 촉각을 곤두세우고
관찰해보는것이다.
이를 위해서, 일기를 쓰거나 메모를 하는방법이 좋겠다.
사실, 누군가 나를 비디오로 촬영한것을 나중에 내가 보는것이 좋겠다고 생각하지만,
현실적으로 실현이 어려울것같으므로 일기나 메모로 대체한다.
다음으로는,
타인의 삶을 간접적으로 체험해 보는 방법이 생각난다.
책이나 영화, 이야기를 통해서 타인의 삶을 체험해보자.
그럼으로써, 그 사람의 세상을 대하는 태도나
자기자신을 대하는 태도에 대해 공부해 볼 수 있다.
이 방법은 최대한 많은 타인의 삶을 경험해 보고,
과거의 자신을 비교해 봄으로써,
자신을 분석해 볼 수 있다.
마지막으로,
사색이다.
사색이란 일종의 상상과도 같은것이다.
상상이란 정말 마법과도 같은것이라서,
생각으로도 많은것을 경험해 볼 수가 있다.
나 자신에 대해 사색해보자.
사실, 대부분의 사람들은 스스로 자기자신을 잘 알고있다고 생각하지만
실제로는 그렇지 않은경우가 대부분이다.
내가 생각하는 자기 자신이 실제로는 자기 자신이 아닐 수 있다는것이 충격적이지 않는가?
답은 없다.
없을 것이다.
소크라테스도 아리스토텔레스도 공자도 맹자도 어느누구도
'내가 누구인가'에 대한 답을 찾지 못했다.
끊임없는 사색을 통해 많이 알 수는 있지만,
결코 모두 알수는 없다. 없을 것이다.
다시 처음으로 돌아가서,
나는 '어떻게 살아야하는것인가'를
'내가 누구인가'를 앎으로써 알아보고자한다.
어떻게 살아야하나..
삶에 목적이라는것이 있을까?
삶에 목적이 있다면, 그 목적을 달성하려고 사는것일테지만..
내 삶에 목표가 무엇인지 잘 모르겠다.
행복해지려고 사는걸까?
행복은 뭐지?
돈이 행복인가?
사람마다 '왜 사는가?'에 대한 답은 다 다를것이다.
따라서, '어떻게 살아야하는가'에 대한 답도 사람마다 다를것이다.
따라서, 나는 나를 좀더 알 필요가 있다.
그래야 어떻게 살아야 할것인가를 생각할 수 있을것이다.
그렇다면 '나 자신을 알기'를 어떻게 알 수있을까?
가장 먼저 떠오르는 방법은,
가까운 타인에게 나를 물어보는 것이 있겠다.
나를 잘 알고있을법한, 또는 그럴 가능성이 높을것으로 추정되는 사람에게
나에대해 물어봄으로써 나를 관찰하는 방법이 있다.
다음 방법으로는,
나를 알기위한 일을 해 보는것이다.
항상 나는 나를 관찰해야한다.
어떤 상황에서도 나를 관찰하는 것에 촉각을 곤두세우고
관찰해보는것이다.
이를 위해서, 일기를 쓰거나 메모를 하는방법이 좋겠다.
사실, 누군가 나를 비디오로 촬영한것을 나중에 내가 보는것이 좋겠다고 생각하지만,
현실적으로 실현이 어려울것같으므로 일기나 메모로 대체한다.
다음으로는,
타인의 삶을 간접적으로 체험해 보는 방법이 생각난다.
책이나 영화, 이야기를 통해서 타인의 삶을 체험해보자.
그럼으로써, 그 사람의 세상을 대하는 태도나
자기자신을 대하는 태도에 대해 공부해 볼 수 있다.
이 방법은 최대한 많은 타인의 삶을 경험해 보고,
과거의 자신을 비교해 봄으로써,
자신을 분석해 볼 수 있다.
마지막으로,
사색이다.
사색이란 일종의 상상과도 같은것이다.
상상이란 정말 마법과도 같은것이라서,
생각으로도 많은것을 경험해 볼 수가 있다.
나 자신에 대해 사색해보자.
사실, 대부분의 사람들은 스스로 자기자신을 잘 알고있다고 생각하지만
실제로는 그렇지 않은경우가 대부분이다.
내가 생각하는 자기 자신이 실제로는 자기 자신이 아닐 수 있다는것이 충격적이지 않는가?
답은 없다.
없을 것이다.
소크라테스도 아리스토텔레스도 공자도 맹자도 어느누구도
'내가 누구인가'에 대한 답을 찾지 못했다.
끊임없는 사색을 통해 많이 알 수는 있지만,
결코 모두 알수는 없다. 없을 것이다.
다시 처음으로 돌아가서,
나는 '어떻게 살아야하는것인가'를
'내가 누구인가'를 앎으로써 알아보고자한다.
'생각들' 카테고리의 다른 글
| 익숙한 것으로부터의 탈피 (0) | 2011.10.14 |
|---|---|
| 언론의 존재의의 (0) | 2011.03.19 |
3.11 일본관동대지진 이후 하루에도 몇시간씩 TV를 보고있다.
인터넷, TV, 라디오 등을 포함한 일본의 언론에 대한 나의 느낌은 "신중"이다. 한국과는 또 다른느낌이다.
한국의 인터넷뉴스를 보고있자면, 도대체 기자라는 사람이 이럴수가있나 싶을 정도다.
한국의 공중파 TV 에서조차도 '경고&주의'를 가장한 '겁주기'식의 보도를 하고있는것 같다.
일본관동대지진에대한 한국의 뉴스제목은 그야말로 경악 그 자체다. 과연 이런 문구는 누가 작성하는것일까..
이번 대참사를 다루는 일본 미디어에서 느낀점은 " 미디어를 통해 실제로 도움이 되는 정보전달 " 을 신중하게 전달하고 있다는 것이다.
물론, 자국민에게 일어난 일이기에 더 신중하고 정확하게, 그리고 책임감있게 전달하는것은 당연한 것이지만
과연 한국에서 똑같은 일이 일어났다면 한국의 언론은 이렇게 할 수 있을까라는 의문이 강하게 남는다.
미디어가 다 그렇지만, 공중파 TV 에서는 더욱 책임감있고 실질적으로 도움이 되는 정보전달을 해야하는 "의무"가 있다.
이미 TV에 송수신되는 전파자체가 공공재이기 때문이다. 공공재는 모두가 이용하는 자원이 아닌가.
그만큼 더 신중하고 책임감있게 정보를 전달 해 주었으면하는 바람은 사치인것일까.
더욱이, 이런 재난이나 긴급상황에서는 언론인들의 책임과 역량이 더욱 절실해지기 마련이지만,
한국언론은 스포츠신문의 한낯 가십거리 기사같은 느낌으로 정보를 전달하는 느낌이다.
과연 한국의 언론인들은 자신들이 전달하는 정보에 의해서 어떤 결과가 초래될 것인가를 신경이나 쓰고 있는것인가?
그저 눈길이나 끌어서 광고수입이나 올리고싶은것이가?
나는 한국을 참 사랑하지만,
국민들을 좀 더 생각할 줄 아는 참 언론이 되어주었으면 좋겠다.
인터넷, TV, 라디오 등을 포함한 일본의 언론에 대한 나의 느낌은 "신중"이다. 한국과는 또 다른느낌이다.
한국의 인터넷뉴스를 보고있자면, 도대체 기자라는 사람이 이럴수가있나 싶을 정도다.
한국의 공중파 TV 에서조차도 '경고&주의'를 가장한 '겁주기'식의 보도를 하고있는것 같다.
일본관동대지진에대한 한국의 뉴스제목은 그야말로 경악 그 자체다. 과연 이런 문구는 누가 작성하는것일까..
이번 대참사를 다루는 일본 미디어에서 느낀점은 " 미디어를 통해 실제로 도움이 되는 정보전달 " 을 신중하게 전달하고 있다는 것이다.
물론, 자국민에게 일어난 일이기에 더 신중하고 정확하게, 그리고 책임감있게 전달하는것은 당연한 것이지만
과연 한국에서 똑같은 일이 일어났다면 한국의 언론은 이렇게 할 수 있을까라는 의문이 강하게 남는다.
미디어가 다 그렇지만, 공중파 TV 에서는 더욱 책임감있고 실질적으로 도움이 되는 정보전달을 해야하는 "의무"가 있다.
이미 TV에 송수신되는 전파자체가 공공재이기 때문이다. 공공재는 모두가 이용하는 자원이 아닌가.
그만큼 더 신중하고 책임감있게 정보를 전달 해 주었으면하는 바람은 사치인것일까.
더욱이, 이런 재난이나 긴급상황에서는 언론인들의 책임과 역량이 더욱 절실해지기 마련이지만,
한국언론은 스포츠신문의 한낯 가십거리 기사같은 느낌으로 정보를 전달하는 느낌이다.
과연 한국의 언론인들은 자신들이 전달하는 정보에 의해서 어떤 결과가 초래될 것인가를 신경이나 쓰고 있는것인가?
그저 눈길이나 끌어서 광고수입이나 올리고싶은것이가?
나는 한국을 참 사랑하지만,
국민들을 좀 더 생각할 줄 아는 참 언론이 되어주었으면 좋겠다.
'생각들' 카테고리의 다른 글
| 익숙한 것으로부터의 탈피 (0) | 2011.10.14 |
|---|---|
| 어떻게 살아야하는걸까.. (0) | 2011.04.16 |
