Blackops

初心易得,始终难守

0%

Grefenstette编码解码原理和简单实现

遗传算法解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'