달력

06

« 2017/06 »

  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  •  
2010.08.24 17:01

watchmaker strings example 분석(2) Watchmaker2010.08.24 17:01

다시한번 실행코드를 보자.
    public static String evolveString(String target)
    {
        StringFactory factory = new StringFactory(ALPHABET, target.length());
        List> operators = new ArrayList>(2);
        operators.add(new StringMutation(ALPHABET, new Probability(0.02d)));
        operators.add(new StringCrossover());
        EvolutionaryOperator pipeline = new EvolutionPipeline(operators);
        EvolutionEngine engine = new GenerationalEvolutionEngine(factory,
                                                                                 pipeline,
                                                                                 new StringEvaluator(target),
                                                                                 new RouletteWheelSelection(),
                                                                                 new MersenneTwisterRNG());
        engine.addEvolutionObserver(new EvolutionLogger());
        return engine.evolve(100, // 100 individuals in the population.
                             5, // 5% elitism.
                             new TargetFitness(0, false));
    }

한줄씩 해석해 보자.


        StringFactory factory = new StringFactory(ALPHABET, target.length());

이것은, factory의 속성에 알파벳 27자를 담고, 추출하려는 10개의 숫자를 저장한다.


        List> operators = new ArrayList>(2);
        operators.add(new StringMutation(ALPHABET, new Probability(0.02d)));
        operators.add(new StringCrossover());

operators 컬렉션 첫번째에 돌연변이 표현 객체인 StringMutation을 넣고, 알파벳27자와 돌연변이 확율값 0.02를 넣는다. 두번째엔, 교배객체로 교배포인트 변수엔 1는 넣는데, 이는 '1점교배'를 한다는 뜻이고, 하나의 부모개체를 교배할때, 한번의 분할점만 사용한다는 뜻이다. 가능성(probability)는 1.0 이므로 100%를 뜻한다.


        EvolutionaryOperator pipeline = new EvolutionPipeline(operators);

operators를 저장하고 있다가, 이후 진화과정에서 다시 연결한다.


        EvolutionEngine engine = new GenerationalEvolutionEngine(factory,
                                                                                 pipeline,
                                                                                 new StringEvaluator(target),
                                                                                 new RouletteWheelSelection(),
                                                                                 new MersenneTwisterRNG());

EvolutionEngine 을 생성하는데, 위에서 생성한 factory, pipeline 변수를 넘기고, 추가로  StringEvaluator 객체를 생성하는데 이는, 'WATCHMAKER'를 저장하고, 각 글자를 배열에 담아서 진화적합도에 쓰인다. RouletteWheelSelection는 진화 선택 메커니즘으로 ' RouletteWheelSelection'을 쓰겠다는 것을 선언한 것이고, MersenneTwisterRNG 는 Mersenne Twister 알고리즘을 이용해서 랜덤하게 대상객체(10자리 스트링)를 생성하겠다는 뜻이다.
이러한 변수들로 EvolutionEngine 객체를 생성한 것이다.


    return engine.evolve(100, 5, new TargetFitness(0, false));

실행결과를 리턴하는데, 엔진에서 evolve()메서드를 실행한다. 이때 인자로 100은 모집단(전체수)를 '100'으로 한정하고, '5'는 엘리티즘을 5%로 지정한 것이고,  TargetFitness(0, false)는 대상 적합도를 확정적으로 정하는 것이다.(예제는 알파벳-'WATCHMAKER'-이라는 확정적인 적합도 목적을 달성하는 100% 적합도 예제이다.)

이렇게 해서, 진화 메서드를 실행한다. 이 실행자(StringExample.java)는 이렇게 진화를 실행하기 위한 환경을 설정하는게 전부다. 더 핵심적인 내용은 이러한 조건으로 부터 진화를 행하는 실제 코드인데 이는 은닉되어 있다. 결국 engine.evolve()메서드는 내부적으로 evolvePopulation()메서드를 실행하면서 루프를 돌며 진화 메커니즘을 실행한다.

그 메서드 인자는 다음과 같이 받으며, 해당 소스코드는 다음에 계속 한다.
    public List> evolvePopulation(int populationSize,
                                                        int eliteCount,
                                                        Collection seedCandidates,
                                                        TerminationCondition... conditions)

신고
Posted by summerwars
2010.08.24 15:08

watchmaker strings example 분석(1) Watchmaker2010.08.24 15:08


watchmaker-examples 프로젝트의 예제중 strings라는 데모를 분석해 본다. 분석전에 watchmaker framework이 무얼하는것인지 알아야 한다. watchmaker는 진화알고리즘을 자바언어로 구현한 프로젝트 중에 하나다. 진화알고리즘 안에 여러가지 비슷한 개념의 알고리즘이 있다. 유전알고리즘, 진화전략, 유전자 프로그래밍 등 비슷하지만, 다른 알고리즘들이 있고, 모두 활발히 연구되었던 분야이다. watchmaker는 The Blind Watchmaker(눈먼시계공) 라는 책에서 따온 것으로 보이고, 유명한 유전학자인 리차드 도킨스의 저서이다.

따라서, watchmaker가 연상되는 것은 어떤 형태든, 진화알고리즘들-EAs(Evolutionary algorithms)-로 연상시킬수 있다. 또한 이런것들이 도대체 왜 필요하고, 무엇에 쓰이는지는 등은, 좀 긴 이야기이니, 일단 궁금하면 구글링 해보거나, 메뉴얼을 참고 하기 바란다.(http://watchmaker.uncommons.org/manual/index.html)

이제 분석에 들어가자. 2010/08/20 - [Watchmaker] - Watchmaker Demo 테스트하기 에서 데모를 테스트 해봤거나, 2010/08/24 - [Watchmaker] - watchmaker framework 0.7.1 maven module project 변환 를 따라 해봤다면, 이미 관련 소스를 확보했을 것이다. (안해도 상관없다) strings 데모는 매우 간단하다. jar를 실행보다, Unit Test로 기능을 확인해 보고, 소스코드 구성과 어떤 원리로 작동하는지 알아보자.

1) 일단 어떻게 동작하는지 결과 보기
watchmaker-examples 프로젝트의 strings Test 코드중 StringsExamplesTest.java 파일이 있다. 이를 실행해 보자(watchmaker는 모든 테스트가 TestNG로 작성되었다. Junit으로 변환해도 되지만, 여기선 소스상태 그대로 테스트 해본다.)
public class StringsExampleTest
{
    @Test
    public void testEvolution()
    {
        String target = "WATCHMAKER";
        String result = StringsExample.evolveString(target);
        assert result.equals(target) : "Evolution returned wrong result: " + result;
    }
}


첫번째, 결과는 28회 반복만에 답을 찾아 냈다. 다시 한번 실행시켜 보자. 두번째 결과는 45회 만에 답을 찾아 냈다. 본 테스트의 문제는 "WATCHMAKER"라는 글짜를 GA로 맞춰가는 예제이다.

첫번째 실행 결과 로그

첫번째 테스트 결과(28회)


두번째 실행결과 로그

두번째 테스트 결과(45회)


이후 여러번 테스트해 보고 각각의 결과들이 대부분 다르다는 것을 알수 있을 것이다.(나는 10번 정도 해봤는데 모두 달랐다.) 본예제에 대한 설명은 개념적인 설명은 http://watchmaker.uncommons.org/manual/ch01.html#d0e62 에 잘 나와 있다. 여기서는 소스코드 추적을 통해서 알아 본다. 처음 시작점은 바로 방금 실행한, 테스트코드 부터이다.

2) strings 데모 진화 실행자 추적하기
소스코드를 잠깐 추적해보니, 설명한다는게 쉽지 않다. 아무튼 그래도 설명해보겠다. Unit Test는 StringsExampels.java의 main() 메서드를 호출하는데, 이는 입력받은 최종목적 스트링('WATCHMAKER')를 적합도 기준으로 보고, 유전알고리즘에 기본이 되는, 첨자들을 함께 넣어 진화엔진을 얻고, 그로 부터 진화 시뮬레이션을 실행시킨다. 
    public static String evolveString(String target)
    {
        StringFactory factory = new StringFactory(ALPHABET, target.length());
        List> operators = new ArrayList>(2);
        operators.add(new StringMutation(ALPHABET, new Probability(0.02d)));
        operators.add(new StringCrossover());
        EvolutionaryOperator pipeline = new EvolutionPipeline(operators);
        EvolutionEngine engine = new GenerationalEvolutionEngine(factory,
                                                                                 pipeline,
                                                                                 new StringEvaluator(target),
                                                                                 new RouletteWheelSelection(),
                                                                                 new MersenneTwisterRNG());
        engine.addEvolutionObserver(new EvolutionLogger());
        return engine.evolve(100, // 100 individuals in the population.
                             5, // 5% elitism.
                             new TargetFitness(0, false));
    }

여기서 첨자들이란, 적합도 함수(new StringEvaluator(target)), 돌연변이 변수(new StringMutation(ALPHABET, new Probability(0.02d))), 교배규칙(new StringCrossover()), 선택방법(new RouletteWheelSelection()) 등을 말한다. 각각 행위에서 사용되는 기법들이 다양하게 있지만, 현 소스코드에서 보이는 것은 RWS(Roulette Wheel Selection ) 정도이다. 이에 대한 정보는 http://yunsunghan.tistory.com/496 과 http://yunsunghan.tistory.com/497 에서 참조하기 바란다.

3) 실행코드의 한계
아무래도, GA에 대한 기본적인 지식이 있다는 전제하에 설명하는 것이 좋을듯 하다. 이론적인 사실을 이해하지 못한 상태에서 코드를 바라본다면 너무 어렵게 느껴지기 때문이고, 왜 그러는지 알기 힘들수 있다. GA에 대한 이해는 단순하게 보면, 몇가지 프로세스를 타는 알고리즘이구나 라고 생각할수도 있지만, 그 안에 선택 가능한 조합이 많으며, 그 조합들의 특성이 엔진의 특성을 나타낸다. 그 틀로 만들어 낼수 있는 로직의 효율성 역시 천차만별이기에, 단번에 좋은 것을 만들어 내기가 어렵다. 많은 시뮬레이션과 검증이 필요하다. 아니면 엉뚱한 결과로 진화될수도 있다.

왜 watchmaker에 메뉴얼이 부실한지 대략 짐작이 간다. 여기서 부터는 더이상 설명하기가 곤란한게, 이론적인것으로 흐를수 밖에 없고, 그것들은 구현체 프로젝트(이 watchmaker 같은)에서는 그리 비중있게 다뤄야 할 것은 아니다. 구현체 프로젝트에서 다뤄야 할것은 각 도메인에서 구현한 EA 조합 구성이 해당 도메인의 기대치에 얼마나 적합한가, 또 신뢰도는 어느정도인가가 프로그램 소스에 대한 평가(원하는 성능)의 기준으로 다뤄저야 할것이기 때문일 것이다.

다음에는 그래도 본 예제의 조합이 어떤 구성인지 다뤄본다.
신고
Posted by summerwars

Git(git://github.com/dwdyer/watchmaker.git) 에서 받은후 메인 디렉토리에 parent pom.xml을 위치시키고, 각 module 프로젝트에 해당하는, framework, swing, examples 디렉토리에 각각의 pom.xml을 위치시키고 빌드하면 된다.

Git Repository엔 기본으로 Ant를 사용하고, Mahout연동을 위해서 몇몇 프로젝트에 maven pom.xml이 있기는 하나, dependency등이 맞춰져 있지 않는다.

이클립스에서 보려면, parent 디렉토리에서 mvn eclipse:eclipse 실행후 import 하면된다.

신고
Posted by summerwars
2010.08.20 18:11

Watchmaker Demo 테스트하기 Watchmaker2010.08.20 18:11

1) 먼저 Git 로 소스를 다운 받는다.
git clone git://github.com/dwdyer/watchmaker.git


2) 받은 위치에서 Build.xml 위치로 이동후 Ant 빌드를 한다. (단, Ant는 1.7.1이상 버전이여야 한다 - 1.7.0에서 했더니 오류남)
ant dist


3) 테스트가 필요하면 역시 ant 로 테스트 한다.
ant release


4) jar파일로 직접 테스트 하기
만약, 원한다면, 빌드된 watchmaker-examples.0.7.1.jar를 찾아서 실행하면 된다.
java -jar watchmaker-examples.0.7.1.jar {옵션}

옵션은 biomorphs, bits, gp, monalisa, salesman, strings, sudoku 등을 테스트 할수 있다.

아래는 그중 monalisa를 돌려본후, 그 변화를 켑쳐한 것이다.
(더 이상은 시간이 없어서 못돌리고 껐음)
신고
Posted by summerwars
2010.08.20 16:32

Watchmaker Framework 관련 링크 Watchmaker2010.08.20 16:32



(watchmaker framework logo에 대한 이야기)


1) 홈페이지 : http://watchmaker.uncommons.org

2) 메뉴얼(Reference는 아닌...) : http://watchmaker.uncommons.org/manual/index.html

3) 저장소 : http://github.com/dwdyer/watchmaker

4) 커뮤니티 : http://groups.google.com/group/watchmaker

5) EA에 대해서 읽어 볼만한 내용들...

신고
TAG EA, GA, Watchmaker
Posted by summerwars


티스토리 툴바