유전자 프로그래밍

Genetic programming
범용 프로그래밍, 유전자 공학 또는 DNA 컴퓨팅과 혼동하지 마십시오.
의 시리즈의 일부
진화 알고리즘
유전 알고리즘
유전자 프로그래밍

인공지능에서 유전자 프로그래밍(GP)은 프로그램 집단에 자연 유전 과정과 유사한 작업을 적용함으로써 부적합한(보통 랜덤) 프로그램 집단에서 시작하여 특정 작업에 적합한 프로그램을 발전시키는 기술이다.

운영은 사전 정의된 적합성 척도에 따라 생식(크로스오버) 및 돌연변이를 위한 적합 프로그램 선택이며, 일반적으로 원하는 작업에 대한 숙련도이다.크로스오버 조작에는, 선택된 페어(부모)의 랜덤한 부분을 교환해, 신세대의 프로그램의 일부가 되는 새롭고 다른 자손을 낳습니다.돌연변이는 프로그램의 일부 랜덤 부분을 프로그램의 다른 랜덤 부분으로 치환하는 것을 포함한다.재생용으로 선택되지 않은 일부 프로그램은 현재 세대에서 새로운 세대로 복사됩니다.그런 다음 선택 및 기타 작업이 새로운 세대의 프로그램에 재귀적으로 적용됩니다.

일반적으로 각 신세대의 구성원은 이전 세대의 구성원에 비해 평균적으로 더 건강하며, 대부분의 경우 이전 세대의 프로그램보다 더 나은 Best-of-generation 프로그램이 이전 세대의 최고 프로그램보다 더 좋습니다.진화의 종료는 일반적으로 일부 개별 프로그램이 사전 정의된 숙련도 또는 적합성 수준에 도달할 때 발생한다.

알고리즘의 특정 실행으로 인해 글로벌하게 최적인 솔루션이나 심지어 적절한 솔루션이 아닌 로컬 최대값으로 조기 컨버전스가 발생하는 경우가 종종 있습니다.일반적으로 매우 좋은 결과를 얻으려면 여러 번의 런(수십 ~ 수백회)이 필요합니다.또한 병리학을 피하기 위해 큰 시작 모집단 크기와 개인의 변동성을 가져야 할 수도 있습니다.

역사

프로그램을 진화시키기 위한 제안의 첫 번째 기록은 아마도 1950년 [1]앨런 튜링의 기록일 것이다.존 홀랜드의 '자연 및 인공 시스템에서의 적응'이 과학의 이론적, 경험적 토대를 제시하기까지는 25년의 공백이 있었다.1981년 Richard Forsyth는 영국 내무부의 [2]범죄 현장 증거 분류를 수행하기 위해 나무로 표현되는 작은 프로그램의 성공적인 진화를 시연했습니다.

비록 진화하는 프로그램의 컴퓨터 언어 Lisp 처음에 그 생각은, 현재 사이 존은 네덜란드의 students,[3] 있을 때까지(GA)첫번째 유전자 알고리즘 조직되었던 것이 아니다 피츠버그에서 회의가 Nichael Cramer[4]는 moder의 처음 진술을 포함했다 두 특별히 고안된 언어로 진화된 프로그램을 발표했다.n"나무e-based" 유전자 프로그래밍(즉, 트리 기반 구조로 구성되고 적절하게 정의된 GA 오퍼레이터에 의해 작동되는 절차 언어)1988년 John Koza(John Holland 박사과정 학생이기도 함)는 프로그램 [5]진화를 위한 GA 발명에 대한 특허를 취득했습니다.그 후, 「인공지능 [6]IJCAI-89에 관한 국제 합동 회의」에 발표되었습니다.

코자는 존 홀랜드의 [7]박사과정 학생인 데이비드 골드버그가 만든 '유전자 프로그래밍'(GP)에 관한 205개의 출판물로 그 뒤를 이었다.그러나, 1992년부터[8] 부속 [9]영상을 시작으로 한 Koza의 4권의 시리즈가 GP를 확립했습니다.그 후,[10] 유전자 프로그래밍 참고 문헌을 포함한 출판물의 수가 10,000개를 돌파하는 등 엄청난 확대가 있었다.2010년에 Koza는[11] 유전자 프로그래밍이 인간 경쟁력을 가진 77개의 결과를 열거했다.

1996년, 코자는 매년 유전자 프로그래밍 컨퍼런스를[12] 시작해 1998년에 이어 매년 EuroGP [13]컨퍼런스를 개최해, 코자가 편집한 GP시리즈의 첫 번째[14] 책이다.1998년에도 최초의 GP [15]교과서가 나왔다.GP는 계속 번창하여 최초의 전문 GP[16] 저널을 만들었고, 3년 후(2003년) Rick [17][18]Riolo에 의해 연례 유전 프로그래밍 이론 및 실습(GPTP) 워크숍이 설립되었습니다.유전자 프로그래밍 논문은 다양한 컨퍼런스 및 관련 저널에서 계속 발표되고 있습니다.오늘날에는 학생들을 [15]위한 몇 권을 포함하여 19권의 GP 도서가 있다.

GP의 기초 작업

현재의 유전자 프로그래밍 연구 주제와 응용 분야를 위한 기반을 마련하는 초기 작업은 다양하며 소프트웨어 합성 및 복구, 예측 모델링,[19] 데이터 마이닝,[20] 재무 모델링,[21] 소프트 센서, 디자인 [22]및 이미지 [23]처리를 포함합니다.디자인 등 일부 분야에서는 Fred Gruau의 셀룰러 [25]인코딩과 같은 중간 [24]표현을 사용하는 경우가 많습니다.금융, 화학 산업, 생물 정보학[26][27] 및 철강 [28]산업을 포함한 여러 분야에서 산업적 활용이 두드러지고 있습니다.

방법들

프로그램 표현

트리 구조로 표시되는 함수
주요 기사: 유전자 표현

GP는 전통적으로 메모리 내에서 트리 [29]구조로 표현되는 컴퓨터 프로그램을 진화시킵니다.트리는 재귀적인 방법으로 쉽게 평가할 수 있습니다.모든 트리 노드는 연산자 함수를 가지며, 모든 터미널 노드는 피연산자를 가지며, 이는 수학식을 발전시키고 평가하기 쉽게 한다.따라서 전통적으로 GP는 트리 구조를 자연스럽게 구현하는 프로그래밍 언어의 사용을 선호합니다(예를 들어 리스프, 다른 기능적 프로그래밍 언어도 적합합니다).

보다 전통적인 명령어에 적합한 선형 유전 프로그래밍과 같은 비수목 표현이 제안되고 성공적으로 구현되었다[예를 들어, Banzhaf 등(1998년)[30] 참조].시판 GP 소프트웨어 Discipulus는 바이너리 머신 코드("[31]AIM")의 자동 인덕션을 사용하여 성능을 향상시킵니다.§ GP는 다이렉트 멀티그래프를 사용하여 특정 어셈블리 언어의 구문을 완전히 이용하는 프로그램을 생성합니다[32].다중 표현식 프로그래밍에서는 솔루션을 인코딩하기 위해 3개의 주소 코드를 사용합니다.중요한 연구 개발이 수행된 다른 프로그램 표현으로는 스택 기반 가상 [33][34][35]머신용 프로그램과 문법을 [36][37]통해 임의의 프로그래밍 언어에 매핑되는 정수 시퀀스가 있습니다.데카르트 유전 프로그래밍은 GP의 또 다른 형태로, 컴퓨터 프로그램을 인코딩하기 위해 일반적인 트리 기반 표현 대신 그래프 표현을 사용합니다.

대부분의 표현은 구조적으로 유효한 코드(내부)가 없습니다.그러한 비부호화 유전자는 어떤 개인의 수행에도 영향을 미치지 않기 때문에 쓸모없어 보일 수 있다.그러나 변동 연산자 아래에서 서로 다른 자손을 생성할 확률을 변경하여 개인의 변동 속성을 변경한다.실험은 비부호화 [38][39]유전자를 가지지 않는 프로그램 표현에 비해 그러한 비부호화 유전자를 허용하는 프로그램 표현을 사용할 때 더 빠른 수렴을 보여주는 것으로 보인다.

선택.

선택은 다음 세대의 부모 역할을 할 특정 개인들을 현재 세대에서 선발하는 과정이다.개인을 선발하는 것은 개연성이 높기 때문에 실적이 좋은 개인을 [18]선발할 확률이 높아집니다.GP에서 가장 일반적으로 사용되는 선택 방법은 토너먼트 선택이지만, 많은 GP 문제에 대해 피트니스 비례 선택,[40] 사전 선택 등과 같은 다른 방법이 더 나은 성능을 발휘하는 것으로 입증되었다.

엘리트주의는 현재 세대에서 최고의 개인(또는 최고의 개인 n명)을 다음 세대에 뿌리는 것을 수반하며, 퇴행을 피하기 위해 때때로 사용되는 기술이다.

크로스오버

유전자 프로그래밍에서는 모집단에서 두 명의 적합한 개체가 한 명 또는 두 명의 아이의 부모가 됩니다.나무 유전자 프로그래밍에서, 이 부모들은 나무처럼 거꾸로 된 혀로 표현되며, 그들의 뿌리 노드가 맨 위에 있다.각 부모의 서브트리 크로스오버에서는 서브트리가 랜덤으로 선택됩니다.(애니메이션에서는 노란색으로 강조 표시됩니다.)루트 기부 부모(왼쪽 애니메이션)에서는 선택한 서브트리가 삭제되고 랜덤으로 선택된 서브트리의 복사본으로 대체되어 새로운 서브트리가 생성됩니다.

경우에 따라서는 2개의 자식 크로스오버가 사용됩니다.이 경우 제거된 하위 트리(왼쪽 애니메이션)는 단순히 삭제되지 않고 무작위로 선택된 하위 트리를 대체하는 두 번째 부모(오른쪽)의 복사본으로 복사됩니다.따라서 이러한 유형의 서브트리 크로스오버는 2개의 적합 트리를 사용하여 2개의 하위 트리를 생성합니다.Genetic programming subtree crossover

돌연변이

유전자 프로그래밍에는 많은 종류의 돌연변이가 있다.그들은 적절한 구문론적으로 올바른 부모로부터 시작하여 무작위로 구문론적으로 올바른 아이를 만드는 것을 목표로 한다.애니메이션에서 하위 트리가 임의로 선택됩니다(노란색으로 강조 표시됨).삭제되고 랜덤하게 생성된 서브트리로 대체됩니다.

다른 돌연변이 연산자는 트리의 리프(외부 노드)를 선택하고 임의로 선택한 리프(leaf)로 대체합니다.또 다른 돌연변이는 함수(내부 노드)를 무작위로 선택하고 동일한 특성(입력 수)을 가진 다른 함수로 대체하는 것입니다.호이스트 돌연변이는 랜덤하게 서브트리를 선택하여 그 내부의 서브트리로 대체합니다.따라서 호이스트 돌연변이는 아이를 더 작게 만들 수 있습니다.리프 및 동일한 arity 함수를 교체하면 자녀가 부모와 동일한 크기를 가질 수 있습니다.반면 (애니메이션에서) 하위 트리 돌연변이는 함수 및 터미널 세트에 따라 트리 크기를 늘리거나 줄이려는 편견이 있을 수 있습니다.다른 서브트리 기반의 돌연변이는 치환 서브트리의 크기를 신중하게 제어하기 위해 시도합니다.

서브트리를 제거하고 랜덤 코드로 대체하여 부모 변이를 통해 유전자 프로그래밍 하위 생성 애니메이션

마찬가지로 선형 유전자 프로그래밍 돌연변이는 여러 종류가 있으며, 각각 변이된 아이가 여전히 구문학적으로 정확함을 보장하려고 한다.

적용들

GP는 자동 프로그래밍 도구, 기계 학습 도구, 자동 문제 해결 [18]엔진으로 성공적으로 활용되었습니다.GP는 솔루션의 정확한 형태를 사전에 알 수 없거나 대략적인 솔루션이 허용되는 영역에서 특히 유용합니다(정확한 솔루션을 찾는 것이 매우 어렵기 때문일 수 있습니다).GP의 적용 분야에는 곡선 피팅, 데이터 모델링, 기호 회귀, 형상 선택, 분류 등이 있습니다.John R. Koza는 유전자 프로그래밍이 인간이 만든 결과와 경쟁적인 결과를 도출할 수 있었던 76가지 사례를 언급했습니다(인간 경쟁 결과라고 [41]불립니다).2004년 이후 매년 GECCO(Genetic and Evolutionary Computation Conference)는 휴미(Humies)라는 대회를 개최하고 있으며, [42]이 대회에서는 모든 형태의 유전자 및 진화적 계산에 의해 도출된 인간 경쟁 결과에 대해 상금이 수여됩니다.GP는 수년간 이 대회에서 많은 상을 받았다.

메타유전자 프로그래밍

메타유전자 프로그래밍은 유전자 프로그래밍 자체를 사용하여 유전자 프로그래밍 시스템을 진화시키는 제안된 메타 학습 기법이다.그것은 염색체, 교차, 그리고 돌연변이가 그 자체로 진화했다는 것을 암시한다. 따라서 그들의 실제 생활 상대와 같이 인간 프로그래머에 의해 결정되기 보다는 스스로 변화하도록 허용되어야 한다.Meta-GP는 1987년 [43]위르겐 슈미트후버에 의해 공식적으로 제안되었다.Doug Lenat의 Eurisko는 같은 기술일 수 있는 초기의 노력입니다.이는 재귀적이지만 종료되는 알고리즘이므로 무한 재귀를 방지할 수 있습니다.메타유전자 프로그래밍에 대한 "자동구축적 진화" 접근방식은 자손의 생산 및 변이를 위한 방법을 진화하는 프로그램 자체 내에서 부호화하고,[34][44] 모집단에 추가되는 새로운 프로그램을 제작하기 위해 프로그램을 실행한다.

이 아이디어를 비판하는 사람들은 종종 이 접근법이 지나치게 광범위하다고 말한다.그러나, 일반 등급의 결과에 대한 적합성 기준을 제한하여 하위 등급에 대한 결과를 보다 효율적으로 생성할 수 있는 진화된 GP를 얻을 수 있다.이것은 인간의 달리기, 점프 등을 진화시키는 데 사용되는 인간 보행 알고리즘을 생성하기 위해 메타 진화 GP의 형태를 취할 수 있다.메타 GP에 적용되는 적합성 기준은 단순히 효율성 중 하나가 될 것이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Computing Machinery and Intelligence". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  2. ^ "BEAGLE A Darwinian Approach to Pattern Recognition". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  3. ^ 톰 웨스터데일과의 개인적인 커뮤니케이션
  4. ^ "A representation for the Adaptive Generation of Simple Sequential Programs". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  5. ^ "Non-Linear Genetic Algorithms for Solving Problems". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  6. ^ "Hierarchical genetic algorithms operating on populations of computer programs". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  7. ^ Goldberg. D.E.(1983년), 유전 알고리즘과 규칙 학습을 이용한 컴퓨터 지원 가스 파이프라인 운영.박사학위 요건을 부분적으로 충족하기 위해 미시간 앤아버에 있는 미시간 대학에 제출된 논문.
  8. ^ "Genetic Programming: On the Programming of Computers by Means of Natural Selection". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  9. ^ "Genetic Programming:The Movie". gpbib.cs.ucl.ac.uk. Archived from the original on 2021-12-11. Retrieved 2021-05-20.
  10. ^ "The effects of recombination on phenotypic exploration and robustness in evolution". gpbib.cs.ucl.ac.uk. Retrieved 2021-05-20.
  11. ^ "Human-competitive results produced by genetic programming". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  12. ^ "Genetic Programming 1996: Proceedings of the First Annual Conference". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  13. ^ "Genetic Programming". www.cs.bham.ac.uk. Retrieved 2018-05-19.
  14. ^ "Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  15. ^ a b "Genetic Programming -- An Introduction; On the Automatic Evolution of Computer Programs and its Applications". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  16. ^ Banzhaf, Wolfgang (2000-04-01). "Editorial Introduction". Genetic Programming and Evolvable Machines. 1 (1–2): 5–6. doi:10.1023/A:1010026829303. ISSN 1389-2576.
  17. ^ "Genetic Programming Theory and Practice". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  18. ^ a b c "A Field Guide to Genetic Programming". www.gp-field-guide.org.uk. Retrieved 2018-05-20.
  19. ^ "Data Mining and Knowledge Discovery with Evolutionary Algorithms". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  20. ^ "EDDIE beats the bookies". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  21. ^ "Applying Computational Intelligence How to Create Value". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  22. ^ "Human-competitive machine invention by means of genetic programming". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  23. ^ "Discovery of Human-Competitive Image Texture Feature Extraction Programs Using Genetic Programming". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  24. ^ "Three Ways to Grow Designs: A Comparison of Embryogenies for an Evolutionary Design Problem". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  25. ^ "Cellular encoding as a graph grammar - IET Conference Publication". ieeexplore.ieee.org. April 1993. pp. 17/1–1710. Retrieved 2018-05-20.
  26. ^ "Genetic Algorithm Decoding for the Interpretation of Infra-red Spectra in Analytical Biotechnology". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  27. ^ "Genetic Programming for Mining DNA Chip data from Cancer Patients". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  28. ^ "Genetic Programming and Jominy Test Modeling". www.cs.bham.ac.uk. Retrieved 2018-05-20.
  29. ^ Nichael L. Cramer "단순 시퀀셜 프로그램의 적응형 생성을 위한 표현" 2005-12-04년 웨이백 머신에 보관되었습니다.
  30. ^ 가넷 윌슨과 볼프강 반자프.데카르트 유전 프로그래밍과 선형 유전 프로그래밍의 비교.
  31. ^ (Peter Nordin, 1997, Banzhaf 등, 1998, 제11.6.2절-11.6.3절)
  32. ^ Giovanni Squillero. "µGP (MicroGP)".
  33. ^ "Stack-Based Genetic Programming". gpbib.cs.ucl.ac.uk. Retrieved 2021-05-20.
  34. ^ a b Spector, Lee; Robinson, Alan (2002-03-01). "Genetic Programming and Autoconstructive Evolution with the Push Programming Language". Genetic Programming and Evolvable Machines. 3 (1): 7–40. doi:10.1023/A:1014538503543. ISSN 1389-2576. S2CID 5584377.
  35. ^ Spector, Lee; Klein, Jon; Keijzer, Maarten (2005-06-25). The Push3 execution stack and the evolution of control. ACM. pp. 1689–1696. CiteSeerX 10.1.1.153.384. doi:10.1145/1068009.1068292. ISBN 978-1595930101. S2CID 11954638.
  36. ^ Ryan, Conor; Collins, JJ; Neill, Michael O (1998). Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 83–96. CiteSeerX 10.1.1.38.7697. doi:10.1007/bfb0055930. ISBN 9783540643609.
  37. ^ O'Neill, M.; Ryan, C. (2001). "Grammatical evolution". IEEE Transactions on Evolutionary Computation. 5 (4): 349–358. doi:10.1109/4235.942529. ISSN 1089-778X. S2CID 10391383.
  38. ^ 줄리안 F.밀러."카르트 유전자 프로그래밍" 웨이백 머신에 2015-09-24 아카이브. 페이지 19.
  39. ^ 재닛 클레그, 제임스 알프레드 워커, 줄리안 프란시스 밀러데카르트 유전 프로그래밍을 위한 새로운 교차 기법"입니다.2007.
  40. ^ Spector, Lee (2012). Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report. Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation. Gecco '12. ACM. pp. 401–408. doi:10.1145/2330784.2330846. ISBN 9781450311786. S2CID 3258264.
  41. ^ Koza, John R (2010). "Human-competitive results produced by genetic programming". Genetic Programming and Evolvable Machines. 11 (3–4): 251–284. doi:10.1007/s10710-010-9112-3.
  42. ^ "Humies =Human-Competitive Awards".
  43. ^ "1987 THESIS ON LEARNING HOW TO LEARN, METALEARNING, META GENETIC PROGRAMMING,CREDIT-CONSERVING MACHINE LEARNING ECONOMY".
  44. ^ GECCO '16 Companion : proceedings of the 2016 Genetic and Evolutionary Computation Conference : July 20-24, 2016, Denver, Colorado, USA. Neumann, Frank (Computer scientist), Association for Computing Machinery. SIGEVO. New York, New York. 20 July 2016. ISBN 9781450343237. OCLC 987011786.{{cite book}}: CS1 유지보수: 기타 (링크)

외부 링크