모서리 재결합 연산자

Edge recombination operator

에지 재조합 연산자(ERO)는 정점이 아닌 에지를 보고 기존 경로(부모) 집합과 유사한 경로를 만드는 연산자다.이것의 주된 적용은 여행 판매원 문제와 같이 반복되지 않는 유전자 서열을 가진 유전자형이 필요한 경우 유전 알고리즘의 교차점에 대한 것이다.그것은 1989년에 Darrell Whitley와 다른 사람들에 의해 설명되었다.[1]

알고리즘.

ERO는 인접 행렬을 기반으로 하며, 부모에 있는 각 노드의 인접 항목을 나열한다.

ERO 크로스오버

예를 들어, 표시된 것과 같은 이동 중인 세일즈맨 문제에서 부모 CABDEF와 ABCEFD(그림 참조)의 노드 맵은 첫 번째 부모('ABCEFD')를 취하여 생성되며, 문자열 끝에서 롤링하는 부모를 포함하여 바로 이웃을 기록한다.

따라서;

... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...

...각 노드를 차례로 선택하고 연결된 인접 항목을 나열하여 다음과 같은 인접 행렬로 변환한다.

A: B D B: A C: B E D: F A E: C F: E D

두 번째 상위(CABDEF)에 대해 동일한 작업을 수행하면 다음과 같이 생산된다.

A: C B B: A D: F A D: B E: D F: E C

그 다음 이 두 리스트를 조합하고 중복된 리스트를 무시했다.이는 각 목록의 요소를 가져다가 고유한 링크 끝 지점 목록을 생성하도록 추가하는 것만큼 간단하다.이 예에서는 이를 생성한다.

A: B C D         = {B,D} ∪ {C,B} B: A C D         = {A,C} ∪ {A,D} C: A B E F       = {B,E} ∪ {F,A} D: A B E F       = {F,A} ∪ {B,E} E: C D F         = {C,F} ∪ {D,F} F: C D E         = {E,D} ∪ {E,C}

그 결과는 부모의 모든 링크에 의해 기술된 네트워크에 대한 링크를 저장하는 또 다른 인접 행렬이다.여기서 세 명 이상의 부모가 고용되어 보다 다양한 연계를 제공할 수 있다는 점에 유의하십시오.그러나 이러한 접근방식은 차선의 경로를 초래할 수 있다.

그런 다음 경로를 생성하려면K, 다음과 같은 알고리즘이 사용된다.[2] 

알고리즘 ero는 K가 빈 리스트가 되게 하고 N은 무작위 부모의 첫 번째 노드가 되게 한다.length(K) < length(Parent) do K := K, N(N에서 K까지 적용) Ns ns n 이웃 목록이 비어 있지 않으면 N*의 이웃이 N의 가장 적은 이웃(또는 임의의 이웃이 여러 개 있어야 함)이 아닌 임의로 선택한 노드가 되도록 한다.K N := N*에

예를 단계별로 살펴보기 위해 상위 시작점 {A, C}에서 노드를 무작위로 선택한다.

  • () -> A모든 이웃집 집합에서 A를 제거하고, B, C, D 중에서 가장 작은 것이 B={C,D}라는 것을 알게 된다.
  • AB. C와 D의 가장 작은 세트는 C={E,F}와 D={E,F}이다.우리는 무작위로 D를 선택한다.
  • ABD. 가장 작은 것은 E={C,F}, F={C,E}이다.우리는 F를 선택한다.
  • ABDF. C={E}, E={C}.우리는 C를 선택한다.
  • ABDFC. 가장 작은 세트는 E={}이다.
  • ABDFCE. 아이의 길이는 이제 부모님의 길이와 같으므로 우리는 끝장이다.

ABDFCE에 도입된 유일한 에지는 AE뿐이라는 점에 유의하십시오.

다른 연산자와 비교

엣지 재조합은 일반적으로 여행 중인 세일즈맨 문제와 같은 문제에 대해 좋은 옵션으로 간주된다.1999년 바스크 대학교의 연구에서, 가장자리 재조합은 부분적으로 매핑된 크로스오버와 사이클 크로스오버를 포함한 다른 모든 크로스오버 연산자보다 더 나은 결과를 제공했다.[3]

참조

  1. ^ Whitley, Darrell; Timothy Starkweather; D'Ann Fuquay (1989). "Scheduling problems and traveling salesman: The genetic edge recombination operator". International Conference on Genetic Algorithms. pp. 133–140. ISBN 1-55860-066-3.
  2. ^ 대럴 휘틀리, 티모시 스타크웨더, 다니엘 섀너:이동 중인 세일즈맨과 시퀀스 스케줄링: L. Davis(편집)의 유전적 에지 재조합을 사용한 품질 솔루션: 유전자 알고리즘 핸드북반 노스트랜드 라인홀드, 1991년 뉴욕
  3. ^ P. 라라냐 외: 여행 세일즈맨 문제를 위한 유전 알고리즘: 표현 및 운영자 검토.인공지능 리뷰, 13권, 1999년 4월 2호, 페이지 129-170