12강. 진화학습
추천글 : 【알고리즘】 알고리즘 목차
1. 진화학습 [본문]
2. 단계 1. 스트링 표현 [본문]
3. 단계 2. 적합성 평가 [본문]
4. 단계 3. 자손 만들기 [본문]
5. 단절된 균형 [본문]
1. 진화학습 [목차]
진화란, 환경에 더 적합한 개체가 더 많은 자손을 낳고 생태계에 우점종이 되어간다는 이론이다. 더 자세한 사항을 알고 싶다면 다음 서적을 참고하도록 하자. 찰스 다윈의 《종의 기원 (Charles Darwin's The Origin of Species)》리처드 도킨스의 《눈먼 시계공 (The Blind Watchmaker)》유전 알고리즘 (GA, Genetic Algorithm)은 진화를 일으키는 유전 과정을 모델링한다.유전 알고리즘은 매우 효율적이지만 많은 중요한 파라미터를 설정하기 힘들고, 좋은 결과를 보장할 수 없다.일반적으로 잘 동작하고 특별한 해법을 찾을 수 없을 때 매우 인기 있는 알고리즘이다.유전자 프로그래밍이라는 개념도 있다.이는 유전 알고리즘을 트리 형태로 표현할 수 있도록 확장해서 컴퓨터 프로그램을 표현할 수 있도록 한다.즉, 진화의 개념으로 프로그램이 알아서 생성되는 것이다!
2. 단계 1. 스트링 표현 [목차]
유전 알고리즘을 적용할 때는 우선 각각의 경우의 수를 염색체로 표현해야 한다.일반적으로 실수로 이루어진 스트링으로 표현한다.예를 들면 가방에 집어넣을 L 개의 물건들을 표현하기 위해 L의 길이의 스트링에서, 각각은 2진수의 값을 설정한다.선택하지 않은 물건은 0의 값으로 코드화하고, 선택할 물건들은 1의 값으로 표현한다.어떤 임의의 스트링이 가능한 해법인지를 알기 위해서는 스트링의 적합성 평가를 해야 한다.
3. 단계 2. 적합성 평가 [목차]
가방 문제에서 가방의 부피가 제한돼 있으므로 이 경우 가방에 집어넣을 물건들의 부피가 적합한지 비교해야 한다.가방의 부피보다 작지만 가장 가깝게 물건을 집어넣는 경우가 가장 적합할 것이다.만약 가방의 부피보다 더 많은 물건이 들어가 있다면 적합성을 0으로 설정할 수도 있을 것이다.하지만 해답이 거의 완벽하다면 배낭의 크기보다 하나의 물건이 더 많은 경우일 것이다.이 경우에 적합성을 0으로 설정하면 다음 반복에서 이를 수정하여 더 좋은 해를 찾을 기회를 잃게 된다.따라서 배낭의 크기를 넘친 만큼의 두 배를 가방의 크기에서 제외하여 적합 함수를 정의하는 게 좋다.이를 통해서 약간 넘치는 경우에는 더 좋은 해법을 찾을 가능성을 제공해 주며, 이와 함께 가장 적합한 해법이 아니라는 것을 확실히 제공한다.
4. 단계 3. 자손 만들기 : 유전 연산자 [목차]
자손 만들기에는 교차 (Cross-over), 돌연변이 (Mutation), 자연선택 (Natural Selection) 알고리즘이 관여한다.이때 자연선택 알고리즘은 정예주의 (Elitism), 토너먼트 (Tournament) 등이 있다.정예주의는 한 세대에서 적합한 스트링들을 찾아서 가장 좋지 않은 적합도를 보이는 것을 선택해서 대체한다.토너먼트는 두 부모와 그들의 두 자손이 경쟁하고, 넷 중 가장 적합도가 높은 자들을 새로운 개체로 사용하는 것이다.그런데 두 가지 모두 조기 수렴 (Premature Convergence)을 만들어서 최적화 값을 절대로 찾지 못하도록 만든다.이를 해결하는 해법은 틈새 (Niching)을 이용하여 개체들을 몇 개의 분리된 조직으로 나누고, 정해진 기간 동안 독립적으로 진화를 수행하고, 각기 다른 지역 최댓값으로 수렴하게 하면서 각 개체로부터 때때로 다른 집합의 개체들로 전달한다.이러한 논리는 동성동본의 결혼 금지와 닮아 있다.또 다른 방법은 적합 공유 (Fitness Sharing)으로 특정 스트링의 적합도를 개체에 특정 스트링이 나타난 횟수만큼의 평균 값으로 정의하는 방법이다.이는 적합도 함수가 덜 일반적인 스트링들로 편향되도록 해서 매우 일반적인 좋은 해법들이 선택되도록 한다.
5. 단절된 균형 : 단속평형설(스티븐 제이 굴드가 주창)의 증거 [목차]
오랫동안 진화를 믿지 않는 창조론자들은 진화상의 중간 단계의 화석이 부족하다는 논리를 펼쳐 왔다.파충류로부터 시조새가 진화되었다면, 파충류와 시조새 중간의 화석은 어째서 없느냐 하는 논리이다.흥미롭게도 유전 알고리즘은 적합도 - 세대 그래프에서 단절된 균형 (Punctuated Equilibrium)을 보여준다.오랜 기간 몇몇 종은 꾸준하게 비슷한 개체수를 유지하는데 이는 아주 단기간에 변화가 생긴다.이 큰 변화가 지나면 한동안 모든 것들이 다시 안정된다.따라서 짧은 시기의 중간 단계에 속하는 화석을 찾을 가능성은 매우 작다.
입력 : 2018. 06. 09 18:30
수정 : 2018. 06. 12 19:33
'▶ 자연과학 > ▷ 알고리즘·머신러닝' 카테고리의 다른 글
| 【알고리즘】 7-1강. SNE, symmetric-SNE, tSNE (2) | 2019.10.05 |
|---|---|
| 【알고리즘】 알고리즘·머신러닝 목차 (0) | 2018.11.05 |
| 【알고리즘】 25강. 수치해석 알고리즘 (0) | 2016.12.11 |
| 【컴퓨터과학】 Dll Explicit Linking (0) | 2016.08.04 |
| 【알고리즘】 26강. RSA 알고리즘 (0) | 2016.06.23 |
최근댓글