在GA中執行與依賴項交叉的好方法是什麼？

Question

我正在寫一個遺傳算法來找到表達目標數字的表達式，即如果目標數字是10解決方案將是2*5。目前我使用的是固定大小的染色體，我想將它改變爲隨機長度，但只有在我找到一種方法來進行交叉之後。

以下是可能的染色體，遵循數字和運算符交替出現在字符串中的規則，以兩個數字或兩個運算符相鄰的方式出現。合法字符串將以數字或+/-運算符開頭。表達式將來自計算左至右-IS（忽略算術運算的順序）：

• 1/2+3+5
• -2+4+1+8
• -7+6*2+8
• +2/5-1+8 2+1*2-2
• +2*7*7+3
• +1/2/2/6 5/5*9*1
• +3-1+1*8 3-8+7*1

想實現我已經嘗試了交叉以下（僞代碼）：

crossover(chrom-a, chrom-b): 
    min_length = min(length(chrom-a), length(chrom-b)) 
    locus = random(1, min_length-1) 

    while (chrom-a[locus] & chrom-b[locus] aren't both digit or operator) 
     ocus = random(1, min_length-1) 

    chrom-a = chrom-a[:locus] + chrom-b[locus:] 
    chrom-b = chrom-b[:locus] + chrom-a[locus:] 

    return chrom-a, chrom-b 

但功能工作不正常，有時花費太多的時間去尋找合適的軌跡。我必須找到一種方法來使交叉隨機大小的染色體工作，但我不知道如何（當然確保沒有除零）。

Answer 1

很長的處理時間很可能是因爲兩個染色體在同一位置上具有不同類型（操作員或數字）字符的事件的概率很小。請注意，對於1位數的數字，兩條染色體總是在同一位置上具有相同類型。該解決方案是在單獨每個染色體找到分割點：

find_loci(chrom-a, chrom-b): 
    return pair(random(1, length(chrom-a)-1), random(1, length(chrom-b)-1)) 

crossover(chrom-a, chrom-b): 
    locus-a, locus-b = find_loci(chrom-a, chrom-b) 

while (chrom-a[locus-a] & chrom-b[locus-b] aren't both digit or operator) 
    locus-a, locus-b = find_loci(chrom-a, chrom-b) 

chrom-a = chrom-a[:locus-a] + chrom-b[locus-b:] 
chrom-b = chrom-b[:locus-a] + chrom-a[:locus-b] 
chrom-c = chrom-a[locus-a:] + chrom-b[locus-b:] 
chrom-d = chrom-b[locus-a:] + chrom-a[:locus-b] 

return chrom-a, chrom-b, chrom-c, chrom-d 

其結果當然是你有四種可能的結果，而不是兩個。你可以使用全部，或忽略一半。

另一種解決方法是首先列舉所有可能的分割點：

enumerate_possible_loci(chrom-a, chrom-b): 
    for all indexes i in (1, chrom-a): 
     for all indexes j in (1, chrom-b): 
      if type(chrom-a[i]) != type(chrom-b[j]): 
       yield return pair(i, j) 

crossover(chrom-a, chrom-b): 
    possible_loci = enumerate_possible_loci(chrom-a, chrom-b) 
    locus_pair = possible_loci[random(0, length(possible_loci) - 1)] 

    locus-a = locus_pair[0] 
    locus-b = locus_pair[1] 

    chrom-a = chrom-a[:locus-a] + chrom-b[locus-b:] 
    chrom-b = chrom-b[:locus-a] + chrom-a[:locus-b] 
    chrom-c = chrom-a[locus-a:] + chrom-b[locus-b:] 
    chrom-d = chrom-b[locus-a:] + chrom-a[:locus-b] 

    return chrom-a, chrom-b, chrom-c, chrom-d 

如果你一直只有1位數，則算法爲列舉可能的位點是更容易，因爲它總是會返回所有可能的如果一個索引是偶數，另一個是奇數，反之亦然。