首页 > 代码库 > 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编码的思想