遗传算法解TSP问题的时候需要对路径状态进行Grefenstette编码方便染色体交叉一类的操作，Grefenstette编码可以使得过程中不出现非法和重复的交叉操作。
编码：维护一个1…n的序列，遍历要编码的序列（是1…n的一个排列），当前数字对应的编码等于当前数字在1…n序列中的下标，然后把当前数字从1…n的序列中删去，继续这样直到所有数字都编码完毕。
解码：维护一个1…n的序列，遍历要编码的序列（是1…n的一个排列），当前的编码数字对应的解码数字等于当前编码数字作为下标的1…n序列中的值，然后把得到的解码值从1…n的序列中删去，继续这样直到所有编码数字都解码完毕。
测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| import numpy as np
import random
def encode(A):
seq = list(range(0, 10))
G = []
for i in range(len(A)):
G.append(seq.index(A[i]))
seq.pop(seq.index(A[i]))
return G
def decode(G):
seq = list(range(0, 10))
RG = []
for i in range(len(G)):
RG.append(seq.pop(G[i]))
return RG
if __name__ == '__main__':
A = list(range(0, 10))
random.shuffle(A)
G = encode(A)
RG = decode(G)
print('original array', A)
print('encoded array', G)
print('decoded array', RG)
assert A == RG, 'decode error'
|