지난번에 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

댓글을 달아 주세요

안녕하세요.

오랜만에 포스팅 입니다.

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

댓글을 달아 주세요