염색체(유전자 알고리즘)

다음 시리즈의 일부
진화 알고리즘
인공발달성 인공생명체 세포진화 알고리즘 문화 알고리즘 미분진화 효과적인 피트니스 진화 연산 진화전략 가우스 적응 진화적 다중모드 최적화 입자 군집 최적화 메미틱 알고리즘 자연 진화 전략 신경진화 프로모터 기반 유전 알고리즘 나선 최적화 알고리즘 자체수정코드 다형 코드
유전 알고리즘
염색체 클론 선택 알고리즘 크로스오버 돌연변이 유전적 기억력 유전 퍼지 시스템 선택 플라이 알고리즘
유전자 프로그래밍
데카르트 유전 프로그래밍 선형유전자프로그래밍 문법적 진화 다중 표현식 프로그래밍 유전적 개선 스키마 유리스코 패리티 벤치마크
v t

유전자 알고리즘에서 염색체(genotype이라고도 함)는 유전자 알고리즘이 해결하려고 하는 문제에 대한 제안된 해결책을 정의하는 매개변수 집합이다. 모든 해결책의 집합은 모집단으로 알려져 있다.^[1] 염색체는 매우 다양한 다른 데이터 구조도 사용되지만 종종 이진 문자열로 표현된다.

염색체 설계

염색체의 설계와 그 매개변수는 반드시 해결해야 할 문제에 특유하다. 전통적으로 염색체는 0s와 1s의 문자열로서 2진법으로 표현되지만, 다른 인코딩도 가능하다;^[2] 용액을 유한한 길이의 문자열로 나타낼 수 있는 거의 모든 표현을 사용할 수 있다.^[3] 염색체에 대한 문제 영역의 적절한 표현을 찾는 것은 중요한 고려사항이다. 좋은 표현은 검색 공간을 제한함으로써 검색을 더 쉽게 만들 수 있기 때문이다. 마찬가지로, 더 낮은 표현은 더 큰 검색 공간을 허용할 것이다.^[4] 유전자 알고리즘에 의해 고용된 돌연변이 연산자와 교차 연산자는 염색체의 설계도 고려해야 한다.

예제 1: 이진 표현

$f{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$에 대한 최대 결과를 제공하는 $0$과 255 사이의$$ x ${\displaystyle$ x$}$의 정수 값을 찾는 것이 문제라고 가정합시다$.$ 이 문제에 대한 가능한 해결책은 모두 8자리 이진 문자열로 나타낼 수 있는 0부터 255까지의 정수다. 따라서, 우리는 염색체로서 8자리 이진 문자열을 사용할 수도 있다. 만약 모집단에서 주어진 염색체가 155의 값을 나타낸다면, 그 염색체는 10011011.

이것은 일반적으로 유전 알고리즘에 의해 해결되는 문제의 유형이 아니라는 점에 유의하십시오. 이는 숫자적인 방법을 사용하여 사소한 해결이 가능하기 때문이다. 이것은 단순한 예로서만 사용된다.

예제 2: 문자열 표현

우리가 해결하고자 할 수 있는 더 현실적인 문제는 여행 판매원 문제다. 이 문제에서, 우리는 판매원이 여행할 수 있는 가장 짧은 여행이 되는 도시들의 주문 목록을 구한다. 우리가 A, B, C, D, E, F라고 부르는 6개의 도시가 있다고 가정합시다. 우리 염색체를 위한 좋은 디자인은 우리가 시도하고 싶은 순서 목록일 것이다. 우리가 인구에서 마주칠 수 있는 염색체의 예는 DFABEC.

선택, 교차 및 돌연변이

유전 알고리즘의 각 세대에서, 두 개의 부모 염색체를 그들의 건강 가치에 기초하여 선택한다; 이 염색체들은 돌연변이와 교차 연산자에 의해 새로운 모집단을 위한 두 개의 자손 염색체를 생산하기 위해 사용된다.^[3]

참조