發問時間: 電腦與網際網路程式設計 · 1 0 年前

關於Python 程式碼_3

The crossover is an important source of variation in geneticalgorithm.Single-pointormulti-point crossover can be easily implemented by using slice operations. Single-point crossover on binary lists can be implemented as shown below.

parent1 = [ 1, 0, 1, 1, 0, 1, 1, 1 ]

parent2 = [ 0, 1, 0, 0, 1, 0, 1, 1 ]

pt = 3# crossover point

offspring1 = parent1[:pt] + parent2[pt:]

offspring2 = parent2[:pt] + parent1[pt:]

In the above example, crossover point is 3. The resultant offspring1 and offspring2 are shown below. The italic numbers represent the inherited part from parent1.

[1, 0, 1, 0, 1, 0, 1, 1]

[0, 1, 0, 1, 0, 1, 1, 1]

Two-point crossover example is given below. pt1 = 2# crossover point 1

pt2 = 5# crossover point 2

offspring1 = parent1[:pt1] + parent2[pt1:pt2] +

parent1[pt2:]

offspring2 = parent2[:pt1] + parent1[pt1:pt2] +

parent2[pt2:]

The resultant offspring1 and offspring2 are shown below. The italic numbers represent the inherited part from parent1.

[1, 0, 0, 0, 1, 1, 1, 1]

[0, 1, 1, 1, 0, 0, 1, 1]

已更新項目:

In case of Traveling Salesman Problem, we perform order crossover to prevent infeasible solutions. An order crossover example is given below.

parent1 = [4, 1, 5, 6, 9, 2, 3, 7, 8]

parent2 = [3, 1, 8, 6, 2, 4, 7, 9, 5]

pt1 = 2# crossover point 1

pt2 = 5# crossover point 2

2 個已更新項目:

latter_length = len(parent1) - pt2

prt1_mid = parent1[pt1:pt2]

prt2_mid = parent2[pt1:pt2]

prt1_reordered = parent1[pt2:] + parent1[:pt2]

prt2_reordered = parent2[pt2:] + parent2[:pt2]

3 個已更新項目:

prt1_reord_filtered = filter( lambda x: x not in prt2_mid, prt1_reordered )

prt2_reord_filtered = filter( lambda x: x not in prt1_mid, prt2_reordered )

4 個已更新項目:

offspring1 = prt2_reord_filtered[-pt1:] + prt1_mid +

prt2_reord_filtered[:latter_length]

offspring2 = prt1_reord_filtered[-pt1:] + prt2_mid +

prt1_reord_filtered[:latter_length]

5 個已更新項目:

The resultant offspring1 and offspring2 are shown below.

[8, 2, 5, 6, 9, 4, 7, 3, 1]

[5, 9, 8, 6, 2, 3, 7, 4, 1]

1 個解答

評分
  • 1 0 年前
    最佳解答

    第一段 是解釋如何用 "slicing" 來作單點的 crossover。

    # 以中心點互相交換

    offspring1 = parent1[:pt] + parent2[pt:]

    offspring2 = parent2[:pt] + parent1[pt:]

    ==================

    第二種 兩點的 crossover也是用slicing;交換中間那一段。

    offspring1 = parent1[:pt1] + parent2[pt1:pt2] +

    parent1[pt2:]

    offspring2 = parent2[:pt1] + parent1[pt1:pt2] +

    parent2[pt2:]

    ==================

    最後一部份,因為TSP的情況如果做簡單的crossover,十分可能會出現不合理的解,所以要做保留順序並避免重複的處理。

    # 保留中間那一段 [pt1:pt2],之後從另一條染色體接上,同時保留原本的順序,並避免重複 [pt1:pt2] 相同的城市

    parent1 = [4, 1, 5, 6, 9, 2, 3, 7, 8]

    parent2 = [3, 1, 8, 6, 2, 4, 7, 9, 5]

    pt1 = 2# crossover point 1

    pt2 = 5# crossover point 2

    latter_length = len(parent1) - pt2

    prt1_mid = parent1[pt1:pt2]

    prt2_mid = parent2[pt1:pt2]

    # 倒置,以便在最後結果pt2接上

    prt1_reordered = parent1[pt2:] + parent1[:pt2]

    prt2_reordered = parent2[pt2:] + parent2[:pt2]

    # 去掉跟另一段染色體中間一段相同的城市

    prt1_reord_filtered = filter( lambda x: x not in prt2_mid, prt1_reordered )

    prt2_reord_filtered = filter( lambda x: x not in prt1_mid, prt2_reordered )

    # 在中間那一段後面接上之前倒置並刪除重複城市的另一段染色體,剩下的兩個接到前頭。

    offspring1 = prt2_reord_filtered[-pt1:] + prt1_mid +

    prt2_reord_filtered[:latter_length]

    offspring2 = prt1_reord_filtered[-pt1:] + prt2_mid +

    prt1_reord_filtered[:latter_length]

    The resultant offspring1 and offspring2 are shown below.

    [8, 2, 5, 6, 9, 4, 7, 3, 1]

    [5, 9, 8, 6, 2, 3, 7, 4, 1]

還有問題?馬上發問,尋求解答。