유전 프로그래밍 소개:스스로 프로그래밍하는 시스템?

아마도 컴퓨터 과학의 "성배"는 우리 기계가 자체 프로그램을 작성할 수 있는 날에 발견되었을 것입니다. 유전 프로그래밍(GP)은 그 방향으로 나아가는 단계를 나타내는 비교적 새로운 기계 학습 패러다임입니다.

GP는 제어 엔지니어링 영역에서 많은 가능성을 가지고 있습니다. 이 기사에서는 유전 프로그래밍이 무엇인지, 어떻게 표현할 수 있는지 논의하고 프로그램의 예를 살펴보겠습니다.

이 기사는 시리즈의 첫 번째 기사입니다. 다음 항목으로 건너뛰려면 아래에서 하나를 선택하십시오.

유전자 프로그래밍 및 유전 알고리즘

GP는 본질적으로 John Holland가 고안한 유전 알고리즘(GA)의 변형입니다. GA와 마찬가지로 GP는 적합성 비례 재생산, 교차 및 돌연변이와 같은 유전 연산자에 의존하여 인코딩된 프로그램 집단 또는 "개인"을 솔루션을 향한 연속 세대를 통해 유도하는 진화 알고리즘입니다.

그러나 일반적으로 고정 길이 비트 문자열 인코딩을 사용하는 GA와 달리 GP는 실제 프로그램의 가변 크기, 트리 기반 표현을 사용합니다. 따라서 성공적인 GP 실행의 결과는 적절한 입력이 주어지고 실행될 때 원하는 결과를 산출하는 컴퓨터 프로그램을 생성합니다.

Nichael Cramer와 John Koza는 GP의 기초를 놓은 것으로 알려져 있습니다. GP에 대한 특허도 보유하고 있는 John Koza는 GP에 대해 상당한 양의 연구를 수행했으며 그의 획기적인 책인 "Genetic Programming"은 이 주제에 대한 획기적인 작업으로 간주됩니다. 현재 연구는 로봇 탐색, 게임 전략 획득, 기호 회귀 분석 및 제어 시스템을 포함한 광범위한 응용 프로그램에서 GP의 고무적인 성공을 입증했습니다.

유전자 프로그래밍 표현

앞에서 언급한 트리 기반 표현은 거의 모든 컴퓨터 프로그램이 이러한 방식으로 표현될 수 있으므로 GP 테마의 핵심입니다. 실제로 LISP와 같은 기능적 언어는 이 형식에 적합하며 LISP S-표현식을 트리로 다이어그램화할 수 있는 방법을 쉽게 알 수 있습니다(그림 1).

아래에서 동일한 정보에 대한 세 가지 개별 표현을 찾을 수 있습니다.

간단한 프로그램 조각: 시작하다 IF a LISP 등가물: (예측(만약 (a  

 
 

 
 
그림 1. 프로그램의 트리 표현. (progn arg1 arg2 arg3 ... argn) 은 각 인수를 순차적으로 평가합니다.  
 

 
 

 트리의 내부 노드는 함수로 구성되는 반면 리프 노드는 터미널로 구성됩니다. 함수는 적어도 하나의 인수 개수(일반적으로 arity라고 함)를 가져야 하며, 이를 통해 다른 함수나 터미널에 연결되어 트리 내의 분기에 "접착제"를 제공합니다.
 

 터미널에는 일반적으로 상수 및 변수와 같은 항목이 포함됩니다. 터미널은 트리의 잎을 형성하기 때문에 항상 0의 승수를 갖습니다. 해결하려는 문제에 대한 일련의 기능과 터미널을 선택해야 합니다. 예를 들어, 논리 함수 AND, OR 및 NOT과 두 개의 부울 입력 변수를 나타내는 터미널 X1 및 X2는 XOR 부울 함수를 합성할 수 있는 프로그램을 검색하려는 경우 적합합니다. 한 프로그램이 주어진 문제를 더 잘 해결한다는 의미에서 다른 프로그램과 비교하여 측정할 수 있는 수단을 제공해야 하므로 피트니스 기능도 필요합니다.
 

 예를 들어, XOR의 경우 X1과 X2에 대한 4개의 가능한 부울 입력(0 0, 0 1, 1 0, 1 1) 및 각 테스트 케이스에 대해 정답 수(0, 1, 1, 0)를 각각 더합니다. 
 

 분명히 4점 만점을 산출하는 프로그램은 목록 1과 같이 XOR 문제에 대한 솔루션으로 간주됩니다.
 

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

 
 
다음:유전 연산자
 

 다음 기사에서는 진화 알고리즘을 가능하게 하는 유전 연산자를 살펴보겠습니다. 더 복잡한 예제 알고리즘에서도 사용할 것입니다.
 

 
 
권장 자료
 <울> 
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.
 
 

            


            

               버즈워드 평가:디지털 혁신        
                퍼지 로직 컨트롤러를 설계하는 방법