GP 의 해가 가지는 특성을 파악하기 위해 실험을 통해 대규모의 데이터를 수집하였다고 가정하자. 그리고 대부분의 해에서 나타나는 어떠한 특성이 발견 되었다면, 과연 여기서 대부분의 해는 반드시 그 어떤 특성을 갖게 되는 것일까?

GA, GP 의 조기수렴이 해의 다양성에 악영향을 끼치고, 좋은 결과로 수렴하는 것을 방해한다고 했을 때, 조기수렴을 막으면 반드시 해가 다양성을 폭넓게 가지면서, 좋은 결과로 수렴할 것인가?

어떠한 명제를 가정했을 때, 그 역이 반드시 참일것이라는 보장 같은 것은 없다. 결국 우리가 일반적으로 데이터를 수집하여 하는 일은 대부분이 그러한 특성을 보인다는 것에서 끝나는 것인데, 이것의 역을 증명해낼 좋은 방법은 없을것인가?

몇년째 계속 고민해보지만, GA, GP 쪽에서는 이를 어떤 수로 증명할 것인지 딱히 머리속에 떠오르는 것이 없다. 실험을 통해 명제 자체가 참임을 증명해낼 수는 있지만, 그 명제를 토대로 알고리즘을 구성하고 타당성을 갖기 위해서는 반드시 그 명제의 역이 참임을 증명해야 하는데 아직까지는 부족한게 많은지 딱히 좋은 방법이 떠오르지 않는다.

하지만 이 부분이 해결되지 않는 한, 결국 어떠한 알고리즘을 만든다 하더라도 이것이 타당성을 갖기는 어려울 것이 분명하기 때문에 앞으로도 계속 고민할 것 같다. 뭔가 좋은 방법은 없는 것일까?

Posted by SHHyun

댓글을 달아 주세요

1. 개요

병렬처리 시스템은 최근에 가장 주목 받고 있는 컴퓨팅 성능 향상 기술 중에 하나입니다. 물론 과거에도 병렬처리 시스템이 주목 받아 왔지만, 그 당시에는 CPU 의 업그레이드 만으로도 50%, 100% 이상의 성능향상을 이룰 수 있었기에 지금보다는 적은 관심을 보였었습니다. 그러나 현재의 CPU 가 가진 한계에 거의 다다름에 따라, 성능 개선의 기법으로 병렬처리 기법들이 주목을 받고 있습니다. 즉, 하드웨어적 한계를 소프트웨어 적인 기법으로서 넘어서려고 한다고 표현할 수 있겠습니다.

이 병럴처리 시스템은 크게 내부, 외부의 두 가지 요소로서 존재한다고 볼 수 있겠습니다. 내부 요소로서는 CPU 의 멀티 코어화, GPU 의 발전 등을 들 수 있겠고, 외부적으로는 대규모 네트워크로 구성된 컴퓨팅 환경을 제공하는 것이 되겠습니다. 대표적으로는 근래에 각광을 받고 있는 클라우드 컴퓨팅이 있겠습니다.

진화연산은 기존의 알고리즘 들에 비해 엄청난 반복작업이 필요하며, 거대한 리소스를 갖출수록 더 좋은 효과를 가질 수 있는 특징이 있습니다. 이 거대한 리소스에 대한 것은 반박의 여지가 충분히 존재하며, 각 문제에 따른 특화된 알고리즘의 적용으로 이를 개선할 수 있습니다만, 그렇다고 해도 아주 오랜시간에 걸쳐 반복작업이 이루어져야 그에 따른 최적값을 기대해 볼 수 있다는 것은 부정할 수 없는 사실입니다.


2. 진화 연산에 적용된 병렬처리기법
2.1 다수의 CPU 사용

초창기 유전프로그래밍(이하 GP)의 창시자라고 언급되는 John. R. Koza 의 경우에는 천 대의 컴퓨터를 하나의 클러스터로 활용해 GP를 수행하였으며, 이를 통해 과거에 발표되었던 특허들을 그대로 GP의 결과물로서 만들어내는 결과를 보여주었습니다.[1] (첫 페이지의 팔짱을 끼고 있는 그의 모습 뒤로 펼쳐진 것들이 수많은 컴퓨터의 클러스터입니다.)

그러나 일반적인 연구자들이 이러한 리소스를 활용할만한 능력을 갖추기는 어려웠기 때문에 사실상 대규모 클러스터링을 활용한 연구는 Koza 의 이후로 거의 나타나지 않고 있었습니다. 소수의 연구자들에 의해 소규모의 분산 처리 시스템[2]이나 여러 개의 CPU 를 사용한 연구[3]는 이루어지고 있었습니다. ([3] 논문은 가상의 병렬 처리 머신을 통해 데이터를 주고받는 것에 대한 논문입니다만, 저 논문의 결과물로서 lil-gp 의 병렬화된 형태를 언급하는 데 이것은 다중의 CPU 를 사용하는 병렬 처리 기법이 사용되어 있습니다.)


2.2 GPU

시간이 흐른 뒤, nVidia 에서 GPU 가 나오게 되었습니다. 이것은 벡터 연산에 특화되어 있고, CPU 에 비해 압도적인 처리성능을 보여주기에 수 많은 알고리즘이 이를 해당 알고리즘에 적용시키기 시작하였습니다. 물론 진화연산에서도 절대 예외일 수는 없었습니다.

대표적인 논문으로 몇가지를 언급하자면, 우선은 진화 연산을 타겟으로 삼은 것은 아니지만, GPGPU(General-Purpose computation on Graphics Processing Units) 의 개념을 활용해 알고리즘에 적용하는 것이 좋겠다고 제안한 논문이 있습니다. [4] 그리고 실제 GPU 를 사용해서 GP를 수행하고, 이에대한 성능 비교를 수행한 논문이 발표되게 되었습니다. [5,6,7]

일반적으로 생각하기에 GPU 를 통해 병렬적으로 개체의 해석을 수행하게 되면 CPU 만을 사용하는 현 GP 에 비해서 엄청난 속도 향상을 기대 하지만, 실제로는 모든 문제에 대해서 그렇지는 않았다는 내용이 [6] 논문에서 나타나고 있습니다. 그러나 위의 논문에서 사용된 컴퓨터의 사양은 T2400 (1.83 Ghz), 1.5GB ram, GeForce 7300 GO with 512 RAM 으로서, 노트북 컴퓨터라고 보시면 됩니다. 즉, 일반적으로 사용하는 GPU 에 비해서는 그다지 좋은 성능을 보여주는 것은 아니었던 것입니다.

그리고 [7] 논문에서는 GPU 에 최적화된 GP 연산 기법을 소개하고, SIMD 처리 형태에 알맞은 데이터 처리 방식을 사용하여 더 좋은 효율을 보여준다는 것을 나타내고 있습니다. 또한, 이 논문에서 더 주목해 볼 수 있는 것은 Geforce 8800 GTX 라는 고사양의 GPU를 사용했다는 것과 이를 통해 CPU 의 오버헤드가 0.1%에 근접한다는 내용, 그리고 기존에 해결하는데 매우 오랜 시간이 걸렸던 거대한 형태의 Regression 문제를 해결했다는 것에 있습니다. 1024 x 1024 x 1000 의 크기의 문제를 200번 수행하는데 6시간 46분 17초가 걸렸다는 건, 기존에 우리가 처리할 엄두도 못 내던 거대한 크기의 문제들을 GPU 를 사용하여 처리한다면 더 큰 효율과 빠른 결과를 얻을 수 있다는 것을 의미합니다.

[8] 논문에 이르러서는 Xbox360 이라는 이 종의 하드웨어를 통해 GP를 수행하게 됩니다. 컴퓨터의 GPU 를 통한 결과와 Xbox 360 의 GPU 를 통한 결과를 서로 비교하는 내용이 있는데, 특이할 만한 점은 C# 과 XNA Framework 를 통해 구현된 동일한 프로그램(GP)을 Xbox360 과 PC 에서 변환 없이 수행할 수 있었다는 것, 그리고 결국 성능은 PC 가 더 좋았다는 것이 되겠습니다.


2.3 기타 웹이나 네트워크 기반의 진화연산 기법

이렇듯 GPU 의 등장과 함께 진화 알고리즘은 매우 빠른 병렬처리 알고리즘을 통한 복잡한 문제의 해결, 그리고 GPU 에 걸맞는 형태의 알고리즘의 변화 등이 이루어져 왔습니다. 그러나 사실 GPU 를 통한 GP 의 발전은 아직은 한계가 있습니다. 가장 큰 한계점이라면 단순 Regression 문제나 디지털 논리회로를 벗어나는 문제에 대해서는 아직 그 위에서 해석할 방법이 없다는 것 입니다. 즉, 단순한 문제지만 거대한 데이터 셋을 갖는 문제에 대해서는 그 효율을 극대화 하여 이용할 수 있지만, 복잡한 시뮬레이션의 경우에는 아직 GPU 에서 그것을 수행하기에는 많은 무리가 따르게 됩니다.

GPU 의 진화 연산보다는 살짝 앞선 시기에 웹을 통한 진화 연산의 수행기법들에 대한 연구가 이루어 졌습니다. [9] 논문의 경우에는 웹을 통해 사람이 어떠한 평가를 내리고, 이를 서버에서 모아서 진화연산을 수행하는 형태에 대한 연구기법에 대해 논하고 있습니다. 이는 기계로 평가를 내리기 어려운 적합도 함수, 즉 좋은 음악이나 색의 조합 등 인간의 주관이 개입되어야 하는 문제에 대해서도 진화연산의 수행이 가능하다는 것을 보여준 사례가 되겠습니다.

2007년에 발표된 [10] 논문의 경우에는 XML 과 Ajax 를 통해 웹브라우저로 데이터를 서로 주고받고, 적합도 함수를 평가하며 해결하는 시스템을 구축하였습니다. 이 논문에서 아쉬운 점은 비교할만한 대상이 없었기 때문에, 해당 기법이 기존의 기법에 비해 어느 정도 효율성을 갖는지가 나타나지 않았고, 매우 빠른 연산을 보여주었다는 시간만을 언급하고 있다는 것이었습니다.

그리고 ECJ Framework[11] 에서는 TCP/IP 상의 Asynchronous Island Model 을 지원함에 따라 기존의 진화 연산 문제를 대규모 네트워크를 통한 처리 형태를 쉽게 사용해 볼 수 있습니다. 이미 모든 구현이 이루어져 있기 때문에 약간의 파라미터 수정만 거치면 바로 네트워크를 통한 진화연산 기법의 연구가 가능하다는 장점이 있습니다. 관심 있으신 분은 한번쯤 해보시면 좋을 것 같습니다.


3. 정리

이보다도 이른 시기에 네트워크를 통한 데이터 교환을 통해 진화 연산의 병렬화의 효율에 대해 논하는 것들이 많이 있었지만, 사실상 GPU 와 같이 핵심 테마로서 자리를 잡을 만큼의 파급력을 갖출 수 없었습니다. 이는 어쩌면 진화 연산 자체를 병렬처리로 수행한다는 것은 하나의 연구테마로 갖추기가 어려운 것이었을 수도 있고, 기존의 방법들에 비해 획기적인 성능을 보여주는 사례가 없었기 때문일 수도 있습니다. 혹은 고도의 시뮬레이터를 통한 시뮬레이션을 필요로 하는 그런 문제가 정의되지 않았기 때문일 수도 있습니다.

진화연산에서는 알고리즘 자체가 적은 수행 횟수를 통해 더 개선된 성능을 보여주는 것은 여전히 중요한 테마입니다. 단위 시간에 대해 더 효율적인 공간의 탐색을 할 수 있다면, 성능 개선을 위한 가장 훌륭한 접근이 될 수 있겠습니다. 거기에 같은 단위 시간에 대해 두 배 아니 열 배 이상의 수행이 가능하다면 더 좋은 성능을 보여주기 위한 가장 좋은 해결책이 아닐까 생각이 듭니다. 물론 이렇게 말하게 되면, 병렬처리 자체는 기존의 알고리즘의 개선을 위한 접근 방법들에 비해서는 중요도가 떨어져 보이는 것이 사실입니다. 그러나 이전에는 접근해 볼 수 없었던 100만개~1억개 이상의 개체의 진화나 이로 인해 나타나는 현상들은 기존의 알고리즘으로 접근하는 방식들과는 다를 것이라 생각되기 때문에, 진화 연산 자체의 병렬처리 시스템은 기존의 방식들과는 별도로 매우 중요한 테마가 되지 않을까 생각합니다.


4. 참고문헌

[1] John. R. Koza – http://www.genetic-programming.com/johnkoza.html

[2] F. S. Chong and W. B. Langdon. Java based distributed genetic programming on the internet. In W. Banzhaf, et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, page 1229, Orlando, Florida, USA, 13-17 July 1999. Morgan Kaufmann. ISBN 1-55860-611-4.

[3] F. Fernandez, J. M. Sanchez, M. Tomassini, and J. A. Gomez. A parallel genetic programming tool based on PVM. In J. Dongarra, et al., editors, Recent Advances in Parallel Virtual Machine and Message Passing Interface, Proceedings of the 6th European PVM/MPI Users' Group Meeting, volume 1697 of Lecture Notes in Computer Science, pages 241-248, Barcelona, Spain, September 1999. Springer-Verlag.

[4] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80-113, March 2007.

[5] D. M. Chitty. A data parallel approach to genetic programming using programmable graphics hardware. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1566-1573, London, 7-11 July 2007. ACM Press.

[6] S. Harding and W. Banzhaf. Fast genetic programming on GPUs. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 90-101, Valencia, Spain, 11 - 13 April 2007. Springer.

[7] W. B. Langdon and W. Banzhaf. A SIMD interpreter for genetic programming on GPU graphics cards. In EuroGP, LNCS, Naples, 26-28 March 2008. Springer.

[8] G. Wilson, W. Banzhaf, Linear Genetic Programming GPGPU on Microsoft’s Xbox 360, in Proceedings of 2008 IEEE World Congress on Computational Intelligence, Hong Kong, 2008.

[9] W. B. Langdon. Pfeiffer - A distributed open-ended evolutionary system. In B. Edmonds, et al., editors, AISB'05: Proceedings of the Joint Symposium on Socially Inspired Computing (METAS 2005), pages 7-13, University of Hertfordshire, Hatfield, UK, 12-15 April 2005a.

[10] J. Klein and L. Spector. Unwitting distributed genetic programming via asynchronous javascript and XML. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1628-1635, London, 7-11 July 2007.

[11] ECJ - http://cs.gmu.edu/~eclab/projects/ecj/

Posted by SHHyun

댓글을 달아 주세요

대단한건 아니지만;;

어쨌든,

(1) 조기수렴 문제?

조기수렴 문제의 해결에 대해서 연구를 좀 했습니다.
그러던 중에 나온 많은 알고리즘들,
적합도 공유방식(Fitness Sharing),
군중 분산 방식(?, 말이 좀 이상합니다만, 본래는 Crowding 방식입니다. 제 생각에 저 표현이 의미와 잘 부합되는것 같습니다.),
다중군집을 기반으로한 새로운 모델들(Multi-pop 을 기반으로한 HFC(Hierarchical Fair Competition) 혹은 ALPS(Age-Layered Population Structure))
이 있습니다.

우선 적합도 공유방식은 적합도가 높은 개체들이 적합도가 낮은 개체들에게 자신의 적합도를 나눠준다고 생각하면 간단합니다. 즉, 비슷한 수준의 적합도를 이용해서 다른 적합도 낮은 개체들도 선택될 확률을 높혀주는 것 입니다.

군중분산방식은 매 세대의 끝에 유저가 선택해준 갯수만큼의 개체를 주위의 개체들에 비해 개체의 본래 타입이 틀린 개체들로 강제적으로 대체시켜주는 방식입니다. 많은 다양성의 확보를 통해 본래의 수렴속도를 늦추는 것이 초점입니다.

다중 군집 기반으로한 모델들은 여러개의 군집으로 나눌때, HFC 같은 경우는 적합도를 기반으로하여 나누게 됩니다. 적합도가 높은 개체는 상위 군집, 낮은 개체를 하위 군집 등으로 분류를 하고 격리시킨후에 교배연산을 수행합니다. 기본 생각은 초등학생은 초등학생끼리, 대학생을 대학생끼리 경쟁을 시켜야 좋은 결과가 나오지 않겠냐 라는 것입니다. ALPS 는 개체들의 나이를 이용해 격리시켜서 교배연산을 수행 합니다. 마찬가지로 비슷한 연령대의 경쟁이 가장 효율적이지 않은가 라는 것에서 시작되었다고 보면 됩니다.

(2) HFC 모델의 단점

위와 같이 조기수렴 문제를 해결하기 위한 많은 방법들이 있습니다. 하지만 위의 방법들은 단점을 가지고 있습니다. HFC 의 다층 군집화 를 하나의 군집으로 만든 CHFC(Continuous HFC) 모델이 있습니다. 이 모델은 다층이 아닌 단일군집에서 HFC의 격리 수용모델을 구현 한 모델입니다. 성능이 기본적 알고리즘 보단 좋았지만, 다른 HFC모델에 비해서 뛰어난 성능을 보여주지는 못했습니다. 저는 그중에서도 위의 CHFC 모델을 타겟으로 잡고 개선을 시도했습니다. 그래서 우선 단점에 대해서 생각해 보았습니다.

첫번째 단점으로는 적합도만을 가지고 군집화를 이룬다는 것이라고 생각했습니다. 왜냐하면 만약에 적합도, 즉 해석된 상태의 결과물이 나쁜 결과를 갖고 있다고 해도 잠재적인 성능향상의 요소를 가지고 있을지도 모르는 것 입니다. 단일 군집에서는 완전 격리효과가 떨어지기 때문에 위의 잠재적 성능향상 요소를 잃게 될 확률이 높다고 생각했습니다.

둘째로는 일반적 세대형 알고리즘(Generational)에 있다고 생각했습니다. 일반적인 세대형 알고리즘이란 한 세대에서 다음 세대로 세대를 넘어갈때에 군집 전체가 바뀌는 것을 의미합니다. 이는 점진적 알고리즘(Steady-State) 에 비해서 수렴속도가 매우 빨라지는 것을 확인할 수 있습니다. 하나의 군집을 이용하는 CHFC의 경우에는 이것이 더 가속화 될 것이라고 판단 했습니다.

세번째로는 매우 큰 군집(여기서 군집이란 총 개체수를 의미합니다)을 가지고 있어야 한다는 것 입니다. 개체의 수가 적을 경우에는 상대적으로 다음 세대로 넘어갈때에 수렴이 급격히 일어나기 때문에, 일정수 이상(약 500~1000개 이상)의 개체를 확보하지 못할 경우에는 HFC나 CHFC 알고리즘의 지연효과가 거의 나타나지 않을 수가 있습니다.

(3) 퍼지추론 기반의 유전알고리즘 선택 연산자

그래서 퍼지추론을 이용해서 잠재적 성능향상이 있을수 있는 개체들을 골라내서 그들간의 경쟁을 유도해 보자는 게 제 의견입니다. 퍼지 추론은 여기서 데이터의 분류 방법이 됩니다. 즉, 기존의 HFC나 CHFC 등이 유도하는 군집화를 퍼지추론의 모호성을 통해 간접적으로 유도해 낼 수 있으며, 잠재적 성능향상이 가능할 법한 개체들에 대해 경쟁을 유도하기 때문에 기존의 알고리즘 보다 나은 성능을 보여 줄 것이라고 판단 했습니다.
하지만 퍼지 추론을 통해 나타난 결과로서 무조건적인 경쟁을 시킬 경우에는 마찬가지로 급격한 수렴을 보일수 있다고 생각했습니다. 그래서 임의의 개체풀 N 에서 몇개만 추려내서 경쟁시키는 방식을 이용 했습니다.

(4) 퍼지모델

  간단한 간략추론 방식을 이용했습니다. 전반부 변수 2개는 적합도와 유사도, 후반부 변수 1개는 계층 으로 이용했으며, 멤버쉽 함수로는 가우시안 함수를 이용했습니다.

(5) 성능 및 결과

  첨부해놓은 발표자료를 첨부해 보시면 됩니다. 전체적으로 이번에 제시한 연산자가 좋은 성능을 발휘한 것을 확인하실 수 있고, 다른 알고리즘 들에 비해서 더 높은 강인성을 가지고 있는 것을 확인하실 수 있습니다.

(6) 결론

  이번 발표때 말씀드린 연산자는 퍼지추론 기반의 유전알고리즘 선택 연산자 입니다. 정확히 의도하고자 하는 것은 기존에 이용하던 적합도 단일 기반의 선택 연산자보다 거기에 다른 요소를 추가해서 기준으로 이용하게 되면, 기존의 다중군집 알고리즘의 효과를 얻을 수 있으면서, 좋은 결과를 도출시킬수 있다고 생각한 것 입니다. 결과적으로 당장의 논문에서 제시한 Deceptive문제에 대해서는 좋은 결과를 얻었습니다만, 문제가 다르게 될 경우에는 퍼지 함수의 조정이 이루어 져야 좋은 결과를 도출 시킬 수 있다고 판단합니다. 소수의 군집으로도 어려운 난이도의 문제를 해결할 수 있고, 구현자체도 어려운 편이 아니기 때문에 임베디드 시스템이나 로봇분야와 같이 제한된 리소스에서 결과를 내야하는 분야에 적용해보면 좋은 결과가 나오리라고 생각 합니다.

퍼지선택연산자슬라이드.ppt


Posted by SHHyun

댓글을 달아 주세요

오랜만에 Genetic Algorithm 에 대한 포스팅을 하는군요.

크게 언급할 부분은 아니지만, 이부분에 대해 연구하시는 대다수의 분들이 매번 느끼시는 부분이리라고 사료됩니다.

Generational 과 Steady-state 의 차이점에 대한 부분입니다.

일반적 유전연산, 즉, Evolutionary Computation 에서, 그것도 유독 GP 와 GA 에서는 Generational 이라 불리는 방식과 Steady-state 라고 불리는 두가지 방식이 있습니다.

이 두 방식의 차이점은 아직 학회에서 확실하게 정의하지는 않았습니다.
반드시 이래야 한다, 라든지 이것이 표준이다 라는 레퍼런스가 없는 것입니다.

하지만 확실한 차이점은 존재합니다.

그 차이점이라는 것은 다음같은 점이지요.

Generational ==> 이전 세대의 모든 개체에 대해 유전연산이 수행되어야 하고, 다음 세대의 개체는 이전 세대의 모든 개체의 유전연산이 수행된 형태여야 한다. ( 여기서 유전연산이란 Reproduction 또한 포함됩니다 , Reproduction 은 개체를 그대로 보존시키는 연산을 의미합니다. )

Steady-State ==> 이전 세대에서의 몇몇의 개체에 대해서만 유전연산이 수행되어야 하고, 이전세대에서 유전연산이 이루어 졌음에도 성능개선이 없다면 그 개체는 소멸될수도 있고, 유지 될 수도 있다 ( 대다수는 소멸시킵니다 ).

라는 것입니다.
저 두가지 점이 바로 Generational 방식과 Steady-state 방식을 구분하는 차이점입니다. 뜬구름 잡는듯한 느낌이죠. 사실 그 내부의 수많은 연산 부분에 대해 정의하는 부분이 없기때문에, 어떤 연산들은 Generational 같기도, 혹은 Steady-state 같기도 합니다. 애매한 구분이죠. 그래서 가장 큰 구분점으로는 이전세대에서 다음세대로 몇개의 개체가 유지되어 갈 지에 대한 점이 될 수 있습니다. 그리고 구분을 짓는데 가장 큰 구분점들을 이용합니다.

그러므로 우리가 Evolutionary Strategies(이하 ES) 같은 경우는 Steady-State 방식이라고 할 수 있는것이지요. 몇개의 개체만 선택하고 그것에 대해서 연산을 한후에 그것들을 다음세대로 넘기게 될지, 소멸 시킬지를 결정하기 때문이죠.

SGA 같은 경우에는 Generational 방식이라고 할 수 있습니다. 모든 개체들이 유전연산에 의해 대체되기 때문이죠.

Generational 방식과 Steady-State 방식을 구분하는 것이 무슨 의미가 있냐면, 서로의 연산 방식의 차이로 인해 서로 고민해야 하는 문제가 달라지기 때문입니다.

Generational 방식은 모든 개체, 모든 세대에 걸쳐 연산이 전범위적으로 일어나기에 수렴속도가 매우 빠릅니다. 일반적인 연산에서 Generational 방식이 많이 이용 되는 것은 그만큼 빠른 수렴을 통해 최소한의 Local Optima 에 도달하는 속도가 빨라지기 때문이죠. 하지만 그것을 다시 생각해보면, 오랜 시간 최적화를 거쳐서 Global Optima 에 도달하는 확률은 적어질 수가 있습니다. 게다가 유전연산을 한번 수행할때마다 걸리는 수행속도를 생각하게 된다면, 오히려 비 효율적인 연산이 될 수도 있습니다. 그래서 수렴 속도를 늦추는 Multi-pop 이나 HFC(Hierarchical Fair Competition) - Kisung Seo, Jianjun Hu, Erik Goodman 등 , ALPS(Age-Layered Population Structures) - Gregory S. Hornby, 등의 기술들이 도입된 것이지요. 이런 기법들을 통해 Generational 방식을 개선시켜 나가게 되었습니다.

하지만 Steady-State 방식은 조금 다릅니다. Steady-State 방식은 소수의 개체에 대해 적은양의 연산이 매우 긴 세대동안에 일어나게 됩니다. 그래서 수렴속도도 일반적 Generational 보다는 느린편이고, Local Optima 에 도달할 확률보다 Global Optima 에 도달할 확률이 높습니다.(짧게짧게 여러 경우의수를 가지고 개선여부를 테스트하기 때문입니다.) 하지만, 다시 생각해보면 Global Optima 에 도달하는 시간이 그만큼 길어진다는 것은 Local Optima 에 조차 빨리 도달하기 어렵다는 말이며, 그만큼 연산의 수행시간이 길어질 수 있다는 것입니다. 양날의 칼인 셈이지요. 그래서 이를 개선하기 위한 기술들로 한번에 확실한 해를 찾아 이동하는 기술들이 많이 제안이 되어 있습니다. UNDX(Unimodal normal distribution crossover), PCX(a generic parent-centric recombination operator) - Kalyanmoy Deb 등, CMA-ES(Covariance Matrix Adaptation ES) - Hansen 등의 기술들이 소개되어 있습니다. Steady-State 자체의 깊고 세밀한 탐색 덕분에 Steady-State 방식은 최근에 각광을 받고 있는 방식이고, 특히 실수최적화 문제에서 최고의 성능을 발휘하고 있는 기술입니다.

가장 핵심이 되는 이야기는 사실 Generational 과 Steady-state 방식이 각각 Bit나 non-permuation 문제, 그리고 실수최적화 문제에 적합하다는 사실이겠죠. Generational 이 Steady-state 방식보다도 아직은 Bit 나 non-perm 문제등에 더 많이 이용이 되는것이 현실이고, 실수최적화 에서는 Steady-State 방식이 ES의 등장과 더불어 가장 널리 쓰이게 되는 방식이 되었습니다.

두 알고리즘의 차이점은 사실 언급하기가 애매한 면도 없지않습니다. 말씀 드렸듯이, 단지 몇개의 개체나 유전연산이 일어나는지에 대한것이 가장 큰 이유이기 때문이죠. Generational 방식을 이용할때에 Reproduction 이 90%이상을 차지하게 된다면 사실 이모델은 Steady-State 와 차이가 없겠지만, 일반적으로는 그렇지 않겠죠. 어디까지나 서로 일반적인 면에서 바라보는 입장입니다. 정확하게 반드시 이렇다 라는건 없는것이지요.

여러분께서도 만약 실수최적화 문제를 해결하시는데에 기존 이용방식이 맘에 드는 결과를 도출해 내지 않는다면, 메인 알고리즘을 Generational 혹은 Steady-state 방식중 어떤 것을 이용하는지 한번 확인해보세요. 모든 분야에서 완벽하게 차이를 보일 수 밖에 없다는 결과발표는 아직 없지만, 일반적으로 각각의 장점이 존재하니까요.


P.S. 정말 오랜만에 포스팅이었습니다. 시험을 앞두고 있는 마당에 이정도도 못하면 정말 더는 못할것 같더군요;; 뭐가이렇게 일이 많은지, 일에 치이고 치이다보니 일반론적인 부분조차도 머리속에서 자꾸 왔다갔다 거리는 바람에 정리하는데 시간이 꽤걸렸습니다. 혹시라도 유전연산이나 이런분야에 대한 연구를 하시는 분이 계시다면 제 자료들이 도움이 되셨으면 좋겠습니다.

참고문헌

  ALPS:The Age-Layed Population Structure for Reducing the Problem of Premature Convergence - Gregory S. Hornby, GECCO'06 July 8-12, 2006, Seattle, Washing ton, USA. ACM 1-59593-186-4/06/0007.
  The Hierarchical Fair Competition(HFC) Framework for Sustainable Evolutionary
Algorithms - Jianjun hu , Erik Goodman, Kisung Seo, Zhun Fan, Rondal Rosenberg, 2005 by the Massachusetts Institute of Technology ,Evolutionary Computation 13(2): 241-277
  A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization - Kalyanmoy Deb, Ashish Anand, Dhiraj Joshi, 2002 by the Massachusetts Institute of Technology, Evolutionary Computation 10(4): 371-395
  The CMA Evolution Strategy: A Tutorial, Nikolaus Hansen, November 11, 2005

 보시면 아주 좋을 논문들입니다. (마지막 논문은 수학적 지식이 없으시면 절대 이해하기 어렵습니다.)
Posted by SHHyun

댓글을 달아 주세요

 이번에는 지난번에 언급했던 Island Parallelism 의 방식중에서 Injection 방식에 대해서 언급해보겠습니다.
Injection 방식이란 말그대로 주입식 방식이라고 표현하면 간단하겠습니다.

 GP 나 GA 에서 사용되는 Multi-POP 을 응용해서 만들어진 여러 알고리즘은 크게보면 POP 을 전체적으로 분산, 격리 시켜서 그 상태를 운용하는 방식을 벗어나지 않습니다. 즉, 거의 모든 방식이 Multi-POP 을 이용하게 되는 기본 이론인 Island Parallelism 을 벗어나지 않는 선에서 만들어집니다.
 Injection 방식이라는 것 또한 마찬가지 입니다. 지난번에 Migration 에 의해 몇몇 방식으로 나뉘어 진다고 말씀 드렸는데, Injection 방식 또한 Migration 방식이 약간 변경된 것입니다. 왜 주입(Injection) 방식이라고 불리는가 하면 말 그대로 이 방식은 모든 POP 에 Best 값을 한데 모아서 경쟁시키게 되기 때문입니다. 각각의 POP 은 격리 수용되고, 그 격리 수용된 상태에서 나타난 준 최적해들 혹은 최적해들을 모아 경쟁을 시키게 됩니다.
 그림으로 보면 아래와 같이 되겠습니다.

사용자 삽입 이미지


 Migration 방식의 대표적인 두가지 중에 하나로 지난번의 Ring Migration 보다 좀 더 강한 수렴성을 나타내게 됩니다. 지난번의 Ring Migration 이 수렴성을 낮추고, 불순물 유입을 통한 조기수렴 방지라는 효과를 노리고 이용되는 반면, 이 방식은 매우 강한 수렴성을 나타나게 해서 조금 더 빠른 속도로 최적화를 이루어 내는게 목적입니다.
 하지만 지난번에 말씀 드렸듯이 수렴이라는 것은 너무 빨라도 안되고 너무 늦어도 안되는 것입니다. 수렴 자체도 최적값이 없기 때문에 여전히 많은 학자들에 의해 논란이 일어나고있고, 논의가 되고 있습니다. 수렴이 빠르게 최적값을 향해 된다면 이것이야 말로 최적이지만 그렇지 않다면 최악의 경우가 나타나는 것이지요.
 문제에 따라서 잘 고르는것이 관건 입니다.

(*) 마치며...

  지금까지는 사실 수학적인 내용이라기 보다는 알고리즘 적인 내용이었습니다. 하지만 좀 더 깊이 들어가보자면 GA 나 GP 의 Tree 나 Bit string 이 구성될 확률에 대한 Scheme 이론, 그리고 현재 실수 최적화 문제에서 매우 강력한 성능을 발휘하고 있는 것으로 알려진 PCX나 UNDX 와 같은 것들은 완전히 수학적인 연산자 입니다. 다음부터는 정말 정리하는데 오래걸리겠네요;;

Posted by SHHyun

댓글을 달아 주세요

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

1. 기본적인 Multi-POP(이주 계획 없음)

  가장 기본적인 알고리즘 입니다. 단지 Island Parallelism 을 이용해서 각각의 POP 을 고립시키고 발전 시키는 방식 입니다. 효과로서 기대해 볼 수 있는 것은 지난 시간에 언급했던 갈라파고스 제도와 같은 효과 입니다. 즉, 유전자 개체는 우수한 개체만이 살아남게 되는데 이때, 각각의 섬의 환경에 따라 우수한 개체가 서로 다르게 되어 다른 여러가지 형태의 우수한 개체가 남게 되는 것입니다. 그림으로 보면 아래와 같습니다.

사용자 삽입 이미지

(*) 단지 각각의 개체를 독립시켜 연산을 수행하는 방식

  결과적으로, 이 알고리즘이 처음 도입되고 기대한 것은 위에서 언급한 것과 같은 효과 입니다. 하지만 실제적인 효과는 미비했습니다. 하지만 이 알고리즘이 여전히 쓰이는 부분이 있습니다. Multi Fitness 를 이용하는 방식에서 쓰이게 되는데, 같은 유전자를 사용하면서 서로 다른 여러개의 Fitness 를 사용해서 각각의 방식에 대해 최적화 시키는데에 이러한 방식이 쓰입니다.

2. Ring Migration 방식
 
  이 방식은 위의 기본적인 Multi-POP 에 대해 아주 간단한 이주계획을 추가시킨 것 입니다. 일정 세대의 수행이 끝나게 되면 각각의 군집에서 가장 우수한 염색체를 n 개 만큼 추출해서 다른 개체의 가장 성능이 좋지 않은 n 개의 염색체를 대체 시키게 되는 방식입니다. 이것이 Ring 인 이유는 모든 군집이 순환하도록 되어 있는 구조 때문입니다. 그림으로 보면 다음과 같습니다.

사용자 삽입 이미지

(*) 링 처럼 서로의 POP 을 연결하는 형태이기에 Ring Migration 이라고 한다.

  이 방식의 장점은 서로 다른 형태의 군집에 어떠한 다른 형태의 우수한 인자를 유입하기 때문에 또다른 형태의 경쟁이 시작되게 됩니다. 여기서 Local Search 와 Global Search 의 이론이 다시 나오게 되는데, 밑의 그림을 보고 이해하시면 쉽게 이해하실 수 있습니다.

사용자 삽입 이미지

(*) 어떤 문제 f(x)의 해가 분포해 있는 단순한 그래프 형태
 
  지난번에 한번 언급했던 문제 입니다. 위의 그래프와 같이 해가 분포해 있다고 가정 하고, 가장 높은 성능의 해를 찾는 것을 목적이라고 가정합니다. 그렇게되면 우리의 최종적 목표는 A1 지점 이라는 것을 아실 수 있습니다.
여기서 목표를 찾기위해서는 최대한 A1 지점의 계곡과 같은 그래프에 근접해서 해의 탐색을 시작해야 A1 지점에 도달 할 수 있다는 사실을 알 수 있습니다.
  만약 Single-POP 방식을 이용해서 탐색을 시작했는데, A3 지점에 근접한 곳에서 탐색을 시작했다고 가정 합니다. 그렇다면 GA 엔진이 Local Search 를 하기 시작한다면, 최고점으로 A3 지점을 찾는데 만족하게 될 것입니다. 하지만 문제의 최적값은 A1 의 지점입니다. 결국 준 최적점을 찾는데 그치게 된 것입니다.
  하지만 Multi-POP 방식을 이용해서 탐색한다고 가정 했을 경우에는 각각의 POP 의 시작 지점이 좀더 여러곳으로 분포할 수 있기 때문에 최대한 A1 지점에서 시작할 수 있다고 예측할 수 있습니다. 그러나 기본적 Multi-POP 방식을 이용해서 탐색 할 경우에 만약 A1 지점 과 A2 지점의 사이의 계곡점에서 A2 쪽으로 탐색이 시작되었다고 한다면, 결국 우리는 최적점을 못찾게 될 수 있습니다.
  우리가 Multi-POP 방식 중 Ring-Migration 을 이용하게 되었다고 가정하게 되면, 각 지점별 탐색이 이루어 지다가 서로의 지점에서 가장 높은 Fitness 를 가진 개체가 다른 지점에서의 가장 낮은 Fitness 의 개체를 대체하게 됩니다. 결과적으로 최적값을 찾아낼 확률이 조금 더 높아지는 것 입니다.

  하지만 결국은 이 모든 것이 확률의 문제입니다. 그렇기에 우리가 새로운 알고리즘을 만들어 내는 것들은 이 확률을 높히는데에 주력하게 되는 것입니다. 최적화된 값을 찾아낼 확률을 높히는데에 초점이 맞추어져 있는 것입니다.

(*) 마치며..

  위의 두가지 외에도 많은 방식이 존재합니다. 이주 규칙 및 방식에 의한 미묘한 차이로도 최적화 값을 찾아 낼 경우도 있고 Multi-POP 을 이용하지 않고, Single-POP 에 다른 연산자들을 적용하는 것만으로도 최적화 값을 찾아낼 수 도 있습니다. 하지만, 가장 중요한 것은 이 기초 이론들이 왜 만들어 졌으며 어떤 근거를 두고 만들어 졌는지를 이해하는 것 입니다. 그래야 새로운 방식을 만들어 낼 때도 그런 근거와 이론에 의해 만들어 낼 수 있기 때문이죠. 모자란 지식으로 많은 것을 정리하다보니 애매한 부분이 많을 수도 있습니다. 틀린 곳 있으면 항상 xjavalov@shhyun.com 으로 메일 보내주시면 감사하겠습니다. (스팸은 사절이예요 ㅠㅠ)
Posted by SHHyun

댓글을 달아 주세요

가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 Island Parallelism 이론 입니다.
한글로 직역하자면 섬 병행진화론 정도가 되겠는데요.
그리고 Multi-Population 방식이라고도 합니다.
GA 자체의 출발점이 유전학적인 요소가 강하다보니 유전학적인 측면에서 발전된 이론입니다.

단순히 설명하자면, 각각의 군집(Population) 이 서로 다른 섬에 떨어져 있다고 가정하는 것이죠.
각각의 섬에서 따로 발전, 진화를 거듭하게되면 그 섬에 특성에 맞는 군집으로 발전되어 나간다는 이론입니다.
다윈의 진화론의 출발점이라고 할 수 있는 갈라파고스 제도와 같은 요소를 도입한 해결방식입니다.

조금 더 자세히 기존 방식과 비교해보면 다음과 같이 될 수 있습니다.

1. 기존방식(Single-Population)

  하나의 군집을 이용하여 매우 큰 개체수를 이용하여 발전시킨다.
  개체수가 커진다면 그만큼 다양한 탐색영역을 초기에 조사, 탐색하게 되고 그것으로 더 최적화된 요소를 찾아낼 수 있다.
  하지만 개체수가 크더라도 일반적인 선택 연산자(Tournament 혹은 Rank 외 기타등등)를 이용하게 된다면 매우 빠른속도로 한 값에수렴해가는 양상을 보이게 된다.

2. Island Parallelism (Multi-Population)

  다양한 군집으로 나누어 조금씩의 개체를 이용하여 발전시킨다.
  각각의 군집으로부터 특정세대, 혹은 어떤 조건에 의해 서로의 개체를 교환하는 등의 조건을 정해야한다.
  수렴속도를 늦춰주는 효과는 서로의 군집에서 개체를 교환할 때 이루어진다.
  개체수에 큰 관계 없이 서로 다양한 개체를 교환해 나가며 연산이 이루어 지기에 기존방식 보다는 수렴 속도가 늦춰지게 된다.
  이 방식도 기존 방식보다는 수렴속도가 늦어지지만 결과적으로는 수렴에 다다르게 된다.

전체적으로 Multi-Population 을 이용하는 것이 기존의 Single-Population 방식보다 좋은성능을 보여주는 것으로 알려져 있습니다. 사실 Multi-Population 을 이용하는 것이 좋은 성능을 보여주기는 합니다. 하지만, 문제의 특성에 따라서, 그리고 개체의 군집은 몇개를 할것이며 몇 세대마다 얼마나 많은 개체를 옮겨주겠느냐와 같은 것에 따라서 성능에 많은 차이를 보여주기에 그에 대한 논문들도 매우 많이 나와 있습니다. 보통 Parallelism, Genetic Algorithm, Migration rule 과 같은 검색어를 이용해서 검색을 해보시면 많은 내용을 찾아보실 수 있습니다.

마지막으로 Island Parallelism 을 구성하게 될 경우 알고리즘의 변화에 대해서 알아보겠습니다.

 기존의 GA 의 알고리즘은 매우 단순합니다.

  Initialize -> Generation(CX, MUT, SELECTION, ETC...) -> Statistics -> Loop -> ... -> Condition -> END

 하지만 Island Parallelism 을 이용하게 될 경우에는

  Initialize -> Generation -> Statistics -> Migration -> Loop -> ... -> Condition -> END

 로서 Migration 부분이 추가 되게 됩니다. 그리고 초기화 조건이나 기타 다른 Generation 부분에 대해서 각각의 군집(Sub-Population) 에 대해서 추가적인 연산이 이루어 져야 되기 때문에 그에 대한 연산이 필요합니다. 그리고 Migration 을 어떻게 수행하느냐에 따라서도 많은 방식이 존재하기에 그에대한 고려 또한 해 주어야 합니다.

(*) 마치며...

  간략하게 말로서 설명을 해 보았습니다. 사실 자세히 정리하고자 한다면 A4 용지 20장 이상의 분량은 나오지 않을까 싶습니다. 그 안에서도 너무 많은 분류와 세부적인 연구결과들이 존재하기 때문에 그에 대한 총체적인 정리를 하기에는 조금 무리가 있지 않나 싶어서 우선은 간략하게 Island Parallelism 에 대해서 서술했습니다. 다음에는 이에 대한 세부적인 내용에 대해서 몇가지만 정리해 보려고 합니다.
Posted by SHHyun

댓글을 달아 주세요

  초기의 진화연산(Evolutionary Computation, 이하 EC) 에서 더 최적 값을 찾기 위해 논의 되었던 최적해에 관련된 두가지 논제가 있습니다. 그것은 바로 조기수렴 문제와 Local Search 문제 입니다. 오늘은 조기수렴 문제와 Local Search 문제가 왜 논의 되었는지 알아보겠습니다.

  GA를 이용한 최적화 문제에서는 보통 Crossover Rate = 0.9, Mutation Rate = 0.1 을 사용합니다. 이는 보다 빠르게 최적값을 찾기 위해 사용하게 됩니다. 하지만 이 문제에서 큰 단점이 있으니, 그것이 바로 조기 수렴의 문제 입니다. 최적값이 저 멀리에 있어도, 그 값에 도달하지 못하고 적당한 중간값을 최적값으로 인식하고 그 값 근처에 머무르게 되는 것입니다. 실제 최적값에 도달하지 못하고, 준 최적값에 도달하거나 전혀 다른 값에 도달해서 머물러 버리는 것입니다. ( f3deceptive 문제와 같은 문제를 참조하시면 엔진 성능이 좋지 않을경우 모든 값이 0에 수렴해 버리는 현상을 확인하실 수 있습니다. 정답은 전부 1에 수렴해야 하는데도 말이죠. ) 
  그러면 CX 와 MUT Rate 를 낮은 값을 사용하면 되지 않겠느냐 라고 반문하실지도 모르겠습니다. 사실 그렇게 하게되면 특정 문제에 대해서는 효과를 볼 수 있습니다. 하지만 실제 GA 가 이용 되는 문제들은 상당한 연산을 하게되는 어려운 문제들 입니다. 그런 문제에서 낮은 CX 와 MUT Rate 를 사용하게 된다면, 최적값을 찾는데 한달, 혹은 몇 달 이상 걸리게 될 수도 있습니다. 그렇기에 보통 CX = 0.9 MUT = 0.1 를 이용하게 됩니다.
  이와같은 이유로 GA 에서는 조기수렴 문제의 극복에 대해 많은 논의가 이루어 졌습니다.

  ES에서는 GA 와는 조금 다른 형태의 문제에 봉착하게 되었습니다. ES 에서는 보통 조기수렴의 문제에 빠지지 않습니다. ES 는 GA 와는 다르게 실수값을 이용하고, 실수 최적화에 최적화 되어있기 때문에 수치를 탐색하는 범위를 어떻게 설정하느냐가 문제가 되었습니다. 이때문에 Global Search 와 Local Search 에 대한 논의가 진행 되게 되었습니다. Global Search 는 해의 공간(Space) 를 아주 넓게 찾는 방식이고, Local Search 는 해의 공간을 아주 좁게 매우 세밀하게 탐색하는 방식입니다. 밑의 그래프는 Rosenbrock 함수(실수최적화문제)의 그래프 입니다.

사용자 삽입 이미지

(*) http://mathworld.wolfram.com/RosenbrockFunction.html 의 자료입니다.

  해의 범위가 매우 특이한 형태를 갖추고 있음을 알 수 있습니다. 가운데 부분에도 굴곡이 있고, 매우 넓은 범위에 걸쳐 굴곡이 펼쳐져 있기 때문에 이를 찾아내기 위해서는 매우 조밀한 Local Search 가 필요하다는 것을 확인할 수 있습니다. 하지만 저 값에 다가가기 위해서는 Global Search 도 필요한 것이죠. 그래서 ES 에서는 이 둘을 조합하는 방식에 대해서 논의가 되게 되었습니다.

(*) 마치며...
 
  오늘은 간단하게 EC 에서 논의된 중요한 두가지 문제에 대해 알아보았습니다. 어째 기초에 대한 것은 많이 모자르게 정리하면서 어려운 문제에 대한 논의만 잔뜩하는 기분이 들기도 합니다. 하지만 기초에 대한 것은 책을 펼쳐보면 쉽게 알 수있는 것들이 많기에 슬슬 어려운 논제와 수학적 논제들에 대해 정리해 보려고 합니다. 아마 포스팅 하나 하는데 2~3일 걸리던게 일주일 넘게 걸릴수도 있겠네요. 하지만 정리를 해야 저도 공부도 하고 그러는 지라 ^^;; 다음에는 조기수렴 문제의 극복에 대한 이야기를 해보겠습니다.
Posted by SHHyun

댓글을 달아 주세요

오늘은 실수최적화 문제에서 이용되는 CX 연산자중

지난번에 다루었던 Arithmetical Crossover[Michalewicz 1996] 의 변형판에 대해서 다루겠습니다.

기존 Arithmetical Crossover 의 특징에 대해 간략하게 알아보면

  1. 적용이 쉽다.
 
  매우 단순한 알고리즘으로 구성되어 있기 때문에 적용이 쉽습니다. 물론 random 으로 lambda 값을 산출해 내는 과정에 어떤 알고리즘을 적용시키느냐가 관건이 되지만( 사실 시간에 의한 난수값이 출력되는 것은 신뢰도나 정확도면에서 그다지 높지 않기때문에 다른 알고리즘에서는 잘 쓰이지 않는 경향이 있습니다. ) 그 부분에 대해서만 제외한다면, 서로의 Chrom 값에 lambda 값의 곱과 1- lambda 값의 곱만으로 새로운 Individual 을 만들어 낼 수 있습니다. 이런 면에서 Arithmetical CX 는 적용이 매우 쉬운 CX 연산자 임을 알 수 있습니다.

  2. Local Search 에 적합한 연산자

  다음 글에서 Local Search 와 Global Search 에 대해서 자세히 알아볼 것이지만, 우선 Local Search 라는 것은 값 자체를 크게 변화없이 조금조금씩 변화시킴으로써 올바른 값으로 수렴해 나가는 원리 입니다. 그렇기에 Local Search 에 적합한 변모를 보이고 있고, 조기 수렴하는 경향을 보이게 됩니다.

  3. Individual 전체를 변화시키는 연산자

  Artithmetical CX 는 Individual 전체를 변화시키게 됩니다. 일부만을 변화시키는 것이 아니라 모든 Chrom 에 걸쳐 연산이 이루어 지기 때문에 Individual 전체를 변화시킵니다. 이는 초기에 전체적으로 좋은 변화를 이끌어 낼 수 있지만, 실제 이상적인 값에 도달하기 위해서 일부분만을 수정하게 되는 일에 약한 면모를 보이기 때문에 정밀한 최적화 작업에는 적합하지 않음을 의미합니다.

  위의 특징을 살펴보시면 아시겠지만, Arithmetical CX 는 초보적인 알고리즘이고, 구현이 쉽고 적당한 결과값을 알아내는 데에 적합합니다. 고로 매우 정교한 작업에는 적합하지 않음을 알 수 있습니다. 하지만 잘 생각해보시면 Individual 전체가 변화하는 문제 때문에 최적화가 거의다 끝날무렵에 미묘한 변화치에 대한 것들을 제대로 캐치하지 못함을 알 수 있습니다. 이런 특징적인 면을 개선시켜서 나온 연산자가 바로 오늘 설명할 수정단순교배(Modified Simple Crossover) 입니다.

 -- 사실 이 연산자는 유전알고리즘과 그 응용(진 강규 저) 에도 소개되어 있기에 저작권 문제도 있을 것 같고 해서 제가 소개하기가 조금 껄끄러운게 사실입니다. 저자 이신 진 강규님께서 2000년 도에 직접 작업하신 연산자 인 것 같습니다. 그렇기에 자세한 설명에 대한 것은 위의 책을 참고하시거나 진 강규님의 논문을 참고하시는 것이 좋을 것 같습니다. 저는 개략적인 설명만을 해보겠습니다. --

Modified Simple Crossover [진 2000]

위에 설명드렸듯이 간단합니다.

지난 번에 소개해 드렸던 Arithmetical Crossover 에

어떤 Chrom 을 변화시킬지를 선택하는 변수가 하나 추가되어 있습니다.

고로

지난번에 소개한 Arithmetical CX 를

특정 선택된 Chrom 에 대해서만 변화시키는 연산자가 되겠습니다.

(*) 마치며...

  본 연산자에 대해서 자세한 설명과 그림을 첨부하고자 했습니다만 왠지 저작권 관련한 문제가 있을 것 같아서 간략한 알고리즘에 대한 설명만을 했습니다. 뭐 저정도로도 충분하다고 생각하지만 그렇지 않을 수도 있구요. 만약 추가적인 설명이나 다른 것에 대해서 알고 싶으시다면 제 블로그에 글을 남겨주시거나 연락주시면 제가 따로 연락을 드리겠습니다. 다음에는 매우 중요한 개념중에 하나인 Local Search 와 Global Search 에 대해서 정리해 보겠습니다. 이 부분은 GA 와 ES 의 성능을 개선시키기 위해 학자들이 연구하는 두 부분중에 하나 입니다. CX 연산자에 대한 소개는 잠시 접어두고, Local Search 와 Global Search 에 대해서 먼저 알아보도록 하겠습니다.
Posted by SHHyun

댓글을 달아 주세요

오랜만에 GA 관련 포스팅 입니다.
예전에 한번 설명 드렸지만, GA 는 원래 Bit 형태의 유전자를 이용해서 연산을 하게 됩니다.
이 Bit 형태의 유전자를 이용해서 연산을 하게 되면,

Bit -> Real Number -> Bit 의 변환과정을 거쳐서 적합도평가(Fitness Evaluation)가 이루어집니다.

결과적으로 변환 과정의 해상도(Bit 의 갯수를 얼마나 더 확장시키는지)가 성능에 어느정도 영향을 미치는 꼴이 됩니다. 이 문제에 대해 간단한 예제로 설명하자면 밑의 More 부분을 클릭하시면 됩니다.



그래서 학자들 사이에서는

Binary 로 이용해서 변환과정을 거치는 것만으로도 실수 최적화에 성공할 수 있다.

 VS

실수 최적화 문제는 실수자체를 이용해서 최적화 시키는 것이 더 좋은 결과가 나온다.

의 두가지 논점으로 갈라지게 되었습니다.

GA 에 대해 오래 연구하신 분들께서는 위의 의견에 동의를 하시는 편이시고, GA 외에도 ES(Evolutionary Strategies)나 다른 C.I.분야에 대해서 연구하신 분들께서는 아래쪽 의견에 동의를 하시는 편 입니다.

저 같은 경우에는 Rosenbrock 이나 Griewangk 과 같은 Benchmark 문제를 두가지 접근방식으로 해결해 본 결과 아랫쪽 의견에 더 동의하는 편 입니다.

만약 우리가 실수 연산을 이용하고자 한다면, 그에 맞는 CX 와 MUT 연산자를 이용 해야 할 필요가 있습니다. 기존의 Bit 방식의 접근으로는 실수 유전자를 이용하는 의미가 떨어지게 되기 때문입니다.

그래서 오늘은 실수 유전자를 이용하는 CX 연산자 중에서 가장 기본적 연산자인 Arithmetical Crossover[Michalewicz 1996] 에 대해서 살펴보도록 하겠습니다.

--------------------------------------------------------------------------------------------

Arithmetical Crossover[Michalewicz 1996]

역시 본론 부터 말씀드리자면 기본 적인 연산자 답게 크게 어려움은 없습니다.

여기서 기억하실 것은 λ(lamda) 값 입니다.

일반 적으로 0~1 사이의 실수값으로 표현되는 λ(lamda) 값에 의해 유전자가 미묘하게 수정되게 됩니다.

그림의 예를 통해 어떻게 수정되는지 표현해보겠습니다.

사용자 삽입 이미지

(*) 그림이 조금 깨지면 클릭 하셔서 보시면 됩니다.

위에 보시면 아시겠지만 아주 단순한 알고리즘 입니다.

λ 값에 의한 변화라고 볼 수 있습니다.
λ 값의 범위가 0 ~ 1 사이로 제한되면 Convex CX
λ 값의 범위가 -0.5 ~ 1.5 사이로 제한되면 Affine CX

라고 부릅니다.

여기서 Convex 범위를 갖게 되면 유전자의 값들이 항상 원래 의도하고자 하는 유전자의 범위를
벗어나지 않게 됩니다만, Affine 범위를 갖게되면 유전자가 자칫 값이 커져버려서 범위를 벗어나곤 합니다.
그렇기에 범위를 벗어나는 것을 막아주어야 하는데, 일반적으로 두가지 방법이 있습니다.

유전자 차원에서 매번 값의 검색을 통해 Error 값을 나타내는 것
적합도 차원에서 값이 벗어날 경우 Error 값을 나타내는 것


이 있습니다. 저의 경우에는 후자를 사용해서 값을 통제했습니다.

결론적으로, Arithmetical CX 방식은 λ값을 통해 유전자 값들을 미묘하게 흔들어 주는 방식입니다.
이 방식은 구현도 매우 쉬운편이고, 효과도 그럭저럭 나쁘지 않은 편이기에 기본적인 GA에서 많이 쓰입니다.


(*) 마치며...

  사실 제가 조금 변형한 GA 를 올릴까 했습니다. 하지만 부족한 것이 너무 많기에 아직은 올리기에 부끄러울 지경입니다. 적어도 기본적인 SGA 보다는 압도적인 성능을 보여야 한다고 생각하는게 제 생각이기에 아직은 올릴 시기가 아닌 듯 싶네요. 그래서 제가 프로그래밍 하고 있는 GA 에 이용되고 있는 몇가지 연산자들에 대해서 천천히 설명하고, 새로 구현되는 내용들에 대해서 언급을 다 한후에 완성된 것을 올려보겠습니다. 보고 공부하기 좋은 GA 를 구현하려고 노력하고 있습니다 ^^
Posted by SHHyun

댓글을 달아 주세요

안녕하세요.

오랜만에 포스팅 입니다.

GA 를 이용하고 연구하고자 할 때, 가장 큰 걸림돌이 되는것은 어떤 엔진을 선택하느냐 입니다.
각기 다른 여러가지 엔진이 있고 그 특징과 이용, 활용면에서 워낙 광범위하기에 어떤 엔진을 선택하는지
매우 고민되지 않을수가 없죠. 이에 몇가지 유명한 엔진에 대해 알아보겠습니다.

사실 여러 그룹이나 연구실에서 이용하는 GA 는 기본 SGA의 틀에서 크게 벗어나지 않는 자체의 GA 엔진이 대부분입니다. 왜냐하면 광범위한 목적으로 개발된 GA 에서는 원하지 않는 기능도 많고 우선 알고리즘 자체의 구성부터 살펴봐야하기 때문입니다.

일단은 유명한 GA 엔진들에 대해서 살펴보고 그 특징과 기능면에서 이야기를 해보도록 하겠습니다.

1. Open Beagle(http://beagle.gel.ulaval.ca/)

  Open Beagle 은 EC(Evolutionary Computation) 의 전반적인 모든 부분을 다 다루고 있는 엔진입니다.
  GA 만 다루고 있는것이 아니라 GP, EA(or ES) 까지도 구현되어 있습니다. C++ 로 구현되어 있고, 가장 유명하고 가장 광범위하게 많이 쓰이고 있는 엔진입니다. ( 하지만 저는 개인적으로 별로 좋아하지 않습니다... )

  제작자들이 말하고 있는 기능들에 대해서 보면 다음과같이 되어 있습니다. ( 위의 홈페이지에서 발췌했습니다. )

Features

Object-Oriented Foundations:

  • Modern C++ programming approach 
  • Structured OO architecture
  • Smart pointers for automatic memory allocation management
  • XML file formats with built-in parsing facility
  • Sophisticated logging mechanism with output in XML
  • Parameters and algorithms dynamically configurable by files
  • Generic representation of the algorithms using a plug-in mechanism
  • Milestone mechanism for evolution recovery and results analysis

Open BEAGLE generic EA framework:

  • Many predefined operators
  • Generational, steady-state, (mu,lambda), and (mu+lambda) replacement strategies
  • Population composed of multiple demes
  • Individuals represented on multiple genomes
  • History of best-of-run individuals for the whole population and for each demes
  • Complete evolution statistics
  • Multiobjective optimization (currently NSGA-II and NPGA2)
  • Population seeding from file

GA framework (linear representations):

  • Bit string GA representation with decoder functions (binary and Gray-coded)
  • Integer-valued vector GA representation
  • Real-valued vector GA representation
  • Evolution strategy (ES)
  • Covariance Matrix Adaptation ES (CMA-ES)
  • Three generic crossover operators (one-point, two-points, uniform) and two float vector specific operators (BLX-alpha and SBX)
  • Four specific mutation operators
  • Operators for shuffled indices genotypes for the integer-valued vector representation
  • Seven illustrative examples (OneMax, ZeroMin (OneMax minimization), Function Maximization with Bit String GA, Function Maximization with Real-Valued GA, Function Maximization with ES, Multiobjective 0/1 Knapsack, Travelling Salesman Problem)

GP framework:

  • Standard crossover operator
  • Five mutation operators: standard (Koza GP I) mutation, swap node mutation, shrink mutation, swap subtree mutation, and random ephemerals value mutation
  • Three initializations method for trees: full, grow, and half-and-half; each ramped or not
  • Abstract primitive class
  • Many predefined primitives
  • Automatically defined functions (ADF)
  • Random ephemeral constants
  • Constrained GP tree operators with support for strongly-typed genetic programming
  • Three illustrative examples (Symbolic Regression, Even 6-Parity, and Spambase)

Co-evolution framework:

  • Co-evolution support based on multi-threading
  • Multi-threading classes incapsulating OS-specific calls
  • Co-evolutionary fitness evaluation operator for basic EC and GP
  • Two illustrative examples (Two-Populations Iterated Prisoner's Dilemma, Co-evolutionary Symbolic Regression)

  두껍게 표시해 놓은 부분이 제가 생각하기에 다른 알고리즘에 비해서 뛰어나다고 할 수 있는 기능들 입니다.
  이중에 Generational, steady-state 의 두가지 기능은 그 두가지 알고리즘의 성능차이에 대한 측면에서도 매우 좋은 기능으로 보입니다. 하지만 워낙에 많은 기능이 지원되어 있기때문에 양 자체도 방대하고 소스를 파악하기가 조금 힘들고, 다른 프로그램과 서로 링크시키는 것이 힘들기 때문에 저는 개인적으로 별로 선호하지 않습니다.

2. ECJ(http://cs.gmu.edu/~eclab/projects/ecj/)

  ECJ는 이 분야에서 매우 유명한 분이신 Sean Luke 씨가 있는 그룹에서 만든 EC 엔진 입니다.
  특징적인 것은 Java 를 베이스로 만들어졌다는 것이고, 그렇기 때문에 플랫폼에 종속적이지 않은 형태로 어느 플랫폼에서든 이용할 수 있다는 것 입니다.

  밑의 표는 위의 홈페이지에서 발췌 했습니다.

Features

General Features
  • GUI with charting
  • Platform-independent checkpointing and logging
  • Hierarchical parameter files
  • Multithreading
  • Mersenne Twister Random Number Generators
  • Abstractions for implementing a variety of EC forms.
EC Features
  • Asynchronous island models over TCP/IP
  • Master/Slave evaluation over multiple processors
  • Genetic Algorithms/Programming style Steady State and Generational evolution, with or without Elitism
  • Evolutionary-Strategies style (mu,lambda) and (mu+lambda) evolution
  • Very flexible breeding architecture
  • Many selection operators
  • Multiple subpopulations and species
  • Inter-subpopulation exchanges
  • Reading populations from files
  • Single- and Multi-population coevolution
  • SPEA2 multiobjective optimization
  • Particle Swarm Optimization
  • Spatially embedded evolutionary algorithms
  • Hooks for other multiobjective optimization methods
  • Packages for parsimony pressure
GP Features
  • Set-based Strongly-Typed Genetic Programming
  • Ephemeral Random Constants
  • Automatically-Defined Functions and Automatically Defined Macros
  • Multiple tree forests
  • Six tree-creation algorithms
  • Extensive set of GP breeding operators
  • Seven pre-done GP application problem domains (ant, regression, multiplexer, lawnmower, parity, two-box, edge)
Vector (GA/ES) Features
  • Fixed-Length and Variable-Length Genomes
  • Arbitrary representations
  • Five pre-done vector application problem domains (sum, rosenbrock, sphere, step, noisy-quartic)
Other Features
  • Multiset-based genomes in the rule package, for evolving Pitt-approach rulesets or other set-based representations.
  • Hooks for using the Teambots robot simultation system to do evaluation.

  이 들이 언급하고 있는 기능들 중에서 주요한 기능들에 대해서만 굵게 표시해 보았습니다.
  일반적 기능에서는 표로 개체의 진화정도와 같은것이 표현된다는 것이 주요한 특징입니다. 그리고 Sean Luke 가 언급한 이론 중에 Strongly-Typed 이 있는데 역시 이 기능도 지원이 됩니다. Strongly-Typed 에 대한 부분은 나중에 따로 포스팅을 하겠습니다.( 사실 별것이 아니기도한 이론이지만 GP 에 있어서는 꽤 좋은 이론 입니다. )

3. GALOPPS ( http://garage.cse.msu.edu/ )

  Michigan State University 의 GARAGe 팀에서 만든 GA 엔진입니다.
  기타 다른 엔진들과 달리 순수하게 GA 만을 지원하고 있습니다. Bit String 타입과 Real Value 타입에 대한 지원이 있고, C 언어로 구성되어 있습니다. 꽤 오랜시간동안 발전해 왔는데, 소스 자체의 구성은 어렵지 않습니다만, Erik Goodman 씨의 과도한(?) 친절로 인한 엄청난 주석의 압박을 느끼실 수 있습니다.

GALOPPS extends the SGA capabilities several fold:

  • 5 selection methods: roulette wheel, stochastic remainder sampling, tournament selection, stochastic universal sampling, linear-ranking-then-SUS.
  • Random or superuniform initialization of "ordinary" (non-permutation) binary or non-binary chromosomes; random initialization of permutation-based chromosomes; or user-supplied initialization of arbitrary types of chromosomes.
  • Binary or non-binary alphabetic fields on value-based chromosomes, including different user-definable field sizes.
  • 3 crossovers for value-based representations: 1-pt, 2-pt, and uniform, all of which operate at field boundaries if a non-binary alphabet is used.
  • 4 crossovers for order-based reps: PMX, order-based, uniform order-based, and cycle.
  • 4 mutations: fast bitwise, multiple-field, swap and random sublist scramble.
  • Fitness scaling: linear scaling, Boltzmann scaling, sigma truncation, window scaling, ranking.
  • (optional) Automatic control of selection pressure, using Boltzmann scaling with automatic control of beta, coupled with Stochastic Universal Sampling.
  • (optional) DeJong-style crowding replacement with (optional) incest- reduction option for mating restriction (negative assortative mating bias), which follows the selection of candidates for mating for an entire generation by a pairing for crossover biased by use of the furthest mate (Hamming distance) among several sampled candidate parents.
  • Other replacement strategy options: child-replaces-parent (from SGA) or child-replaces-random.
  • Elitism is optional.
  • Convergence: "lost," "converged," "percent converged," & other measures.
  • Performance measures: on-line and off-line (local and global across subpopulations), plus current local best, best ever, global best ever.
  • (optional) Inversion operation on entire subpopulations, with migration among them automatically handled, even if fields are of different lengths.
  • Allows user to define multiple (different) representations in subpopulations, with migration among them (by user-supplied migration "conversion" code unless difference is only in order of loci on chromosome, which is handled automatically by GALOPPS).
  • Provides a "beta" implementation of Emanuel Falkenauer's Grouping Genetic Algorithm (GGA) representation and operators, implemented by Brian Zulawinski, which provides tools for efficient solution of a variety of "grouping-type" combinatorial problems (including a bin packing example included, various assignment problems, partitioning problems, etc.). Useful for approximating solutions to many NP-complete problems.
  • Uses "SGA philosophy" of one template file for the user to modify, but enriched with MANY additional user callbacks, for added flexibility, extensibility. All but definition of objective function may be ignored if not needed.
  • All runs are restartable or seedable from automatic checkpoint files.
  • Output easily suppressed to one of 3 reduced levels, including user-callback-driven outputs. Input is from file or keyboard, and files allow optional keywords to permit automatic diagnosis of missing parameters, etc.
  • Communication topology for parallel runs is easily specified in a single "master" file, using either a detailed specification or a "cloned" sample communication pattern. May be defined graphically using new Graphical User Interface.
  GALOPPS 는 특징적으로 SGA 의 발전적 형태를 띄고 있습니다. 그렇기에 SGA 에서 크게 발전된 모습을 보이진 않습니다. 하지만, 여러 수학적인 알고리즘( Boltzman Scaling, Crowding Factor 등) 이나 다른형태의 Chrom ( non-permutation, user-supplied initialization chromosome )등을 사용할 수 있는 GA 입니다.
  알고리즘 자체를 알아보고 공부하기에는 제 생각에는 GALOPPS가 가장 좋은 것 같습니다. 교육용이 아닐까 싶을 정도로 잘 구성되어 있는 주석이나 유저가 원하는 데로 설정하는 부분에 대해 사전에 전부 정의가 되어 있기 때문에 다른 프로그램과의 융합도 간단한 편 입니다.


(*) 마치며...

  GA 는 기본적으로 Generational 한 방식과 Steady-State 한 두가지 방식으로 구분되고 있습니다. 이 둘간의 차이 외에는 연산자들이나 GA Chrom 의 표현등의 Minor Factor 들의 차이가 대 부분입니다. 그렇기 때문에 GA 를 공부하고자 하신다면 오히려 구조적으로 알아보기 편한 형태의 엔진을 이용하시는 것이 좋을 것 같습니다.
  다음 포스팅때는 아마 제가 만든 간단한 GA 에 대해서 소개하고 올려놓게 되지 않을까 싶습니다.
Posted by SHHyun

댓글을 달아 주세요

안녕하세요.

기본적인 SGA( Simple GA ) - David Edward Goldberg(1989) 소스에

f3deceptive function 을 적용시킨 것입니다.

기본 적인 SGA 에는 Elitism 이 적용되어 있지 않기 때문에 세대별로 꾸준한 성능 증가도 없고,

세대가 증가할수록 항상 좋은 결과가 나타나지는 않습니다.

그리고 위의 f3deceptive Problem 같은 어려운 문제들은 30비트 정도도 풀어내질 못합니다.

하지만!

중요한 것은 GA 알고리즘이 어떤방식으로 구성이 되는지에 대한 기초적인 문제와

Fitness Function 의 구성을 어떻게 하는지에 대한 가장 단순한 문제를 파악하기에는

SGA 만한것이 없습니다.

관심이 있으신분은 소스를 유심히 살펴보시면 되겠습니다.

다음 포스팅 때에는 이보다 더 발전된 형태의 GA 소스에 대해서 살펴보도록 하겠습니다.

물론,

저작권 문제때문에 소스의 주소 및 소개만 있을것입니다.

- P.S - 혹시 특정 부분에 대해서 모르신다면 이메일 혹은 답글 남겨주시면 답변을 드리겠습니다. ^^

Posted by SHHyun

댓글을 달아 주세요

GA 에서 만약 우리가 어떤 새로운 방식의 CX 나 MUT 혹은 기타 MultiPOP 의 이주계획을 만들었다고 가정해봅시다.
 하지만 우리는 이 알고리즘이 이전의 알고리즘에 비해 어느정도의 개선 정도를 갖고 있는지 혹은 어려운 문제를 풀어갈 수 있는 능력이 있는지에 대한 여부를 알 수가 없습니다.
  어디까지나 이런점에서 더 개선된 성능을 보여줄 것이라고 추측을 하는 것입니다.

하지만 우리는 그것의 성능여부를 증명을 해야 겠죠?
그렇기 때문에 여러가지 수학적인 복잡한 문제들이 나를 GA 혹은 기타 알고리즘으로 풀어달라고 기다리고 있습니다.

  GA 에 대해 조금 공부를 하신분들은 De jong 의 Test Problem 에 대해서 들어보셨을 것입니다. 이것은 확장이 가능한 문제로서 문제 자체를 아주 어려운 고급의 문제로 확장이 가능한 문제입니다. 하지만 이 문제는 수학적인 문제이기 때문에 구현이 까다롭습니다.

 제가 여기서 말하려고 하는 것은 Deceptive Problem 입니다. 이 문제들은 구현 자체도 간단하고 확장 또한 아주 쉽습니다. 그리고 알고리즘 자체가 지역극소점에 빠지는 현상을 유도적으로 만들어 냅니다. 하지만 영리한 알고리즘은 그것을 피해가는 경향을 나타나게되고 최종적으로 해답을 만들어 내게 됩니다.

 가장 간단한 f3deceptive 에 대해서 살펴보면 다음과 같습니다.

  3비트를 한 묶음으로 보고 하나의 Problem 단위로 생각을 합니다. 조건식은 다음과 같습니다.
 
  000   = 0.9
  001   = 0.8
  011   = 0
  111   = 1

  이것이 끝입니다..... 뒤에 적힌 수치는 Fitness 의 값입니다.

  만약 0 이 3개 있을경우 0.9 의 Fitness 값을 반환하고, 0 이 2개 있을 경우 0.8, 1개는 0, 그리고 1이 3개가 있을 경우에는 1 의 Fitness 값을 반환하게 됩니다.

  이것은 알고리즘 자체가 해답을 0으로 몰고나아가게 되는 현상을 유도하게 됩니다. 111이 분명 최고의 Fitness 값을 지닌 해답이지만, 0이 많아 질수록 Fitness 값이 좋아지는 현상을 보여주기 때문에 알고리즘이 0을 해답으로 생각하고 모든 비트가 0으로 수렴하게 되는 지역 극소에 빠질 확률이 매우 높아집니다. 알고리즘의 성능이 좋다면 짧은 시간 내에 111 을 찾아내는 것입니다.
 
  사실 이걸 1 Problem 에서 본다면 아주 쉬운 문제지요. 하지만 이 문제는 확장가능한 문제이기에 자주 쓰입니다. 보통 200~300 Problem 정도를 해결하려고 하면 정말 좋은 알고리즘의 경우에 10만 Evaluation(1) 정도에 해결하게 됩니다.

  오늘은 갑자기 벤치마크 문제에 대해 다뤘기 때문에 기존에 정리하지 않았던 말들도 쓰이고 난잡한 면이 조금 보입니다. 하지만 벤치마크 문제에 대해 논한 것은 기본적인 것에 대해서는 전부 정리를 했다고 판단되기 때문입니다.

  다음 번에는 SGA (Simple Genetic Algorithm) 에 f3deceptive 를 구현한 것을 Source 와 함께 정리해 보도록 하겠습니다. 또 다음번 글을 언제 쓸지는 모르겠지만 -_-;;; 최대한 빨리 정리하도록 하겠습니다.


(1) Evaluation -> GA가 몇번이나 Fitness 값을 계산했는지를 기록하는 변수

Posted by SHHyun

댓글을 달아 주세요

너무나 오랜만에 글을 포스팅 합니다.
요 근래 너무 바빠서 별다른 정리의 시간을 갖지를 못했네요.

어쨌든 Selection 연산자에 대해서 알아보겠습니다.

우선 Selection 연산자는 유전자 선택에 쓰이는 연산자 입니다.
밑에 설명한 Mutation 과 Crossover 를 해주기 위해서는 그 대상이 필요하겠죠?
그 대상을 골라주는 역할을 해주는 것이 바로 이 Selection 연산자입니다.

Selection 연산자도 꽤 많은 종류가 있는데 몇가지에 대해서만 알아 보겠습니다.

알아볼 Selection 연산자로는

  1. 룰렛휠(Roulette Wheel Selection)
  2. 균등선택(Stochastic Universal Sampling Method)
  3. 랭크선택(Rank-based Selection)
  4. 토너먼트선택(Tournament Selection)

이중에 일반적으로 룰렛휠 이나 토너먼트 선택이 가장 많이 쓰이는 경향이 있습니다.

저는 이것들에 대해 다른 여러 설명과는 다르게 수식은 최대한 배제 하고 설명하겠습니다.
제가 이것을 정리하고 있는 이유가 수식이야 언제든 다른곳을 참조하거나 만들 수 있지만
직관적으로 연산자가 쓰이는 것에 대해 알아보는게 힘들기 때문도 있습니다.


1. 룰렛휠(Roulette Wheel Selection)

  이것은 Fitness 와 그것이 차지하고 있는 비율을 이용하는 연산자 입니다.
  만약 총 Fitness 의 합이 100 이고 어떤 유전자의 Fitness 가 10 의 Fitness 수치를 갖는다면
  이 것이 선택될 확률은 10 / 100, 즉 1/10 이 되는 것입니다.
  약 10%의 확률로 선택되는 것입니다.
  이 연산자는 그래서 다른 이름으로 적합도 비례선택(proportional selection) 이라고 불립니다.
  간단히 정리하면 현재의 유전자가 차지하고 있는 비율에 따라 선택될 확률이 정해지는 것입니다.

2. 균등선택(Stochastic Universal Sampling Method)

  이것은 모든 유전자를 Fitness 에 관계없이 같은 확률로 선택될 수 있도록 해주는 것입니다.
  보통은 모든 Fitness 값들을 더한 것을 Popsize 로 나눠서 각각의 유전자가 같은 확률을 갖게 해 줍니다.

3. 랭크선택(Rank-based Selection)

  이 연산자는 최고의 값을 갖는 유전자를 선택해 줍니다.
  조기수렴의 염려가 매우 많은 관계로 보통은 잘 사용하지 않습니다.
  조기수렴이란것에 대해서는 나중에 설명 하겠지만
  값이 전역극대 또는 전역극소를 찾아내지 못하고,
  그에 준하거나 그렇지 못하는 지역극대 또는 지역극소를 찾아내게 되는 경우가 있는데,
  그것이 너무 빠르게 지역극대나 지역극소점에 수렴하게되면
  전역극대나 전역극소를 찾지못하고, 수렴하게 되는 현상을 말합니다.

  어쨌든 이 연산자는 최고의 Fitness 를 지닌 유전자부터 내림차순으로 선택하게 됩니다.

4. 토너먼트 선택(Tournament Selection)

  가장 많이 쓰이는 토너먼트 선택 연산자 입니다.
  위의 랭크 선택과 다른 점이라고 하면
  유저가 지정한 7 또는 10 과 같은 수치에 의해 해당갯수만큼 후보를 선택하게 되고
  이것들을 경쟁을 시켜 승리하는 값을 선택하는 것이 다른 점입니다.
  무조건 적으로 전체를 후보로 두고 최고의 값을 찾는것이 아닌
  랜덤한 후보를 이용해서 경쟁을 시켜 최고의 값을 찾는 것이 조금 다릅니다.
 

오늘은 Selection 연산자에 대해서 알아보았습니다.

제가 정리하고 있는 내용들은 수식이나 구체적인 내용이 빠져있는 개략적인 설명정도이기 때문에 자세히 알아보고 싶으신분은 저에게 따로 이메일을 주시거나 아니면 다른 여러사이트들을 참조하시는 것도 좋을 것 같습니다.

다음에는 벤치마크 Problem 들에 대해서 알아보도록 하겠습니다.
일반적으로 많이 쓰는 dejong function 말고, f3deceptive 와 같은 기만적인 문제들에 대해서 알아보겠습니다.
GA 알고리즘을 연구하시는 분께는 살짝 도움이 될 것 같습니다.
Posted by SHHyun

댓글을 달아 주세요

오랜만에 글을 포스팅 합니다.
이래저래 하고 있는건 많고 정리할 시간이 부족하다보니 이제야 포스팅합니다.

일반적으로 쓰이는 MUT 연산자는 다음과 같은 2가지가 있습니다.

1. Single MUT
2. Multi MUT

하나는 하나의 Bit 를 MUT 시키는 것이고 다른 하나는 여러개의 Bit 를 대상으로 MUT를 수행합니다.

1. Single MUT

  이것은 하나의 Bit 만을 MUT 시킵니다. 아주 간단하게 알아 볼 수 있습니다.

  (1) 선택연산자를 통하여 선택이 이루어진다.
 (2) 선택된 개체의 한 bit 를 선택하여 MUT 시킨다.

  예를 보면 간단하게 변화를 알아볼 수 있습니다.

 만약 다음과 같은 유전자가 있다면
 
  0 0 0 0 0 0 1 0

  이것이 선택되어 7번째 bit 를 Mutation 시킨다고 가정합니다.
  그렇다면 다음과 같이 변하는 것입니다.

  0 0 0 0 0 0 0 0

2. Multi MUT

  이것은 여러개의 Bit 를 MUT 시키는 것입니다. 이전것과 동일한 방식으로 이루어 집니다.

  만약  다음과 같은 유전자가 있다면

  0 0 0 1 1 0 1 0
 
  그리고 이것이 선택 되었다고 가정을 하고, 4~8 번째 bit 가 선택 되었다고 한다면
 
 0 0 0 0 0 1 0 1

 이런식으로 변화하게 됩니다.



오늘 살펴본 MUT 는 아주 간단한 연산자 입니다만 그 사용에 있어서 아주 조심해야 합니다.
이것은 파괴연산자라 불리는 것으로서 확률의 의외성을 바라고 이용하는 것입니다.
즉 이 연산이 너무 자주 수행되게 된다면, 실제 답을 잘 못찾는 현상이 나타나기도 합니다.
보통 GA 연산 수행시에 1 ~ 10% 정도의 확률로 수행하게 하는게 일반적입니다.
알고리즘의 테스트를 위해서라면 아예 수행을 하지 않는 경우도 있습니다.

다음 번에는 Selection 연산자에 대해서 알아보겠습니다.
Posted by SHHyun

댓글을 달아 주세요

이번에는 GA 의 핵심 연산자인 Crossover 연산자 입니다.

GA 의 연산자 중에서 가장 많은 연산을 수행하고
그만큼 중요도도 높은 Crossover 연산자 입니다.

수많은 방식의 연산자 들이 존재하지만 오늘은 밑에 있는 것에 대해서만 알아보겠습니다.

1. Onepoint crossover(Single)
2. Twopoint crossover(Multi)
3. Uniform crossover

위의 1,2 번 연산자는 대표적인 기본 연산자 이고, 거의 모든 bit 연산에서 쓰입니다.
3번은 거의 쓰이지 않지만 어떤 문제에는 쓰이기도 합니다. 그래서 소개하는 것입니다.

어쨌든 하나하나 알아보도록 하죠.

1. One-point Crossover(Single Crossover)

  Onepoint Crossover 는 Single Crossover 라고도 하고 GA 의 대표적 연산자 입니다.
  초기에 GA 가 만들어졌을때부터 사용된 연산자 입니다.
  가장 기본적이면서도 가장 많이 이용되고 있는 연산자 입니다.
  방식은 이전에 GA 소개 할때 보여 드렸던 것과 같은 방식입니다.

  (1) 랜덤한 수(point) 를 만들어내어 CX 할 위치 선정
  (2) Select 에 의해 선택된 두개의 개체에 대해 CX 수행

  이것이 끝입니다. 간단하죠.
  예를 들면 다음과 같습니다.

    1 0 0 0 1 1 1 0
    1 0 0 1 1 1 0 0  

위의 두 개체가 있다고 가정해봅시다. 그리고 point 가 4로 설정 되었다고 하면

    1 0 0 0 1 1 1 0
    1 0 0 1 1 1 0 0
            ^  <-- 바로 이 위치

결과는 다음과 같이 되는 것입니다.

    1 0 0 1 1 1 0 0
    1 0 0 0 1 1 1 0

  그리하여 개체는 발전해 나갈수도 있는 것이고, 더 성능이 안 좋아 질 수도 있는 것입니다.

2. Two-point Crossover (Multi Crossover)

Twopoint CX 는 Onepoint CX 가 발전된 방식 입니다. 문제의 특성에 따라 다르지만
대체적으로 Twopoint CX 가 Onepoint CX 보다 더 좋은 성능이 나오는 것으로 알려졌습니다.
  다음과 같은 방식으로 수행이 됩니다.

  (1) 랜덤한 수 (point) 를 두개를 만들어 낸다.
  (2) Select에 의해 선택된 두개의 개체에 대해 CX 를 수행

  Onepoint 와의 차이점이라면 단지 두개의 수를 만들어 낸다는 것입니다.
예를 보면 바로 이해할 수 있습니다.

  1 1 0 0 1 1 0 1
  1 0 1 1 1 0 1 1  

위와 같이 두 개체가 있다고 가정해 봅시다. 그리고 point 가 각각 2,4로 설정이 되면
 
  1 1 0 0 1 1 0 1
  1 0 1 1 1 0 1 1
      ^   ^ <-- 바로 이 두 위치
 
  결과는 다음과 같이 됩니다.

    1 0 1 1 1 1 0 1
    1 1 0 0 1 0 1 1

  최초의 point 에서부터 마지막 point 까지의 사이의 값들에 대한 CX가 이루어 지는 것입니다.
  어떤 특정 지점에 대해 좋은 형질만, 혹은 나쁜 형질만 CX 가 이루어 질 수 있는것이
  Twopoint CX 의 강점입니다.

3. Uniform Crossover

  Uniform Crossover 는 일반적으로 잘 쓰이는 연산자는 아니지만 가끔 쓰일때가 있습니다.
  방식은 다음과 같습니다.

  (1) Mask 를 설정해 줍니다.
  (2) 그 Mask 에 맞추어 선택된 두개의 개체의 CX 를 수행합니다.
 
  이것 역시 예만 보면 간단히 이해할 수 있습니다.

    1 0 0 0 0 1 1 1
    1 0 1 1 1 0 0 0

  다음과 같은 두 개체가 있다고 생각해 봅시다. 그리고 이것에 대해 UCX 를 수행하는겁니다.
  여기서 UCX 는 다른것과 다르게 Mask 를 설정해 줘야 합니다.
  임의에 설정에 따라 Mask 를 설정해 줄 수도 있고, 직접 해 줄 수도 있습니다.
  우리는 0 0 0 1 1 0 0 1 로 Mask를 설정했다고 가정해보죠.
  그리고 이 Mask 를 토대로 다음과 같이 연산을 수행합니다.
 
    1 0 0 0 0 1 1 1
    1 0 1 1 1 0 0 0
    0 0 0 1 1 0 0 1 <-- Mask

  Mask 는 1로 설정된 위치에 대해서만 서로를 CX시켜주는 역할을 합니다.
  그러므로 결과는 다음과 같이 됩니다.

    1 0 0 1 1 0 0 0
    1 0 1 0 0 0 0 1
 
  결과적으로 특정 위치에 대해서만 CX 를 시켜주는 용도로 이용되는 연산자입니다.


CX 연산자들은 개체의 형태에 따라 조금씩 달라지기는 합니다.
하지만 기본적으로 컴퓨터는 2진수를 사용하고 개체가 어떻게 표현이 되더라도
그것은 2진수로 변환할 수 있기에 위의 연산자를 이용하면 광범위한 CX 연산이 가능합니다.

다음에는 대표적인 Mutation 방식 2가지에 대해서 알아보도록 하겠습니다.
Posted by SHHyun

댓글을 달아 주세요

몇가지 용어에 대해서 정리해 보도록 하겠습니다.

사실 GA 에서는 크게 2가지의 알고리즘으로 나뉘어 있고
흐름에 의한 알고리즘 자체의 차이가 있을뿐이지
용어에 대해서는 차이가 없습니다.

하지만 GA 를 구현한 프로그램들마다
용어자체에 약간의 차이를 두고 구현되어 있는 경우가 있습니다.
그에 대해서 한번 생각해 보기 위해 용어에 대해 정리해 보는 것입니다.

가장 하위계층의 개체부터 개체의 조합. 그리고 연산자까지 정리해보도록 하겠습니다.

먼저 하나의 개체는 일반적으로 다음과 같이 되어 있습니다.

Chromosome - 유전자표현
Fitness - 적합도
OBJ(x) - 유전자표현을 10진수로 변환한것, 다른형태로 표현하기도 합니다.
parent1 -
parent2 - parent1과 2는 현재의 개체가 Crossover로 부터 다시 생성되었을 때
             이 두 개체의 부모개체가 되는 유전자의 번호입니다.

일반적으로 하나의 개체를 표현하는데에 저 다섯가지의 요소로서 구성됩니다.

저 개체는 Individual 이라고 표현하고 개체라고 합니다.

Individual < Population < Multi-population

이런식으로 되어 있습니다.

각각의 Individual 이 모인 집합을 Population 이라고 하고
Population 이 모인 집합을 Multi-population 이라고 합니다.

Multi-population 에 대해서는 나중에 소개를 하겠지만
대부분의 실제 알고리즘에서는 다수의 Population 을 이용해서
서로간의 연산 알고리즘이 이루어 집니다.
복잡해지는 관계로 다음에 추후 이야기 하겠습니다.

그리고 연산자에 대해서 간단히 용어정리를 하겠습니다.
CX = Crossover 를 의미하는 것입니다.
      제가 지난번에 Crossover 연산에 대해 간략하게 소개 했습니다.
      그런 식으로 이루어지는 일련의 연산들을 Crossover 라고 합니다.
      더 자세하게는 다음에 소개하겠습니다.
MUT = Mutation 을 의미합니다.
         역시 마찬가지로 다음에 소개 하겠습니다.
         (소개할 내용이 무지하게 많습니다;;)
SELECT = 말그대로 선택 연산자입니다.
INV = Inversion , 역위 연산자 입니다. 거의 쓰지 않습니다만
       몇몇 알고리즘에서는 여전히 이용합니다. 역시 나중에 설명하겠습니다.

사실 이 외에도 엄청나게 다양한 용어의 정리가 필요합니다.
하지만 가장 기본이 되는 저 틀은 거의 변하지 않습니다.

다음번에는 CX 연산자들에 대해서 소개하겠습니다.
몇회에 걸쳐서 소개해 보겠습니다.

Posted by SHHyun

댓글을 달아 주세요

오늘은 GA 의 간단한 예제에 대해서 올려봅니다.

우선 하나의 가정을 하죠.

다음과 같은 수식이 있고 그것의 범위를 다음과 같이 할당해 줍니다.
우리는 이 수식의 최대값을 알아내려고 하는 것입니다.

y = x^2 - 2*x + 4

x = [ -10 , 10 ]

이렇다고 가정을 해보는 것입니다.
위 문제는 누구라도 간단하게 구할수 있는 문제이지만 그냥 하나의 예로서 들어본 것입니다.

그렇다면 GA 의 흐름에서 이 문제를 어떤 식으로 풀어나가는지 알아보도록 하죠.

우리는 GA 연산에서 쓰일 몇가지 구체적인 변수에 대해 설정을 해 줘야 합니다.
우선 GA 에서 초기화에 몇가지의 개체를 이용할 것인지 설정해 줘야 하고,
몇개의 비트로서 그 개체에 대해 표현을 할지도 결정을 해 줘야 합니다.
어느정도 확률로서 Crossover 와 Mutation 연산을 수행하게 할지도 설정을 해 줘야 합니다.
그리고 몇 세대 정도 계산을 해 나갈지에 대해서도 설정을 해야 하죠

우선 초기 개체의 수를 설정을 합니다. 5개로 가정을 하고,
그리고 하나의 개체는 5개의 비트를 이용한다고 가정해 봅시다.
Crossover 와 Mutation 확률 90% 와 10%로 각각 설정을 한다고 가정 하죠.
그리고 5세대만 진행한다고 가정을 해 봅시다.

------------------------------------------------------------------------------------
먼저 여기서 설명드릴게 하나 있는데
5개의 비트를 이용해서 하나의 개체를 만들었는데,
그 개체를 x 의 범위에 한정 시킨 10진수로 변환을 해야 한다는 문제가 있습니다.
이 문제는 일반적으로 다음과 같은 방법으로 해결합니다.
  (Max - Min ) * (x의 개체를 10진수로 변환한것 / (2^개체의 비트수) - 1 ) + Min
이런방식으로 해결을 합니다.
만약 지금과같이 5개의 비트로서 Max값이 10이고 Min 값이 -10 이고
x 가 11111 이 나왔다고 가정을 하죠. 그럼 이것을 10진수로 바꾸면 31이 됩니다.
  (10 - -10 ) * ( 31 / 2^5 -1 =31 ) - 10
이라고 한다면 20 * ( 1 ) - 10 으로 최대값 10이 나오게 됩니다.
------------------------------------------------------------------------------------

다음과 같이 초기 개체가 생성 되었다고 가정을 해 보죠
1. 10101 ==> 21 ==> 3.5484
2. 11000 ==> 24 ==> 5.4839
3. 00010 ==> 2  ==> -8.7097
4. 00101 ==> 5  ==> -6.7742
5. 10001 ==> 17 ==> 0.96774
  원래개체 ==> 10진수로 변환 ==> -10~10의 범위 한정

그리고 이것에 대해 위에서 설명드린 10진수로의 변환을 거친 후,
평가의 작업을 하게 됩니다.

위의 우리가 가정한 y의 방정식인 x^2 - 2*x + 4 에 대입을 하면
1. 9.4943
2. 23.1054
3. 97.2783
4. 63.4382
5. 3.0010
이 값을 각 개체의 Fitness(적합도) 값으로 갖게 되는 것입니다.

그리고 우리는 이 값을 토대로 선택의 작업을 하게 됩니다.
균등한 선택을 이용한다고 가정하면 각각의 개체들은 2번정도로 거의 동등한 선택을 받게됩니다. 거의 2번이라고 한다는 것은 3번이 선택될수도 있고 1번이 선택될수도 있기 때문입니다.
어디까지나 랜덤한 확률에 의한 선택이기 때문입니다.
우선 편하게 1,2 2,4 4,5 가 Crossover 에 이용되었다고하고 3번이 Mutation 되었다고 합시다.

그렇다면 Crossover 연산이 이루어지게 되는데 이연산은 각각의 개체들을 서로 교배시킨다고 말씀 드렸습니다. 이 연산에도 많은 방식이 있는데 우선 One Point Crossover 를 이용한다고 해보죠. 이것은 다음과 같은 방식의 연산입니다. 자세한 것은 추후 설명 하겠습니다.

현재 1,2 번 개체가 선택 되었고, 만약 Crossover Point 를 4번이라고 잡았다고 합시다.
Crossover Point 라는 것은 그 위치에서부터 뒤에있는 모든 비트에 대해 서로 교배를 하겠다는 것입니다.

그러므로 1,2 번 개체는 10101 과 11000 이었으므로 다음과 같이 계산이 되게 됩니다.
  1 0 1 0 1  
         | | <--- 두 개체의 교환.
  1 1 0 0 0

1번은 10100 2번은 11001  이런식으로 형태가 변하게 되는 것입니다.
그리고 뒤이어 2,4 4,5 번에 대해서도 연산을 수행하게 되면 각각 다음과 같이 됩니다.

2번 11001 4번 00101 --> 변환후 2번 11001 4번 00101
4번 00101 5번 10001 --> 변환후 4번 00101 5번 10001

그렇게 Crossover 연산이 끝난 후에는 각각의 유전자는 다음과 같은 형태를 지니게 됩니다.
1. 10100
2. 11001
3. 00010
4. 00101
5. 10001

이제 Mutation 연산을 수행하게 됩니다. 여기서는 3번에 대해 4번째 비트가 Mutation 되었다고 가정 합니다.

00010 --> 00000 이런식으로 선택된 비트를 반전시켜 버리는 것입니다.

결국 한세대의 연산이 모두 끝난후에 유전자는 다음과 같이 바뀌었습니다.

1. 10100 ==> 2.9032
2. 11001 ==> 6.1290
3. 00000 ==> -10
4. 00101 ==> -6.7742
5. 10001 ==> 0.96774

그리고 이 유전자에 대해 재 평가 작업이 이루어지게 됩니다.

결론적으로
1. 6.6222
2. 29.3066
3. 124
4. 63.4382
5. 3.0010

이런 Fitness 값을 갖게 되고 GA 는 결과적으로 x 값 -10 y 값 124 의 최대값에 도달했습니다.

GA 의 알고리즘은 이와 같은 방식으로 수행이 되는 것입니다.
각각의 연산자들은 매우 많은 종류가 있고
여기서는 가장 기본적인 연산자들에 대해서만 예제를 수행했습니다.
내일은 용어에 대해서 정리를 해보겠습니다.
각 알고리즘의 형태마다 쓰이는 용어가 조금씩 차이를 보이기때문에
조금은 정리해볼 필요가 있습니다.

P.S 제가 이런것을 하는데는 제 개인이 배운것에 대한 정리도 하는 것이고 
     다른 사람들로부터 제가 잘못 알고 있거나 틀린것에 대해서 알고자 하는 것도 있습니다.

Posted by SHHyun

댓글을 달아 주세요

GA 는 하나의 알고리즘으로서 기본적으로 다음과 같은 순서로 동작합니다.
(여기서 설명하는 것은 일반적인 알고리즘이고 변형된 알고리즘으로서 Steady-State 알고리즘이 있습니다.)

1. 초기화(Initialize)

  유전자 개체를 초기화 합니다.
  임의로 지정한 수치 만큼의 유전자를 생성해 내는 것입니다.

2. 평가(Evaluate)

위에 생성된 유전자 개체에 대해 평가를 합니다.
  평가의 기준은 사용자가 만드는 것입니다.
  생성된 유전자가 문제에 어느정도 적합한 유전자 인지 평가하는 것입니다.
 
3. 반복(Loop)
 
  여기서 부터는 몇가지 반복작업이 계속 이루어 집니다.
  반복이 멈추는 조건은 사용자가 지정한 최대 세대수[1]에 도달하거나
사용자가 지정한 최대조건에 도달 했을 경우 입니다.
  멈추지 않을경우 밑에 작업을 순서대로 반복 수행 하게 됩니다.

  (1) 선택(Selection)

    선택도 하나의 연산입니다.
    여러가지 방식이 있으며 가장 평가가 좋은 유전자를 선택할 수도 있습니다.
    아니면 랜덤하게 선택할 수도 있는 것입니다.
    문제에 맞게 선택연산자를 선택해 주면 됩니다.
    여기서 선택된 유전자는 다음의 교배, 돌연변이 연산자에 이용 됩니다.

(2) 교배(Crossover)
 
    유전자 알고리즘의 가장 핵심이 되는 부분이라고 할 수 있습니다.
    각각의 선택된 유전자 개체에 대해 교배가 이루어 지는 부분입니다.
    유전자의 일부분을 다른 상대방 유전자의 일부분과 교체 하는 등의 연산입니다.
    이것을 통해 개선이 이루어질 수 있습니다. 물론 성능이 떨어질 수도 있죠.
    대부분의 연산은 이것을 통해 이루어 집니다.

  (3) 돌연변이(Mutation)

    돌연변이 연산은 유전자의 일부분을 임의대로 변경해버리는 것입니다.
    교배와 다른점이라면 교배는 한 쌍의 유전자를 서로 교체 하는 등 같이 연산되는 것이지만
    이것은 하나의 유전자의 일부분을 랜덤하게 교체시켜 버리는 것입니다.
    그것으로서 유전자가 파괴될수도 있지만 의외로 좋은 유전자가 될수도 있기때문에
    아주 적은 확률로서 이루어지게 합니다.

  (4) 재조합(Recombination)

    이것은 위의 교배와 돌연변이의 연산자로서 새로 변경된 유전자들을 모아서 새로운 세대를
    생성하는 것입니다. 이것이 이루어지면 한 세대가 지났다고 할 수 있습니다.

  (5) 평가(Evaluate)
 
    다시 평가 작업입니다. 새로 교배와 돌연변이를 통해 생성된 유전자를 평가하는 것입니다.
    유전자의 성능의 개선여부에 대해 확인할 수 있습니다.
   
  (6) 통계(Statistics)

    평가가 이루어진 유전자에 대한 통계를 냅니다.
    주로 개체의 최대,최소,평균 성능에 대해 통계를 냅니다.


위와 같은 반복적 작업을 통해 개체의 상태를 개선시켜 나가고 문제의 해답을 알아내는 알고리즘이 GA 입니다.

최대한 수학적인 요소는 제거하고 가장 간단한 상태의 GA 에 대해 설명했습니다. 내일은 간단한 예에 대해 올려보도록 하겠습니다.

Posted by SHHyun

댓글을 달아 주세요

우선 크게 분류를 나눠보고 제가 어느 분야를 공부하고 있는지를 말씀드리자면
Artificial Intelligence 와 Computational Intelligence 로 구분할 수 있는데
A.I. 는 흔히 알고 있는 인공지능 이고
C.I. 는 계산지능이라고 표현하면 올바를것 같습니다.
저는 C.I. 쪽을 공부하고 있습니다.
이것은 Fuzzy System(FS), Neural Network(NN), Evolutionary Computation(EC) 등 으로 구분할 수 있는데
저는 이중에서도 Evolutionary Computation 쪽을 공부하고 있습니다.
그 중에서도 Genetic Algorithm 과 Genetic Programming 에 대해서 공부를 하고 있습니다.
유전적인 이론(예: 다윈의 진화론)들을 토대로 이것을 연산에 이용하는 것인데요

Genetic Algorithm 에 대해 간단히 말씀드리면
어떤 문제에 대한 해결책으로서의 유전자를 생성후에 이것을 진화시켜 나가는 것이죠
진화 시켜 나가는 방식이 바로 다윈의 진화론이나 교육시스템 과 같은 사회적, 자연적 현상들을
모티브로서 가져온 것들입니다.
(물론 인위적인 요소들이 많이 있습니다만 실제적으로 우리는 자연적 현상들을 더 많이 적용시킨것을 볼 수 있습니다.)
GA 에 대해서는 많은 자료들이 있기때문에 검색해보시면 잘 알수 있을거예요.

GA 에 대한 실질적 예제와 방식은 다음에 정리해 보렵니다.

이 블로그에 앞으로 제가 배우고 있는 것들과 연구하고 있는 것들에 대해서
정리해서 올려놓을 생각입니다.

Posted by SHHyun

댓글을 달아 주세요