여러 개의 내부 배낭 및 피트니스 계산

Question

내 머리를 긁적이며 잘못 생각했을 수 있습니다.

기본적으로 배낭 문제이지만 수정되었습니다. 다양한 가중치를 지닌 일련의 항목이 있으며, 20 개의 용량으로 3 개의 배낭에 넣어야합니다.

모든 항목을 임의로 자루에 초기화하는 코드가 있습니다. 20 개 이상, 20 개 미만, 20 개 이상인 자루를 가질 수 있다는 것을 의미합니다. 문제는 항목이 모두 추가되어 전체 점수가 모든 모집단에서 동일하므로 변경이 불가능하다는 것입니다. 예

,

• KnapsackA 1 개 점수 = 72
• KnapsackA 2 점수 = 50
• KnapsackA 3 점수 = 10

I가 4의 인구를 가지고 있다면, 그 수단 나는 배낭 사이에 다른 점수의 배낭과 함께 게놈의 다른 물건을 갖겠지 만 합계는 같을 것이다.

• KnapsackB 1 점 = 80
• KnapsackB이 점수 = 18
• KnapsackB 3 점 = 34

난 그냥 무작위로 임의을 생성하는 코드를 실행 할 수 있다는 생각을했다 번호를 사용하여 초기화보다는 첫 번째 세대에 대한 항목을 다시 할당 할 수 있지만 잘못 될 수도 있습니다. .

가장 낮은 게놈을 제거하고 남은 돌연변이를 돌연변이시킬 수있는 독특한 점수 (피트니스 평가)를 계산하려면 어떻게해야합니까?

점수 - 용량은 항상 같은 수입니다.

당신은 항목이 배낭에서 할 수 있도록하기 위해, 정보의 다른 코딩을 사용할 수 있습니다

Answer 1

(다른 포럼에서 X 게시물).

gene[0] = 1 (item 0 is in knapsack 1) 
gene[1] = 0 (item 1 is not in any knapsack) 
gene[2] = 3 (item 2 is in knapsack 3) 
gene[3] = 2 (item 3 is in knapsack 2) 
gene[4] = 1 (item 4 is in knapsack 1) 

그래서 개인이 3에 대한 가능한 해결책을 나타냅니다

예를 들어, 나는 항목이 어떤 배낭에없는 나타 내기 위해 항목의 배낭 번호와 같은 유전자를 고려하고 0 것 배낭. 그리고 당신은 예를 들어 인구 100 명을 가질 수 있습니다.

이 정보를 코딩하면 변형 및 재생산을 계산하기가 쉽습니다.

유전자를 돌연변이시키기 위해서는 [0,3] 범위의 난수 인 새로운 값을 지정하면됩니다. 예를 들어, 돌연변이 알고리즘 :

n = number of genes 
mutation_rate = 0.01 // it means a mutation rate of 1% 
For i from 0 to n-1 
    r = random real number between 0.0 and 1.0 
    If(r < mutation_rate) 
    gene[i] of new individual = (random integer number) modulo 4 
    Else 
    gene[i] of new individual = gene[i] of original individual 
    EndIf 
EndFor 

당신이 재생을 구현하려면, 당신은 단지 첫 번째 개인의 유전자의 절반, 두 번째 개인의 유전자의 반대 반을 선택해야합니다.

n = number of genes 
For i from 0 to n-1 
    r = random integer number 
    If(r modulo 2 == 0) 
    gene[i] of new individual = gene[i] of first individual 
    Else 
    gene[i] of new individual = gene[i] of second individual 
    EndIf 
EndFor 

당신은 아동이 개인보다 효율적으로보다 먼저 계산에 돌연변이 아이들을 계산하기 위해, 하나에 두 개의 선행 알고리즘을 결합하고 그것을 변이 할 수 있습니다.

저는 피트니스 기능의 전문가는 아니지만, 다음과 같은 점에서 당신을 격려 할 수 있다고 생각합니다. 매우 기본적이고 배낭이 가능한 한 많이 채워 져야한다는 사실을 고려해야합니다. 이 운동 기능의 경우, 적합성 높은 값이 더 나은 솔루션입니다 :

n = number of genes 

fitness = 0 

weight_noknapsack = 0 
weight_knapsack1 = 0 
weight_knapsack2 = 0 
weight_knapsack3 = 0 

For i from 0 to n-1 
    Switch gene[i] 

    case 0: weight_noknapsack += item[i].weight 

    case 1: weight_knapsack1 += item[i].weight 

    case 2: weight_knapsack2 += item[i].weight 

    case 3: weight_knapsack3 += item[i].weight 

    EndSwitch 
EndFor 

If(weight_knapsack1 <= MAX_WEIGHT_KNAPSACK1) 
    fitness += weight_knapsack1 
EndIf 
If(weight_knapsack2 <= MAX_WEIGHT_KNAPSACK2) 
    fitness += weight_knapsack2 
EndIf 
If(weight_knapsack3 <= MAX_WEIGHT_KNAPSACK3) 
    fitness += weight_knapsack3 
EndIf 

그것은 피트니스을 계산,하지만 난 더 나은 피트니스 기능이있을 수 있습니다 생각합니다.