함수합성법은 주어진 입출력 데이터 쌍으로부터 입출력관계를 충족하는 함수를 예측하는 것으로, 특성을 알 수 없는 시스템을 제어할 때에 필수적이다. 일반적으로 시스템은 비선형인 성질을 갖는 경우가 많고, 함수 합성에 취급하는 변수, 정수, 제약 등으로 조합된 문제가 발생하기가 쉽다. 그 함수를 합성하는 방법 중 한 가지로 유전적 프로그래밍이 제안되고 있다. 이것은 함수를 트리구조로 표시한 함수 트리에 유전적 조작을 적용하여, 입출력 관계를 충족하는 함수 트리를 탐색하는 방법이다. 본 논문에서는 기존의 유전적 프로그래밍에 의한 함수 합성법의 문제점을 지적하고, 새로운 4종류의 개선법을 제안한다. 즉, 함수 트리를 탐색할 때에 함수가 복잡하게 되는 것을 방지하기 위하여 함수 트리의 성장 억제, 조기 수렴을 목표로 하는 국소 탐색법의 채택, 함수 트리 내의 필요 없이 길어지는 요소의 효과적인 삭제, 대상으로 하는 문제의 특성을 이용하는 방법이다. 이러한 개선법을 이용할 경우, 기존의 유전적 프로그래밍에 의한 함수 합성법보다도 짧은 시간에 우수한 구조의 함수 트리가 구해지는 것을 2-spirals 문제에 대하여 컴퓨터 시뮬레이션을 통하여 확인하였다.
함수합성법은 주어진 입출력 데이터 쌍으로부터 입출력관계를 충족하는 함수를 예측하는 것으로, 특성을 알 수 없는 시스템을 제어할 때에 필수적이다. 일반적으로 시스템은 비선형인 성질을 갖는 경우가 많고, 함수 합성에 취급하는 변수, 정수, 제약 등으로 조합된 문제가 발생하기가 쉽다. 그 함수를 합성하는 방법 중 한 가지로 유전적 프로그래밍이 제안되고 있다. 이것은 함수를 트리구조로 표시한 함수 트리에 유전적 조작을 적용하여, 입출력 관계를 충족하는 함수 트리를 탐색하는 방법이다. 본 논문에서는 기존의 유전적 프로그래밍에 의한 함수 합성법의 문제점을 지적하고, 새로운 4종류의 개선법을 제안한다. 즉, 함수 트리를 탐색할 때에 함수가 복잡하게 되는 것을 방지하기 위하여 함수 트리의 성장 억제, 조기 수렴을 목표로 하는 국소 탐색법의 채택, 함수 트리 내의 필요 없이 길어지는 요소의 효과적인 삭제, 대상으로 하는 문제의 특성을 이용하는 방법이다. 이러한 개선법을 이용할 경우, 기존의 유전적 프로그래밍에 의한 함수 합성법보다도 짧은 시간에 우수한 구조의 함수 트리가 구해지는 것을 2-spirals 문제에 대하여 컴퓨터 시뮬레이션을 통하여 확인하였다.
The method of function synthesis is essential when we control the systems not known their characteristic, by predicting the function to satisfy a relation between input and output from the given pairs of input-output data. In general the most systems operate non-linearly, it is easy to come about pr...
The method of function synthesis is essential when we control the systems not known their characteristic, by predicting the function to satisfy a relation between input and output from the given pairs of input-output data. In general the most systems operate non-linearly, it is easy to come about problem is composed with combinations of parameter, constant, condition, and so on. Genetic programming is proposed by one of function synthesis methods. This is a search method of function tree to satisfy a relation between input and output, with appling genetic operation to function tree to convert function into tree structure. In this paper, we indicate problems of a function synthesis method by an existing genetic programming propose four type of new improved method. In other words, there are control of function tree growth, selection of local search method for early convergence, effective elimination of redundancy in function tree, and utilization of problem characteristic of object, for preventing function from complicating when the function tree is searched. In case of this improved method, we confirmed to obtain superior structure to function synthesis method by an existing genetic programming in a short period of time by means of computer simulation for the two-spirals problem.
The method of function synthesis is essential when we control the systems not known their characteristic, by predicting the function to satisfy a relation between input and output from the given pairs of input-output data. In general the most systems operate non-linearly, it is easy to come about problem is composed with combinations of parameter, constant, condition, and so on. Genetic programming is proposed by one of function synthesis methods. This is a search method of function tree to satisfy a relation between input and output, with appling genetic operation to function tree to convert function into tree structure. In this paper, we indicate problems of a function synthesis method by an existing genetic programming propose four type of new improved method. In other words, there are control of function tree growth, selection of local search method for early convergence, effective elimination of redundancy in function tree, and utilization of problem characteristic of object, for preventing function from complicating when the function tree is searched. In case of this improved method, we confirmed to obtain superior structure to function synthesis method by an existing genetic programming in a short period of time by means of computer simulation for the two-spirals problem.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
또한, 그 기본 함수로 복잡한 함수를 합성할 때에는 함수의 규모가 커지는 경향이 있다. 그러므로, 본 논문에서는 기본 함수에 자유도가 있으므로, 대역적으로 탐색하는 성질을 갖는 유전적 프로그래밍에 의한 함수 힙성에 주목한다. 유전적 프로그래밍에 의한 함수 합성의 공학적 응용 예에는 시계열 예측 문제, 패턴인식 문제, 부울 함수 합성 문제 등이 있다.
여기서, 구해진 근사함수는 가장 단순한 구조로 되는 것이 중요하다. 본 논문에서는 이와 같은 근사함수 구를 GIF) 의하여 생성하는 것을 목적으로 한다.
본 논문에서는 우선 함수 합성법으로 샘플 GP를 이용할 때의 문제점을 지적하였다. 다음에는 그 문제점의 개선과 효율적인 탐색을 목적으로 함수 트리의 성장 억제, 국소 탐색법에 의한 정수의 최적화, compact화의 적용법, 대상 문제 특성의 부분함수로 이용하는 4가지의 개선법을 제안하였다.
수 없는 것이 현실이다. 이러한 점에 착안하여 태양의 흑점 수를 예측하는 실험을 진행하고 있지만 아직 완료되지 않은 관계로 다음 발표로 미루고자 한다.
가설 설정
이 함수 트리에는 정수 노드가 3개 포함되어 있는데, 그중에서 3.2의 정수 노드가 선택되었다고 가정한다. 이때 최소 단위를 3.
제안 방법
유전적 프로그래밍은 교차나 돌연변이 등의 유전적 operator를 트리 구조에 적용하고, 목표로 하는 프로그램이나 개념 트리를 탐색하는 방법이다[6], [7]. 본 논문에서 대상으로 하는 함수 합성에 있어서는 트리 구조의 개체가 함수 합성에 대응하고, 각 함수 트리는 함수의 입력이 되는 변수나 정수, 연산자로 구성된다. 이러한 요소는 대상이 되는 시스템에 따라 다르다.
샘플 GP는 계산량 이방 대하기 때문에, 효율적인 탐색을 위한 몇 가지 방법이 제안되고 있다[8], [9], [11], [12], [15]. 그러나, 이러한 개선법을 적용할 수 있는 문제가 한정되어 있으므로 샘플 GP와 마찬가지로 우연성에 의존하는 경우가 많으므로, 본 논문에서는 2-spirals 문제에 대한 평가실험을 통하여, 샘플 GP의 문제점을 지적한 다음 기존의 개선법과 달리 제약을 받지 않고 여러 가지 문제에 적용할 수 있는 4가지 방법을 제안한다. 첫 번째 방법은 함수 트리의 성장에 관한 제어로 트리의 크기를 억제하면서 유전조작을 하는 것이다.
그러나, 이러한 개선법을 적용할 수 있는 문제가 한정되어 있으므로 샘플 GP와 마찬가지로 우연성에 의존하는 경우가 많으므로, 본 논문에서는 2-spirals 문제에 대한 평가실험을 통하여, 샘플 GP의 문제점을 지적한 다음 기존의 개선법과 달리 제약을 받지 않고 여러 가지 문제에 적용할 수 있는 4가지 방법을 제안한다. 첫 번째 방법은 함수 트리의 성장에 관한 제어로 트리의 크기를 억제하면서 유전조작을 하는 것이다. 두 번째 방법은 조기 수렴을 목적으로 함수 트리에 나타난 정수에 대하여 국소 탐색법으로 최적화하는 것이다.
첫 번째 방법은 함수 트리의 성장에 관한 제어로 트리의 크기를 억제하면서 유전조작을 하는 것이다. 두 번째 방법은 조기 수렴을 목적으로 함수 트리에 나타난 정수에 대하여 국소 탐색법으로 최적화하는 것이다. 세 번째 방법은 함수 트리의 크기를 축소하기 위하여 함수 트리 내의 필요 없는 요소를 최적화 시간에 삭제하는 것이다.
마지막 네 번째 방법은 취급하는 문제의 특성을 함수 트리에 이용하는 것이다. 위에서 설명한 개선법을 적용한 GP를 평가하기 위하여 2-spirals 문제에 대한 평가 실험을 한다. 즉, 2중 나선이 분포하는 xy 평면 위의 좌표가 어느 쪽의 나선에 속하는지를 분류하는 문제이다.
다음 II장에서는 샘플 GP 를 이용한 함수의 합성과 기존의 개선법에 관해서 개략적으로 설명한다. HI장에서는 2-spirals 문제에 대하여 샘플 GP를 적용하고, 그 문제점을 분석한 다음 기존의 개선법의한 가지인 MDL에 관해서도 평가한다. IV장에서는 GP의 개선법을 제안하고, V장에서는 2-spirals의 문제에 대하여 개선된 GP 를 적용하여 평가하고, 마지막 VI장에서는 결론을 맺는다.
Tournament 선택과 집단 내에서 설정한 개수(실험할 때에는 15개)의 개체(함수 트리)를 선택하여, 그 중에서 적합도가 가장 높은 개체를 부모로 하는 선택방법이다. 또한, 본 유전조작에 의해서 집단을 모두 교체하지만, 그 때 교차, 돌연변이 외에 부모의 구조를 그대로 복사한 조작도 실시한다. 실험에서는 이러한 조작 선택 확률을 교차, 돌연변이, 복사 순으로 0.
또한, 본 유전조작에 의해서 집단을 모두 교체하지만, 그 때 교차, 돌연변이 외에 부모의 구조를 그대로 복사한 조작도 실시한다. 실험에서는 이러한 조작 선택 확률을 교차, 돌연변이, 복사 순으로 0.8, 0.1, 0.1 로 한다.
그러므로, 본 논문에서 제안한 개선법의 비교 대상으로는 샘플 GP와 부분 문제로 분할할 수 없어도 적용할 수 있도록 노드 수의 항을 추가하여 적합도를 유지하는 MDL로 한다.
본 장에서는 2-spirals 문제[15]를 대상으로 하여 샘플 GP, 및 적합도에 함수 트리를 구성하는 노드 수의 항을 갖는 MDL 평가실험을 실시하였다.
샘플 GP의 개선법으로 기존의 개선법과 달리 적용 문제에 제약을 받지 않는 방법을 4가지 제안한다.
이것을 방지하기 위해서 트리의 성장을 억제한다. 구체적으로 우선 유전조작 후의 트리 깊이의 상한을 비교적 작은 값(초기 생성 때의 트리 깊이의 상한과 동일한 값)으로 설정하고, 그 범위 내에서 교차, 돌연변이를 시행하고, 이 상한을 넘는 경우는 그 유전조작을 무효로 한다. 그러나, 설정 상한 내에서 적합도가 일정 세대동안 연속하여 개선되지 않으면, 트리 깊이의 상한을 약간 늘린다.
여기서 이 효율성을 높이기 위하여 국소 탐색법을 도입한다. 즉 함수 트리에 나타난 정수를 국소 탐색법으로 조정함으로써 그 구조에서 얻어진 가장 양호한 함수 트리를 탐색한다. 본 국소 탐색법의 알고리즘을 다음과 같다.
위에서 기술한 제안법 1+2에 더하여 compact화 즉 함수 트리 내의 필요 없는 요소를 삭제(제안법 3)하였다.
우선, compact화의 최적인 적용 빈도와 대상 개체를 조사하기 위하여 제안법 1+2에서 함수의 합성이 성공한 5회 시행에 대하여 예비 실험을 하였다.
1세대마다, 2세대에 1회, 4세대에 1회, 6세대에 1회, 8세대에 1회, 10세대에 1회의 6가지 방법의 적용 빈도에 대해, 각 세대에 얻어진 가장 양호한 함수 트리에 대하여 compact 화를 실행하여 그 결과를 표 3에 나타내었다.
역으로 1세대, 2세대마다의 경우는 함수의 합성을 방해하고 있다고 생각할 수 있다. 여기서 적용 빈도로는 노드의 삭감률과 합성 세대의 개선률 모두에 효과가 있는 4세대마다를 적용하였다.
즉, 결과에 영향을 주지 않는 트리에도 실행 초기 및 중기의 단계에는 유용한 것과 일치하고 있다. 따라서, 아래에서는 4세대마다 가장 양호한 개체를 대상으로 compact화를 시행하였다.
제안법 4로 2-spirals 문제의 특성을 이용한다. 2개의 소용돌이는 점대칭에 가까운 분포를 하고 있으므로 극좌표 계를 이용하는 것이 유용하며, 함수의 부분 함수로 zg 좌표계를 극좌표 계로 변환한 식 (4), (5)를 도입하였다.
문제점을 지적하였다. 다음에는 그 문제점의 개선과 효율적인 탐색을 목적으로 함수 트리의 성장 억제, 국소 탐색법에 의한 정수의 최적화, compact화의 적용법, 대상 문제 특성의 부분함수로 이용하는 4가지의 개선법을 제안하였다. 그리고 2-spirals 문제에 대한 평가 실험에 의해서 본 개선법이 유효하다는 것을 나타내었다.
다음으로 compact화 적용 대상의 함수 트리를 증가시킨 경우에 대해서 실험하였다. 구체적으로 전집단 10%(실험에서는 KX)개)를 대상으로 gnpact화를 시행한 결과 함수의 합성을 완료한 세대가 지연되거나 합성을 할 수 없는 것으로 나타났다.
대상 데이터
또한, 제안한 개선법에 관해서는 집단 수를 1,000, 초기 생성 때의 트리 깊이의 상한(유전 조작 후의 트리 깊이의 상한)을 6으로 한다. 종료 조건은 소용돌이 A 와 소용돌이 3를 형성하는 194점을 올바르게 함수 합성할 수 있는 경우, 또는 100세대 실행한 경우로 한다. 이러한 처리를 1번 시행하여 다른 난수를 이용하여 모두 30번 시행한다.
이론/모형
기존의 개선법인 MDL 평가로 함수 트리를 구성하는 노드 수의 항을 더한 적합도를 식 (3)에 의하여 평가 실험한다.
때문에 탐색하는 시간이 필요하다. 여기서 이 효율성을 높이기 위하여 국소 탐색법을 도입한다. 즉 함수 트리에 나타난 정수를 국소 탐색법으로 조정함으로써 그 구조에서 얻어진 가장 양호한 함수 트리를 탐색한다.
성능/효과
있다. 이상의 설정에서 100세대까지 실행한 결과 얻어진 가장 좋은 개체(함수 트리)의 적응도, 즉 잘못 분류한 수는 20개였다. 이 100세대 동안에 생성된 함수 트리의 적합도와 크기의 관계를 나타내기 위하여, 세대마다 함수 트리의 깊이와 노드 수에 관하여 조사한 결과를 각각 그림 4, 5에 나타낸다.
그러나, 적합도가 수렴하는 51세대 이후에 주목하면 트리의 깊이에서 최대 27에 수렴하고 있지만, 노드 수는 계속 증가하는데, 이것은 적응도가 개선되지 않음에도 불구하고, 함수 트리의 크기가 단조롭게 증가함을 나타낸다. 이상으로부터 샘플 GP 의 탐색법에는 유전조작을 랜덤하게 계속 실시하여 트리의 구조를 변화시켜 버려, 트리의 성장에 대하여 제어가 되지 않기 때문에 세대가 진행됨에 따라 폭발적으로 트리의 크기가 커진다고 생각할 수 있다.
그러나, 설정 상한 내에서 적합도가 일정 세대동안 연속하여 개선되지 않으면, 트리 깊이의 상한을 약간 늘린다. 실험에서는 5세대 동안 적합도가 개선된 개체를 탐색할 수 없는 경우, 유전조작 후의 트리 깊이의 상한을 +2로 하면 작은 크기로 함수 트리의 탐색이 가능하고, 샘플 GP에 관해서 유전조작 후의 깊이의 상한을 미리 적당한 값으로 설정한다고 하는 문제도 해결할 수 있다.
이상 각 방법의 GP에 관한 의의를 정리하면 함수 트리의 성장 억제와 국소 탐색법에 의한 정수 최적화를 병용함으로써 intron의 발생을 억제함과 동시에 building block의 형성을 촉진하고, 또한 campact화로 intron에 대한 억제를 높인다고 생각할 수 있다. 여기서 특성의 이용은 building block으로 주어지고 있다.
표 중에 값은 모든 시행의 평균값이다. 본 결과에서 기존법에서는 어떤 시행에 대해서도 100 세대 실행하여도 함수의 합성을 전혀 할 수 없었는데 반하여 제안법 1+2를 적용한 경우, 194점 모두를 올바르게 분류한 함수가 4회 시행한 중에 1회는 합성되어 있는 것을 알 수 있다. 또한, 합성에 실패한 경우에도 제안법 1+2의 방법이 양호한 적합도(잘못 분류한 수)로 되고 있다.
대해서 실험하였다. 구체적으로 전집단 10%(실험에서는 KX)개)를 대상으로 gnpact화를 시행한 결과 함수의 합성을 완료한 세대가 지연되거나 합성을 할 수 없는 것으로 나타났다.
다음에는 그 문제점의 개선과 효율적인 탐색을 목적으로 함수 트리의 성장 억제, 국소 탐색법에 의한 정수의 최적화, compact화의 적용법, 대상 문제 특성의 부분함수로 이용하는 4가지의 개선법을 제안하였다. 그리고 2-spirals 문제에 대한 평가 실험에 의해서 본 개선법이 유효하다는 것을 나타내었다. 본 개선법은 GP를 적용할 수 있는 문제에도 적용할 수 있을 것으로 판단되지만, 실제의 문제에 적용한 실증은 후에 연구해야 할 과제이다.
후속연구
이상에서 compact화의 적용 빈도나 대상 개체를 많이 하면, 다음 세대에서 진화할 가능성이 있는 부분 트리나 필요한 intis까지 삭제되어, 함수의 탐색을 방해할 수 있다고 판단된다. 즉, 결과에 영향을 주지 않는 트리에도 실행 초기 및 중기의 단계에는 유용한 것과 일치하고 있다.
그리고 2-spirals 문제에 대한 평가 실험에 의해서 본 개선법이 유효하다는 것을 나타내었다. 본 개선법은 GP를 적용할 수 있는 문제에도 적용할 수 있을 것으로 판단되지만, 실제의 문제에 적용한 실증은 후에 연구해야 할 과제이다.
참고문헌 (15)
片山 徹, システム同定入門, システム制御情報ライブリ？ 9, 2008.
K. J. Astrom and P. Eykhoff, "System identification-A survey," Automatica, vol. 7, pp. 123-162, 1971.
K. S. Narendra and K. Parthasarathy, "Identification and control of dynamical systems using neural networks," IEEE Trans. Neural Networks, vol. 1, no. 2, pp. 4-27, 1990.
S. Chen, S. A. Billings, C. F. N. Cowan, and P. M. Grant, "Non-linear systems identification using radial basis function networks," Int. J. Systems Sci., vol. 21, no. 12, pp. 2513-2539, 1990.
J. P. Rosca and D. H. Ballard, "Hierarchical self-organization in genetic programming," Proc. 11th Int. Conf. of Machine Learning, pp. 251-258, 1994.
J. P. Rosca and D. H. Ballard, "Causality in genetic programming," Proc. 6th Int. Canf. of Genetic Algorithms, pp. 256-263, 1994.
K. E. Kinnear, Jr., "Alternatives in automatic function definition: A comparison of performance," Advances in Genetic Programming, pp. 119-141, MIT Press, 1994.
H. Iba, H. de Garis, and T. Sato, "Genetic programming using a minimum description length principle," Advances in Genetic Programming, pp. 265-284, MIT press, 1994.
H. Iba, T. Kurita, H. de Garis, and T. Sato, "System identification using structured genetic algorithm," Proc. 5th. Conf. on Genetic Algorithm, pp. 279-286, 1993.
伊庭齊志, 進化論的計算の方法, 東京大事出版局, 2008.
P. J. Angeline, "Two self-adaptive crossover operators for genetic programming," Advances in Genetic Programming, pp. 89-109, MIT Press, 1994.
이 논문을 인용한 문헌
저자의 다른 논문 :
활용도 분석정보
상세보기
다운로드
내보내기
활용도 Top5 논문
해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다. 더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.