유전자 발현 프로그래밍

이 기사의 주요 기고자는 그 주제와 밀접한 관련이 있는 것으로 보인다.Wikipedia의 콘텐츠 정책, 특히 중립적인 관점을 준수하기 위해 청소가 필요할 수 있습니다.토크 페이지에서 더 자세히 논의해 주세요. (2012년 11월)(이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

컴퓨터 프로그래밍에서 유전자 표현 프로그래밍(GEP)은 컴퓨터 프로그램이나 모델을 만드는 진화 알고리즘이다.이 컴퓨터 프로그램들은 살아있는 유기체처럼 크기, 모양, 구성을 바꿈으로써 배우고 적응하는 복잡한 나무 구조이다.그리고 살아있는 유기체와 마찬가지로 GEP의 컴퓨터 프로그램도 고정된 길이의 단순한 선형 염색체로 암호화되어 있습니다.따라서 GEP는 유전자형-표현형 시스템으로 유전자 정보를 보관하고 전달하는 단순한 게놈과 환경을 탐색하고 적응하는 복잡한 표현형으로부터 이익을 얻는다.

배경

진화 알고리즘은 개인의 집단을 사용하고, 적합성에 따라 개인을 선택하고, 하나 이상의 유전자 연산자를 사용하여 유전자 변이를 도입합니다.인공 계산 시스템에 이러한 기술을 사용한 것은 최적화 문제를 해결하기 위해 사용되었던 1950년대(예: Box^[1] 1957 및^[2] Friedman 1959)로 거슬러 올라간다.그러나 진화 알고리즘이 인기를 끈 것은 1965년^[3] 레첸버그의 진화 전략의 도입과 함께였다.진화 알고리즘에 대한 좋은 개요 텍스트는 미첼(1996)^[4]의 "유전자 알고리즘 소개" 책이다.

유전자 발현 프로그래밍은^[5] 진화 알고리즘 계열에 속하며 유전 알고리즘 및 유전 프로그래밍과 밀접한 관련이 있습니다.유전 알고리즘으로부터 그것은 고정된 길이의 선형 염색체를 물려받았고, 유전 프로그래밍으로부터 그것은 다양한 크기와 모양의 표현 해석 나무를 물려받았습니다.

유전자 발현 프로그래밍에서 선형 염색체는 유전자형으로, 구문 분석 나무는 표현형으로 작용하여 유전자형/표현형 시스템을 만듭니다.이 유전자형/표현형 시스템은 다유전적이며, 따라서 각 염색체의 다중 해석 트리를 부호화한다.즉, GEP에 의해 작성된 컴퓨터 프로그램은 여러 해석 트리로 구성되어 있습니다.이러한 해석 트리는 유전자 발현의 결과이기 때문에 GEP에서는 발현 트리라고 불립니다.

부호화: 유전자형

유전자 발현 프로그래밍의 게놈은 같은 크기의 하나 이상의 유전자로 구성된 고정된 길이의 선형, 상징적 끈 또는 염색체로 구성됩니다.이 유전자들은 고정된 길이에도 불구하고 크기와 모양이 다른 발현 나무를 코드화한다.각각 크기가 9인 두 개의 유전자를 가진 염색체의 예는 끈이다(위치는 각 유전자의 시작을 나타낸다).

012345678012345678

L+a-baccd**cLabacd

여기서 "L"은 자연 로그 함수를 나타내고 "a", "b", "c" 및 "d"는 문제에 사용된 변수와 상수를 나타냅니다.

식 트리: 표현형

위와 같이 유전자 발현 프로그래밍의 유전자는 모두 같은 크기를 가지고 있다.단, 이러한 고정 길이의 문자열은 크기가 다른 식 트리를 코드화합니다.이는 코딩 부위의 크기가 유전자마다 다르므로 적응과 진화가 원활하게 이루어질 수 있다는 것을 의미한다.

예를 들어, 수식은 다음과 같습니다.

${\displaystyle {(a-b)(c+d)},$

는 식 트리로도 나타낼 수 있습니다.

여기서 "Q"는 제곱근 함수를 나타냅니다.

이러한 종류의 발현 트리는 GEP 유전자의 표현형 발현으로 구성되는 반면 유전자는 이러한 복잡한 구조를 코드하는 선형 문자열입니다.이 예에서 선형 문자열은 다음 항목에 해당합니다.

01234567

Q*-+abcd

위에서 아래로, 왼쪽에서 오른쪽으로 표현 트리를 쉽게 읽을 수 있습니다.이러한 선형 문자열을 K-식이라고 합니다(Karva 표기법에서).

k-표현식에서 식 트리로 이동하는 것도 매우 간단합니다.예를 들어 다음과 같은 k-식입니다.

01234567890

Q*b**+baQba

는, 2개의 다른 단말(변수 「a」와 「b」), 2개의 인수(「*」와「+」)의 2개의 다른 함수, 및 1개의 인수(「Q」)의 함수로 구성됩니다.표현은 다음과 같습니다.

K-발현과 유전자

유전자 발현 프로그래밍의 k-발현은 발현되는 유전자의 영역에 대응한다.이것은 유전자에 발현되지 않은 배열이 있을 수 있다는 것을 의미하는데, 이것은 사실 대부분의 유전자에 해당된다.이러한 비부호화 영역의 이유는 GEP 유전자로 인코딩된 모든 k-표현이 항상 유효한 프로그램 또는 표현에 대응하도록 단말기의 버퍼를 제공하기 위함이다.

따라서 유전자 발현 프로그래밍의 유전자는 각각 다른 특성과 기능을 가진 머리와 꼬리라는 두 개의 다른 영역으로 구성되어 있다.헤드는 주로 당면한 문제를 해결하기 위해 선택된 함수와 변수를 인코딩하는 데 사용되는 반면, 테일은 기본적으로 모든 프로그램이 오류가 없음을 보장하기 위해 터미널 저장소를 제공합니다.

GEP 유전자의 경우 꼬리의 길이는 다음 공식으로 나타납니다.

${\displaystyle t=h(n_{\max }-1)+1}$

여기서 h는 머리 길이, n은_max 최대 각도입니다.예를 들어 기능 F = {Q, +, -, δ, /} 및 말단 T = {a, b}, n_max = 2를 사용하여 생성된 유전자의 경우.머리 길이를 15로 하면 t = 15 (2–1) + 1 = 16으로 유전자 길이 g는 15 + 16 = 31이 됩니다.아래 무작위로 생성된 문자열은 이러한 유전자의 한 예입니다.

0123456789012345678901234567890

*b+a-aQab+//+b+babbabbbababbaaa

식 트리를 부호화합니다.

이 경우에는 유전자를 구성하는 31가지 요소 중 8가지 요소만 사용합니다.

그들의 고정된 길이에도 불구하고, 각각의 유전자는 크기와 모양이 다른 발현 나무를 코드화할 수 있는 잠재력을 가지고 있다는 것을 어렵지 않게 알 수 있습니다, 가장 단순한 것은 오직 하나의 노드(유전자의 첫 번째 요소가 말단일 때)로 구성되고 가장 큰 것은 유전자에 있는 요소들의 수만큼 많은 노드들로 구성됩니다.최대 특성으로 기능합니다).

또한 모든 결과적인 자손들이 정확하고 오류 없는 프로그램을 암호화한다는 보장을 가지고 모든 종류의 유전자 변형(변형, 반전, 삽입, 재조합 등)을 실행하는 것이 사소한 일이라는 것을 어렵지 않게 알 수 있다.

다원적 염색체

유전자 발현 프로그래밍의 염색체는 보통 같은 길이의 하나 이상의 유전자로 구성되어 있다.각 유전자는 서브 발현 트리(sub-ET) 또는 서브 프로그램을 코드화한다.그러면 서브 ET는 서로 다른 방식으로 상호 작용하여 더 복잡한 프로그램을 형성할 수 있습니다.그림에서는 3개의 서브ET로 구성된 프로그램의 예를 보여 줍니다.

최종 프로그램에서는 서브 ET를 추가 또는 다른 기능으로 링크할 수 있다.이는 사용자가 선택할 수 있는 링크 기능의 종류에 제한이 없기 때문이다.더 복잡한 링커의 예로는 평균, 중앙값, 미드레인지, 이항 분류를 위해 합계를 역치화, 확률을 계산하기 위해 Sigmoid 함수를 적용하는 등이 있습니다.이러한 연결 기능은 보통 각각의 문제에 대해 우선적으로 선택되지만, 그것들은 또한 유전자 발현 프로그래밍의 세포^[6][7] 시스템에 의해 우아하고 효율적으로 진화될 수 있습니다.

셀 및 코드 재사용

유전자 발현 프로그래밍에서 동종 유전자는 메인 프로그램의 다른 서브 ET 또는 모듈의 상호작용을 제어한다.그러한 유전자의 발현은 다른 주요 프로그램이나 세포를 낳는다. 즉, 그것들은 각 세포에서 발현되는 유전자와 각 세포의 서브 ET가 서로 어떻게 상호작용하는지를 결정한다.다른 말로 하자면, 동종 유전자는 어떤 서브 ET가 얼마나 자주 호출되는지, 그리고 어떤 메인 프로그램이나 세포가 서로 어떤 종류의 연결을 형성하는지 결정한다.

동종유전자 및 세포계

호메오틱 유전자는 정상 유전자와 정확히 같은 종류의 구조 구조를 가지고 있으며 그들은 동일한 과정을 통해 만들어진다.그것들은 또한 머리 도메인과 꼬리 도메인을 포함하며, 머리에는 현재 정상적인 유전자를 나타내는 연결 기능과 특별한 종류의 말단인 유전자 말단이 포함되어 있다는 차이점을 가지고 있다.정상 유전자의 발현은 세포 시스템에서 ADF(자동으로 정의된 기능)라고 불리는 다른 서브 ET에서 평소와 같이 발생한다.테일에는 제네릭 단자, 즉 알고리즘에 의해 플라이로 생성되는 파생 피쳐만 포함되어 있습니다.

예를 들어, 그림 속의 염색체는 3개의 정상 유전자와 1개의 동종 유전자를 가지고 있으며, 3개의 다른 기능을 호출하는 주요 프로그램을 총 4회 암호화하여 특정한 방식으로 연결한다.

이 예에서 셀룰러 시스템은 링크 기능의 제약 없는 진화뿐만 아니라 코드 재사용도 가능하게 합니다.그리고 이 시스템에 재귀 구현은 어렵지 않을 것입니다.

다중 메인 프로그램 및 다세포 시스템

다세포 시스템은 하나 이상의 동종 유전자로 구성되어 있다.이 시스템의 각 동종 유전자는 여러 개의 세포나 주요 프로그램을 만들면서 하위 발현 나무 또는 ADF의 다른 조합을 결합합니다.

예를 들어, 그림에 표시된 프로그램은 두 개의 세포와 세 개의 정상 유전자를 가진 세포 시스템을 사용하여 만들어졌습니다.

이러한 다세포 시스템의 용도는 다원적이고 다양하며, 다원적 시스템과 마찬가지로 하나의 출력 문제에서도 다중 출력 문제에서도 사용할 수 있습니다.

다른 수준의 복잡성

GEP 유전자의 머리/꼬리 도메인(정상 및 호메오틱 모두)은 모든 GEP 알고리즘의 기본 구성 요소이다.그러나 유전자 발현 프로그래밍은 머리/꼬리 구조보다 더 복잡한 다른 염색체 조직도 탐색한다.기본적으로 이러한 복잡한 구조는 기본 머리/꼬리 도메인과 하나 이상의 추가 도메인을 가진 기능 단위 또는 유전자로 구성된다.이러한 추가 도메인은 보통 알고리즘이 적절한 솔루션을 찾기 위해 끊임없이 미세 조정되는 랜덤 수치 상수를 인코딩합니다.예를 들어, 이러한 수치 상수는 함수 근사 문제의 가중치 또는 요인(아래 GEP-RNC 알고리즘 참조), 신경망의 가중치 및 임계값(아래 GEP-NN 알고리즘 참조), 의사결정 트리의 설계에 필요한 수치 상수(아래 GEP-DT 알고리즘 참조)가 될 수 있습니다.d - 다항식 유도 또는 매개변수 최적화 작업에서 매개변수 값을 발견하는 데 사용되는 랜덤 숫자 상수.

기본 유전자 발현 알고리즘

기본 유전자 발현 알고리즘의 기본 단계는 다음과 같습니다.

1. 함수 세트를 선택합니다.
2. 터미널 세트를 선택합니다.
3. 적합성 평가를 위한 부하 데이터 세트
4. 최초 모집단의 염색체를 무작위로 생성한다.
5. 모집단의 각 프로그램에 대해:
   1. 발현 염색체
   2. 프로그램 실행
   3. 적합성 평가
6. 정지 상태를 확인합니다.
7. 프로그램 선택
8. 선택한 프로그램을 복제하여 다음 모집단을 형성한다.
9. 유전자 연산자를 사용하여 염색체를 수정한다.
10. 스텝 5로 넘어갑니다.

첫 번째 4단계에서는 알고리즘의 반복 루프에 필요한 모든 성분을 준비합니다(5~10단계).이러한 준비 단계 중 중요한 것은 함수와 단말 세트의 요소를 사용하여 무작위로 생성되는 초기 모집단의 생성이다.

프로그램 집단

모든 진화 알고리즘과 마찬가지로 유전자 발현 프로그래밍은 개인의 집단과 함께 작동하는데, 이 경우에는 컴퓨터 프로그램입니다.따라서, 일을 시작하기 위해 어떤 종류의 초기 인구가 생성되어야 합니다.후속 모집단은 선택과 유전자 수정을 통해 초기 모집단의 후손이다.

유전자 발현 프로그래밍의 유전자형/표현형 체계에서, 그들의 표현은 항상 구문적으로 올바른 프로그램을 낳기 때문에, 그들이 코드하는 프로그램의 구조적 건전성에 대해 걱정하지 않고 개인의 단순한 선형 염색체를 생성하기만 하면 된다.

피트니스 기능 및 선택 환경

피트니스 기능과 선택 환경(기계 학습에서는 트레이닝 데이터 세트라고 함)은 피트니스의 두 가지 측면이며, 따라서 복잡하게 연결되어 있습니다.실제로, 프로그램의 적합성은 성능 측정에 사용되는 비용 함수뿐만 아니라 적합성을 평가하기 위해 선택된 훈련 데이터에 의해서도 좌우된다.

선택 환경 또는 교육 데이터

선발 환경은 일련의 훈련 기록으로 구성되어 있으며, 이는 피트니스 케이스라고도 불립니다.이러한 피트니스 케이스는, 몇개의 문제에 관한 관찰이나 측정의 집합이 될 수 있습니다.이러한 케이스는, 트레이닝 데이터 세트라고 불리는 것을 형성합니다.

트레이닝 데이터의 품질은, 좋은 솔루션의 진화에 불가결합니다.적절한 트레이닝 세트는, 당면한 문제를 나타내어 밸런스가 좋은 것이어야 합니다.그렇지 않으면 알고리즘이 로컬 최적에서 막혀 버릴 수 있습니다.또한 불필요한 대규모 데이터셋을 교육에 사용하지 않는 것도 중요합니다. 이렇게 하면 작업이 불필요하게 느려지기 때문입니다.경험에 비추어 볼 때 검증 데이터를 적절히 일반화할 수 있도록 훈련에 필요한 충분한 레코드를 선택하고 나머지 레코드는 검증 및 테스트용으로 남겨두는 것이 좋습니다.

피트니스 기능

일반적으로 예측의 종류에 따라 기본적으로 세 가지 종류의 문제가 있습니다.

1. 수치(연속) 예측과 관련된 문제
2. 이항 및 다항 예측 모두 범주형 또는 명목 예측과 관련된 문제
3. 이진 또는 부울 예측과 관련된 문제입니다.

첫 번째 유형의 문제는 회귀라는 이름으로 진행되며, 두 번째 문제는 분류로 알려져 있으며, 로지스틱 회귀는 "예" 또는 "아니오"와 같은 명확한 분류 외에 각 결과에 확률도 부가됩니다. 마지막 문제는 부울 대수 및 논리 합성과 관련이 있습니다.

회귀를 위한 적합성 함수

회귀 분석에서 반응 또는 종속 변수는 숫자(일반적으로 연속형)이므로 회귀 모형의 출력도 연속형입니다.따라서 모델의 출력과 교육 데이터의 응답 값을 비교하여 진화하는 모델의 적합성을 평가하는 것은 매우 간단합니다.

모형 성능을 평가하기 위한 몇 가지 기본 적합성 함수가 있으며, 가장 일반적인 것은 모형 출력과 실제 값 사이의 오차 또는 잔차를 기반으로 하는 것입니다.이러한 함수에는 평균 제곱 오차, 루트 평균 제곱 오차, 평균 절대 오차, 상대 제곱 오차, 루트 상대 제곱 오차, 상대 절대 오차 등이 포함됩니다.

이러한 모든 표준 척도는 솔루션 공간에 세세한 부분이나 매끄러운 정도를 제공하기 때문에 대부분의 애플리케이션에서 매우 잘 작동합니다.그러나 예측이 특정 간격(예: 실제 값의 10% 미만) 내에 있는지 확인하는 등 일부 문제는 더 거친 진화가 필요할 수 있습니다.그러나 히트 카운트에만 관심이 있더라도(즉, 선택한 간격 내에 있는 예측), 각 프로그램 점수가 히트 수만을 기반으로 모델 모집단을 진화시키는 것은 일반적으로 피트니스 환경의 거친 세분성 때문에 매우 효율적이지 않다.따라서 일반적으로 솔루션은 위의 표준 오차 측정값과 같은 부드러운 함수와 이러한 거친 측정값을 결합하는 것을 포함합니다.

상관 계수와 R-제곱에 기초한 적합성 함수 또한 매우 부드럽습니다.회귀 문제의 경우 이러한 함수는 모형 출력의 값 범위를 고려하지 않고 상관 관계만 측정하는 경향이 있기 때문에 다른 측도와 결합하는 것이 가장 효과적입니다.따라서 목표값의 범위를 근사하는 함수와 결합함으로써 예측값과 실제값 사이의 상관관계가 좋고 적합성이 좋은 모델을 찾기 위한 매우 효율적인 적합성 함수를 형성합니다.

분류 및 로지스틱 회귀 분석을 위한 적합성 함수

분류 및 로지스틱 회귀 분석을 위한 적합성 함수 설계는 분류 모형의 세 가지 특성을 활용합니다.가장 확실한 것은 히트수를 세는 것, 즉 기록이 올바르게 분류되면 히트수로 계산된다는 것입니다.이 적합성 기능은 매우 단순하고 단순한 문제에는 잘 작동하지만, 보다 복잡한 문제나 데이터 집합의 불균형에는 좋지 않은 결과를 가져옵니다.

이러한 유형의 히트 기반 피트니스 기능을 개선하는 한 가지 방법은 올바른 분류와 잘못된 분류의 개념을 확장하는 것이다.이진 분류 작업에서는 올바른 분류는 00 또는 11이 될 수 있습니다."00"은 음의 경우("0"으로 표시됨)가 올바르게 분류되었음을 의미하며, "11"은 양의 경우("1"로 표시됨)가 올바르게 분류되었음을 의미한다.타입 「00」의 분류는, True Negative(TN) 및 True Positive(TP)라고 불립니다.

또한 두 가지 유형의 잘못된 분류가 있으며 01과 10으로 표시됩니다.실제 값이 0이고 모형이 1을 예측하면 False Positive(FP; 거짓 양수)라고 하며, 목표값이 1이고 모형이 0을 예측하면 FN(거짓 음수)이라고 합니다.TP, TN, FP 및 FN의 카운트는 일반적으로 혼동 매트릭스로 알려진 테이블에 저장됩니다.

이항 분류 작업에 대한 혼란 행렬입니다.

		예측 클래스
		네.	아니요.
실제. 학급	네.	TP	FN
	아니요.	FP	TN

따라서 TP, TN, FP 및 FN을 계수하고 이들 4가지 분류에 서로 다른 가중치를 추가로 할당함으로써 보다 부드럽고 효율적인 피트니스 기능을 만들 수 있습니다.혼란 매트릭스에 기반한 일부 인기 있는 피트니스 함수에는 민감도/특이성, 리콜/정밀성, F-측정, 자카드 유사성, 매튜스 상관계수, 4가지 다른 분류 유형에 할당된 비용과 이득을 결합한 비용/게인 매트릭스가 포함된다.

혼란 매트릭스에 기초한 이러한 함수는 매우 정교하며 대부분의 문제를 효율적으로 해결하기에 적합합니다.그러나 분류 모델에는 솔루션 공간을 보다 효율적으로 탐색하는 데 중요한 또 다른 차원이 있어 더 나은 분류자를 발견할 수 있습니다.이 새로운 차원은 도메인 및 범위뿐만 아니라 모델 출력의 분포와 분류자 마진을 포함하는 모델 자체의 구조를 탐색하는 것을 포함합니다.

이 다른 차원의 분류 모델을 탐색하고 모델에 대한 정보를 혼란 매트릭스와 결합함으로써 솔루션 공간을 원활하게 탐색할 수 있는 매우 정교한 피트니스 함수를 설계할 수 있습니다.예를 들어, 원시 모델 출력과 실제 값 사이에서 평가된 평균 제곱 오차와 혼동 행렬에 기초한 일부 측정을 결합할 수 있습니다.또는 F 측정값을 원시 모형 출력 및 목표값에 대해 평가된 R-제곱과 결합하거나 상관 계수를 사용하는 비용/게인 행렬 등을 결합할 수 있습니다.모델 입도를 탐구하는 보다 이국적인 피트니스 기능에는 ROC 곡선 아래 영역과 순위 측정이 포함됩니다.

또한 이 새로운 차원의 분류 모형과 관련이 있는 것은 로지스틱 회귀 분석에서 수행되는 모형 출력에 확률을 할당하는 것입니다.그런 다음 이러한 확률을 사용하여 확률과 실제 값 사이의 평균 제곱 오차(또는 다른 유사한 측도)를 평가한 다음 이를 혼란 행렬과 결합하여 로지스틱 회귀 분석을 위한 매우 효율적인 적합 함수를 생성할 수도 있습니다.확률에 기초한 피트니스 함수의 일반적인 예로는 최대우도 추정과 힌지 손실이 있다.

부울 문제에 대한 적합성 함수

논리학에는 (분류 및 로지스틱 회귀에 대해 위에서 정의한) 모델 구조가 없습니다. 논리 함수의 도메인과 범위는 0과 1로 구성되거나 false와 true로 구성됩니다.따라서 부울 대수에 사용할 수 있는 적합성 함수는 위의 절에서 설명한 대로 히트 또는 혼란 행렬에만 기초할 수 있습니다.

선택과 엘리트주의

룰렛 휠 선택은 아마도 진화 계산에 사용되는 가장 인기 있는 선택 체계일 것이다.이것은 각 프로그램의 적합성에 비례하는 룰렛 휠 조각에 각 프로그램의 적합성을 매핑하는 것을 포함합니다.그리고 룰렛은 모집단의 크기를 일정하게 유지하기 위해 모집단의 프로그램 수만큼 회전한다.따라서 룰렛 휠 선택 프로그램은 적합성과 추첨 운에 따라 선택되며, 이는 때때로 최상의 특성이 상실될 수 있음을 의미합니다.그러나 룰렛 휠 선택과 각 세대의 최고의 프로그램 복제를 결합함으로써 최소한 최고의 특성이 손실되지 않음을 보증한다.가장 우수한 프로그램을 복제하는 이 기술은 단순 엘리트주의로 알려져 있으며 대부분의 확률적 선택 체계에 사용된다.

수정에 의한 재생

프로그램의 재생산에는 우선 그들의 게놈을 선택하고 그 다음에 복제하는 것이 포함됩니다.게놈 수정은 번식을 위해 필요하지 않지만, 그것이 없으면 적응과 진화는 일어나지 않을 것이다.

레플리케이션 및 선택

선택 연산자는 복제 연산자가 복사할 프로그램을 선택합니다.선택 방식에 따라서는, 1개의 프로그램의 카피의 개수가 다를 수 있습니다.복사되는 프로그램이 여러 개 있는 반면, 1회만 복사되거나 전혀 복사되지 않는 프로그램도 있습니다.또한 일반적으로 모집단 크기가 한 세대에서 다른 세대로 일정하게 유지되도록 선택이 설정됩니다.

자연에서 게놈의 복제는 매우 복잡하며 과학자들이 DNA 이중나선을 발견하고 복제 메커니즘을 제안하는데 오랜 시간이 걸렸다.그러나 유전체 내의 모든 정보를 세대에서 세대로 전달하기 위해 문자열을 복사하는 명령만 필요한 인공 진화 시스템에서 문자열의 복제는 사소한 일이다.

선택된 프로그램의 복제는 모든 인공 진화 시스템의 기본 요소이지만 진화가 이루어지려면 복사 명령의 통상적인 정밀도가 아니라 몇 가지 오류를 삽입하여 구현해야 합니다.실제로, 유전적 다양성은 돌연변이, 재조합, 전위, 반전, 그리고 많은 다른 것들과 같은 유전자 연산자들과 함께 만들어진다.

돌연변이

유전자 발현에서 돌연변이는 가장 중요한 유전자 ^[8]연산자이다.그것은 한 원소를 다른 원소로 바꾸면서 게놈을 바꾼다.시간이 지남에 따라 많은 작은 변화들이 축적되면 큰 다양성을 만들어 낼 수 있다.

유전자 발현 프로그래밍 돌연변이는 완전히 제약되지 않으며, 이것은 각 유전자 영역에서 어떤 도메인 기호가 다른 것으로 대체될 수 있다는 것을 의미합니다.예를 들어 유전자의 선두에서는 이 새로운 함수의 인수 수에 관계없이 어떤 함수도 단자 또는 다른 함수로 대체될 수 있으며, 단자는 함수 또는 다른 단자로 대체될 수 있다.

재결합

재조합은 보통 부모 염색체와 다른 부분을 결합함으로써 두 개의 새로운 염색체를 만들기 위해 두 개의 부모 염색체를 포함한다.그리고 부모 염색체가 정렬되어 교환된 조각들이 상동성이 있는 한, 재조합에 의해 만들어진 새로운 염색체들은 항상 구문적으로 올바른 프로그램을 부호화할 것입니다.

다른 종류의 크로스오버는 관련된 부모의 수(2개만 선택할 이유가 없음)나 분할점의 수, 또는 랜덤 또는 어떤 질서 있는 방법으로 조각을 교환하는 방법을 변경함으로써 쉽게 구현됩니다.예를 들어, 유전자 재조합의 특별한 경우인 유전자 재조합은 상동 유전자(염색체에서 같은 위치를 차지하는 유전자)를 교환하거나 염색체 내의 임의의 위치에서 무작위로 선택된 유전자를 교환함으로써 이루어질 수 있다.

전위

전이는 염색체 어딘가에 삽입 순서를 도입하는 것을 포함한다.유전자 발현 프로그래밍에서 삽입 시퀀스는 염색체의 아무 곳이나 나타날 수 있지만, 그것들은 유전자의 머리에만 삽입된다.이 방법을 사용하면 테일에서 삽입된 시퀀스도 오류가 없는 프로그램을 만들 수 있습니다.

전이가 제대로 되려면 염색체 길이와 유전자 구조를 보존해야 한다.따라서 유전자 발현에서 프로그래밍 전위는 두 가지 다른 방법을 사용하여 구현될 수 있습니다. 첫 번째 방법은 삽입 부위에서 이동을 생성하고, 두 번째 방법은 머리 끝에서 삭제됩니다. 두 번째 방법은 대상 부위에서 로컬 시퀀스를 덮어쓰므로 구현하기가 더 쉽습니다.두 가지 방법 모두 염색체 간 또는 염색체 내 또는 단일 유전자 내에서 작동하도록 구현될 수 있습니다.

반전

인버전(Inversion)은 흥미로운 연산자로 조합 최적화에 ^[9]특히 강력합니다.그것은 염색체 내의 작은 염기서열을 뒤집는 것으로 구성되어 있다.

유전자 발현 프로그래밍에서 그것은 모든 유전자 영역에서 쉽게 구현될 수 있고, 모든 경우에, 생성된 자손은 항상 구문적으로 정확하다.모든 유전자 영역에 대해, 염기서열(적어도 두 가지 요소에서 도메인 자체만큼 큰 범위)은 그 영역 내에서 무작위로 선택되고 그 후에 반전된다.

기타 유전자 조작자

몇몇 다른 유전자 연산자들이 존재하며 유전자 발현 프로그래밍에서는 다른 유전자와 유전자 영역을 가지고, 가능성은 무한하다.예를 들어 원포인트 재조합, 2포인트 재조합, 유전자 재조합, 균일한 재조합, 유전자 전위, 뿌리 전위, 도메인 특이적 돌연변이, 도메인 특이적 반전, 도메인 특이적 전위 등의 유전자 연산자를 쉽게 구현하여 널리 이용할 수 있다.

GEP-RNC 알고리즘

수치 상수는 수학적 및 통계적 모델의 필수 요소이므로 진화 알고리즘에 의해 설계된 모델에 통합할 수 있도록 하는 것이 중요하다.

유전자 발현 프로그래밍은 랜덤 수치 상수(RNC)를 처리하기 위해 추가적인 유전자 영역인 Dc를 사용함으로써 이 문제를 매우 우아하게 해결합니다.이 도메인을 RNC 전용 단말 플레이스 홀더와 조합함으로써 풍부한 표현력을 갖춘 시스템을 구축할 수 있다.

구조적으로 Dc는 꼬리 뒤에 오고 꼬리 t의 크기와 동일한 길이를 가지며 RNC를 나타내기 위해 사용되는 기호로 구성됩니다.

예를 들어, 아래는 머리 크기가 7인 하나의 유전자로 구성된 단순한 염색체이다(Dc는 위치 15~22에 걸쳐 있다).

01234567890123456789012

+?*+?**aaa??aaa68083295

여기서 터미널 "?"는 RNC의 플레이스 홀더를 나타냅니다.이러한 종류의 염색체는 위와 같이 정확하게 발현되어 다음과 같이 나타납니다.

그런 다음 식 트리의 ?는 왼쪽에서 오른쪽으로, 위에서 아래로 Dc의 기호(간단하게 숫자로 표시됨)로 대체되어 다음과 같이 나타납니다.

이러한 기호에 대응하는 값은 배열에 보관됩니다(간단히 하기 위해 숫자로 표시되는 숫자는 배열의 순서를 나타냅니다).예를 들어, RNC의 다음 10 요소 배열의 경우:

C = {0.611, 1.184, 2.449, 2.98, 0.496, 2.286, 0.93, 2.305, 2.185, 0.755}

위의 식 트리는 다음과 같습니다.

랜덤 수치 상수를 처리하기 위한 이 우아한 구조는 GEP 뉴럴 네트워크 및 GEP 의사결정 트리와 같은 다양한 GEP 시스템의 핵심이다.

기본 유전자 발현 알고리즘과 마찬가지로 GEP-RNC 알고리즘도 다유전이며, 그 염색체는 하나의 유전자를 차례로 발현시킨 후 동일한 종류의 연결 과정에 의해 모두 결합함으로써 평상시와 같이 복호화된다.

GEP-RNC 시스템에 사용되는 유전자 연산자는 기본 GEP 알고리즘의 유전자 연산자에 대한 확장(위 참조)이며, 이들 모두는 이러한 새로운 염색체에 직접 구현될 수 있다.한편, GEP-RNC 알고리즘에서는 돌연변이, 반전, 전위 및 재조합의 기본 연산자도 사용된다.또한 변환, 반전, 전이와 같은 특별한 DC 고유 연산자도 개별 프로그램 간의 RNC 순환을 보다 효율적으로 지원하기 위해 사용됩니다.또한 특별한 돌연변이 연산자가 있어 RNC 세트에 영구적인 변동을 도입할 수 있습니다.RNC의 초기 세트는 실행 시작 시 무작위로 생성되며, 이는 초기 모집단의 각 유전자에 대해 특정 범위에서 선택된 지정된 수의 숫자 상수가 무작위로 생성됨을 의미한다.그리고 그들의 순환과 돌연변이는 유전자 조작자에 의해 가능하게 된다.

뉴럴 네트워크

인공신경망(ANN 또는 NN)은 많은 단순 연결 단위 또는 뉴런으로 구성된 계산 장치입니다.장치 간의 연결은 일반적으로 실제 값 가중치에 의해 가중됩니다.이러한 가중치는 신경망의 주요 학습 수단이며 학습 알고리즘은 보통 그것들을 조정하기 위해 사용됩니다.

구조적으로 뉴럴 네트워크에는 입력 단위, 숨겨진 단위 및 출력 단위의 세 가지 다른 클래스가 있습니다.활성화 패턴은 입력 유닛에 제시되며, 입력 유닛에서 하나 이상의 숨겨진 유닛 레이어를 통해 출력 유닛으로 전진 방향으로 확산된다.다른 유닛에서1개의 유닛에 도달하는 활성화에, 그 유닛이 퍼지는 링크상의 가중치를 곱합니다.그런 다음 모든 수신 활성화가 함께 추가되고 수신 결과가 장치의 임계값을 초과하는 경우에만 장치가 활성화됩니다.

요약하자면, 뉴럴 네트워크의 기본 구성요소는 단위, 단위 간의 연결, 가중치 및 임계값입니다.따라서 인공신경망을 완전히 시뮬레이션하기 위해서는 어떤 식으로든 이 성분들을 선형 염색체로 부호화해서 의미 있는 방법으로 표현할 수 있어야 합니다.

GEP 뉴럴 네트워크(GEP-NN 또는 GEP 네트)에서는 네트워크 아키텍처는 헤드/^[10]테일 도메인의 통상적인 구조로 부호화됩니다.헤드에는 숨겨진 장치와 출력 장치를 활성화하는 특수 기능/뉴런(GEP 컨텍스트에서는 이러한 모든 장치를 더 적절하게 기능 장치라고 함) 및 입력 장치를 나타내는 단자가 포함되어 있습니다.테일에는 통상대로 단자/입력 장치만 포함됩니다.

머리와 꼬리 외에, 이러한 뉴럴 네트워크 유전자는 뉴럴 네트워크의 무게와 임계값을 인코딩하기 위한 두 개의 추가 도메인, Dw와 Dt를 포함한다.구조적으로 Dw는 꼬리 뒤에 오고 길이_w d는 머리 크기 h와 최대 각도_max n에 따라 달라지며 다음 공식으로 평가됩니다.

${\displaystyle d_{w}=hn_{\max}}$

Dt는 Dw 뒤에 오며 길이_t d는 t와 같습니다.두 도메인은 모두 뉴럴 네트워크의 가중치와 임계값을 나타내는 기호로 구성됩니다.

각 NN-gene에 대해, 체중과 임계값은 각 실행 시작 시 생성되지만, 이들의 순환과 적응은 돌연변이, 전위, 반전 및 재조합의 일반적인 유전자 연산자에 의해 보장된다.또한 가중치 및 임계값 집합에서 유전적 변동의 지속적인 흐름을 허용하기 위해 특수 연산자가 사용된다.

예를 들어, 아래는 2개의 입력 단위(i₁ 및 i₂), 2개의 숨겨진 단위(h₁ 및₂ h), 1개의 출력 단위(o₁)를 가진 신경 네트워크를 보여 줍니다.총 6개의 연결과 6개의 대응하는 가중치가 숫자 1~6으로 나타납니다(간단하게 하기 위해 임계값은 모두 1과 같으며 생략됩니다).

이 표현은 표준 뉴럴 네트워크 표현이지만, 뉴럴 네트워크는 트리로도 표현될 수 있습니다.이 경우, 다음과 같습니다.

여기서 "a"와 "b"는 두 입력₁ i와₂ i를 나타내고 "D"는 연결성 2를 가진 함수를 나타냅니다.이 함수는 무게 부여 인수를 모두 추가한 후 이 액티베이션의 임계값을 설정하여 전송 출력을 결정합니다.이 출력(이 단순한 경우는 0 또는 1)은 각 유닛의 임계값에 의존합니다.즉, 착신 액티베이션의 합계가 임계값 이상인 경우 출력은 1, 그렇지 않은 경우 0입니다.

위의 NN 트리는 다음과 같이 선형화할 수 있습니다.

0123456789012

DDDabab654321

7~12위(Dw)의 구조가 체중을 부호화한다.각 가중치의 값은 배열에 유지되며 표현에 필요한 경우 검색됩니다.

보다 구체적인 예로서 배타적 또는 문제의 뉴럴넷 유전자를 이하에 나타낸다.헤드 사이즈는 3이고 Dw 사이즈는 6입니다.

0123456789012

DDDabab393257

그 표현에 의해 다음과 같은 뉴럴네트워크가 생성됩니다.

무게 집합의 경우:

W = {-1.978, 0.514, -0.465, 1.22, -1.686, -1.797, 0.120, 1.606, 0, 1.7533

다음과 같은 이점이 있습니다.

배타적 기능에 대한 완벽한 해결책입니다.

GEP-nets 알고리즘은 바이너리 입력과 바이너리 출력의 간단한 부울 함수 외에도 모든 종류의 기능 또는 뉴런(선형 뉴런, tanh 뉴런, atan 뉴런, 로지스틱 뉴런, 한계 뉴런, 방사형 기저 및 삼각 기저 뉴런, 모든 종류의 스텝 뉴런 등)을 처리할 수 있습니다.또한 흥미로운 점은 GEP-nets 알고리즘이 이 모든 뉴런을 함께 사용할 수 있고 진화가 어떤 뉴런이 당면한 문제를 해결하기 위해 가장 적합한지를 결정하도록 할 수 있다는 것입니다.따라서 GEP-net은 부울 문제뿐만 아니라 로지스틱 회귀, 분류 및 회귀에서도 사용할 수 있습니다.모든 경우에 GEP-net은 다세대 시스템뿐만 아니라 단세포 및 다세포 시스템에서도 구현될 수 있다.또한 다항 분류 문제는 다세대 시스템과 다세포 시스템 모두에서 GEP-net에 의해 한 번에 해결할 수 있다.

의사결정 트리

의사결정 트리(DT)는 일련의 질문과 답변이 노드 및 방향 가장자리를 사용하여 매핑되는 분류 모델입니다.

Decision Tree에는 루트 노드, 내부 노드 및 리프 노드 또는 터미널 노드의 3가지 노드가 있습니다.루트 노드와 모든 내부 노드는 데이터 집합의 서로 다른 속성 또는 변수에 대한 테스트 조건을 나타냅니다.리프 노드는 트리의 모든 다른 경로에 대한 클래스 레이블을 지정합니다.

대부분의 의사결정 트리 유도 알고리즘은 루트 노드의 속성을 선택한 후 트리 내의 모든 노드에 대해 동일한 종류의 정보에 근거한 결정을 내리는 것을 포함합니다.

결정 트리는 또한 유전자 발현 프로그래밍에 ^[11]의해 만들어질 수 있으며, 나무의 성장에 관한 모든 결정은 어떠한 종류의 인간 입력 없이 알고리즘 자체에 의해 이루어진다는 이점도 있다.

DT 알고리즘에는 기본적으로 두 가지 유형이 있다. 하나는 명목 속성만으로 의사결정 트리를 유도하는 것이고, 다른 하나는 수치 및 명목 속성 모두로 의사결정 트리를 유도하는 것이다.의사 결정 트리 유도의 이러한 측면은 유전자 발현 프로그래밍에도 적용되며 의사 결정 트리 유도를 위한 두 가지 GEP 알고리즘이 있다. 즉, 명목 속성을 단독으로 다루기 위한 진화가능 의사 결정 트리(EDT) 알고리즘과 명목 및 숫자 속성을 모두 다루기 위한 EDT-RNC(랜덤 수치 상수를 가진 EDT)이다.

유전자 발현 프로그래밍에 의해 유도되는 의사결정 나무에서 속성은 기본 유전자 발현 알고리즘에서 기능 노드로서 동작하는 반면 클래스 라벨은 단말로서 동작한다.즉, 속성 노드에는 특정 속성 또는 브랜치 수가 관련지어져 있으며, 이러한 특성 또는 브랜치 수가 트리의 성장을 결정짓습니다.클래스 라벨은 단말기와 같이 동작합니다.즉, k클래스 분류 태스크의 경우 k개의 다른 클래스를 나타내는 k개의 터미널 세트가 사용됩니다.

선형 게놈에서 결정 트리를 인코딩하는 규칙은 수학식을 인코딩하는 데 사용되는 규칙과 매우 유사합니다(위 참조).그래서 의사결정 트리 유도에서는 유전자는 머리와 꼬리를 가지고 있으며, 머리는 속성과 말단을 포함하고 꼬리는 말단만을 포함하고 있습니다.이를 통해 GEP에 의해 설계된 모든 의사결정 트리가 항상 유효한 프로그램임을 확인할 수 있습니다.또, 테일 t의 사이즈는, 헤드 사이즈 h와 브랜치_max n이 많은 속성의 브랜치 수에 의해서도 결정되어 다음 식에 의해서 평가된다.

${\displaystyle t=h(n_{\max }-1)+1,}$

예를 들어, 아래의 Decision Tree를 참조하여 외부에서 재생할지 여부를 결정합니다.

다음과 같이 선형 부호화할 수 있습니다.

01234567

HOWbaaba

여기서 "H"는 습도, "O"는 Outlook, "W"는 Windy, "a"와 "b"는 클래스 레이블 "Yes"와 "No"를 각각 나타냅니다.노드를 연결하는 가장자리는 데이터의 속성이며 각 속성의 유형과 분기 수를 지정하므로 인코딩할 필요가 없습니다.

유전자 발현 프로그래밍에 의한 의사결정 트리 유도 과정은 보통과 같이 무작위로 생성된 염색체의 초기 집단에서 시작됩니다.그런 다음 염색체는 의사결정 트리로 표현되며 훈련 데이터 세트에 대해 적합성이 평가된다.적합성에 따라 수정하여 재생산하도록 선택됩니다.유전자 연산자는 돌연변이, 반전, 전위, 재조합과 같은 전통적인 단일 유전 시스템에서 사용되는 것과 정확히 동일합니다.

명목 및 수치 속성을 모두 가진 의사결정 나무도 랜덤 수치 상수를 다루기 위해 위에서 설명한 프레임워크를 사용하여 유전자 발현 프로그래밍에 의해 쉽게 유도된다.염색체 아키텍처는 랜덤 수치 상수를 부호화하기 위한 추가 도메인을 포함하며, 각 분기 노드에서 데이터를 분할하기 위한 임계값으로 사용된다.예를 들어, 머리 크기가 5인 아래 유전자는 다음과 같습니다(Dc는 위치 16에서 시작합니다).

012345678901234567890

WOTHabababbbabba46336

는 다음과 같은 Decision Tree를 부호화합니다.

이 시스템에서는 헤드의 모든 노드가 그 유형(숫자 속성, 명목 속성 또는 터미널)에 관계없이 랜덤한 수치 상수를 관련지을 수 있습니다.상기 예에서는 간단하게 하기 위해 0 ~9 의 숫자로 나타냅니다.이러한 랜덤한 수치 상수는 DC 도메인에 부호화되어 표현식은 매우 간단한 방식을 따릅니다.즉, 위에서 아래로, 왼쪽에서 오른쪽으로, Dc의 요소는 Decision Tree의 요소에 하나씩 할당됩니다.즉, 다음과 같은 RNC 배열의 경우:

C = {62, 51, 68, 83, 86, 41, 43, 44, 9, 67}

위의 Decision Tree 결과는 다음과 같습니다.

또한 일반적인 의사결정 트리로 더욱 다채롭게 표현될 수 있습니다.

비판

GEP는 다른 유전자 프로그래밍 기술에 비해 크게 향상되지 않았다는 비판을 받아왔다.많은 실험에서 기존 ^[12]방법보다 성능이 좋지 않았습니다.

소프트웨어

상용 어플리케이션

GeneXproTools

GeneXproTools는 Gepsoft가 개발한 예측 분석 스위트입니다.GeneXproTools 모델링 프레임워크에는 로지스틱 회귀, 분류, 회귀, 시계열 예측 및 논리 합성이 포함됩니다.GeneXproTools는 GeneXproTools의 모든 모델링 프레임워크에서 사용되는 기본 유전자 발현 알고리즘과 GEP-RNC 알고리즘을 구현합니다.

오픈 소스 라이브러리

GEP4J – Java 프로젝트용 GEP

Jason Thomas가 개발한 GEP4J는 Java에서의 유전자 발현 프로그래밍의 오픈 소스 구현입니다.이 알고리즘은 진화 결정 트리(공칭 속성, 숫자 속성 또는 혼합 속성) 및 자동으로 정의된 함수를 포함하여 다양한 GEP 알고리즘을 구현합니다.GEP4J는 Google Code에서 호스팅됩니다.

PyGEP – Python용 유전자 발현 프로그래밍

Ryan O'Neil이 Python의 유전자 발현 프로그래밍 학술 연구에 적합한 심플 라이브러리를 만들고 사용 편의성과 신속한 구현을 목표로 하여 만들었습니다.표준 다유전자 염색체와 유전자 조작자 돌연변이, 교차 및 전이를 구현합니다.PyGEP는 Google Code에서 호스팅됩니다.

jGEP – Java GEP 툴킷

Matthew Sottile이 GEP를 사용하는 Java 프로토타입 코드를 신속하게 구축하기 위해 만든 것입니다.이 코드는 C 또는 Fortran 등의 언어로 실제 속도로 작성할 수 있습니다.jGEP는 SourceForge에서 호스트됩니다.

추가 정보

• Ferreira, C. (2006). Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Springer-Verlag. ISBN 3-540-32796-7.
• Ferreira, C. (2002). Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Portugal: Angra do Heroismo. ISBN 972-95890-5-4.

「 」를 참조해 주세요.

• 심볼릭 회귀
• 인공지능
• 의사결정 트리
• 진화 알고리즘
• 유전 알고리즘
• 유전자 프로그래밍
• 문법적 진화
• 선형 유전 프로그래밍
• GeneXproTools
• 기계 학습
• 다중 표현식 프로그래밍
• 뉴럴 네트워크

레퍼런스

외부 링크

• 유전자 발현 프로그래밍의 발명자가 관리하는 GEP 홈페이지.
• GeneXproTools, 상용 GEP 소프트웨어