내 룰렛 선택 방법보다 더 나은 자손의 가치를 더 잘 나타내는 방법은 무엇입니까?

Question

나는 유전 프로그래밍 알고리즘을 가지고 놀고 있는데, 어떻게하면 가치를 부여 할 수 있는지를 알고 싶다. 그리고 최고의 모범을 재현 할 수있는 방법을 대체하거나 개선함으로써 더 많은 것을 재생산 할 수 있기를 바란다.

function roulette(population) 
    local slice = sum_of_fitnesses(population) * math.random() 
    local sum = 0 
    for iter = 1, #population do 
     sum = sum + population[iter].fitness 
     if sum >= slice then 
      return population[iter] 
     end 
    end 
end 

하지만 특정 값보다 평균 체력에 도달 내 인구를 얻을 수 있으며, 좀 더 적합 회원들과 함께 재현 때문에 덜 적합 위원 그것의 걱정 : 현재 내가 사용하는 방법은 다음과 같습니다 따라서 약한 유전자를 퍼뜨리는 것을 계속합니다.

그래서 어떻게 내 룰렛 선택 방법을 개선 할 수 있습니까? 아니면 완전히 다른 피트니스 비례 선택기를 사용해야합니까?

Answer 1

여기에는 몇 가지 문제가 있습니다.

개인의 체력에 따라 복제 할 확률을 선택했기 때문에 사용중인 피트니스 기능이 작은 차이를 과장해야하거나 그렇지 않으면 체력의 사소한 감소가 그리 나쁘지 않습니다. 예를 들어, 적합도가 81에서 80으로 떨어지면이 변화는 시스템의 소음에 해당하며 진화와 크게 다르지 않습니다. 선택 압력이 단순히 충분히 강하지 않기 때문에 일련의 작은 변화가 필요하다면 매우 높은 적합성으로 상승하는 것은 거의 불가능합니다.

이 문제를 해결하는 방법은 토너먼트 선택과 같은 것을 사용하는 것입니다. 가장 간단한 형태로, 태어날 다른 개인을 선택할 때마다 K 개의 임의 개인을 선택합니다 (K는 알려져 있고 "토너먼트 크기"라고 알려짐). 당신은 각 개인의 체력과 가장 높은 체력이 복제 된 사람을 계산합니다. 체력 차이가 81 대 80인지 또는 10000 대 2인지는 중요하지 않습니다. 왜냐하면 단순히 체력이 가장 높기 때문입니다.

이제 질문이 있습니다. K를 어떻게 설정해야합니까? K는 선택의 힘이라고 생각할 수 있습니다. 이 수치를 낮게 설정하면 (예 : K = 2) 많은 저조한 개인이 운이 좋고 빠져 나와 다른 저조한 개인과 경쟁하게됩니다. 다양성은 많지만 섹션은 거의 없습니다. 반면에 K를 높게 설정하면 (예 : K = 100), 모집단에서 가장 높은 가중치 중 하나를 선택하여 인구 평균이 최대 값에 근접하도록 보장하지만 항상 인구의 다양성을 떨어 뜨립니다.

여기서 특정 타협점은 특정 문제에 달려 있습니다. 어떤 문제가 발생하는지 확인하기 위해 여러 가지 문제가있는 다양한 옵션 (원래 알고리즘 포함)을 시험해 보는 것이 좋습니다. 예를 들어 all-ones 문제를 시도하십시오. 잠재적 솔루션은 비트 문자열이며 피트니스는 단순히 1의 수입니다. 약한 선택 (예 : 원래 예에서 또는 K = 2)을 사용하면 완벽한 만능 솔루션을 얻지 못할 것입니다.

그래서 항상 높은 K를 사용하지 않는 이유는 무엇입니까? 사람들이 4 개의 연속 된 블록 (또는 8 개 또는 많은 블록)에 나타나지 않으면 갑자기 매우 긍정적 인 문제가 발생하는 것을 고려해보십시오. 이러한 문제는 "사기성"입니다. 즉, 문제가있는 솔루션을 통해 탐색해야 좋은 것을 찾을 수 있습니다. 선택의 강도를 너무 높게 설정하면, 네 번째를 제공하기 위해 최종 변이에 대해 세 가지를 수집하지 않습니다.

볼만한 토너먼트 선택을 사용하는 고급 기술이 많이 있습니다. 예를 들어 시간에 따라 K를 변화 시키거나 심지어 인구 내에서 K를 낮추거나 K를 사용하는 사람들을 선택하십시오. 더 나은 알고리즘을 만들 계획이라면 좀 더 읽을 가치가 있습니다.