오랜만에 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
보시면 아주 좋을 논문들입니다. (마지막 논문은 수학적 지식이 없으시면 절대 이해하기 어렵습니다.)
크게 언급할 부분은 아니지만, 이부분에 대해 연구하시는 대다수의 분들이 매번 느끼시는 부분이리라고 사료됩니다.
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
보시면 아주 좋을 논문들입니다. (마지막 논문은 수학적 지식이 없으시면 절대 이해하기 어렵습니다.)