교차(유전자 알고리즘)
Crossover (genetic algorithm)| 다음 시리즈의 일부 |
| 진화 알고리즘 |
|---|
| 유전 알고리즘 |
| 유전자 프로그래밍 |
유전 알고리즘과 진화 계산에서, 재조합이라고도 불리는 크로스오버는 새로운 자손을 생성하기 위해 두 부모의 유전 정보를 결합하는 데 사용되는 유전 연산자다. 기존 개체군에서 새로운 솔루션을 확률적으로 생성하는 한 가지 방법이며, 생물학에서 성적 재생산 중에 일어나는 크로스오버와 유사하다. 솔루션은 기존 솔루션을 복제함으로써 생성될 수도 있는데, 이는 무성 생식과 유사하다. 새로 생성된 솔루션은 일반적으로 모집단에 추가되기 전에 변이된다.
진화 연산에서의 서로 다른 알고리즘은 유전 정보를 저장하기 위해 서로 다른 데이터 구조를 사용할 수 있으며, 각각의 유전적 표현은 서로 다른 교차 연산자와 재결합될 수 있다. 크로스오버와 재결합할 수 있는 대표적인 데이터 구조로는 비트 배열, 실수의 벡터 또는 트리가 있다.
예
전통적인 유전 알고리즘은 비트 배열로 대표되는 염색체에 유전 정보를 저장한다. 비트 어레이에 대한 크로스오버 방법이 인기 있고 유전적 재조합의 예도 있다.
원 포인트 크로스오버
양친의 염색체에 있는 점을 무작위로 골라 '크로스오버 포인트'로 지정한다. 그 지점의 오른쪽에 있는 비트는 두 개의 상위 염색체 사이에서 교환된다. 이것은 각각 양부모로부터 약간의 유전적 정보를 가지고 있는 두 자녀를 낳는다.
2점 및 k점 교차
2점 교차점에서는 부모 염색체로부터 무작위로 두 개의 교차점을 선택한다. 두 지점 사이의 조각들은 모체 유기체들 사이에서 교환된다.
2점 크로스오버는 서로 다른 크로스오버 포인트로 2개의 단일 포인트 크로스오버를 수행하는 것과 동일하다. 이 전략은 모든 양의 정수 k에 대해 k 포인트 크로스오버로 일반화할 수 있으며 k 크로스오버 포인트를 선택할 수 있다.
균일 크로스오버
균일한 교차점에서는 일반적으로 각 비트가 동일한 확률의 부모 중 하나에서 선택된다. 다른 혼합비율이 때때로 사용되어, 다른 부모보다 한 부모로부터 더 많은 유전적 정보를 물려받는 자손이 생긴다.
순서 리스트에 대한 교차
일부 유전 알고리즘에서는 가능한 염색체가 모두 유효한 해결책을 나타내는 것은 아니다. 어떤 경우에는 문제의 제약조건을 위반하지 않도록 설계된 전문 교차 연산자와 돌연변이 연산자를 사용할 수 있다.
예를 들어, 여행 판매원 문제를 해결하는 유전자 알고리즘은 해결 경로를 나타내기 위해 순서가 지정된 도시 목록을 사용할 수 있다. 그러한 염색체는 목록에 판매원이 반드시 방문해야 하는 모든 도시가 포함되어 있을 경우에만 유효한 해결책을 나타낸다. 위의 십자수를 사용하면 종종 그 제약을 위반하는 염색체가 생기게 된다. 따라서 주어진 리스트의 순서를 최적화하는 유전 알고리즘은 유효하지 않은 해결책 생성을 피할 수 있는 서로 다른 교차 연산자를 요구한다. 그러한 많은 크로스오버는 다음과 같이 발표되었다.[1]
- 부분적으로 매핑된 크로스오버(PMX)
- 사이클 크로스오버(CX)
- 오더 크로스오버 연산자(OX1)
- 주문 기반 교차 연산자(OX2)
- 위치 기반 교차 연산자(POS)
- 투표 재결합 교차 연산자(VR)
- 교대 위치 교차 연산자(AP)
- 순차 건설적 교차 연산자(SCX)
- 시뮬레이션된 이항 교차 연산자(SBX)
다른 가능한 방법으로는 에지 재결합 연산자가 있다. 또는 언급된 문제를 극복하기 위해 이중 염색체를 사용할 수 있다.[2]
참고 항목
참조
- John Holland, Adaptation in Natural and Phositive Systems, University of Michigan Press, University of Michigan, Ann Arbor, 1975. ISBN0-262-58111-6.
- Larry J. Eshelman, CHC 적응 검색 알고리즘: Gregory J. E. Rawlins 편집기의 Genergy J. E. Rawlins 편집기, 유전 알고리즘의 기초에 관한 첫 번째 워크샵 진행 265-283페이지에서 비전통적 유전자 재조합에 관여할 때 안전한 검색을 하는 방법 모건 카우프만, 1991년 ISBN 1-55860-170-8.
- 토마즈 D. Genetic Algorithm Reference Vol.1 단일 목표 수치 최적화 문제에 대한 Crossover, Tomasz Gwiazda, Lomianki, 2006. ISBN 83-923958-3-2
- ^ 페드로 라라가 외 연구진, "유전자 알고리즘으로 최적의 순서를 검색하여 베이시안 네트워크 구조 학습", IEEE 시스템, 인간 및 사이버 네틱스에 관한 거래, 1996년 제26권, 제4호.
- ^ Riazi, Amin (14 October 2019). "Genetic algorithm and a double-chromosome implementation to the traveling salesman problem". SN Applied Sciences. 1 (11). doi:10.1007/s42452-019-1469-1.
외부 링크
- 뉴스 그룹: comp.ai.properties FAQ - 교차(재결합이라고도 함)에 대한 섹션을 참조하십시오.
