유전자 알고리즘 응용 프로그램 및 제한 사항

유전 프로그래밍(GP) 시리즈의 이 시점에서 우리는 유전 프로그래밍이 무엇이며 정보를 표현하는 방법, 유전 연산자가 진화 알고리즘에서 어떻게 작동하는지, 기호 회귀를 통해 분류 프로그램을 진화시키는 과정을 배웠습니다.

여기에서는 이 기술이 발전하면서 무엇을 달성할 수 있는지 개략적으로 살펴보겠습니다.

유전자 프로그래밍의 실제 고려사항

이 시리즈의 마지막 장을 이해하기 위해 이 시리즈의 첫 번째 부분에서 논의한 XOR 예제를 기억해 보겠습니다.

GP가 발견한 XOR 문제에 대한 완벽한 솔루션: (디펀 프로그램() (그리고 (또는 X1 X2) (NOT (그리고 X1 X2) ) ) ) 

목록 1. XOR 결과.

또한 이전 기사의 기호 회귀 예제를 다시 살펴보겠습니다.

구간에서 sin(x)에 대한 다항식 근사(0 <=x <=pi/2) (디펀 프로그램() (+ (* (* (* X X) X) (* 0.2283 -0.6535)) 엑스) ) 위의 프로그램을 단순화하면 다음과 같은 등가 방정식이 생성됩니다. 폴리신(x) =-.1492 x
3
 + x 결과:

x	죄(x)	폴리신(x)
0.000	0.000	0.000
0.078	0.077	0.077
0.156	0.155	0.155
0.234	0.231	0.232
0.312	0.306	0.307
0.390	0.380	0.381
0.468	0.451	0.452
0.546	0.519	0.521
0.624	0.584	0.587
0.702	0.645	0.650
0.780	0.703	0.709
0.858	0.756	0.763
0.936	0.805	0.813
1.014	0.848	0.858
1.092	0.887	0.897
1.170	0.920	0.931
1.248	0.948	0.957
1.326	0.970	0.978
1.404	0.986	0.991
1.482	0.996	0.996
1.560	0.999	0.993

목록 4. 상징적 회귀.

여기에 제시된 XOR 및 기호 회귀 예제는 모두 평가될 때 단일 값을 반환합니다.

이 특성은 함수나 터미널이 실행될 때 부작용이 있을 수 있으므로 제한할 필요는 없습니다. 이것은 벡터에서 한 쌍의 요소를 교환하는 잠재적인 부작용이 있는 함수를 포함하는 정렬 프로그램의 경우입니다. 실제로는 부작용이 있는 것이 일반적입니다. 유용한 부작용의 몇 가지 추가 예는 한 변수를 다른 변수에 할당하거나 로봇이 향하는 방향을 변경하는 것입니다.

우리의 기능 세트에는 진화된 프로그램에 결정을 내릴 수 있는 능력을 제공하는 조건부 기능이 포함될 수 있습니다. 조건부 함수는 인수를 선택적으로 평가합니다. 예를 들어, (if arg1 arg2 arg3)와 같이 arity가 3인 함수를 고려하십시오. 함수는 첫 번째 인수를 평가하여 평가되고 결과가 true이면 두 번째 인수가 평가됩니다. 그렇지 않으면 세 번째 인수가 평가됩니다. 함수가 인수 중 하나를 여러 번 평가할 수 있으므로 반복 구문도 가능합니다. 그러나 개인 평가에 지나치게 오랜 시간이 소요될 수 있는 상황을 피하기 위해 반복 횟수와 중첩 수준을 제한해야 하므로 추가 복잡성이 도입됩니다. 이 영역에서의 성공은 다소 제한적이지만 재귀 공식을 허용하기 위해 일부 작업이 수행되었습니다.

GP 시스템의 결과는 LISP와 유사한 프로그램인 경향이 있지만 GP 시스템을 LISP에서 구현할 필요는 없습니다. 많은 시스템이 C 또는 C++로 구현됩니다. 프로그램 트리의 선형화된 표현을 사용할 수 있으며 값비싼 가비지 수집과 함께 동적 메모리의 오버헤드를 피할 수 있습니다. 피트니스 함수의 효율성은 각 세대에서 호출되는 횟수가 많기 때문에 종종 병목 현상이 발생하므로 특별한 주의를 기울일 필요가 있습니다. Advances in Genetic Programming 에서 다양한 구현 기술을 논의하는 우수한 문서를 찾을 수 있습니다. (아래 추천 읽을거리 섹션에서 인용).

신경망과 같은 다른 기계 학습 패러다임과 마찬가지로 훈련 데이터(GP 테스트 사례)를 과적합할 가능성이 있습니다. 솔루션이 데이터를 효과적으로 "기억"하여 정교한 조회 테이블 이상을 제공할 때 과적합이 발생할 수 있습니다. 이 효과를 줄이는 데 도움이 되는 한 가지 간단한 방법은 간결성 요소를 사용하는 것입니다. 간결함 요소는 일반적으로 프로그램 트리 내의 노드 수를 곱한 작은 분수이며, 그 결과는 적합도 함수에 통합됩니다. 아이디어는 더 작고 아마도 더 일반적인 솔루션을 보상하는 것입니다. 또한 적절한 실험 설계 기법을 사용하는 것이 좋습니다. 예를 들어, 예측을 위한 모델을 개발하려는 경우 적합성 평가를 사용 가능한 데이터의 하위 집합으로 제한하는 것이 좋습니다. 이런 식으로 나머지 데이터는 결과 모델의 예측 성능을 측정할 수 있습니다.

진화 알고리즘의 경우와 마찬가지로 GP는 정확한 솔루션이나 수용 가능한 솔루션을 찾는 것을 보장하지 않습니다. 결과는 실행마다 크게 다를 수 있습니다. 종종 프로세스는 조기에 국소 최솟값에 수렴합니다. 성능은 문제 복잡성, 기능 및 터미널 선택으로 특징지어지는 표현, 적합성 기능의 속성에 크게 의존합니다.

유전자 프로그래밍을 위한 응용

유전 프로그래밍은 다음과 같은 영역에서 발생하는 문제에 성공적으로 적용되었습니다.

<울>

회로 설계

조합 최적화

제어 시스템

곡선 피팅/회귀 분석

데이터 압축

경제 예측/재무 모델링

게임 전략 획득

수열 유도

신경망 설계

패턴 인식 및 분류

난수 생성

로봇 탐색

상징적 통합 및 차별화

3차원 디자인

유전자 프로그래밍의 미래 방향

문제의 복잡성에 따라 수용 가능한 솔루션을 찾기 위해 여러 GP 실행이 필요할 수 있습니다. 이상적으로는 문제의 복잡성이 증가함에 따라 GP가 "확장"되기를 바랍니다. 이 목표를 달성하기 위한 좋은 방법을 찾는 것은 활발한 연구 분야입니다. 기존 프로그래밍에서와 같이 서브루틴을 통해 더 높은 수준의 표현을 구축한다는 개념은 이 문제에 접근하는 한 가지 방법입니다. 유전 프로그래밍 II에서 , Koza는 재사용 가능한 서브루틴을 발견할 수 있는 방법에 대해 논의하고 더 복잡한 문제를 해결하기 위한 계층적, 모듈식 프로그램의 능력을 지원하는 결과를 제시합니다.

우리가 보았듯이 GP는 유전 알고리즘의 자기 조직화 특성과 S-표현의 표현력 및 일반성을 결합합니다. 이 접근 방식의 우아함은 문제 사양을 도메인별 적합성 기능과 적절한 기능 및 터미널 집합을 제공하는 것으로 단순화합니다. 다양한 문제에 적용할 수 있는 GP는 계속해서 연구를 위한 비옥한 땅입니다.

아직 초기 단계에 있지만 미래의 혁신을 통해 자체 프로그램을 작성할 수 있는 시스템의 성배에 한 걸음 더 나아갈 수 있습니다.

권장 자료

<울>

Kinnear, Jr., K. E. (ed.). 유전자 프로그래밍의 발전 . 매사추세츠주 캠브리지:MIT Press, 1994.

Knuth, D. E. 컴퓨터 프로그래밍의 기술, 3권, 정렬 및 검색 . 독서, 매사추세츠:Addison-Wesley, 1973

Koza, J. R. 유전자 프로그래밍 . 매사추세츠주 캠브리지:MIT Press, 1992.

Koza, J. R. 유전자 프로그래밍 II . 매사추세츠주 캠브리지:MIT Press, 1994.

Montana, D. J. "강력한 유형의 유전자 프로그래밍." BBN 기술 보고서 ​​#7866, 1993년 5월.

Mitchell, Melanie, 유전 알고리즘 소개 , MIT Press, 1998.