TSP에 대한 유전자 알고리즘의 크로스 오버 작동

StackOverflow https://stackoverflow.com/questions/1544055

문제

나는 그것을 해결하려고 노력하고있다 여행 세일즈맨 문제 (TSP) ~와 함께 유전자 알고리즘. 내 게놈은 그래프에서 정점 (세일즈맨 경로)의 순열입니다.

게놈보다 크로스 오버 작업을 수행해야합니까?

C#에서 내 문제의 구현을 어디서 찾을 수 있습니까?

도움이 되었습니까?

해결책

당신은 확인해야합니다 "특수 교차 및 돌연변이를 피하는 TSP의 유전자 알고리즘 솔루션"Gokturk Ucoluk. 그것은 순열을위한 특수 크로스 오버 연산자의 개요를 제공하고 표준 크로스 오버와 잘 어울리는 순열의 영리한 표현을 제안합니다 (즉, 두 개의 순열을 가로 지르는 두 개의 순열은 항상 두 개의 순열을 생성합니다).

주요 통찰력은 순열을 반전 시퀀스, 즉 각 요소에 대한 순서로 나타내는 것입니다. i, 저장 a[i] 보다 큰 요소는 몇 개입니다 i 왼쪽에 있습니다 i 순열에서. 직접 표현과 달리 유일한 제약 a[i] 현지입니다 a[i] 보다 클 수 없습니다 N - i. 이는 두 개의 유효한 반전 시퀀스의 간단한 크로스 오버가 항상 두 개의 유효한 반전 시퀀스를 생성한다는 것을 의미합니다. 반복 요소의 특수 처리가 필요하지 않습니다.

다른 팁

표준 GA 크로스 오버 기술을 사용하는 대신 musigenesis에 의해 설명됩니다), 사용하는 것이 좋습니다 여행 세일즈맨 문제에 대한 크로스 오버.

피트니스 기능은 절대적인 위치보다는 진화 된 경로에서 다른 도시의 상대 위치에 매우 민감하기 때문에 일반적인 접근 방식은 TSP에 적합하지 않습니다. 예를 들어, 모든 유럽의 수도를 방문하는 경우 가장 짧은 경로는 실제로 Bratislava 1, 2nd 또는 9th를 방문하는지 여부에 달려 있지 않습니다. 더 중요한 것은 방문한다는 것입니다 비엔나 방문 직전 또는 직후 헬싱키, 아테네 및 6 개의 다른 수도를 방문하는 대신.

물론 MJV도 지적합니다, 전통적인 크로스 오버는 또한 경로에 복제물을 소개합니다. 한 부모가 2 위에 파리를 가지고 있고 다른 부모가 14 위에 파리를 가지고 있다면, 크로스 오버는 파리를 두 번 방문하고 다른 도시를 그리워하는 하나의 진화 된 경로와 전혀 방문하지 않는 진화 된 경로를 초래할 수 있습니다. 정렬 된 교차 유전자 운영자는이 문제로 고통받지 않습니다. 요소를 보존하고 순서를 수정합니다.

여기에 있습니다 C# 프로그램 당신이 찾고있는 것에 대한 접근.

구현의 이익 (또는 그 부족)과 관련하여 크로스 오버, 구현이 사용하는 특정 선택 로직에 달려 있습니다 (예 : 개선 속도의 평가가 포함 된 경우 평가 함수 자체). 많은 경우에, 크로스 오버 작업은 "도마 블록에서 구출"합니다. 그래프 영역에서 효과적이거나 최적이지만 다른 사람들에게는 "고정 된"솔루션이 있습니다.. 이것은 전체 알고리즘이 느리게 진행되고 솔루션 공간의 좋은 비율을 다루는 경우 동일한 솔루션이 새로 발견되지 않았을 수도 있지만 교차-오버도 이러한 발견을 증가시킬 수 있다고 말하는 것은 아닙니다 (및/또는 갇히게 할 수도 있습니다. 또 다른 지역 최소값 ;-))

GA를 바라 보는 사람에게 직접 관련이 아니라 주목할만한 관심은 다음과 같습니다. GA의 원래 "궁극적"실험 Alderman 교수 (RSA 명성)의 GA에서의 원래 "Ultimate"실험은 실제 DNA 분자 [C 프로그램 - 농담]을 사용하여 해밀턴 그래프의 관련 그래프 문제를 해결했습니다.

편집하다: 질문을 다시 읽을 때 나는 당신이 왜 그 질문을했는지 또는 더 정확하게 물었습니다. "아니요 크로스 오버"응답을 원하는 이유 ;-)
당신의 Genonme은 그래프에 직접 연결되어 있습니다 그 자체로 (아무 문제가없고, 선험적으로), 그러나 이것은 대부분의 크로스 오버 오프 스핀이 중복 노드를 가질 수 있고 (같은 도시를 두 번 이상 방문하고) 노드가 누락 될 수 있으므로 (일부 도시를 방문하지 못함) ... 크로스 오버는 유사한 그래프에 영향을 미치므로 돌연변이가 발견 한 것과 비교하여 검색을 점진적으로 소비 할 수 있습니다.
험 ... 그럼 어쩌면 크로스 오버, 이 특정 구현에서 알고리즘을 크게 도울 수는 없습니다 (그리고 실제로 CPU의 많은 부분이 크로스 오버 오프 스프링을 생성, 테스트 및 폐기하는데, CPU는 더 많은 반복과 느린 냉각 속도...). 하지 않는 한! 당신은 크로스 오버 오퍼레이션을 수행하는 영리한 방법을 찾습니다 ;-)

크로스 오버의 목적은 새로운 게놈 조합을 모아서 진화 적 검색 공간을 확장하는 것입니다.

진화 과정에 필요한 유일한 기준은 크로스 오버의 산물이 부모의 일부를 포함하고 유효한 게놈을 나타냅니다.

당신만이 알고리즘의 유효성 규칙을 알고 있으므로만이 작동하는 크로스 오버 방법을 지정할 수 있습니다 (게놈 구조에 대한 검증 규칙에 대한 자세한 내용을 공유하지 않는 한).

다음은 TSP 용 GA에서 소위 "부분적으로 매핑 된 크로스 오버"메소드의 정확한 구현입니다.

여기 이론에서 부분적으로 매핑 된 크로스 오버를 설명하는 논문은 내 코드입니다.

//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which            //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
    int[] genes = new int[father.Genes.Length];
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
    father.Genes.CopyTo(genes, 0); //give child all genes from the father
    for (int i = 0; i < genes.Length; i++) //create the map
    {
        map[genes[i]] = i;
    }
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
    {
        int temp = crossoverPoint1;
        crossoverPoint1 = crossoverPoint2;
        crossoverPoint2 = temp;
    }
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
    {
        int value = mother.Genes[i];
        int t = genes[map[value]]; //swap the genes in the child
        genes[map[value]] = genes[i];
        genes[i] = t;
        t = map[genes[map[value]]]; //swap the indices in the map
        map[genes[map[value]]] = map[genes[i]];
        map[genes[i]] = t;
    }
    Individual child = new Individual(genes);
    return child;
}

대학의 첫 번째 과정에 있었을 때 다양한 GA 운영자가 솔루션 수렴에 미치는 영향에 대해 계산 (약 30 페이지를 차지했습니다)을 수행했습니다. 내가 기억하는 바와 같이, 크로스 오버는 TSP를위한 최상의 솔루션이 아니며, 더 적합한 솔루션은 돌연변이이며, 이는 정점의 하위 시퀀스를 반전시키는 것입니다.

예시:

전 : aBCDEFGH

후 : aFedcbGH

유전자 알고리즘의 "크로스 오버"는 단지 두 가지 "유전자 서열"을 혼합하는 임의의 방법을 말합니다. 각각의 문제는 문제에 대한 특정 솔루션을 나타냅니다 (서열이 솔루션에 맵핑되는 방법). 예를 들어, 다음 두 시퀀스로 구성된 인구가 있다고 가정 해 봅시다. 

AAAAAAAAAA
BBBBBBBBBB

이 두 "부모"시퀀스를 재조합하는 한 가지 방법은 교차점 (예 : 위치 3)을 무작위로 선택 하여이 두 "자식"시퀀스를 초래하는 것입니다.

AAABBBBBBB
BBBAAAAAAA

또는 두 개의 크로스 오버 지점 (예 : 3 및 8)을 무작위로 선택 하여이 두 시퀀스를 초래할 수 있습니다.

AAABBBBBAA
BBBAAAAABB

재미 있고 추가 변동성을 위해 가끔 포인트 돌연변이의 가능성을 소개 할 수도 있습니다.

AAABBBABAA
BBBAAAAABB

생물학적 세계에서 진화를 지배하는 어려운 규칙이없는 것처럼 유전자 알고리즘에서 크로스 오버를 구현하는 방법에 관한 어려운 규칙은 실제로 없습니다. 무엇이든지 작동합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top