8. 많이 쓰이고 있는 GA 엔진 몇가지 소개

안녕하세요.

오랜만에 포스팅 입니다.

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 에 대해서 소개하고 올려놓게 되지 않을까 싶습니다.