유전 프로그래밍을 위한 적응 연산자 메커니즘

Abstract

their performances are competitive with systems without an adaptive operator mechanism. However they showed some drawbacks, which we discuss. To overcome them, we suggest three variants on operator selection, which performed somewhat better.

We have investigated evaluation of operator impact in adaptive operator mechanism, which measures the impact of operator applications on improvement of solution. Hence the impact guides operator rates, evaluation of operator impact is very important in adaptive operator mechanism. There are two issues in evaluation of operator impact: the resource and the method. Basically all history information of run are able to be used as resources for the operator impact, but fitness value which is directly related with the improvement of solution, is usually used as a resource. By using a variety of problems, we used two kinds of resources: accuracy and structure in this thesis. On the other hand, although we used same resources, the evaluated impacts are different by methods. We suggested several methods of the evaluation of operator impact. Although they require only small change, they have a large effect on performance.

Finally, we verified adaptive operator mechanism by applying it to a real-world application

a modeling of algal blooms in the Nakdong River. The objective of this application is a model that describes and predicts the ecosystem of the Nakdong River. We verified it with two researches: fitting the parameters of an expert-derived model for the Nakdong River with a GA, and modeling by extending the expert-derived model with TAG3P.

유전 프로그래밍은 모델 학습에 효과적인 진화 연산 알고리즘이다. 유전 프로그래밍은 다양한 파라미터를 가지고 있는데, 이들 파라미터의 값은 대체로 주어진 문제에 맞춰 사용자가 직접 조정한다. 유전 프로그래밍의 성능은 파라미터의 값에 따라 크게 좌우되기 때문에 파라미터 설정에 대한 연구는 진화 연산에서 많은 주목을 받고 있다. 하지만 아직까지 효과적으로 파라미터를 설정하는 방법에 대한 보편적인 지침이 없으며, 많은 실험을 통한 시행착오를 거치면서 적절한 파라미터 값을 찾는 방법이 일반적으로 쓰이고 있다.

본 논문에서 제시하는 적응 연산자 메커니즘은 여러 파라미터 중 유전 연산자의 적용률을 설정해 주는 방법으로, 학습 중간중간의 상황에 맞춰 연산자 적용률을 자동적으로 조정한다. 본 논문에서는, 기존의 적응 연산자 방법을 다양한 유전 연산자를 가진 문법 기반의 유전 프로그래밍인 TAG3P에 적용하고 새로운 적응 연산자 방법을 개발함으로써, 적응 연산자 메커니즘의 적용 범위를 유전 프로그래밍 영역까지 확장하였다. 기존의 적응 연산자 알고리즘을 TAG3P에 적용시키는 연구는 성공적으로 이루어졌으나 몇 가지 문제점을 드러내었다. 이 문제점은 본문에서 후술한다. 이 문제점을 해결하기 위해 유전자 선택에 대한 새로운 변형 알고리즘을 제시하였고, 이는 기존 알고리즘과 비교하여 더 좋은 성능을 보여주었다.

한편으로 유전 연산자가 해의 향상에 미치는 영향을 측정하는 연산자 영향력 평가에 대한 연구도 진행하였다. 적응 연산자 메커니즘에서는 측정된 영향력을 바탕으로 연산자의 적용률을 변화시키기 때문에 영향력 평가는 적응 연산자 메커니즘에서 매우 중요하다. 이 연구에서는 어떤 정보를 이용하여 영향력을 측정할 것인지, 그리고 어떤 방법을 이용하여 영향력을 측정할 것인지의 두 가지 주요 쟁점을 다룬다. 연산자 영향력 평가에는 학습 과정의 모든 정보가 사용될 수 있으며, 대체로 해의 향상과 직접적인 관련이 있는 적합도를 이용한다. 본 논문에서는 다양한 문제를 이용하여 정확도와 구조에 관련된 두 지표를 영향력 평가에 이용해보았다. 한편으로 같은 정보를 이용하더라도 그것을 활용하는 방법에 따라 측정되는 영향력이 달라지는데, 본 논문에서는 작은 변화를 통해서도 큰 성능 변화를 야기시킬 수 있는 영향력 평가 방법을 몇가지 소개한다.

마지막으로 적응 연산자 메커니즘을 실제 문제에 적용함으로써 유용성을 확인하였다. 이를 위해 사용된 실제 문제는 낙동강의 녹조 현상에 대한 예측으로, 낙동강의 생태 시스템을 묘사하고 예측하는 모델을 개발하는 것을 목적으로 한다. 2가지 연구를 통해 유용성을 확인하였다. 우선 전문가에 의해 만들어진 기본 모델을 바탕으로, 유전 알고리즘을 이용하여 모델의 파라미터를 최적화 하였고, 그리고 TAG3P를 이용하여 기본 모델의 확장하고 이를 통해 새로운 모델을 만들어 보았다.

Genetic programming (GP) is an effective evolutionary algorithm for many problems, especially suited to model learning. GP has many parameters, usually defined by the user according to the problem. The performance of GP is sensitive to their values. Parameter setting has been a major focus of study in evolutionary computation. However there is still no general guideline for choosing efficient settings. The usual method for parameter setting is trial and error.

The method used in this thesis, adaptive operator mechanism, replaces the user's action in setting rates of application of genetic operators. adaptive operator mechanism autonomously controls the genetic operators during a run. This thesis extends adaptive operator mechanism to genetic programming, applying existing adaptive operator algorithms and developing them for TAG3P, a grammar-guided GP which supports a wide variety of useful genetic operators. Existing adaptive operator selection algorithms are successfully applied to TAG3P