# 關於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]