분류 전체보기 66

유전 프로그래밍에서 트리간의 유사도 측정방식에 대한 고찰

유사 - [명사]{주로 일부 명사 앞에 쓰여} 서로 비슷함. 그렇습니다. 유사하다는 말을 서로 비슷하다는 말입니다. 비슷하다? 그럼 비슷하다는 말은? 비슷하다 [형용사] ━ ⅰ『(…과)』 {‘…과’가 나타나지 않을 때는 여럿임을 뜻하는 말이 주어로 온다} 두 개의 대상이 크기, 모양, 상태, 성질 따위가 똑같지는 아니하지만 전체적 또는 부분적으로 일치하는 점이 많은 상태에 있다. {명사의 단독형 뒤에 쓰여} 1 정체가 확인되지 아니한 어떤 대상에 대하여 누구 또는 무엇이라고 짐작되는 상태에 있다. 2 비교가 되는 대상과 어느 정도 일치되지만 다소 미흡한 면이 있다. 네 그렇습니다. 크기, 모양, 상태, 성질 따위가 똑같지는 않지만, 전체적 또는 부분 적으로 일치하는 점이 많은 상태에 있다 라고 하고 있습..

기타. 알고리즘과 적용에 대한 작은 생각들(주로 유전프로그래밍)

본 글은 어떤 일반론적인 생각도 아니고 어디까지나 제 자신의 개인적인 생각들 임을 사전에 밝히도록 하겠습니다. 짧은 지식을 통해 나오는 생각들이기에 편협할 수도 있고, 좁은 식견이 확 보일수도 있고 정리가 안된 그냥 머리속 튀어나오는 대로 쓰는거지만... 그냥 한번 써보렵니다. 사족이므로 반말나갑니다. - 다른 녀석들을 봤을 때 유전프로그래밍이라는 것의 가능성... - 우선 신경회로망 이라는 녀석. 많이 알고 있는 녀석은 아니지만 태어난지 매우 오래되었음에도 불구하고, 과거의 알고리즘에 비해 심대한 변화는 없는 녀석이다. 다층 퍼셉트론 이후에 오류역전파 알고리즘, 그것들을 제외하고는 어째 크게 발전은 없는 모양이다. 사실 내가 크게 관심이 없어서 그럴수도 있지만, 여러 논문을 검색해 보았을때 다 고만고만..

기타. 이번퍼지 학회에서 제가 발표한 퍼지추론기반의 유전알고리즘 선택 연산자 입니다.

대단한건 아니지만;; 어쨌든, (1) 조기수렴 문제? 조기수렴 문제의 해결에 대해서 연구를 좀 했습니다. 그러던 중에 나온 많은 알고리즘들, 적합도 공유방식(Fitness Sharing), 군중 분산 방식(?, 말이 좀 이상합니다만, 본래는 Crowding 방식입니다. 제 생각에 저 표현이 의미와 잘 부합되는것 같습니다.), 다중군집을 기반으로한 새로운 모델들(Multi-pop 을 기반으로한 HFC(Hierarchical Fair Competition) 혹은 ALPS(Age-Layered Population Structure)) 이 있습니다. 우선 적합도 공유방식은 적합도가 높은 개체들이 적합도가 낮은 개체들에게 자신의 적합도를 나눠준다고 생각하면 간단합니다. 즉, 비슷한 수준의 적합도를 이용해서 다른 ..

기타 5. Steady-state 와 Generational 방식

오랜만에 Genetic Algorithm 에 대한 포스팅을 하는군요. 크게 언급할 부분은 아니지만, 이부분에 대해 연구하시는 대다수의 분들이 매번 느끼시는 부분이리라고 사료됩니다. Generational 과 Steady-state 의 차이점에 대한 부분입니다. 일반적 유전연산, 즉, Evolutionary Computation 에서, 그것도 유독 GP 와 GA 에서는 Generational 이라 불리는 방식과 Steady-state 라고 불리는 두가지 방식이 있습니다. 이 두 방식의 차이점은 아직 학회에서 확실하게 정의하지는 않았습니다. 반드시 이래야 한다, 라든지 이것이 표준이다 라는 레퍼런스가 없는 것입니다. 하지만 확실한 차이점은 존재합니다. 그 차이점이라는 것은 다음같은 점이지요. Generati..

기타4. 조기수렴 문제의 극복 (3) Island Parallelism(MPOP-Injection)

이번에는 지난번에 언급했던 Island Parallelism 의 방식중에서 Injection 방식에 대해서 언급해보겠습니다. Injection 방식이란 말그대로 주입식 방식이라고 표현하면 간단하겠습니다. GP 나 GA 에서 사용되는 Multi-POP 을 응용해서 만들어진 여러 알고리즘은 크게보면 POP 을 전체적으로 분산, 격리 시켜서 그 상태를 운용하는 방식을 벗어나지 않습니다. 즉, 거의 모든 방식이 Multi-POP 을 이용하게 되는 기본 이론인 Island Parallelism 을 벗어나지 않는 선에서 만들어집니다. Injection 방식이라는 것 또한 마찬가지 입니다. 지난번에 Migration 에 의해 몇몇 방식으로 나뉘어 진다고 말씀 드렸는데, Injection 방식 또한 Migration ..

기타3. 조기수렴 문제의 극복 (2) Island Parallelism(Multi-Population)

지난번에 Island Parallelism(이하 Multi-POP) 에 대해서 간략한 언급을 했습니다. 이번에는 세부적으로 Multi-POP 이 동작하는 방식과 조기수렴을 막는 것을 살펴보겠습니다. Multi-POP 자체는 여러개의 POP 을 사용하는 것 외에는 큰 의미를 가지지 않습니다. 하지만 Multi-POP 을 이용할 때 사용할 수 있는 여러가지 기법들에 의해 그 효용성 이 나타납니다. 그러한 기법들 중 Migration 방식에 의해 여러가지 효용성이 나타날 수 있습니다. 여기서 Migration 이라는 것은 개체들이 이주하는 규칙입니다. 오늘은 이 이주 규칙(Migration Rules) 중 가장 대표적으로 쓰이는 2가지 방식에 대해 이야기해 보겠습니다. 1. 기본적인 Multi-POP(이주 계..

기타2. 조기수렴 문제의 극복 (1) Island Parallelism 에 대한 간략소개

가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 Island Parallelism 이론 입니다. 한글로 직역하자면 섬 병행진화론 정도가 되겠는데요. 그리고 Multi-Population 방식이라고도 합니다. GA 자체의 출발점이 유전학적인 요소가 강하다보니 유전학적인 측면에서 발전된 이론입니다. 단순히 설명하자면, 각각의 군집(Population) 이 서로 다른 섬에 떨어져 있다고 가정하는 것이죠. 각각의 섬에서 따로 발전, 진화를 거듭하게되면 그 섬에 특성에 맞는 군집으로 발전되어 나간다는 이론입니다. 다윈의 진화론의 출발점이라고 할 수 있는 갈라파고스 제도와 같은 요소를 도입한 해결방식입니다. 조금 더 자세히 기존 방식과 비교해보면 다음과 같이 될 수 있습니다. 1. 기존방식(Single-P..

Webots 에서 VS 6.0 을 이용한 Controller 프로그래밍 셋팅 방법

Webots 을 이용해 보신 분들이라면 아시겠지만 Webots 내부에서 제공되는 에디터를 이용해 프로그램을 작성하는게 여간 불편한게 아닙니다. 메뉴얼에 이미 있는 내용이지만, 한번 다시 정리해 보겠습니다. 순서대로만 따라서 하면 아주 쉽게 이용하실 수 있습니다. 1. 새로운 Project 생성 위의 그림에서 보이듯이 New 를 눌러서 새로운 Project 를 생성해 줍니다. 2. Project 생성(세부) Win32 Console Application 을 선택해 주신 후, Project name 에 이용하실 Controller의 이름을 넣어줍니다. 3. Project Settings 그리고 Project 가 생성된 후 Project -> Settings 메뉴를 통해 설정을 해 줍니다. 저 메뉴를 누르게되..

기타 1. 조기수렴 문제와 Global Search, Local Search 문제

초기의 진화연산(Evolutionary Computation, 이하 EC) 에서 더 최적 값을 찾기 위해 논의 되었던 최적해에 관련된 두가지 논제가 있습니다. 그것은 바로 조기수렴 문제와 Local Search 문제 입니다. 오늘은 조기수렴 문제와 Local Search 문제가 왜 논의 되었는지 알아보겠습니다. GA를 이용한 최적화 문제에서는 보통 Crossover Rate = 0.9, Mutation Rate = 0.1 을 사용합니다. 이는 보다 빠르게 최적값을 찾기 위해 사용하게 됩니다. 하지만 이 문제에서 큰 단점이 있으니, 그것이 바로 조기 수렴의 문제 입니다. 최적값이 저 멀리에 있어도, 그 값에 도달하지 못하고 적당한 중간값을 최적값으로 인식하고 그 값 근처에 머무르게 되는 것입니다. 실제 최..

10. 실수최적화 문제에서 이용되는 CX 연산자 (2)

오늘은 실수최적화 문제에서 이용되는 CX 연산자중 지난번에 다루었던 Arithmetical Crossover[Michalewicz 1996] 의 변형판에 대해서 다루겠습니다. 기존 Arithmetical Crossover 의 특징에 대해 간략하게 알아보면 1. 적용이 쉽다. 매우 단순한 알고리즘으로 구성되어 있기 때문에 적용이 쉽습니다. 물론 random 으로 lambda 값을 산출해 내는 과정에 어떤 알고리즘을 적용시키느냐가 관건이 되지만( 사실 시간에 의한 난수값이 출력되는 것은 신뢰도나 정확도면에서 그다지 높지 않기때문에 다른 알고리즘에서는 잘 쓰이지 않는 경향이 있습니다. ) 그 부분에 대해서만 제외한다면, 서로의 Chrom 값에 lambda 값의 곱과 1- lambda 값의 곱만으로 새로운 In..