문법적 진화
Grammatical evolution| 다음 시리즈의 일부 |
| 진화 알고리즘 |
|---|
| 유전 알고리즘 |
| 유전자 프로그래밍 |
문법적 진화(GE)는 진화적 연산이며, 보다 구체적으로 말하면 리머릭 대학의 BDS 그룹에서 1998년[1] 코너 라이언, JJ 콜린스, 마이클 오닐이 개척한 유전자 프로그래밍(GP) 기법(또는 접근법)으로, 비록 이전에 출판된 것과 같은 다른 관련 작품도 있다.[2]
다른 GP 접근방식과 마찬가지로, 목표는 실행 가능한 프로그램, 프로그램 조각 또는 기능을 찾는 것이며, 이는 주어진 객관적 기능에 대한 좋은 적합성을 달성할 것이다.GP에 관한 대부분의 출판물에서는 LISP 스타일의 트리 구조식 표현이 직접 조작되는 반면, GE는 유전자 연산자를 정수 문자열에 적용하고, 이후 문법을 이용하여 프로그램(또는 이와 유사한 것)에 매핑되는데, 이는 일반적으로 백커스-나우르 형태로 표현된다.GE의 장점 중 하나는 이 매핑이 다른 프로그래밍 언어와 다른 구조에 대한 검색 적용을 단순화한다는 것이다.
해결된 문제
형식 없는 전통적인 Koza 스타일 GP에서, 함수 집합은 폐쇄 요건을 충족해야 한다: 모든 함수는 함수 집합에 있는 다른 모든 함수의 출력을 그들의 주장으로 받아들일 수 있어야 한다.통상 이중정밀 부동소수점 등 단일 데이터형태를 처리해 시행한다.현대의 유전 프로그래밍 프레임워크는 타이핑을 지원하지만, 그러한 타입 시스템은 문법적 진화가 겪지 않는 한계를 가지고 있다.
GE의 솔루션
GE는 사용자 지정 문법(대개 Backus-Naur 형식의 문법)에 따라 솔루션을 진화시킴으로써 이 문제에[which?] 대한 해결책을 제시한다.따라서 검색 공간을 제한할 수 있으며, 문제에 대한 도메인 지식이 통합될 수 있다.이러한 접근방식에 대한 영감은 "유형"과 "유형"을 "유형"과 분리하고자 하는 욕망에서 비롯된다. GP에서는 검색 알고리즘이 동작하는 개체와 피트니스 평가 기능이 해석하는 것이 하나이고 동일하다.이와는 대조적으로 GE의 "유형"은 제공된 문맥 없는 문법에서 규칙을 선택하기 위한 코드 정수의 순서 목록이다.그러나 이 표현형은 코자식 GP에서와 동일하다: 재귀적으로 평가되는 나무와 같은 구조다.이 모델은 유기체의 유전자형과 단백질 등에서 표현형의 최종 발현 사이에 분리가 있는 자연에서 유전자가 어떻게 작용하는가에 더 부합한다.
유전자형과 표현형을 분리하는 것은 모듈형 접근을 가능하게 한다.특히 GE 패러다임의 검색 부분은 특정 알고리즘이나 방법에 의해 수행될 필요가 없다.GE가 검색을 수행하는 개체가 유전 알고리즘에 사용되는 개체와 동일한지 확인하십시오.이는 원칙적으로 인기 있는 GAlib와 같은 기존의 유전자 알고리즘 패키지를 사용하여 검색을 수행할 수 있으며, GE 시스템을 구현하는 개발자는 정수 목록에서 프로그램 트리로 매핑을 수행하는 것에 대해서만 걱정하면 된다는 것을 의미한다.또한 원칙적으로 입자 군집 최적화(아래 설명 참조)와 같은 다른 방법을 사용하여 검색을 수행하는 것이 가능하다. GE의 모듈화 특성은 풀려야 할 관심 문제가 지시하는 대로 하이브리드에 많은 기회를 창출한다.
브라바존과 오닐은 GE를 기업 파산 예측, 주식 지수 예측, 채권 신용 등급 및 기타 금융 애플리케이션에 성공적으로 적용했다.[citation needed]GE는 또한 포식자 효율, 틈새 수, 무작위 돌연변이가 생태학적 안정성에 미치는 영향을 탐구하기 위해 전통적인 포식자-프리 모델과 함께 사용되어 왔다.[3]
주어진 함수/단자 집합에 대해 유전 프로그래밍과 동등한 GE 문법을 구성할 수 있다.
비판
성공했음에도 불구하고 GE는 일부 비판의 대상이 되어 왔다.한 가지 문제는 지도제작의 결과 GE의 유전사업자는 진화 알고리즘에서 유전사업자의 높은 평가를 받는 높은 지역성을[4][5] 달성하지 못한다는 점이다.[4]
변형
GE는 꽤 새로운 버전이지만, 이미 개선된 버전과 변형들이 있다.GE 연구진은 일반 GE와 유사한 결과를 가진 유전자 알고리즘 대신 미립자 군집 최적화를 사용하여 검색을 수행하는 실험을 했다. 이를 "문법 군집"이라고 하며, 기본 PSO 모델만 사용하여 PSO가 GE a에서 검색 프로세스를 수행할 수 있는 능력이 동일한 것으로 밝혀졌다.s 단순한 유전 알고리즘은 다음과 같다. (PSO는 일반적으로 부동 소수점 검색 패러다임이지만, 예를 들어, 각 벡터를 GE와 함께 사용하기 위해 가장 가까운 정수로 반올림하면 분명이 가능하다.)
그러나 문헌에서 실험된 또 다른 가능한 변화는 검색 과정을 더욱 편향시키기 위해 문법에서 의미 정보를 인코딩하려고 시도하고 있다.
참고 항목
메모들
- ^ "Grammatical Evolution: Evolving Programs for an Arbitrary Language".
- ^ https://www.researchgate.net/profile/PA_Whigham/publication/2450222_Grammatically-based_Genetic_Programming/links/55c3c89908aebc967df1b765.pdf
- ^ Alfonseca, Manuel; Soler Gil, Francisco José (2 January 2015). "Evolving a predator-prey ecosystem of mathematical expressions with grammatical evolution". Complexity. 20 (3): 66–83. Bibcode:2015Cmplx..20c..66A. doi:10.1002/cplx.21507. hdl:10486/663611.
- ^ a b DOI.org
- ^ "Publication: Positional Effect of Crossover and Mutation in Grammatical Evolution - School of Computing - University of Kent".
자원.
- 문법 진화 튜토리얼.
- 자바에서의 문법적 진화.
- JGE - 자바 문법 진화.
- 리머릭 대학의 BDS(Biocomputing and Development Systems.
- 마이클 오닐의 문법적 진화 페이지에는 참고 문헌 목록이 포함되어 있다.
- DRP(Directed Ruby Programming)는 사용자가 하이브리드 GE/GP 시스템을 만들 수 있도록 설계된 실험 시스템이다.그것은 순수한 루비로 구현된다.
- GERET, 문법 진화 루비 탐험 도구 키트.
- 그래미볼, R을 위한 문법적 진화.
