首页 > 代码库 > Grefenstette编码的思想
Grefenstette编码的思想
今天粗略学习了遗传算法，对于基因采用二进制表示、染色体采用一串二进制数表示（如11000100）还是比较容易理解的。但是，在TSP问题（旅行商问题，traveling
salesman problem）中，需要通过遗传算法求解较优的旅行路径，如何对基因和染色体进行建模？比较合理的思路是采用城市排列作为染色体，例如在5个城市的情况下，1、2、3、4、5表示按照1->2->3->4->5->1的顺序进行遍历。但是，遗传算法中比较关键的步骤有交叉（Crossover）、变异（Mutation）等操作，如果对两个城市排列染色体进行交叉，就会大概率出现路径中多次出现相同城市，同时缺少部分城市的情况，这样交叉所得的染色体就不是合格的染色体了，如何解决这个问题？
这时，Grefenstette编码就出场了。
网上的资料说，所谓的GrefenStette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1对应8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。这句话太TM拗口了，怎么理解？
在TSP问题中，我们可以构造3个序列，A表示当前尚未旅行的城市编号序列，P表示实际的旅行序列，G代表GrefenStette编码序列。
假设TSP问题中有10个城市，编号分别是1到10，我们来看如何求取旅行序列P=[8, 9, 2, 1, 3, 4, 6, 5, 7, 10]的编码序列G。
步骤 | 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
初始条件 | A | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
P | – | – | – | – | – | – | – | – | – | – | |
G | – | – | – | – | – | – | – | – | – | – | |
STEP1（选择8在A中的位置，A中删除8） | A | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
P | 8 |
|
|
|
|
|
|
|
|
| |
G | 8 |
|
|
|
|
|
|
|
|
| |
STEP2（选择9在A中的位置） | A | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 |
|
P | 8 | 9 |
|
|
|
|
|
|
|
| |
G | 8 | 8 |
|
|
|
|
|
|
|
| |
STEP3（选择2在A中的位置） | A | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 10 |
|
|
P | 8 | 9 | 2 |
|
|
|
|
|
|
| |
G | 8 | 8 | 2 |
|
|
|
|
|
|
| |
STEP4（选择1在A中的位置） | A | 1 | 3 | 4 | 5 | 6 | 7 | 10 |
|
|
|
P | 8 | 9 | 2 | 1 |
|
|
|
|
|
| |
G | 8 | 8 | 2 | 1 |
|
|
|
|
|
| |
STEP5（选择3在A中的位置） | A | 3 | 4 | 5 | 6 | 7 | 10 |
|
|
|
|
P | 8 | 9 | 2 | 1 | 3 |
|
|
|
|
| |
G | 8 | 8 | 2 | 1 | 1 |
|
|
|
|
| |
STEP6（选择4在A中的位置） | A | 4 | 5 | 6 | 7 | 10 |
|
|
|
|
|
P | 8 | 9 | 2 | 1 | 3 | 4 |
|
|
|
| |
G | 8 | 8 | 2 | 1 | 1 | 1 |
|
|
|
| |
STEP7（选择6在A中的位置） | A | 5 | 6 | 7 | 10 |
|
|
|
|
|
|
P | 8 | 9 | 2 | 1 | 3 | 4 | 6 |
|
|
| |
G | 8 | 8 | 2 | 1 | 1 | 1 | 2 |
|
|
| |
STEP8（选择5在A中的位置） | A | 5 | 7 | 10 |
|
|
|
|
|
|
|
P | 8 | 9 | 2 | 1 | 3 | 4 | 6 | 5 |
|
| |
G | 8 | 8 | 2 | 1 | 1 | 1 | 2 | 1 |
|
| |
STEP9（选择7在A中的位置） | A | 7 | 10 |
|
|
|
|
|
|
|
|
P | 8 | 9 | 2 | 1 | 3 | 4 | 6 | 5 | 7 |
| |
G | 8 | 8 | 2 | 1 | 1 | 1 | 2 | 1 | 1 |
| |
STEP10（选择10在A中的位置） | A | 10 |
|
|
|
|
|
|
|
|
|
P | 8 | 9 | 2 | 1 | 3 | 4 | 6 | 5 | 7 | 10 | |
G | 8 | 8 | 2 | 1 | 1 | 1 | 2 | 1 | 1 | 1 |
所以，我们最终求得的P所对应的GrefenStette编码序列就是G=[8, 8, 2, 1, 1, 1, 2, 1, 1, 1]。
结合GrefenStette编码的定义以及上面这个表的计算过程，如何进行GrefenStette编码就很清楚了。
在TSP问题中，我们实际上是采用遍历路径的GrefenStette编码序列作为遗传算法的染色体，那么，为什么采用GrefenStette编码进行交叉、变异就不会产生无效的染色体呢？
从GrefenStette编码的过程我们可以发现，对于G的任何元素i而言，G[i]的最小值min是1（选中元素在A中排列在第1个），最大值max是citiyCount-(i-1)（也就是排在A的最后）。所以，对于任意两个染色体而言，在局部交叉后，交换基因的位置没有发生变化，其仍然属于区间[min, max]，因而必然是合法的，所以交叉不会产生非法的染色体。
那么变异的情况呢？
在对某个基因G[i]而言，假定变异的概率是ri(介于0和1之间)，那么可以设置其值为min+ri*(max-min)即可，变异后的值仍然是合法的，也就不会产生非法的染色体了。
所以，采用GrefenStette编码就很好地解决了TSP问题中染色体定义的问题，使得我们能够使用遗传算法解决TSP问题。
Grefenstette编码的思想